[Sulk-devel] path finding algorithm

[Robert M. W. <ro...@wa...>]

Hello,

I posted a new bug describing in brief a solution to the slowness of the 
path finding algorithm.

However I think that the path finding algorithm can be greatly improved 
by implementing an A* path finding algorithm.

Basically, the A* path finding algorithm uses a heuristic function to 
determine the minimal cost for reaching the desired destination via a 
next step.  The lowest cost of all available next steps is expanded 
until the solution is found.  This has been proven to be an optimal 
pathfinding algorithm.

The problem comes in picking a good heuristic function for estimating 
the cost for reaching the destination.  Generally it is easiest to pick 
a heuristic function which will always underestimate the cost.  One such 
simple method for doing this is taking the cost thus far and adding it 
to the Manhattan distance from the path-step under consideration. 
Because the minimum distance to arrive at a destination on a grid is a 
set of two perpendicular lines, this works well as a constant time 
heuristic function.

The nice thing about this, though, is that you can throw in additional 
heuristics. In this case it would make sense to add in the AP path cost 
for making the next step.  It would be good if the path finding function 
would take a player object as an agrument, and the player object have a 
method that would return the path cost for particular types of paths 
(which would allow for player objects to vary the path cost for 
different terrain types between player objects and/or states).

The added benefit to doing this would be removing the need to compute a 
list of all possible shortest routes and then applying the heuristics 
afterwards.  This method would then return a single shortest path in a 
close to optimal amount of time.

So, the basic algorithm would work like this (in a rough pseudocode):

determineShortestPath(Square origin, Square destination, Player player):
	squaresToReset = []
	queue = minimumPriorityQueue(origin)
	while queue not empty:
		currentSquare = queue.dequeueMinimum()
		for neighbor in currentSquare.neighbors():
			neighbor.setPrior(currentSquare)
			pathCost = currentSquare.getPathCost() +\
				player.moveCost(neighbor) +\
				distance(neighbor, destination)
			neighbor.setPathCost(pathCost)
			squaresToReset.append(neighbor)
	shortestPath = []
	backtrackSquare = destination
	while backtrackSquare not None:
		shortestPath.prepend(backtrackSquare)
		backtrackSquare = backtrackSquare.getPrior()
	reset(squaresToReset)
	return shortestPath

A few notes:
In the absolute worst case this algorithm will perform as bad as a 
breadth first search, which is what we have now.  Reseting of the 
squares visited adds a minor amount of cost (basically clearing out the 
pathcost attribute and the prior attribute).  This can be avoided by 
making copies or representations of the map that are discarded with each 
use.  It depends on if you mind polluting the Square object with path 
finding attributes.

Anyway, let me know what you guys think.  With a tweak in the path 
finding algorithm it runs much faster and is actually playable with the AI.

robert