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

Thompson Lee · 2014-02-21T08:42:25

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?

Artificial Intelligence Programming

Started by tom_mai78101 December 21, 2013 02:07 AM

10 comments, last by Ashaman73 10 years, 2 months ago

ferrous

6,164

February 18, 2014 02:58 AM

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.

Ashaman73

13,718

February 21, 2014 08: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).

Ashaman

Gnoblins: Website - Facebook - Twitter - Youtube - Steam Greenlit - IndieDB - Gamedev Log

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

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

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

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines