🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Pathfinding
Author
Hey guys,
I''m not quite at the point where I''m programming the AI in my game yet, but I''d like to go ahead and get this bit out of the way, since it''s the only part I don''t really know...
Ok, my tile map is stored in a 2D array. I have seperate collision data stored in a 2D array. The collision data sort of "overlays" the map data. A 1 in the collision array means the tile is unwalkable, a 0 means it''s walkable.
So, using this, how do I find the shortest path from tile (x,y) to tile (x1,y1)? I would imagine this is just a simple A* algorithm, but I still have no clue how to do it.
If you have questions or an answer, simply post or e-mail me at nairb@usa.com
Thanks,
--Nairb
Hello Nairb:
Some references that hopefully will explain things:
http://www.geocities.com/jheyesjones/astar.html
http://www.gdmag.com/backissue1996.htm
http://www-cs-students.stanford.edu/~amitp/gameprog.html
Hope those help!
Ferretman
ferretman@gameai.com
www.gameai.com
From the High Mountains of Colorado
Edited by - Ferretman on July 9, 2001 10:01:38 PM
Edited by - Ferretman on July 9, 2001 10:02:53 PM
Some references that hopefully will explain things:
http://www.geocities.com/jheyesjones/astar.html
http://www.gdmag.com/backissue1996.htm
http://www-cs-students.stanford.edu/~amitp/gameprog.html
Hope those help!
Ferretman
ferretman@gameai.com
www.gameai.com
From the High Mountains of Colorado
Edited by - Ferretman on July 9, 2001 10:01:38 PM
Edited by - Ferretman on July 9, 2001 10:02:53 PM
Actually, A* would not be the best algorithm for this task. Dijkstra's algorithm would be. Essentially, your 2-D array is a graph structure. The array elements can be transformed into nodes of the graph. The benefit of Dijkstra's algorithm is that not only does it return the shortest path between two nodes in a graph, but it actually returns all of the shortest paths from the source to all other points in the graph
Assuming that you can move diagonally, each tile can either be crossed or it cannot be crossed. If it can be crossed, then there is a path from each side of the tile to each other side of the tile. Alternatively, you can think of it as being able to move from the centre of one tile to the centres of surrounding tiles (or not).
So, each tile has a coordinate (x,y). The section of the array looks like:
(x-1,y+1),(x,y+1),(x+1,y+1)
(x-1,y ),(x,y ),(x+1,y )
(x-1,y-1),(x,y-1),(x+1,y-1)
Now, if the elements within this part of the array are:
0 1 1
1 1 0
1 1 0
Then this corresponds to a graph structure, where the arcs between nodes represent that you can move from either element to the other or back (clearly then, elements that are zero cannot be moved to or from)
So, we get
(x-1,y+1)....(x,y+1)<-->(x+1,y+1)
.....................^................
......................|................
.....................v................
(x-1,y )<-->(x,y )....(x+1,y )
......^..............^................
.......|...............|................
......v..............v................
(x-1,y-1)<-->(x,y-1)....(x+1,y-1)
[Please ignore the dots... they are only filler so that the graph structure will be properly spaced when this text is displayed]
Unfortunately someone seems to have borrowed my search algorithm book from my bookshelf so I cannot give you the pseudo-code for the algorithm. However, a very quick google search turned up many sites with Dijkstra's algorithm. Here's one of them:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html
I hope this helps you out.
Cheers,
Tim
Edited by - Timkin on July 9, 2001 12:15:00 AM
Assuming that you can move diagonally, each tile can either be crossed or it cannot be crossed. If it can be crossed, then there is a path from each side of the tile to each other side of the tile. Alternatively, you can think of it as being able to move from the centre of one tile to the centres of surrounding tiles (or not).
So, each tile has a coordinate (x,y). The section of the array looks like:
(x-1,y+1),(x,y+1),(x+1,y+1)
(x-1,y ),(x,y ),(x+1,y )
(x-1,y-1),(x,y-1),(x+1,y-1)
Now, if the elements within this part of the array are:
0 1 1
1 1 0
1 1 0
Then this corresponds to a graph structure, where the arcs between nodes represent that you can move from either element to the other or back (clearly then, elements that are zero cannot be moved to or from)
So, we get
(x-1,y+1)....(x,y+1)<-->(x+1,y+1)
.....................^................
......................|................
.....................v................
(x-1,y )<-->(x,y )....(x+1,y )
......^..............^................
.......|...............|................
......v..............v................
(x-1,y-1)<-->(x,y-1)....(x+1,y-1)
[Please ignore the dots... they are only filler so that the graph structure will be properly spaced when this text is displayed]
Unfortunately someone seems to have borrowed my search algorithm book from my bookshelf so I cannot give you the pseudo-code for the algorithm. However, a very quick google search turned up many sites with Dijkstra's algorithm. Here's one of them:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html
I hope this helps you out.
Cheers,
Tim
Edited by - Timkin on July 9, 2001 12:15:00 AM
Dijkstra will also need more CPU time (unless I am mistaken)
A* will not necessarily return the shortest path (although it can be changed so it will return the shortest path, but then it would probably be a bit slower than Dijkstra)
A* will normally be quicker to actually find the path which is nice.
Dijkstra has another advantage in that it would probably be easier to write and also easier to write so you can break up the calculation.
I''ve recently written a nice little VB module which uses A* to do searches, but because I was worried about speed and there is no neat multithreading available in VB, I wrote it so I could break up the calculations, and that way I would allocate say 10ms to the pathfinder, tell it to search then 10ms later it would return (earlier if it found the path obviously), then when I had a bit more spare CPU time, I would tell it to go for another 10ms.
The coding for the whole algorithm was a bit tricky, definately possible (it took about 3 afternoons after school, which included writing a program to test it and finding out how A* actually works
) but I think it would be a bit easier to make Dijkstra work the same way... though thinking about it, maybe it wouldn''t 
Anyway, make your algorithm as non-specific as it can be. Have external functions like: CanWalk and WalkCost, so you can then plonk it into another project when you move on, and it will make your code more readable and robust.
Also, depending on the maps, you might be able to do an even less CPU taxing algo... Dijkstra for finding a path through a desert is overkill. If the map is fairly open with a few small obstacles, you might want to just go straight for the target and turn when you hit something.
Trying is the first step towards failure.
A* will not necessarily return the shortest path (although it can be changed so it will return the shortest path, but then it would probably be a bit slower than Dijkstra)
A* will normally be quicker to actually find the path which is nice.
Dijkstra has another advantage in that it would probably be easier to write and also easier to write so you can break up the calculation.
I''ve recently written a nice little VB module which uses A* to do searches, but because I was worried about speed and there is no neat multithreading available in VB, I wrote it so I could break up the calculations, and that way I would allocate say 10ms to the pathfinder, tell it to search then 10ms later it would return (earlier if it found the path obviously), then when I had a bit more spare CPU time, I would tell it to go for another 10ms.
The coding for the whole algorithm was a bit tricky, definately possible (it took about 3 afternoons after school, which included writing a program to test it and finding out how A* actually works
) but I think it would be a bit easier to make Dijkstra work the same way... though thinking about it, maybe it wouldn''t Anyway, make your algorithm as non-specific as it can be. Have external functions like: CanWalk and WalkCost, so you can then plonk it into another project when you move on, and it will make your code more readable and robust.
Also, depending on the maps, you might be able to do an even less CPU taxing algo... Dijkstra for finding a path through a desert is overkill. If the map is fairly open with a few small obstacles, you might want to just go straight for the target and turn when you hit something.
Trying is the first step towards failure.
Hi,
just started to learn A* .... I own the Game Programming Gems Book and read the great articles about A* implementation. Steve Rabin explained the Points of Visibility in his article. I am the type of guy learning from looking at code .... All A* implementations i have seen so far are based on grids and hexagonal maps. The implementation of using PoV's seems quite different to me so i was wondering if there is c code out on the net, explaining A* and Point's of visibility .... Any comments are very welcome.
Thanks in advance
Ronny
Edited by - RonnyFunk on July 10, 2001 8:43:24 AM
just started to learn A* .... I own the Game Programming Gems Book and read the great articles about A* implementation. Steve Rabin explained the Points of Visibility in his article. I am the type of guy learning from looking at code .... All A* implementations i have seen so far are based on grids and hexagonal maps. The implementation of using PoV's seems quite different to me so i was wondering if there is c code out on the net, explaining A* and Point's of visibility .... Any comments are very welcome.
Thanks in advance
Ronny
Edited by - RonnyFunk on July 10, 2001 8:43:24 AM
The best way i've found to do POV is to get all of your enemies to check the tiles in between them and the player if the player is in an area where they could be visible (not behind the enemy, for example). The enemy object would scan through the tiles starting at itself then moving toward you. If one of the tiles in that path has a NO_VISIBILITY flag set, then the loop is broken and the enemy can't see the player. Otherwise, they can see you.
You could do this on the pixel level, which would be more exact, but it would take much more CPU than doing it on the tile level.
Hope that helps.
dave
[edit] damned typos. [/edit]
--
david@neonstar.net
neonstar entertainment
Edited by - neonstar on July 10, 2001 9:33:47 AM
You could do this on the pixel level, which would be more exact, but it would take much more CPU than doing it on the tile level.
Hope that helps.
dave
[edit] damned typos. [/edit]
--
david@neonstar.net
neonstar entertainment
Edited by - neonstar on July 10, 2001 9:33:47 AM
quote: Original post by Timkin
Actually, A* would not be the best algorithm for this task. Dijkstra''s algorithm would be. Essentially, your 2-D array is a graph structure. The array elements can be transformed into nodes of the graph. The benefit of Dijkstra''s algorithm is that not only does it return the shortest path between two nodes in a graph, but it actually returns all of the shortest paths from the source to all other points in the graph
FWIW, A* works very nicely with graph structures (what it was designed to do).
Furthermore, if you remove the h() out of the A* basic algorithm f() = g() + h() then the A*
actually performs like a Dijkstra''s Algorithm.
And if h() is admissible, then A* has been proven to always return the optimum path in the
fewest node expansions (read: faster). See Bryan Stout''s Game Dev Article for details.
And finally, if someone (as in the original poster) does not need all the shortest paths, but simply
needs ''the'' shortest path, Dijkstra''s is overkill.
All that being said, I found Dijkstra''s to be more suited than A* for solving a path in a world where
the geometry was non-Euclidian.
Eric
Author
Thanks for all the information guys,
I''ll weave through the articles and research a bit on the A* and Dijkistra algs.
Wish me luck on this game... I''m hoping to get it done before the IGF :-D
Thanks,
--Nairb
I''ll weave through the articles and research a bit on the A* and Dijkistra algs.
Wish me luck on this game... I''m hoping to get it done before the IGF :-D
Thanks,
--Nairb
quote: Original post by Geta
Furthermore, if you remove the h() out of the A* basic algorithm f() = g() + h() then the A* actually performs like a Dijkstra''s Algorithm.
Actually, it performs as Depth First Search if you omit your heuristic cost.
quote: Original post by Geta
And if h() is admissible, then A* has been proven to always return the optimum path in the
fewest node expansions (read: faster). See Bryan Stout''s Game Dev Article for details.
Thanks, but no need. I am fully aware of the optimality proof of A*. I was, after all, formerly a mathematician before moving into AI!
The biggest problem with A* is finding admissable heuristics. Of course in pathfinding, straight line distance normally suffices. (Besides, part of my motivation for encouraging Dijkstra''s was to get people to learn that there is more out there than just A*, neural nets, genetic algorithms and finite state machines! )quote: Original post by Geta
And finally, if someone (as in the original poster) does not need all the shortest paths, but simply
needs ''the'' shortest path, Dijkstra''s is overkill.
Yes, Dikstra''s can be overkill. However, if we assume that movement costs are a function of terrain type then path costs can be precomputed during game development (or a base cost for which different units use a multiple of) and stored along with terrain information. In which case, while Dijkstra''s will certainly expand more nodes (because it expands all accessible nodes at least once) this wont be too much of a burden on processor time given small graph sizes (which would be true for many games). Since targets often move during execution of a plan (at least in the RTS genre) then the extra info returned by Dijkstra''s may be of use in dynamically replanning the path.
quote: Original post by Geta
All that being said, I found Dijkstra''s to be more suited than A* for solving a path in a world where
the geometry was non-Euclidian.
...and that will most likely be due to the difficulty in finding admissable heuristics in non-Euclidean spaces! Did you consider using the metric appropriate to the space as your heuristic unit length?
Cheers,
Tim
I find in a lot of cases for pathfinding, the a better heuteristic to use than straight line distance is manhatten distance ( |x2 - x1| + |y2 - y1| ) although obviously it depends on the movement you allow for the agent. But the other advantage this has is that it is a lot faster than straight line distance to calculate because there is no square root operaton.
Trying is the first step towards failure.
Trying is the first step towards failure.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
