•      Sign In
• Create Account

## How to split up pathfinding? How to implement divide-and-conquer on pathfinding?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

11 replies to this topic

### #1asperatology  Members

687
Like
0Likes
Like

Posted 20 December 2013 - 08:07 PM

When pathfinding itself becomes a time hog, it's usually because it's calculating a long path from point A to point B. My hypothesis is that if the path from point A to point B is split up into halves, it may cut down the time it needs to calculate from point A to point B.

I'm trying to use divide and conquer on my A* 2D-grid pathfinding algorithm. I was thinking of splitting up my long path into two shorter paths, with point M (M for median) in the center of the long path. So, a character starts from point A to point M, would mean that I just have to calculate path from point A to point M. And then redo the calculations for the next path from point M to point B.

• Do I just have to find the median point of a path from point A to point B when I'm about to start calculating the path?
• Where do I start updating my character when a smaller path has just completed and it's about to start calculating the next path?

Here's a Java pseudo-code:

	public ArrayList<Node> createHalfPath(Node start, Node goal) {
return createPath(null, getEstimatedMedianNode(start, goal));
}

private Node getEstimatedMedianNode(Node start, Node goal) {
Node result = null;
double dist = Math.hypot((start.x - goal.x), (start.y - goal.y));
if (dist > 16.0) {
int dx = (start.x - goal.x) / 2;
int dy = (start.y - goal.y) / 2;
result = new Node(dx, dy);
result.distanceFromStart = dist / 2.0;
result.hueristicDistanceToGoal = this.getEstimatedDistanceToGoal(result, goal);
}
return result;
}


I've realized I can only get the first half of the path, but not the second part of the path. I have the theory in place, but the logic is where I'm stuck at. Does anyone know how to work it out?

### #2DrEvil  Members

1134
Like
2Likes
Like

Posted 20 December 2013 - 08:48 PM

I work with huge terrains and navigation meshes. We can't even build the entire navmesh due to memory constraints(it uses the popular voxellization techniques), so we built the navmesh in tiles. In order to facilitate long distance pathfinding, which would be extremely slow for long paths, I use the resolution of these tiles as part of the hierarchial pathfinding, which I recommend you do here as well. it's much simpler with tile maps.

The idea is just to group your navigation into larger tiles, and then build a higher level graph on this information. You can do it with a higher level grid or create tile groupings.

http://www.gamasutra.com/view/feature/3000/gdc_2002_polygon_soup_for_the_.php

Depending on the size and complexity of the map, this can simplify the pathfinding hugely. Pathfinding could boil down to a simple search inside the region you are in, and once the search hits the high level sector border, it can skip entirely over all sectors in between, using the cached connectivity of the high level graph. Once it reaches the destination sector, it can fall back down to the tile grid for the rest of the path. Once you have that path through, which includes a mix of high and low level paths, the high level edges would need to be filled in for each tile, but this can be done incrementally as you follow the path. I ended up not doing incremental updates though, because it caused problems such as not having enough path context into the future in order to do my string pulling properly, so I ended up building out the whole path by the time I returned it, but the multi-level pathing is still a huge performance improvement, and filling in those high level sectors is basically a flood fill from the starting polygon/tile until it reaches the next expected high level tile.

### #3asperatology  Members

687
Like
1Likes
Like

Posted 20 December 2013 - 08:54 PM

May I ask, did you use recursive methods to complete this task?

	public ArrayList<Node> createRecursivePath(Node start, Node goal) {
Node median = getEstimatedMedianNode(start, goal);
if (median != null) {
ArrayList<Node> results1 = createPath(start, median);
ArrayList<Node> results2 = createPath(median, goal);
results1.addAll(results2);
return results1;
}
else {
ArrayList<Node> results = createRecursivePath(start, getEstimatedMedianNode(start, median));
results.addAll(createRecursivePath(getEstimatedMedianNode(median, goal), goal));
return results;
}
}


I know my recursive skills are bad, but I'm thinking I might be going in the right direction. Somehow...

### #4asperatology  Members

687
Like
1Likes
Like

Posted 21 December 2013 - 03:04 AM

Here's an attachment of a ZIP-ed JAR file, containing the current working state of the divide-and-conquer A* pathfinding.

To start, click anywhere in the screen. The pink pixel means the starting node, and the green pixel means the ending node. The background is grayed out, so that the whiter, lighter colors of the path can be displayed easily to the eyes.

astar_pixel.zip   16.15KB   73 downloads

One of the paths generated created this path, shown below:

I followed your advice on splitting the screen up into 4 sectors, with each sectors having their portals connecting to each adjacent sectors. I don't know what I've done to get this path. Here's the code for the path above:

	public ArrayList<Node> makePath(Node start, Node goal) {
System.out.println("Making path from sectors...");
if (tempPath == null)
tempPath = new ArrayList<Node>();
Sector startingSector = findSector(start);
Sector endingSector = findSector(goal);

if (startingSector == null || endingSector == null) {
System.out.println("Something is wrong...");
return null;
}

System.out.println("Calculating different segments of paths from each sectors...");
System.out.println("The first path...");
tempPath = createPath(start, startingSector.centerNode);
System.out.println("The second path...");
tempPath.addAll(createPath(startingSector.centerNode, endingSector.centerNode));
System.out.println("The last path...");
tempPath.addAll(createPath(endingSector.centerNode, goal));
System.out.println("Paths complete.");
return tempPath;
}

private Sector findSector(Node node) {
for (Sector sector : sectors) {
if (sector.boundingBox.hasNode(node))
return sector;
}
return null;
}

//Box class - the "boundingBox" member is a Box object.

public boolean hasNode(Node node) {
int x1 = this.width + this.x;
int y1 = this.height + this.y;
if (node.x >= this.x && node.x < x1 && node.y >= this.y && node.y < y1)
return true;
return false;
}



I wanted to ask myself, what else could go wrong?

Java out-of-memory error. There's an infinite loop that for some reasons, the parent of the node is always that same node. (node.parent == node is always true).

So, just to make sure, I did this, in order to stop the infinite loop:

	private ArrayList<Node> recreatePath(Node node) {
int counter = 0;
ArrayList<Node> results = new ArrayList<Node>();
while (node.parent != null) {
if (node.equals(node.parent)) {
counter++;
if (counter > 5)
break;
}
results.add(node);
node = node.parent;
}
//DEBUG
System.out.println("Size of path: " + results.size());
return results;
}


It might be possible this can cause the weird path in the picture shown above. Got any hints?

### #5ferrous  Members

5755
Like
0Likes
Like

Posted 30 December 2013 - 01:45 PM

You don't have to make things recursive, any recursion can also be programmed iteratively.  (Though sometimes recursion can be cleaner/easier)

I suggest spitting out some more debug info graphically.  It looks like the path is trying to go to the wrong median node?  I would draw all the sectors, and the entrances/exits to the sectors.  I think it will make tracking down why the path looks like it does easier.

### #6asperatology  Members

687
Like
0Likes
Like

Posted 30 December 2013 - 07:45 PM

I suggest spitting out some more debug info graphically.  It looks like the path is trying to go to the wrong median node?

Yeah, it's going to the wrong median node. The old code was hardwired to reach that node before advancing on to the next node.

But to be honest, I can hardly see any difference in speed when comparing the old method of "going from node A to node B directly", and the new method of "going through portal A to portal B, then connect node X in portal A to node Y in portal B, finally connect."; the speed difference is minimal. In fact, I'd say it's slower than the old method, because the new method has to be called 3 times to make the path, rather than the old method of calling 1 time.

### #7ferrous  Members

5755
Like
0Likes
Like

Posted 31 December 2013 - 02:17 PM

An empty map is probably not the best test, that's the worst case scenario, and could probably be optimized out in a game with lots of open spaces with a simple raycast to the goal check, before doing any pathfinding.

A super cluttered map is where you'd save time, as the agent only has to look at it's local surroundings before starting to move, it wouldn't have to wait for the pathfind to complete.

To test it though, you can do two things.  First, I suggest more visualization, perhaps color all nodes that are visited by each algorithm (different shades), and then I suggest also profiling the results as well (with visualizations off)

### #8wodinoneeye  Members

1669
Like
0Likes
Like

Posted 16 February 2014 - 10:49 AM

The portal (hierarchical) method can help alot (on sufficiently large maps where the extra complexity of the hierarchical mechanism overhead is insignificant) when there are restricted paths (saving alot of blind alley checking in typical solid wall  maze like maps).

For some games actually saving a path and reusing/sharing it (ie- units being sent to the same destination) and portal (high) level paths are alot less data to store if you have many combinations of reused source + destination paths

--------------------------------------------Ratings are Opinion, not Fact

### #9KnolanCross  Members

1935
Like
0Likes
Like

Posted 17 February 2014 - 07:33 AM

Splitting the path in two is faster because you reduce the number of nodes explored, still, keep in mind that you will only notice difference in huge maps. Also, the median point doesn't really have to be part of the path, so you may end up with a non-optimal path.

That being said, I'd rather use JPS (assuming you don't have different weight restrictions), it is much faster than any other approach.

Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).

### #10asperatology  Members

687
Like
0Likes
Like

Posted 17 February 2014 - 08:39 AM

An empty map is probably not the best test, that's the worst case scenario, and could probably be optimized out in a game with lots of open spaces with a simple raycast to the goal check, before doing any pathfinding.

Isn't an empty test a good way to test the performance of optimized A* pathfinding for worst case scenarios? If I were to optimize my own derivation of A* pathfinding for my game, so that it's logic is adapted into what my game wants, I could use an empty map in order to see exactly how the most lagging scenario it is and how it's affecting my game.

### #11ferrous  Members

5755
Like
0Likes
Like

Posted 17 February 2014 - 08:58 PM

I guess you can make sure that you're new algorithm isn't terrible at empty maps, but modifying your pathfinder so it does a check to see if it can do a direct walk from the start to the goal, and just returns that straight path would bypass that case entirely.

You're also not going to see any speedup compared to the standard A* algorithm, so you'd mostly just be doing a sanity test to make sure the more complicated algorithm isn't overdoing it.

The most lagging scenario would be when the paths are not straightforward, or when the goal cannot be reached at all. Though the latter, again is a scenario that's best optimized out entirely if possible.

### #12Ashaman73  Members

13650
Like
0Likes
Like

Posted 21 February 2014 - 02:42 AM

You should consider several approaches. The hierachy is a really good solution for really large maps. If you just have issues with performance (stuttering due to long calculations), then you should consider to split up your A* calculation. This works quite fine, just explore maybe 100 nodes per frame to equally distribute the performance hit on severaly frames. I use this technique by calculating several paths over one or more frames distributed on multiple cores. This should work for small to medium sized maps.

If you want an immediate reaction of the entity start with an A* and take the result of the first frame (the A* heuristic should point into the right direction). This path is a good guess of where the final path will point to, and it should be good enough to let your entity start to move in the right direction, though it only works if you have one potential goal. After the final path has been calculated you can "connect" the entity to the final path (maybe a small A* is necessary to connect them).

Edited by Ashaman73, 21 February 2014 - 02:44 AM.

Ashaman

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.