This is an A* implementation I wrote in 2007.
It's highly customizable: You provide it with a class of methods to define your map/graph.
You can get away with implementing just four functions:
* neighbors( node ) -> iterable of nodes who neighbor given node.
* cost_to_target( node ) -> int : an estimation of cost to target.
* movement_cost( node_a, node_b ) -> int : assume adjacency.
* is_target( node ) -> bool
You can implement more functions for better control and more experimental search methods.
Unlike most implementations, you can call each step individually, so providing progress-bars or running several searches simultaniously is simple.
Quirks
Result is returned in the last call to step().
To avoid using step(), call loop_and_return().
Result is a list, in which the target is the first element and the last element is adjacent to the start node. The start node is omitted. You may want to reverse the list and/or add the start node for a "logical" display.
Requires
pqueue (automatically imports through snippets)
Example Usage
astar = snippets.get('astar') class SearchDictGraph(astar.NodeMapInterface): def __init__(self, d, target): self.d = d self.target = target astar.NodeMapInterface.__init__(self) def neighbors(self, node): return self.d[node] def cost_to_target(self, node): return 1 # always close. this will cause a BFS behaviour def movement_cost(self, a, b): return 1 # all movements are the same cost def is_target(self, node): return node==self.target >>> d = {1: [2,3], 2: [4,5], 3:[6], 4:[2], 5:[1,3,4], 6:[]} >>> >>> sdg = SearchDictGraph(d, 6) >>> astar.AStar(sdg, 4).loop_and_return()[::-1] [2, 5, 3, 6]
$$latest_version=0.1$$