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?

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

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...");
		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?

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.

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.

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)

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.