Saturday, November 15, 2008

AI for Video Games Project Update

Today I spent about 5 hours at Starbucks working on getting the dog I jacked from this dude to follow a path in ActionScript. Right now, I solved the problem related to applying the points on the incorrect place and getting the dog to follow the points on the path. I still want to clear the path after the dog has finished following it, make the sheep run away from the dog and work on the dog's animation a bit. I think once I get the sheep running from the dog and the path cleared though, I am going to setup SVN and work on the splash screen and some other non-AI components of the game. My partner Jon has done an awesome job creating the AI framework, and we agreed to have him do a bit more AI and I would focus on the other structural points of the game. Our professors wanted to make sure all group members did AI related stuff, so path following seemed like a good place for me to work.

Click here for a full screen version.

Code is available here in case you want to see how I did path following in ActionScript. If you have any questions / suggestions, let me know. I see that a lot of people have been searching for algorithms and data structures related to ActionScript, but I never receive any feedback from you guys. Leave me a comment if this is useful.

Monday, November 10, 2008

AI for Video Games Final Project

For my final project, Jon Bradley and I decided to work together on a video game he has an idea for. The game is all about herding sheep. So far, Jon has done a huge amount of work. Today I made some progress on implementing path following in the ActionScript framework Jon developed. I still need to make something actually follow the path, as well as figure out why my path adding is getting messed up with regards to clicking on a sheep or the shepherd whenever you are trying to add a path.

Anyways, here is a sample of what we have coming. I'm going to hold off on posting any code until the assignment has been turned in. My path algorithm is the same one that Bill Klein implemented in Processing, which is probably the same one from "Artificial Intelligence for Computer Games" by Ian Millington.

Click here for a full screen version.

Number one is getting the points to be correctly placed when you click on the shepherd or sheep. After that, comes getting something that looks like a dog to following the path, then setting up SVN so we don't have to email our code back and forth. After that, I am going to work on an intro screen, a level loader, a sound track (hopefully just finding one) and the other animation sequences, probably in that order. Jon has already finished the brunt of the AI, I he's going to add some obstacles, make a pen for the sheep to go into, add a little bit of state information and make it so flocks can be broken up. As long as I can get my pieces done, there isn't a ton more to do, since Jon has been working so hard!!

Sunday, November 9, 2008

Finished A* Finally


I finally implemented an OK heuristic (Manhattan distance / Taxicab geometry from the current node to the end node). Everything looks the same, but the code is a bit different.

My full implementation of A* in ActionScript is available here.

Wednesday, November 5, 2008

A* for ActionScript, with an incomplete heuristic function

I have finished my (first completely working) implementation of A* for ActionScript. However, the heuristic function is a constant function and thus not implemented, so 'A*' is just breadth first search. Technically, I believe it is correct to still call it A*, but I'm not certain since I'm not keeping track of my path cost, and my heuristic is more of an artful description of something that always returns the same value but has not been implemented... I suppose I am feeling a bit discouraged since the assignment is due tomorrow at 5 p.m. and it is 3:21 a.m. and I still have a bit to do in order to make it perfect. However, I think choosing which path to recurse down first based on a heuristic shouldn't be too big of an addition now that everything else is working well.

I feel very happy that I choose to implement this in ActionScript. I like being able to share my programs with people online and notice the Google search terms that bring others to my site. I gain satisfaction when I see that someone from China, Spain, or some other distant place, spent 20 minutes reading about some technical issue on my site.

Press space bar to switch between blocking off nodes, selecting a start position and selecting an ending position.

Click HERE to view this in it's own web page.

My sister would be proud of my photoshopping skills on the waving hand. I also have to give a shout-out to Michael Baczynski for the cool data structures library (I didn't have to write my own FIFO thanks to him.)

As always, my complete source code is available. Please don't hesitate to contact me if you have any questions. I plan on making it more of an actual A* implementation, and if time permitting, possible using Michael Baczynski's graph data structure and implementing A* in his (very well designed) framework. I did not plan on doing that from the beginning, even though I'm sure it would have saved me time, since I did not see him code until after I already made my own graph, and adjacency list, management routines.

Thanks for Laurie Phillips for finding a bug in my code.

Monday, November 3, 2008

A* for ActionScript

For my class titled "Artificial Intelligence for Video Games" I have been working on an implementation of the algorithm A* in ActionScript. I've been pretty happy that the professors allow us to use ActionScript, instead of Processing, because it makes sharing my work on the Internet much easier. In addition, I think having substantial ActionScript skills is a marketable quality, as opposed to skills in the programming language "Processing." Hopefully I also will develop skills in artificial intelligence, to transcend any of the language-specific focuses I may have in mind.

As of this post, I have no actually implemented A* in ActionScript. What I have done is to implement a mechanism to draw and manipulate a relatively straighforward graph. This graph has the edges layed out in a regular, rectangular, pattern.

Here is a SWF of what I have so far:

Click to block/unblock a node, and press space bar to alternate between different modes of selecting a node. Eventually, the blue square will be for the starting position, and the green square will be for the ending position. Once I finish implementing A*, the path between start and end will be drawn in red squares.

Most likely if you are reading about my implementation of A* in ActionScript, you are interested in seeing my code. At this point, the most interesting thing will be how I keep track of adjacency lists for each node.

I will make another post when I finish everything, but I like making things available as I work so I can view my own progress. Here is a .zip of all the files for my project so far. I ask that if you use them, please somewhere link to my blog and email me so I can get some satisfaction.