Requirements for A* (A Star):
- basic knowledge of control stuctures
- basic knowledge of Classes
- basic knowledge of callbacks as events
- basic knowlegde of movie clips
- basic knowledge of model movement
- basic knowledge of mouse interaction
- basic knowledge of traversing a path
If you are having trouble with any of the consepts above please see our tutorials on them.
Download Code
Ok to get on topic, the code i used is VERY basic. It is not designed to win any awards for performance, its designed to be understandable and use only basic control structures and objects. The source code is posted above, and i recommend downloading it and having it open while you go over this tutorial. The code for this tutorial is long (simple but long), so posting it all on this page could be counter productive.
That being said, the A* algorithm at its most basic level consists of 4 things:
1. a Grid (much like a chess board)
2. a starting point (this is the point on the grid the current object is located)
3. an end point (this is the point on the grid that you want the current object to move to)
4. The calculation between start and end points.
Sounds simple enough right?
1) The Grid:
This is composed normally by a 2D array or 2D list. Because Flash treats arrays in much the same manor that say C# treats lists they are very much interchangable depending on the language that you are useing. This is a Flash tutorial and so we are using a 2D array.
var masterGrid = new Array();
for(var iii=0; iii < 20; iii++)
{
masterGrid[iii] = new Array();
for(var jjj=0; jjj<20; jjj++)
{
masterGrid[iii][jjj] = new GridTile(null);
}
}
That will create a 20x20 grid (to make a different sized grid just change the 20's to whatever you need). GridTile() is just a class that holds basic infomation on the tile that now exists there and all information starts blank.
2) The Start Point:
This can be composed of any object that has x,y coordinates. In this case i created an array of "Mob" objects. Mob is another class that holds information about what a mob is. This is a class that i actually use for video game creation. if you dont want to see whats in it you dont have to, just know when you call it that i will product a movie clip to be displayed.
3) The End Point:
This is much the same as the start point. For this tutorial i used just a singular movie clip of and "X".
4) The calculation, This is the only part that really requires any decent amount of programming. After a mob is place by clicking on the grid, it will look for the finishing point (the "X") and will start checking what nodes on the grid are free and which ones are taken.
How does it do that?
FORMULA:
F = G + H;
G = distance traveled to that node.
H = axis- distance from that node to the end point node (only streight lines parrallel to the axis are used).
Every node must have an F score, this should be added every time a node is inputed into the open array.
1) First it takes in the position on the grid of the start point and places it in an array of items looked at (a closed array).
2) Next it checks all 4 points directly above,below,right, and left of the start point and adds all free spaces to an array that is waiting to be looked at (an open array) and set their parent to the current location.
3) Now you have to decide how do deal with corners. The first way will reqire both axis nodes to be free in order to consider the subsiquent corner. (both top and left have to be clear in order to consider the top-left corner) Or you can make it so that only 1 of the two has to be free in order to consider the corner (for this tutorial i choose this option). After you decide, you must then consider the appropriate corners and add them to the open array and set their parent to the current location.
4) We are finished with the current location. Now we must select node with the smallest F score from the open array. Add the node to the closed array, and remove it from the open array.
now we repeat this process with 2 changes.
1) If you come up with a node that is free, but on either the open or closed array, you do not add it back onto the open array.
2) If the node you came in contact with is on the open or closed array, then check to see if the new F score is smaller. If so replace the nodes F score with the smaller F score and set their parent to the current location. (This is very importaint for finding the shortest grid based path)
At any point, if you reach the end point you are finished with the path calculation.
At this point the closed array contains all of the nodes required, but it also contains alot of junk nodes. How do we sift through them? Simple, we use the parents of all the nodes starting with the current node (last node that you focused on, which is also the end point) and ending with the start node (node with no parent). Simply add all the nodes to a list of x,y coordinates that your object will traverse.
Now that we have the list of nodes known as a path, its time to traverse them. If you are uncertain on this, please see our tutorial on traversing a path.
See demo:
Demo of tutorial
Practical Applications:
Royal Tower Defense
Sources used:
http://www.policyalmanac.org/games/aStarTutorial.htm