Archived

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

ServantOfGlaaki

Which algorithm do I use?

Recommended Posts

For my pathfinding system, I have my connectivity map sorted out now (thanks Timkin!). Now, I need to use a search algorithm to make use of it. What I want is: An algorithm as fast as possible It doesn''t have to be too accurate (I''m only using a maximum of about 10 nodes) It should be (fairly) simple to implement I was thinking about A*, but it seemed very complex, and kind of overkill for a simple operation such as this. All comments and suggestions gratefully received. Thanks Stewart

Share this post


Link to post
Share on other sites
Kylotan    10011
10 nodes? Simple? Depth-first search implemented recursively is the simplest (I think), but not guaranteed to get you anything like the best path. Breadth-first search with an explicit queue can get you better paths, but is almost as complex to implement as A* in my experience. It''s pretty much the same thing except without the heuristic.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ]

Share this post


Link to post
Share on other sites
Timkin    864
Good to hear you''ve got things going Servant!

Did you want to do the search for a single path online, during gameplay, or offline and store all possible paths?

If you do it offline, use Dijkstra''s algorithm or brute force (since you have a very small state space).

If you want to do it online, then you might want to use the Distance Transform algorithm. It''s fairly simple and works basically like this. Starting at the goal region, find all adjacent (connected) regions and mark them as having cost 1. Then, for each of those regions, find their adjacent regions and mark them with a cost of 2, unless they already have a lower cost, in which case you don''t change the cost. Then, for each region marked with a cost of two, find it''s adjacent regions and mark them with 3 (unless they''re 2 or 1). Keep doing this, making sure that you consider all regions at depth n before considering regions at depth n+1. The first time you hit the start region, the path to the goal is given by following a path of decreasing numbers.

Alternatively, just brute force the search, but might I suggest searching out from the goal toward the start state.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Just to make things a bit more comprehensible for you, I''ll explain exactly what I''m doing:

I''m making the path-finding for a 2d Point-and-Click adventure (like the Lucasarts games).

The idea is that, when the user clicks on a region designated ''walkable'', a path is worked out. The walkable regions are split up into polygons, which I have in a connectivity map. All I need to do now is implement a search algorithm so that my program knows how to get from one polygon to another.

The search would take place online, when the user clicks somewhere.

quote:

If you want to do it online, then you might want to use the Distance Transform algorithm. (snip)



Ah-ha! That''s seems fairly easy to implement, and sounds like it should get the job done perfectly. I''ll implement it, and then report back!

Thanks again Timkin!
Stewart

Share this post


Link to post
Share on other sites
I had a go at implementing the distance transform algorithm, but it went quite wrong. I ended up getting into 2 recursive functions that I''m pretty sure won''t work. Can you give me some advice on how to code this?

Thanks
Stewart

Share this post


Link to post
Share on other sites