AStar - an A* implementation

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$$

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License