Shortest meeting point of two paths

Question

Explanation :

In the example picture above there is a green circle following an arbitrary path.

I want the red circle to meet the green circle in the minimum steps possible as demonstrated in the picture.

The circles can move to any of the 8 adjacent cells in one step and black cells can’t be traversed.

The paths are represented as a list of coordinates. In this case, the green path is [(0,3),(0,2),(0,1)...(5,0)].

To find the shortest meeting point I can iterate though each coordinate in the green path list and use the A* algorithm to find the shortest path from the red circle to that coordinate. If the length of the path returned is equal to the number of steps it takes the green circle to get to that coordinate, then the shortest meeting point path is found.

This is of course, a brute force approach and the java code looks something like this:

List<Coord> minMeetingPointPath(Coord redLoc, List<Coord> greenPath) {
    for (int step = 0; step < greenPath.size(); step++) {
        Coord greenLoc = greenPath.get(step);
        List<Coord> redPath = shortestPathAStar(redLoc, greenLoc);
        if (redPath.size() == step)
            return redPath;
    }
    return null;
}

Question

So my question is:

1. Is there a more efficient way to solve this problem without using a brute force approach?

Answer 1

I have 2 ways you could make it more efficient

1) start with the goal. start with the green ball. Find (and keep track of) the shortest path from the green position to the red node position. This on it's own will not reduce the search but if you limit the depth of the search to the move number (ie move 0 search to depth of 0 move 1 search to a depth of 1 ... move n search to a depth of n) it will reduce the time you spend searching since you will only be searching to the relevant depth, anything past that point is of no value and does not need to be checked.

2) Don't search at all if you don't need to. Give your search a seance of depth, you already have each node with an x,y positions of the start and finish so before you do your A* search check the move number and the straight line distance For example: the shortest distance between 0,5 (green current position) and 0,0 (red start position) is 5 so if the green object is on move is move 4 or less you know there is no way to get there even if there is nothing blocking the way. however if it is move 5 or more you know there might a way to get to that location in time so it is worth searching to see how long the path actually takes.