Python版的A*寻路算法

Python版的A*寻路算法,实现了基本的A*算法，可以显示寻路图

“““{-
Copyright （c） 2009 Pauli Henrikki Rikula 

Permission is hereby granted free of charge to any person
obtaining a copy of this software and associated documentation
files （the “Software“） to deal in the Software without
restriction including without limitation the rights to use
copy modify merge publish distribute sublicense and/or sell
copies of the Software and to permit persons to whom the
Software is furnished to do so subject to the following
conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS“ WITHOUT WARRANTY OF ANY KIND
EXPRESS OR IMPLIED INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM DAMAGES OR OTHER LIABILITY
WHETHER IN AN ACTION OF CONTRACT TORT OR OTHERWISE ARISING
FROM OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
-}“““


import heapq

class NotImplemented（Exception）:
    pass


class Map:
    def __init__（self）:
        pass
    def heuristic_estimate_of_distance（self startgoal）:
        raise NotImplemented
    def neighbor_nodes（self x）:
        raise NotImplemented

    def dist_between（self x y）:
        raise NotImplemented

def reconstruct_path（came_from current_node）:
    if current_node in came_from:
        p = reconstruct_path（came_fromcame_from[current_node]）
        return p + [current_node]
    else:
        return []


class HeapItem:
    def __init__（selfygoal a_map）:
            
        self.node = y
        “““f_score Estimated total distance from start to goal through y.“““
        self.f_score = None
        “““ g_score = Distance from start along optimal path.“““
        self.g_score = None

        “““h_score the heuristic estimates of the distances to goal“““
        self.h_score = a_map.heuristic_estimate_of_distance（y goal）

    def set_scores（selfg_score）:
        self.g_score = g_score
        self.f_score = self.h_score + self.g_score

    def as_list（self）:
        return [self.f_score self.g_score self.h_score self.node]


    def __repr__（self）:
        return str（self.as_list（））

    def type_check（selfother）:
        return type（self） == type（other）
    def __lt__（self other）:
        return self.type_check（other） and self.as_list（）.__lt__（other.as_list（））
    def __le__（self other）:
        return self.type_check（other） and self.as_list（）.__le__（other.as_list（））
    def __eq__（self other）:
        return self.type_check（other） and self.as_list（）.__eq__（other.as_list（））
    def __ne__（self other）:
        return self.type_check（other） and self.as_list（）.__ne__（other.as_list（））
    def __gt__（self other）:
        return self.type_check（other） and self.as_list（）.__gt__（other.as_list（））
    def __ge__（self other）:
        return self.type_check（other） a

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2218  2009-02-18 00:42  pathFinder.py

     文件        254  2009-02-18 00:43  a_map.txt

     文件       5063  2009-02-18 00:42  a_star.py

----------- ---------  ---------- -----  ----

                 7535                    3