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?