@Tapewormz and others;
A* Pathfinding ( and almost all other tile-based Pathfinding ) works like this:
First, your map/level is divided up into tiles, usually hexagonal tiles, and usually no bigger than the smallest unit size ( ie, in an RTS, the space that a single worker would take up [ in Warcraft, that would be roughly the space that a peasant takes up ] ).
Then, before the main loop is executed, the A* algorithm ( that you create ) checks all the tiles in the map/level to see if they're occupied by a part of the map, lets say a tree or such. This is then marked in an array.
Alternatively, this step can be skipped, but it does help to speed up the Pathfinding algorithm in the main loop.
Once in the loop, when a unit, or object wants to move, the A* Pathfinding algorithm takes over.
Lets say that your unit is on Hex coordinate 0,0 ( Bottom Left ).
And, it wants to move in a diagonal fashion upward to its right
Eg, it wants to travel between the two marked hex's below:
The Start and Destination positions are those marked with
The tiles that are blocked/occupied are marked with
The A* Algorithm is then pretty simple.
It checks the hex to the upper right of the current one ( the logical choice as that would send the unit in a direct line toward the destination. This direction is easily obtained with little trig ). If that hex is available, then the unit is moved to there, and that hex's position in the previously populated array becomes marked as occupied.
The new position of the unit ( marked with an arrow ):
The next top-right hex is checked ( again, sending it in a straight line toward the destination ) This hex is empty, thus the unit moves onto it.
The movement of the unit is now like this:
The next check again checks the upper-right adjacent hex, but the result this time is that it is occupied.
From here, there are two options for the unit to take.
(a) It can move straight upward to go around the blocked hex, or,
(b) it can move to the lower right hex.
(b) is the direction it will move, as the hex in (a) is also occupied/blocked.
The units movement would now look like this:
The next move would be to the upper right hex, as it is the closest to a straight line toward the destination.
After this, the next hex would be either directly above or the upper right, because these two options would result in equal distance from a straight line to the destination.
Then, finally, the last move would move the unit onto the destination ( provided of course that it is not occupied/blocked ).
That is a rather simple explanation, and may not be 100% correct, but if you coded something like that, it would work almost without fail ( You may have to cater for a few special cases etc ).
If you would like me to explain anything further then just ask.
Also, if you'd like to make a correction, or complain about the images, feel free to
Jess.
[EDIT]
Another way to do it would be this:
Instead of checking which position to go to each move, it could all be worked out in one go.
For example, in an RTS, when a unit is given a destination, it needs to find it's way there.
So, instantly, the A* algorithm takes over, and calculates the shortest route to the destination, while avoiding blocked/occupied hex's. Each hex move is stored in a seperate array as a waypoint, and the unit simply moves from waypoint to waypoint untill the destination is reached.
The same method for determining the next hex would apply as above.
[/EDIT]
Team EOD :: Programmer/Logical Engineer/All-Round Nice Guy