I'm making this 2D Game, and I was wondering how you would exactly implement the A* Algorithm to find the best path along a 2D Plane, and then let your character follow the path. The A* Algorithm is suppose to be the best algorithm for finding the best path. I need this for an RTS game.
Posted on 2003-01-25 11:39:00 by CyberGuy
Have you looked at the essays at generation5.org?

Thomas
Posted on 2003-01-25 11:44:46 by Thomas
Well we have implemented 2 algorithms for pathfinding in Hostile Encounter:
-"Wave" (our own algorithm)
-A*

However i guess you should ask Eugen for A8 as he implemented it in HE. All i can say is that it was unrecognisable at the end of implementation/optimizations. Without this optimizations A* performed very badly/poorly.

So you should first implement is simple as the algorithm say and keep this for a reference.... after optimizations it will be very diferent !!!

A* also has inconstant behviour: sometimes is very fast (empty maps) and sometimes is very bad (complicated maps or path not found) . Unfortunately you can not assume you will have simple maps nor you can assume a path will be always found (like unit wants to reach a island with no acces points to it)

You must think to find a seccond best loaction if no path can be found. Unit should go to the closest available location nearby unreachable destination.

Curently i think our own "Wave" algorithm is much better than A*... however it is our own propetary algorithm and not freely availabe... Wave is much more simple compared to A* and performs very well under curent CPU (cache optimiztions)...

Whatever algorithm you will use you will have to optimize it a lot to get decent speeds on 256x256 maps or 512x512 for 100+ units moving at same time !!

It is NOT a trivial task... even if it might look like one
Posted on 2003-01-25 12:18:38 by BogdanOntanu
Hi

I can not tell you "exactly" how to implement a* for a lot of reasons. But here is the general idea:

From start position evaluate all your neighbours, choose the best one, make it the current node and so on. All those nodes must be added to a list or vector and at each step must be recalculated the best one to follow. The formula is minim dist from here to start + minim dist from here to end. Nodes already explored must be reexplored if a shorter path to them is found.

- from start :
1 add all neighbours to list
2 Find best node with formula
3 Go there
4 Mark as read
5 go 1 until end is found

i'm sorry i havent got the time now, if you have more questions ask me. There is plenty of documentation around so a google search will help.

Also for big maps and time critical programs a lot of optimisations must be done to make it work at a decent speed.

Eugen
Posted on 2003-01-27 17:56:50 by Eugen
This is just out of curiosity but is the A* algorithm used in 3d games for pathfinding too? If not then which other algorithm is used?

Also is it the only algorithm for pathfinding? Arent there any more, better algorithms?
Posted on 2003-01-29 02:12:41 by clippy
Yes A* is also suitable for 3D games but the calculations will be a little more complicated instead of testing 8 locations nearby you will have to start with 8+9+9 locations/voxels

However on most 3D games terrain is almost 2D (highfield) also ;)
The ideea is tha locations on map are still 2D connected even if on different altitudes

However full 3D games like Descent are different... but you will not see many robots navigating on such complicated 3D maps... wile humman players do their own NN driven A* :)
Posted on 2003-01-29 14:37:07 by BogdanOntanu

wile humman players do their own NN driven A* :)


That's an idea.... teach an NN to do pathfinding... :)

I'm also trying currently to wrestle with pathfinding algo... an idea which popped into my mind was to subdivide a straight line into a polyline, then twist the nodes of the polyline around until I get a set of straight lines from A to B around any obstacles. Of course, it's probably not feasible, heck I get lost in real life easily, I prolly would get lost virtually too :grin: :grin: :tongue:
Posted on 2003-01-30 06:28:23 by AmkG