Pathfinding method: discussion

Game Mechanics Artificial Intelligence
#1

Hi there

I don’t have a specific question per se, but would appreciate some discussion on this topic.

As with many game developers, I have now reached the point where Pathfinding has become a problem. I have spent some time on the following idea, and would like you to comment on it, or find errors in my thinking. I realize that I am probably re-inventing the wheel, in which case I would appreciate it if you point that out to me. Also, I think that this method may only work for small networks, because you start running into problems somewhere between “The Towers of Hanoi” and “The Traveling Salesman”.

So, without further ado…

Here is the network of nodes connected by existing paths. SP is the Start Point, EP is the end point. How to get from SP to EP (shortest route)? A very important consideration in this case is that by “shortest path”, I mean “the least number of nodes to traverse”, and NOT “shortest physical distance”. That would be “Best Path”. However, it it easy to figure out which path is the shortest if you have the x, y (and z) coordinates of the nodes.

http://www.gps-coords.co.za/path/network.jpg

Make a list of all the connections. At this point check if a connection between SP and EP exists (in this case it would have been 9-6). If there is, you have found the only (and shortest) path. If it doesn’t, continue.

http://www.gps-coords.co.za/path/cnxlist.jpg

Starting at the top left of the connections list (node 1), start eliminating duplicate connections. In this example, 1-3 is the same as 3-1, 1-4 is the same as 4-1, etc.

http://www.gps-coords.co.za/path/cnxrem.jpg

You are now left with a list of all the connections

http://www.gps-coords.co.za/path/cnx2.jpg

Separate the start and end points from the intermediaries. If a path element contains the start point (9) it will be considered a start path, if the path element contains the end point (6) it will be considered an end path, all other path elements are considered intermediaries. At this point, check if there are any shared nodes between start paths and end paths (9-x, x-6). If there are, calculate the lengths of these paths to determine the shortest route. There may be any number of these three-node paths, find all of them, find the shortest, end. If not, continue…

http://www.gps-coords.co.za/path/cnxsep.jpg

When no two node paths (9-6), or three node paths (9-x-6) could be found, things start getting a little complex. In our example, there are two path leading from node 9 (start point) and two paths leading to node 6 (end point). Let’s call the start point paths 9-a and 9-b, and the end point paths x-6 and y-6. Ideally, if there exists a 4 node path, we should look for a-x, a-y, b-x or b-y. These mid-paths, if they exist, will be found in the Intermediary path list. If more than one path is found, calculate distance, find shortest, end.

http://www.gps-coords.co.za/path/iterate.jpg

If no 4-node path was found, the next logical step will be to seek for a 5-node path. More or less the same procedure is followed. Again, we know that there are two paths leading from SP, namely 9-1 and 9-8. We also know that there are 4 intermediary paths with node 1 as an element, namely 1-3, 1-4, 1-7 and 1-8. Since the 9-1-3 path is established, we now consider the first intermediary path element (1-3) as the start point, and use the same method as above to find the shortest route to EP. Ideally this will be 3-2-6 (looking for 2-3 or 3-2) or 3-5-6 (looking for 3-5 or 5-3), since we know that the two paths converging on node 6 come from node 2 and node 5. If such a path is found, we would have 9-1, 1-3, 3-2, 2-6 (9-1-3-2-6 - five nodes) or 9-1, 1-3, 3-5, 5-6 (9-1-3-5-6 - five nodes).

If no path was found, we take the second path element from the node 1 list, namely 1-4. We now consider this intermediary path element (1-4) as the start point, and use the same method as above to find the shortest route to EP. Ideally this will be 4-2-6 (looking for 2-4 or 4-2) or 4-5-6 (looking for 4-5 or 5-4), since we know that the two paths converging on node 6 come from node 2 and node 5. If such a path is found, we would have 9-1, 1-4, 4-2, 2-6 (9-1-4-2-6 - five nodes) or 9-1, 1-4, 4-5, 5-6 (9-1-4-5-6 - five nodes).

If more than one 5-node path was found, find the one with the shortest physical distance. End.

If no 5-node path was found…

And so on.

Comments?

#2

BAM!

#3

As Dijkstra’s algorithm does take distance (or penalty…) into account, while the OP said he only wanted to find the least nodes to traverse, and numerous heuristics wouldn’t work, as the position of the nodes might not be relevant (as again, there is no penalty - is it safe to assume that?), I think the dead-easy to implement flood-fill will suffice.

#4

Flood fill? Please elaborate.

#5

Dijkstra’s algorithm works just fine for that. Cost of all edges should be the same, like 1.

If all edges cost the same, then clearly, the least nodes traversed would be:
9-8, cost 1
8-5, cost 1
5-6, cost 1
total cost = 3

or “3 jumps”

#6

Well ofcourse you can use the algorithm with all edge-costs being a constant, but then you have a heck of a lot overhead.

For floodfill, simply use these steps
begin at the origin-node, tag it ‘0’
traverse to the neighbouring nodes of the last step, that are not tagged yet, tag them 1
traverse to the neighbouring nodes of the last step, that are not tagged yet, tag them 2
traverse to the neighbouring nodes of the last step, that are not tagged yet, tag them 3
etc.
when you find your destination-node, loop:
-> find the node near you that’s tagged lower than the current node
now you found your destination->source path

#7

That’s actually pretty darn clever! I’ve had a quick look at it and it seems to suit my requirements very well, in that it is as easy to find an alternative shortest route (possibly same amount of node traversals) as it is to find the first. For the purpose I will be applying the pathfinding method for, I will be dealing with an extremely small number of nodes (typically less than 20)…however, possible alternative routes will be vitally important. Thanks for your description.

That said, I am still going to explore the possibilities of the original post. As you may have gathered, I have never really ventured into this realm and I only know algorithms by name, not by nature. Does “my method” bear any resemblance to an existing algorithm? Would be interested to know.

#8

You have implemented a two way breadth first search

http://cogsci.ucsd.edu/~batali/108b/lectures/heuristic.html#other
#9

Nope, that’s something else. It’s very interesting though!

I’m just determining the path destination->source, not searching from the destination.

Another nice feature of my algorithm is that you can search from multiple sources and multiple destinations at the same time, simply by tagging a few tiles 0 instead of only 1. The algorithm doesn’t have to be changed to support this.

I implemented this to find which unit is nearest to a which resource, without calculating N*M paths for N units and M resources.

Some example-code for those interested:


pathfinder = new PathFinder(Surroundings s, new ResponseExample());
pathfinder.addSource(x, y);
pathfinder.addSource(x, y);
pathfinder.addSource(x, y);

while(pathfinder.isSearching())
{
   pathfinder.search();

   while(pathfinder.hasNextPath())
   {
      Path path = pathfinder.nextPath();
      int[] coords = new int[2];

      while(path.hasNext())
      {
         path.next(coords);
         int x = coords[0];
         int y = coords[1];
      }
   }
}


public class ResponseExample implements SurroundingsResponse
{
   public int getResponse(int x, int y)
   {
      if(x == 45 && (y == 25 || y == 29))
         // we have found silver, continue for gold
         // we get a new Path to this location
         return FOUND_AND_CONTINUE;

      if(x == 104 && y == 43)
         // we stumbled upon some gold, stop searching!
         // we get a new Path to this location
         return FOUND_AND_STOP;

      return NOT_FOUND_AND_CONTINUE;
   }
}







public interface Surroundings
{
   public boolean isAccessible(int x, int y);
}

public interface SurroundingsResponse
{
   public static final int NOT_FOUND_AND_STOP     = 0;
   public static final int NOT_FOUND_AND_CONTINUE = 1;
   public static final int FOUND_AND_STOP         = 2; // this is a destination, after it is found, pathfinder.isSearching() returns false
   public static final int FOUND_AND_CONTINUE     = 3; // this is a destination, after it is found, the pathfinder will continue

   public int getResponse(int x, int y);
}
#10

Its hard to beat A*, which is a type of goal oriented flood fill.

Pathfinding in games is not only the question of finding a way from node to node, but also how to place nodes in the world. There can be a lot of optimization done with placing the nodes. A* cannot be tweaked that much.

There are other solutions to pathfinding, but they only apply to very certain problems or situations, so they just fit a few individual games. For example games
with very open space and only small obstacles, you can basically use a direct path and just avoid obstacles along the way. For this it is required, that there are no dead ends and you can go around any obstacle. An easy algorithm just follows the border of the obstacle to one direction until it reaches a point where it can continue to use the direct path.

-JAW

#11

has anyone every heard of Graph Theory? It can be used, by multiplying matrices, to find the shortest path between to points. Done correctly you can easily find the shortest path between any 2 locations on any kind of surface 2d or 3d. For some reason the simple algorithm that makes it work does not seem to be mentioned anywhere on these forums… If you need more detail on how i got it work… say something maybe? and ill post again

#12

something maybe

#13

Dijkra’s method and all methods use graph theory. The different approaches have different uses. A* stores all nodes, so if you have 1 trillion nodes then you may want to use a different method. Also the size of the problem with A* is actually a lot larger than you think since it has to measure the cost of each node each time.

You will find that depth first search tends to be the best all round solution. And if memory serves it is also the most speed efficient (when all edges are the same length) and memory efficient.

#14

you are right, we are already all talking about graph theory :wink:

It is correct that A* needs all possible nodes in memory but the cost between them does not change. The only value which needs to be recalculated is the (under)estimated distance between node and target. The technically interesting part of the A* is that it always returns the best route to the target.

it took me for a radius 128 hexagonal map around 2seconds to calculate the perfect route from one pole to the other (and the map was really complicated with a lot of dead ends, obstacles and mountains).

#15

if all these odly named methods of finding a path are really just graph theory in disgueise, why all the funny names? O! I believe the methods i said (well… didnt quite say but have figured out) finds the path quickly so i use it each time a path needs to be found. It will find the path through crwods of unrelated objects because each time it runs it updates all paths and once again picks the shortest to the destination. If a crowd or swarm of something moves one way, it will change its path to accomidate.

#16

I’m not saying graph theory in disguise, but they are all related to reachability and just find them in different ways. A* is not as fast as you think either, remember that it has to check every node on every iteration, and each time it adds a new node it has to check all of its children.

When we did AI we looked at the complexity of these algorithms and the storage requirements. If the node lengths are equal then the better choice is depth first, if they are not then usually A*. Within a game where the environment may change you don’t just use searching algorithms!

#17

@amazing:- graphy thoery is not a fixed thing, but a discapline. The path finding algorithms we are talking about like A*, depth first, etc. are search methods on graphs and a small aspect of graph theory, we need the funny names to identify what we are talking about, there are an infinite number of ways you could calculate a path from node A to B, but each method has its advantagous and disadvantagous (memory requirements, time complexity, optimality). Graph thoery also deals with lots of other things like labelling different forms of graphs, algorithms for determining what type a graph is etc. Anything to do with graphs really (colouring them in, triangulating them etc. its a huge on-going mathmatical discapline).