2
\$\begingroup\$

I have a worldmap, with different cities on it. The player can choose a city from a menu, or click on an available cities on the world map, and the toon should walk over there.

I want him to follow a predefined path.

cities

Lets say our hero is on the city 1. He clicks on city 4. I want him to follow the path to city 2 and from there to city 4.

I was handling this easily with arrow movement (left right top bottom) since its a single check.

Now I'm not sure how I should do this. Should I loop threw each possible path and check which one leads me to D the fastest ... and if I do how do I avoid running in circle forever with cities 1-5-2 ?

\$\endgroup\$

2 Answers 2

Reset to default
3
\$\begingroup\$

Unless you're dealing with a very large grid, A* is overkill. You're probably better off with Dijkstra's Shortest Path, which has the advantage of being far easier to implement, to boot.

A* matters when you have an enormous number of possible paths, like when searching a large game grid. However it also relies on datastructures, particularly the priority queue, which aren't commonly available (and when are are often inefficient.)

http://rosettacode.org/wiki/Dijkstra%27s_algorithm

\$\endgroup\$
13
  • \$\begingroup\$ True that, I used (3D)-A* a lot in the past few weeks, and somehow blocked out everything else... In retrospect I would choose this for your (smallscale?) Problem. \$\endgroup\$
    – JFBM
    Commented Aug 21, 2014 at 8:10
  • \$\begingroup\$ alright i'll check for it, thanks for the info ! I didnt knew it was possible to tweak those pathfinding to follow a define path, I always use them with grid pathfinding. \$\endgroup\$
    – Thierry Savard Saucier
    Commented Aug 21, 2014 at 12:54
  • \$\begingroup\$ @ThierrySavardSaucier What is a grid other than a graph with a fancy layout? It is easy to see each gridcell (Node) individually, but to search a grid, the connections (Edges) are far more interesting. \$\endgroup\$
    – JFBM
    Commented Aug 21, 2014 at 14:27
  • \$\begingroup\$ @Larethian Your getting into very theoric place, and thats not my forte ... I got no idea how the computer place/see/computes these "edges" between each cell. If I knew, I couldve probably find my way around this easily. \$\endgroup\$
    – Thierry Savard Saucier
    Commented Aug 21, 2014 at 14:34
  • 1
    \$\begingroup\$ @ThierrySavardSaucier I believe you misunderstood me. Take a chessboard. You have gridcells and borders of these gridcells. Now, instead of drawing squares for each gridcell, draw a dot. And at every border, draw a line to the dot that is on the other side of the border. If you are done, you have 8x8 Dots all connected with their neighbors. Now forget the chessboard, and name your dots Town1, Town2 ect. You've got a graph connecting towns to each other. You can find from Town1 to Town42 in this graph the same way as if you had named the fields on the chessboard, and searched there. Grid=Graph# \$\endgroup\$
    – JFBM
    Commented Aug 21, 2014 at 14:42
1
\$\begingroup\$

Any A* implementation will do the trick. Look on Wikipedia for example.

A* even allows you to add weight to your connections, resulting in not the route with the fewest hops, but the route with the shortest travel time beeing selected.

Example: Frankfurt→NYC
There is a connection Frankfurt→Moskau→NYC. This one has 2 hops, but the cost is high.
Then there os a way Frankfurt→Rotterdam→London→NYC. This one has three hops, but the cost is low.

Adding costs is worthwile if distance, the mean of transport or something else is important.

\$\endgroup\$
1
  • \$\begingroup\$ and here I though a* was for "regular" pathfinding ... I used it for my battle AI ... didnt knew i could implement it to do way point pathfinding too \$\endgroup\$
    – Thierry Savard Saucier
    Commented Aug 21, 2014 at 12:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .