nicolasgramlich/AndEngine — pull request #142 by winniehell (2012-07-13 14:51:51+00:00)
Title: Floyd-Warshall-algorithm

This is the implementation of an alternative shortest path algorithm. It is feasible for tiled maps which do not change frequently (i.e. number of columns and rows, step cost and blocked tiles remain the same).

The main differences to the already present A* algorithm are:
* can handle negative step cost
* can detect negative cycles (though it can not handle them)
* needs preprocessing time of O(n³) (A* has no preprocessing)
* needs O(n²) space (A* needs O(n))
* needs O(n) time for finding a shortest path (A* needs O(n²))

(n is the number of tiles in the map)

The algorithm is not tested yet, but I thought that you may already have suggestions.