Python で aster: http://d.hatena.ne.jp/pashango_p/20090713/1247455609 より

aster.py

import heapq
    
def astar(start, goal, nexts,
          distance=len,
          heuristic=lambda pos: 0):
    hpush = heapq.heappush
    hpop = heapq.heappop
    queue = []
    checked = set([start])
    hpush(queue, (distance([start]) + heuristic(start), [start]))
    while queue:
        score, path = hpop(queue)
        last = path[-1]
        if last == goal:
            return path
        for pos in nexts(last):
            if pos in checked:
                continue
            checked.add(pos)
            newpath = path + [pos]
            hpush(queue, (distance(newpath) + heuristic(pos), newpath))

if __name__ == "__main__":
    dungeon = [
        'OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO',
        'OS  O     O     O         O          O',
        'O   O  O  O  O  O         O    OOOO GO',
        'O      O     O  O   OOOO  O    O  OOOO',
        'OO OOOOOOOOOOOOOOO  O     O    O     O',
        'O                O  O     O          O',
        'O        OOO     O  O     OOOOOOOOO  O',
        'O  OO    O    OOOO  O     O      OO  O',
        'O   O    O          O     O  O   O   O',
        'O   OOO  O          O        O   O   O',
        'O        O          O        O       O',
        'OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO',
        ]

    def find_ch(ch):
        for i, l in enumerate(dungeon):
            j = l.find(ch)
            if j >= 0:
                return (i, j)
        raise ValueError

    start = find_ch("S")
    goal = find_ch("G")

    def nexts(pos):
        wall = "O"
        if dungeon[pos[0] - 1][pos[1]] != wall: yield (pos[0] - 1, pos[1])
        if dungeon[pos[0] + 1][pos[1]] != wall: yield (pos[0] + 1, pos[1])
        if dungeon[pos[0]][pos[1] - 1] != wall: yield (pos[0], pos[1] - 1)
        if dungeon[pos[0]][pos[1] + 1] != wall: yield (pos[0], pos[1] + 1)

    def heuristic(pos):
        return ((pos[0] - goal[0]) ** 2 + (pos[1] - goal[1]) ** 2) ** 0.5

    def render_path(path):
        buf = [[ch for ch in l] for l in dungeon]
        for pos in path[1:-1]: buf[pos[0]][pos[1]] = "*"
        buf[path[0][0]][path[0][1]] = "s"
        buf[path[-1][0]][path[-1][1]] = "g"
        return ["".join(l) for l in buf]

    path = astar(start, goal, nexts, heuristic=heuristic)
    #path = astar(start, goal, nexts)
    print "\n".join(render_path(path))