Archived

This topic is now archived and is closed to further replies.

GekkoCube

path finding simpler than i thought???

Recommended Posts

GekkoCube    116
looking at stuff relating to path finding, looks like those algorithms consider unexpectful things, such as obstacles, walls, and etc. but my graph that i create is a simple connected graph. there are no external obstacles i need to consider at this time. so, would it be overkill if i used A*?

Share this post


Link to post
Share on other sites
JTippetts    12970
Finding the shortest path from one node in a connected graph to another node is exactly what A* was designed for, so I don''t think it would be overkill to implement it. Most games that use A* for pathing (eg. tile-based games or what-have-you) do so in the context that the "grid" is in itself a connected graph of nodes. Some of the nodes which are adjacent in the grid are not "connected" within the graph, in that one of the nodes has a wall or other obstacle and so is not considered as an adjacent node when the graph is being searched; this is all your "unexpected things" really are.

A* is a simple enough algorithm to implement, that it really is worth the effort to implement, even if the problem it is intended to solve seems at the moment rather trivial.


Josh
vertexnormal AT linuxmail DOT org


Check out Golem at:
My cheapass website

Share this post


Link to post
Share on other sites
johnnyBravo    100
if u r using a small maze, or dont require speed 2 much, you can use flood fill, which finds the path everytime, and the perfect path depending on the way u program it

it does already make a perfect path basically, but it looks more shaper when moving towards the target

[edited by - johnnybravo on September 1, 2003 9:51:04 PM]

Share this post


Link to post
Share on other sites