Sunday July 21, 2024
 The Maths of 3D You can't have 3D without a little maths...

A* PathFinding Algorithm

Have you ever wondered how you can make the ghosts in Pac-man, smart enough to find the shortest route to Pac-man and not go down any paths that are dead ends etc?  Well one way is to use the A* Algorithm.....pronounced.. "A-Star".  There is a load of stuff on the internet on it - and is used in numerous 3D and 2D games because of its effectiveness and simplistic nature.

Now some of the C code that I've put together to implement the A* Demo's, uses a bubble sort to find values with the lowest value....while again this works...its not always the most optimised... but you can always modify the code if you prefer :)  I've tried to keep the tutorial as simple as possible...but would be grateful for any feedback.

Tinny Bit of Theory First!

If we assume a 2D grid...or map it might be called for starters...moving onto 3D sometime in the future, where we would only move in the x-z axis in 3D.

We have a starting point and an ending point!  Our mission is to find the shortest path from the start to the goal without to much overhead.  Of course, the problem is tricky because we have obsticles in our way...which you can see I've added to the image on the right....

A quick sketch always helps to visualise things.

But there is a formula!... Yup an equation to help us on our journey...it is:

F = G + H

where G - is the movement cost from the starting point to the current square

H - cost of movement from the current square to the goal...usually an estimate

F is used to choose our next square...usually deciding which of the 8 surrounding squares has the lowest F, is the one we'll choose.

So lets make each square a node...and of course each node has 8 possible choices for the next node.

From node to node we can calculate our way... but we must keep track of dead ends and record only the shortest path.  This is where list's come into it.... a list is just an array of data, and we use two of them.  Of of them is called the closed list, and the other the open list.  The open list will eventually contain our shortest path from the start to the end, and the closed list will keep track of where we have been, so while the algorithm is running it doesn't go down the same wrong path again.

Putting a Code Example Together

Hmmm....well it all seems simple in theory doesn't it... but when it sometimes come's to coding it, its not always as easy as that.  Well hopefully my demo C code will clarify things and give you a starting point from which you can build a more robust and flexible A* Engine that will plug into anything.

For the two lists, I decided to use the STL library's....but there's nothing stopping you changing the code so that it uses a large allocated space of memory for you own custom array.  I just decided to use the STL library's so it looks simplier.

I start with a text file (map.txt) which contains a 10x10 grid of characters.... '0' for space... '1' for wall....'2' for start and of course '3' for the goal.  Its only a simple dos application....I tried to make it as simple as possible...as understanding is the biggest concern here.  Later I'll add a GUI windows version that you can see it travel its journey....and later on again a Pac-Man game, so you can see how good those ghosts are at getting to you :)

 Txt File: map.txt

A word to the wiser..if your worried about the length of the code don't be... it looks long...but if you break it up, you'll be okay....for example the ReadMap() function does what the name says, and only reads the data from the txt file into a global array called map[10][10]....

The program code starts and finishes from the function main()....and most of the function names are pretty descriptive...I would recommend printing a copy out and doing some scribbling on the paper if you get stuck.

Again if you have any serious problems, just give me a shout, and I'll be glad to give you a hand if I can.

 Output: OpenList (x,y coords of shortest path) node: 1 1 node: 2 2 node: 3 2 node: 2 3 node: 3 4 node: 4 5 node: 5 5 node: 6 6 node: 7 6 node: 8 6 node: 9 7 CloseList (x,y of how we got our optimised path) node: 1 1 node: 2 2 node: 3 2 node: 4 2 node: 5 2 node: 4 2 node: 3 2 node: 2 3 node: 3 4 node: 4 5 node: 5 5 node: 6 6 node: 7 6 node: 8 6 node: 9 7

Wow...a lot of code.... but it's a cool ability to find the shortest path...or even a path from a start point to an end point....using closelist array for example.... as sometimes you don't want your enemy to come straight for you...you could have it slowly work its way towards you....but you want it to get there in the end. (Pac-man basics soon).

Notice how you can move in any of 8 directions...top, top_right, right, bottom_right, bottom, bottom_left, left, top_left......will very little work you can change this to only up, left,right and down...4 possible directions...just remember the A* Algorithm is very flexible as long as you understand it.

One thing I think is worth mentioning...is how far to go before stopping.....a good solution, would be to check the size of the CloseList or OpenList array...and if it reaches a certain size, then to stop....maybe have your character...or object move to there before doing the calculation again etc.... always a good idea.

Optimisations are always important in games....some ideas off the top of my head on improving the speed of the code, would be to use a large allocated block of memory for the arrays...as its slightly faster than linked lists...all that allocating and deleting.  Also maybe use the build in sort algorithms in the STL librarys....or write improved ones for searching for the smallest F value.... there's loads of little tweaks you can work on.

Well I think the next step is to put our A* code into another file....a_star.cpp/.h I think and implement a graphical implementation so you can drewl over just how cool it really is.