自分ならこう書く - pythonでA*

(更新してます: pythonでA*のコードを修正しました - ラシウラ)

ホッテントリで見かけた PythonでA*(A-Star)アルゴリズム - Pashango’s Blog がpythonらしくなかったので、python的に書き直してみました。

A*アルゴリズムは特定の実装に依存しない汎用的な関数にし、priority queue実装として標準モジュールのheapqを使っています。

def astar(init, goal, nexts,
          distance=lambda path: len(path),
          heuristic=lambda pos: 0):
    import heapq
    queue = []
    checked = [init]
    heapq.heappush(queue, (distance([init]) + heuristic(init), [init]))
    while len(queue) > 0:
        score, path = heapq.heappop(queue)
        last = path[-1]
        if last == goal: return path
        for pos in nexts(last):
            if pos in checked: continue
            checked.append(pos)
            newpath = path + [pos]
            heapq.heappush(queue,
                           (distance(newpath) + heuristic(pos), newpath))
            pass
        pass
    return None

全体

位置はclassのかわりにtupleを使い、位置に間する各機能はdungeonを束縛してるクロージャにしてます。これをclassで作り、機能をmethodで実装してみるのもいいでしょう。