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

This topic is 2062 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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?

##### Share on other sites

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.

##### Share on other sites

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);
return results1;
}
else {
ArrayList<Node> results = createRecursivePath(start, getEstimatedMedianNode(start, median));
return results;
}
}


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

##### Share on other sites

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.

[attachment=19207:astar_pixel.zip]

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...");
System.out.println("The last path...");
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;
}
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?

##### Share on other sites

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.

##### Share on other sites

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.

##### Share on other sites

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)

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

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.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 14
• 30
• 9
• 16
• 22