Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Pathfinding method: discussion  (Read 6524 times)
0 Members and 1 Guest are viewing this topic.
Offline mokopa

Senior Newbie





« Posted 2007-03-30 13:32:15 »

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.


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.


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.


You are now left with a list of all the connections


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...


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.


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?
Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #1 - Posted 2007-03-30 13:47:49 »

BAM!
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 841
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2007-03-30 14:48:24 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline mokopa

Senior Newbie





« Reply #3 - Posted 2007-03-30 15:08:16 »

I think the dead-easy to implement flood-fill will suffice.

Flood fill? Please elaborate.
Offline appel

JGO Wizard


Medals: 68
Projects: 4


I always win!


« Reply #4 - Posted 2007-03-30 16:00:45 »

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"



Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 841
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #5 - Posted 2007-03-30 19:04:41 »

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline mokopa

Senior Newbie





« Reply #6 - Posted 2007-04-01 00:00:05 »

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.
Offline t_larkworthy

Senior Devvie


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #7 - Posted 2007-04-09 18:23:47 »

You have implemented a two way breadth first search
1  
http://cogsci.ucsd.edu/~batali/108b/lectures/heuristic.html#other

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 841
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2007-04-09 18:38:35 »

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:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
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);
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline JAW

Senior Devvie


Medals: 2



« Reply #9 - Posted 2007-04-25 14:59:35 »

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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline amazing

Junior Newbie





« Reply #10 - Posted 2007-07-12 02:19:32 »

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
Offline 2playgames

Junior Devvie





« Reply #11 - Posted 2007-07-12 15:28:46 »

something maybe

Offline keldon85

Senior Devvie


Medals: 1



« Reply #12 - Posted 2007-07-12 23:41:18 »

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.

Offline bienator

Senior Devvie




OutOfCoffeeException


« Reply #13 - Posted 2007-07-13 00:30:54 »

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.
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).

Offline amazing

Junior Newbie





« Reply #14 - Posted 2007-07-13 03:11:49 »

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.
Offline keldon85

Senior Devvie


Medals: 1



« Reply #15 - Posted 2007-07-13 07:53:08 »

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!

Offline t_larkworthy

Senior Devvie


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #16 - Posted 2007-07-13 16:44:40 »

@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).




 

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (36 views)
2014-12-15 09:26:44

Mr.CodeIt (27 views)
2014-12-14 19:50:38

BurntPizza (61 views)
2014-12-09 22:41:13

BurntPizza (96 views)
2014-12-08 04:46:31

JscottyBieshaar (56 views)
2014-12-05 12:39:02

SHC (72 views)
2014-12-03 16:27:13

CopyableCougar4 (74 views)
2014-11-29 21:32:03

toopeicgaming1999 (134 views)
2014-11-26 15:22:04

toopeicgaming1999 (125 views)
2014-11-26 15:20:36

toopeicgaming1999 (35 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!