A-Star pathfinding app with source code
by ChrisG · in Technical Issues · 07/11/2007 (1:56 pm) · 6 replies
I've posted this as a resource, just waiting approval
I developed an AStar pathfinding test application a little while back.
The plan was to use it as a test bed for Hierarchical AStar pathfinding. At the moment I've just got the basic A star working.
It's in 2D but should work in 3D.
The cool thing about it is you can actually see how the computer performs the A Star search.
It can be downloaded here www.colab-aktiv.com/strangeDays/misc/freeStuff/
All the source files are included
It's done in Borland C++ Builder 6 but you should be able to port the classes to VS.
If you want to use it in Torque you'll probably have to implement it in C++
It requires nodes to be placed and if you look at the test map at how I've group nodes around the corners of walls you can see how it would be easy to find cover. Look for the closest node that is out of sight of the aggressor.
Anyone is free to use any of the code/classes they want.
To run the test map
- load bmp
- load nodes
- select start node on map and click 'set' start node (on right)
- select end node and set the end node
- click search
I developed an AStar pathfinding test application a little while back.
The plan was to use it as a test bed for Hierarchical AStar pathfinding. At the moment I've just got the basic A star working.
It's in 2D but should work in 3D.
The cool thing about it is you can actually see how the computer performs the A Star search.
It can be downloaded here www.colab-aktiv.com/strangeDays/misc/freeStuff/
All the source files are included
It's done in Borland C++ Builder 6 but you should be able to port the classes to VS.
If you want to use it in Torque you'll probably have to implement it in C++
It requires nodes to be placed and if you look at the test map at how I've group nodes around the corners of walls you can see how it would be easy to find cover. Look for the closest node that is out of sight of the aggressor.
Anyone is free to use any of the code/classes they want.
To run the test map
- load bmp
- load nodes
- select start node on map and click 'set' start node (on right)
- select end node and set the end node
- click search
About the author
Currently working on ZDay: www.zdaygame.com
#2
The purple nodes are those on the open list, the grey ones are on the closed list. The green lines are paths that it has tested.
If you go to the website above it explains how a star works and the open and closed lists
07/11/2007 (4:27 pm)
This is where I got the algorithm from www.policyalmanac.org/games/aStarTutorial.htm.The purple nodes are those on the open list, the grey ones are on the closed list. The green lines are paths that it has tested.
If you go to the website above it explains how a star works and the open and closed lists
#3
07/11/2007 (6:06 pm)
Ah, I've been trying to base A* off that same one. Using nodes around the map is a good idea. I've been testing the 8-adjacent squares method on paper and that always gets me getting into rooms, and turning around again. Very clever, Chris.
#4
This doesn't require the placement of nodes although I have no idea how to create the mesh dynamically - especially inside difs.
07/12/2007 (1:51 am)
Another way to go with a-star is to use a navigation mesh. You've probably already found this but if not check out Justin Mette's plan: www.garagegames.com/blogs/1828/5350This doesn't require the placement of nodes although I have no idea how to create the mesh dynamically - especially inside difs.
#5
07/12/2007 (5:34 am)
(Bryce cannot comment because he is working on translating ASTARSEA.cpp into Torque Script while reading out of his "Learn C++ in Ten Minutes" book. Please stand by.)
#6
07/27/2007 (11:13 am)
And he succeeded. Thank you, Chris! 
Torque Owner Bryce
Tactical AI Kit
While it's processing the path and I'm watching it, I can see that there are green lines drawn to little purple squares and light green squares. What's the color difference mean here?
Program works well, never failed a path yet. I have ASTARSEA.cpp printed out, and I am about to somehow interpret that into english without any C++ knowledge (I can program a little calculator, but that's pretty much it :-p).