Is there a better path finding algorithm than A * when you have multiple sources and multiple destinations?

Question

We have a school project in which we have an 8x8 game board with pieces on it. The goal is to get any shape onto any square of the opposite back row. Parts can only move forward, but in any direction forward (forward-left, forward or forward-right).

We were able to present the board as an oriented acyclic graph, and with different rules of the game, we were also able to set the weight on each edge. In short, we are on the path, with every detail as possible origin, to any of the squares in the back rows to find the path of least resistance from any part to the end. In addition, most resistances will be found near the finish line.

However, our program spends a lot of time on this. We believe that this is due to the fact that many paths are very similar in weight, especially considering that any possible step will lead to victory (since this is only possible to move forward, and all the back squares of the lines are the destination). There are no obstacles on this board, only the edges are heavier, so this leaves us with a lot of open knots that “look good”.

Our heuristic function is very simple:

movement_cost = # movement cost here # def heuristic(node): return node.cost + node.distanceToFinish * movement_cost 

Where node.cost is the sum of the weights of the edges traveled, plus movement_cost is multiplied by the number of edges traveled.

Is there an algorithm that will be more efficient than A * to handle cases where you have multiple sources and multiple destinations? The board will never be more than 8x8, so fasting algorithms are probably welcome.

EDIT We were thinking about how to find the way from the finish to the parts, but this adds considerable complexity to the heuristic function, since now we need to track each part, and not just keep track of how far from the last line.

Answer 1

As it turns out, the size of the problem makes the brute force approach the most effective, i.e. computes the shortest path to each node from each source, moving the entire grid faster than using A *. This is probably due to the fact that we do not have any overhead associated with PriorityQueue , and the comparison can be simplified.

This would probably be nice for larger sizes, as it is O (n ² ) with a grid width.

Answer 2

Unless you have a specific suboptimization of the problem, A * is completely suitable for your purposes. However, you can improve this solution by memoizing the paths shared between parts, allowing you to calculate the cost of each path to the goal at least a number of times.

Answer 3

The Dijkstra algorithm is a path search algorithm that finds the least cost path from a given node to all other nodes in the graph. You can take a look at this and see if it is more efficient for your use.