CODEWITHSUNDEEP
javagraphpath-finding
zneak
zneak

Reputation: 138031

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

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

We were able to represent the board as a directed acyclic graph, and with the various rules of the game we were also able to set a weight on every edge. In short, we are pathfinding, with every piece as possible origin, to any of the back row squares, in order to find the path of least resistance from any piece to finish. Besides, most resistance will be met near the finish line.

However, our program spends a lot of time doing just that. We believe this is because a lot of paths are extremely similar in weight, especially given that any possible step will lead towards victory (since it's only possible to move forward and all back row squares are destinations). There are no obstacles on this board, just edges that weight heavier, so this leaves us with a lot of open nodes that all '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 traversed edges, plus movement_cost times the number of traversed edges.

Is there an algorithm that will be more efficient than A* to handle cases where you have multiple origins and multiple destinations? The board is never going to be bigger than 8x8 either, so space-hungry algorithms are probably welcome, too.

EDIT We thought about pathfinding from finish to the pieces, but this adds a good deal of complexity to the heuristic function, since we now have to keep track of every piece rather than just track of how far we are from the last line.

Upvotes: 4

Views: 4565

Answers (3)

zneak
zneak

Reputation: 138031

As it turns out, the size of the problem makes it so the "brute force" approach is the most efficient–that is, computing the shortest path to every node from every source by traversing the whole grid is faster than employing A*. This is likely because we don't have any of the overhead incurred by the PriorityQueue and comparisons can be made simpler.

This probably wouldn't be a good idea for larger sizes though, since this is O(n2) with the width of the grid.

Upvotes: 2

MrGomez
MrGomez

Reputation: 23886

Unless you have a specific suboptimization of the problem in mind, A* is entirely appropriate for your purposes. However, you can improve this solution through memoization of paths shared amongst pieces, allowing you to calculate the cost of each path to the target a minimum number of times.

Upvotes: 2

RMorrisey
RMorrisey

Reputation: 7739

Dijkstra's algorithm is a pathfinding algorithm that finds the least-cost path from a given node to every other node in the graph. You may want to take a look at this, and see if it's more efficient for your use case.

Upvotes: -1

Related Questions