A-Star算法探索和实现（五）

绝地灬酷狼 2024-03-27 10:44 47阅读 0赞

**提醒：A-Star算法探索和实现系列博文不具备参考价值，仅仅作为个人探索和尝试的记录！**

##### 本篇摘要 #####

在上一篇中我们对寻路的移动规则进行了制定，而在本篇我们将对最佳路径的查找方式进行优化，而这就会涉及到移动规则的检测改进、权值计算的改进、NextNode集的处理改进、寻路逻辑的改进，我们将从上述四个方面进行详细讲解。

##### 方案探讨 #####

**（一）移动规则的检测改进：可移动检测、可替换斜向移动检测、可替换二次非斜向移动检测、方向Node集检测。**

（1）可移动检测：检测当前Node的NextNode集中是否存在可以移动的下一步Node，这个基本的检测用于判断下一步是否可行。

（2）可替换斜向移动检测：检测是否存在一次斜向移动可替换两次非斜向移动的情况，如果存在，则进行替换，两次非斜向移动的权值高于一次斜向移动的权值，所以通过这个方式来优化最佳路径查找方式。

（3）可替换二次非斜向移动检测：检测是否存在二次斜向移动可替换为二次非斜向移动，如果存在，则进行替换，一次斜向移动的权值高于一次非斜向移动的权值，所以通过这个方式来优化最佳路径查找方式。

（4）方向Node集检测：检测当前Node的NextNode集中是否存在上一步Node至当前Node的方向Node集元素，如果存在则进行剔除，如下四图，CurNode（橙色圆）当前当前Node，NextNode（绿色圆）代表下一步Node，方向Node集为图中黄色方块，这就相似于A星算法中的OpenList，但是不同的是，OpenList是将上一步Node的NextNode集中所有元素进行添加，而方向Node集仅添加与前进方向相反方向的三个Node。

![a963799fc6dc44eda2b57217ffa49eb5.jpeg][]

![0038242034344b418229b80cf8856dc7.jpeg][]

![7ce30d5a9bee45b68cfcbdb8b63e4d0f.jpeg][]

![e28cb37e0b80419a972edfbf90b8b90a.jpeg][]

**（二）权值计算的改进：G和H值的计算改进**

（1）G值计算改进：

●1.设StartNode（v\_staX,v\_staY）,CurNode（v\_curX,v\_curY）

●2.计算：

●●2.1满足abs(v\_curX - v\_staX) != abs(v\_curY - v\_staY)

**v\_g=abs(v\_curX-v\_staX)\*nonDiagonalCost+abs(v\_curY-v\_staY)\*nonDiagonalCost**

●●2.2满足 abs(v\_curX - v\_staX) == abs(v\_curY -v\_staY)

**v\_g=abs(v\_curX-v\_staX)\*diagonalCost**

（2）H值计算改进

●1.设EndNode（v\_endX,v\_endY）,CurNode（v\_curX,v\_curY）,行数为rowsCount，列数为colsCount，则横坐标范围为\[0.5,(colsCount-1)+0.5\]，纵坐标范围为\[0.5,(rowsCount-1)+0.5\]，nonDiagonalCost为一次非斜向移动权值，diagonalCost为一次斜向移动权值，v\_minCount代表rowsCount和colsCount二者之间最小的一个，若rowsCount<colsCount则v\_minCount=rowsCount，否则v\_minCount=colsCount。

●2.计算：

●●2.1满足v\_curX == v\_endX

**v\_h=abs(v\_endX-v\_curX)\*nonDiagonalCost**

●●2.2满足v\_curY == v\_endY

**v\_h=abs(v\_endY-v\_curY)\*nonDiagonalCost**

●●2.3满足 abs(v\_curX - v\_endX) == abs(v\_curY -v\_endY)

**v\_h = abs(v\_curX - v\_endX)\*diagonalCost**

●●2.4满足 v\_curY > v\_endY

●●●2.4.1 令v\_x = v\_endX - i，v\_y = v\_endY + i，i为区间\[1,rowsCount-0.5-v\_endY\]内的整数

●●●●2.4.1.1满足 i <= v\_endX - 0.5

●●●●●2.4.1.1.1 满足abs(v\_curX - v\_x) == abs(v\_curY- v\_y)

●●●●●●2.4.1.1.1.1令v\_xA = v\_x - j，v\_yA = v\_y – j，j为区间\[1,v\_minCount - 1\]内的整数

●●●●●●●2.4.1.1.1.1.1满足v\_xA >= 0.5 and v\_yA >v\_endY

**v\_h = (j + i)\*diagonalCost**

●●●●●●2.4.1.1.1.2令v\_xB = v\_x + j，v\_yB = v\_y + j，j为区间\[1,v\_minCount - 1\]内的整数

●●●●●●●2.4.1.1.1.2.1满足v\_xB < v\_endX and v\_yB<= v\_rowsCount - 0.5

**v\_h = (j + i)\*diagonalCost**

●●●●●2.4.1.1.2满足v\_curY == v\_y

●●●●●●2.4.1.1.2.1满足v\_curX <= v\_x

**v\_h = abs(v\_x - v\_curX)\*nonDiagonalCost + i\*diagonalCost**

●●●●●●2.4.1.1.2.2满足v\_curX > v\_x

**v\_h = (abs(v\_endX - v\_curX) + abs(v\_curY - v\_endY))\*nonDiagonalCost**

●●●●●2.4.1.1.3满足v\_curX == v\_x

**v\_h = abs(v\_y - v\_curY)\*nonDiagonalCost + i\*diagonalCost**

●●●2.4.2 令v\_x = v\_endX + i，v\_y = v\_endY + i，i为区间\[1,rowsCount-0.5-v\_endY\]内的整数

●●●●2.4.2.1满足i <= v\_colsCount - 0.5 - v\_endX

●●●●●2.4.2.1.1满足abs(v\_curX - v\_x) == abs(v\_curY -v\_y)

●●●●●●2.4.2.1.1.1令v\_xA = v\_x + j，v\_yA = v\_y – j，j为区间\[1,v\_minCount - 1\]内的整数

●●●●●●●2.4.2.1.1.1.1满足v\_xA <= v\_colsCount - 0.5and v\_yA > v\_endY

**v\_h = (j + i)\*diagonalCost**

●●●●●●2.4.2.1.1.2令v\_xB = v\_x - j，v\_yB = v\_y + j，j为区间\[1,v\_minCount - 1\]内的整数

●●●●●●●2.4.2.1.1.2.1满足v\_xB > v\_endX and v\_yB<= v\_rowsCount - 0.5

**v\_h = (j + i)\*diagonalCost**

●●●●●2.4.2.1.2满足v\_curY == v\_y

●●●●●●2.4.2.1.2.1满足v\_curX >= v\_x

**v\_h=abs(v\_curX-v\_x)\*nonDiagonalCost+i\*diagonalCost**

●●●●●●2.4.2.1.2.2满足v\_curX < v\_x

**v\_h=(abs(v\_curX-v\_endX)+abs(v\_curY-v\_endY))\*nonDiagonalCost**

●●●●●2.4.2.1.3满足v\_curX == v\_x

**v\_h=abs(v\_y-v\_curY)\*nonDiagonalCost+i\*diagonalCost**

●●2.5满足v\_curY < v\_endY

●●●2.5.1令v\_x = v\_endX - i，v\_y = v\_endY – i，i为区间\[1,v\_endY-0.5\]内的整数

●●●●2.5.1.1满足i <= v\_endX - 0.5

●●●●●2.5.1.1.1满足abs(v\_curX - v\_x) == abs(v\_curY -v\_y)

●●●●●●2.5.1.1.1.1令v\_xA = v\_x + j，v\_yA = v\_y – j，j为区间\[1,v\_minCount - 1\]内的整数

●●●●●●●2.5.1.1.1.1.1满足v\_xA < v\_endX and v\_yA>= 0.5

**v\_h = (j + i)\*diagonalCost**

●●●●●●2.5.1.1.1.2令v\_xB = v\_x - j，v\_yB = v\_y + j，j为区间\[1,v\_minCount - 1\]内的整数

●●●●●●●2.5.1.1.1.2.1满足v\_xB >= 0.5 and v\_yB <v\_endY

**v\_h = (j + i)\*diagonalCost**

●●●●●2.5.1.1.2满足v\_curY == v\_y

●●●●●●2.5.1.1.2.1满足v\_curX <= v\_x

**v\_h=abs(v\_x-v\_curX)\*nonDiagonalCost+i\*diagonalCost**

●●●●●●2.5.1.1.2.2满足v\_curX > v\_x

**v\_h=(abs(v\_endX-v\_curX)+abs(v\_endY-v\_curY))\*nonDiagonalCost**

●●●●●2.5.1.1.3满足v\_curX == v\_x

**v\_h=abs(v\_y-v\_curY)\*nonDiagonalCost+i\*diagonalCost**

●●●2.5.2令v\_x = v\_endX + i，v\_y = v\_endY – i，i为区间\[1,v\_endY-0.5\]内的整数

●●●●2.5.2.1满足i <= v\_colsCount - 0.5 - v\_endX

●●●●●2.5.2.1.1满足abs(v\_curX - v\_x) == abs(v\_curY -v\_y)

●●●●●●2.5.2.1.1.1令v\_xA = v\_x - j，v\_yA = v\_y – j，j为区间\[1,v\_minCount - 1\]内的整数

●●●●●●●2.5.2.1.1.1.1满足v\_xA > v\_endX and v\_yA>= 0.5

**v\_h = (j + i)\*diagonalCost**

●●●●●●2.5.2.1.1.2令v\_xB = v\_x + j，v\_yB = v\_y + j，j为区间\[1,v\_minCount - 1\]内的整数

●●●●●●●2.5.2.1.1.2.1满足v\_xB <= v\_colsCount - 0.5and v\_yB < v\_endY

**v\_h = (j + i)\*diagonalCost**

●●●●●2.5.2.1.2满足v\_curY == v\_y

●●●●●●2.5.2.1.2.1满足v\_curX >= v\_x

**v\_h=abs(v\_curX-v\_x)\*nonDiagonalCost+i\*diagonalCost**

●●●●●●2.5.2.1.2.2满足v\_curX < v\_x

**v\_h=(abs(v\_curX-v\_endX)+abs(v\_endY-v\_curY))\*nonDiagonalCost**

●●●●●2.5.2.1.3满足v\_curX == v\_x

**v\_h=abs(v\_y-v\_curY)\*nonDiagonalCost+i\*diagonalCost**

●●2.6开始之前记得检测v\_x和v\_y是否超出有效范围，例如当终点Node位于网格最左边时，那么对于v\_x=v\_endX - i的情况均超出网格有效范围，则直接进行排除，需要检测的情况通常是终点Node处于网格边界上，反之则不需要有效范围检测。

**（三）NextNode集的处理改进：NextNode集生成、超出网格范围检测、特殊Node集元素包含检测、NextNode集权值计算、NextNode集排序**

（1）NextNode集生成：生成当前Node的下一步Node集

（2）超出网格范围检测：将生成的NextNode集中超出网格范围的Node进行剔除

（3）特殊Node集元素包含检测：将NextNode集中属于CloseList、BlockNode集、CheckedList的元素进行剔除

（4）NextNode集权值计算：对NextNode集中的Node进行权值计算

（5）NextNode集排序：对NextNode集中的Node按照权值小的在表头，从小到大进行排序

**（四）寻路逻辑的改进：**

（1）更新当前Node

（2）获取当前Node的NextNode集

（3）对NextNode集进行移动检测

（4）使用NextNode集

（5）重复（1）、（2）、（3）、（4）过程，直至到达终点，若出现无法到达终点的情况，则对最后一步Node进行上锁，上锁即代表到达终点前将无法使用该Node，然后重置相关参数，重新查找路径，直至找到一条可到达终点的路径。

##### 示例代码UML图 #####

![4c3e67c939fa4787a1361a21dc3cfe1e.jpeg][]

##### 效果截图 #####

![0f15b0a4f0824d5ea1db9b86e120bc70.jpeg][]

![b8c54b4058e34d48af1548c210228657.jpeg][]

![d7620feb9ae54ec184c41e9d1b243ac0.jpeg][]

##### 代码示例（Python） #####

Grid.py

import matplotlib.pyplot as pp
    import numpy as np
    from myCodes import SharedData as sd
    from myCodes import Node as node
    
    
    # 视图的构建和绘制
    class Grid:
        # 横纵坐标轴的刻度标记
        _xLabels = []
        _yLabels = []
        # 网格单元格的信息
        _data = None
        # 是否完成初始化
        _isInit = False
    
        def __init__(self, p_rowsCount, p_colsCount, p_sizes: tuple = ()):
            if self._isInit is False:
                # 网格的行列数
                if 3 <= p_rowsCount <= 7:
                    self._rowsCount = p_rowsCount
                elif p_rowsCount < 3:
                    self._rowsCount = 3
                else:
                    self._rowsCount = 7
                if 3 <= p_colsCount <= 7:
                    self._colsCount = p_colsCount
                elif p_colsCount < 3:
                    self._colsCount = 3
                else:
                    self._colsCount = 7
                # 将网格的行列数设置为共享信息
                sd.SharedData.rowsCount = self._rowsCount
                sd.SharedData.colsCount = self._colsCount
                # 将各类尺寸大小设置为共享信息
                v_sizes = p_sizes
                if len(p_sizes) == 0:
                    v_sizes = sd.SharedData.GetSizes(self._rowsCount, self._colsCount)
                for i in range(len(v_sizes)):
                    if i == 0:
                        sd.SharedData.startNodeSize = v_sizes[0]
                    elif i == 1:
                        sd.SharedData.endNodeSize = v_sizes[1]
                    elif i == 2:
                        sd.SharedData.blockNodeSize = v_sizes[2]
                    elif i == 3:
                        sd.SharedData.pathNodeSize = v_sizes[3]
                    elif i == 4:
                        sd.SharedData.arrowWidth = v_sizes[4]
                    elif i == 5:
                        sd.SharedData.fontSize = v_sizes[5]
                self._isInit = True
    
        def Draw(self):
            """
            绘制图形
            """
            pp.rcParams['font.sans-serif'] = ['SimHei']
            pp.title(sd.SharedData.blockInfo)
            # 获取坐标轴实例
            v_ax = pp.gca()
            self._AxisSet(v_ax)
            self._GridValueSet(v_ax)
            # 将数据以二维图片的形式进行显示
            v_ax.imshow(self._data, cmap='Accent', aspect='equal', vmin=0, vmax=255)
            # 标记起始点和终点
            self.Mark(sd.SharedNodes().GetStartNode(), sd.SharedData.startNodeSize, 'go')
            self._PathNodeSet()
            self.Mark(sd.SharedNodes().GetEndNode(), sd.SharedData.endNodeSize, 'ro')
            # 布置网格线
            pp.grid(visible=True, color='w')
            pp.tight_layout(pad=1)
            pp.show()
    
        # 标记所查找到的路径
        def _PathNodeSet(self):
            v_pathNodes = sd.SharedNodes().GetPathNodes()
            v_length = len(v_pathNodes)
            for i in range(v_length):
                if 0 < i < v_length - 1:
                    self.Mark(v_pathNodes[i], sd.SharedData.pathNodeSize, 'bo')
                    self._Arrow(v_pathNodes[i - 1], v_pathNodes[i])
                elif i == v_length - 1:
                    self._Arrow(v_pathNodes[i - 1], v_pathNodes[i])
    
        @classmethod
        def Mark(cls, p_node: node.Node, p_marksize: int, p_fmt: str):
            """
            用于在图象上标记Node
    
            :param p_node: 表示待标记的Node
            :param p_marksize: 表示标记的尺寸大小
            :param p_fmt: 表示标记颜色和图形的样式描述
            """
            v_x = p_node.nodePos.x
            v_y = p_node.nodePos.y
            pp.plot(v_x, v_y, p_fmt, markersize=p_marksize, zorder=1)
    
        # 箭头指向方法
        def _Arrow(self, p_firstNode, p_secondNode):
            v_dx = p_secondNode.nodePos.x - p_firstNode.nodePos.x
            v_dy = p_secondNode.nodePos.y - p_firstNode.nodePos.y
            pp.arrow(p_firstNode.nodePos.x, p_firstNode.nodePos.y, v_dx, v_dy, color='orange',
                     width=sd.SharedData.arrowWidth, head_width=0.08,
                     zorder=3)
    
        # 坐标轴设置
        def _AxisSet(self, p_ax):
            v_ax = p_ax
            for i in range(0, self._colsCount + 1):
                self._xLabels.append(str(i))
            for i in range(0, self._rowsCount + 1):
                self._yLabels.append(str(i))
            # 隐藏刻度线
            v_ax.tick_params(left=False, bottom=False, top=False, right=False)
            # 生成Image Data
            v_low = 1
            if self._rowsCount > self._colsCount:
                v_high = self._rowsCount
            else:
                v_high = self._colsCount
            self._data = np.random.randint(v_low, v_high, size=(self._rowsCount + 1, self._colsCount + 1))
            # # 设置横纵坐标轴的范围
            pp.xlim(0, self._colsCount)
            pp.ylim(0, self._rowsCount)
            # 设置坐标轴的刻度标记
            v_ax.set_xticks(np.arange(self._colsCount + 1), labels=self._xLabels, visible=False)
            v_ax.set_yticks(np.arange(self._rowsCount + 1), labels=self._yLabels, visible=False)
            # 设置坐标轴的横纵轴比例相等
            v_ax.set_aspect('equal')
    
        # 网格内容设置
        def _GridValueSet(self, p_ax):
            v_ax = p_ax
            for i in range(self._colsCount):
                for j in range(self._rowsCount):
                    v_str = '(' + str(i + 0.5) + ',' + str(j + 0.5) + ')'
                    v_ax.text(i + 0.5, j + 0.5, v_str, ha='center', va='center', color='w', fontsize=sd.SharedData.fontSize,
                              zorder=4)

Node.py

import random
    from enum import Enum, unique
    from myCodes import SharedData as sd
    import threading as th
    
    
    # Node坐标类
    class NodePosition:
        def __init__(self, p_x: float = 1, p_y: float = 1):
            """
            Node坐标信息初始化
    
            :param p_x: 横坐标值
            :param p_y: 纵坐标值
            """
            self.x = p_x
            self.y = p_y
    
        def __str__(self):
            return '[' + str(self.x) + ',' + str(self.y) + ']'
    
    
    # Node标签
    @unique
    class NodeTag(Enum):
        PATHNODE = 1
        BLOCKNODE = 2
    
    
    # Node类
    class Node:
        def __init__(self, p_nodeName: str, p_nodePos: NodePosition):
            """
            Node初始化
    
            :param p_nodeName: Node名称
            :param p_nodePos: Node的坐标信息
            """
            self.nodeName = p_nodeName
            self.nodePos = p_nodePos
            # f=g+h，g代表从上一个点到该点的代价和，h代表从该点到终点的代价和，f代表总权值weight
            self.f: int = 0
            self.g: int = 0
            self.h: int = 0
            # Node的标签，用于判断是否为不可到达的Node，
            self.nodeTag = NodeTag.PATHNODE
            # 前驱Node
            self.preNode = None
            # 后继Node
            self.nextNode = None
    
        def SetWeight(self, p_f: int, p_g: int, p_h: int):
            """
            设置Node的权值
    
            :param p_f: 代表总权值weight, f = g + h
            :param p_g: 代表从上一个点到该点的代价和
            :param p_h: 代表从该点到终点的代价和
            :return: 无返回值
            """
            self.f = p_f
            self.g = p_g
            self.h = p_h
    
        def __str__(self):
            return '{nodeName:' + self.nodeName + ',nodePos:' + str(
                self.nodePos) + ',f=' + str(
                self.f) + ',g=' + str(
                self.g) + ',h=' + str(self.h) + '}'
    
        def __eq__(self, other):
            if other is not None and self.nodePos.x == other.nodePos.x and self.nodePos.y == other.nodePos.y:
                return True
            return False
    
    
    # Node工厂，用来创建和获取起始点Node和终点Node
    class NodeFactory:
        _lock = th.Lock()
        _isCreateEndNode = False
        _isCreateStartNode = False
        _startNode: Node
        _endNode: Node
        # Node名称索引
        _nameIndex = 1
        # GenerateOneNode的Node索引
        _rowIndex = 1
        _colIndex = 1
        _generateCount = 0
    
        def __init__(self):
            if self._isCreateStartNode is False:
                self._CreateStartNode()
                sd.SharedNodes().SetStartNode(self._startNode, 'SNSET')
            if self._isCreateEndNode is False:
                self._CreateEndNode()
                sd.SharedNodes().SetEndNode(self._endNode, 'ENSET')
    
        def __new__(cls, *args, **kwargs):
            if hasattr(NodeFactory, '_instance') is False:
                with cls._lock:
                    if hasattr(NodeFactory, '_instance') is False:
                        NodeFactory._instance = object.__new__(cls)
            return NodeFactory._instance
    
        # 创建起始点Node
        def _CreateStartNode(self):
            v_nodePos = NodePosition(0.5, 0.5)
            self._startNode = Node('StartNode', v_nodePos)
            self._isCreateStartNode = True
    
        # 创建终点Node
        def _CreateEndNode(self):
            v_startNode = self._startNode
            v_node = v_startNode
            while v_node == v_startNode:
                v_node = self.GenerateOneNode('EndNode', p_isRandom=True)
            self._endNode = v_node
            self._isCreateEndNode = True
    
        def GenerateXYNodes(self, p_x=0, p_y=0, p_isRefX=True, p_isDefCheck=True):
            """
            生成横坐标或纵坐标为指定参考值的Node集
    
            :param p_x: 横坐标参考值
            :param p_y: 纵坐标参考值
            :param p_isRefX: 是否以横坐标为参考坐标，默认为True，若为False则以纵坐标为参考坐标
            :param p_isDefCheck: 是否开启默认检测，默认为True，会自动排除起始点Node和终点Node
            :return: 返回一个列表
            """
            v_list = []
            v_index = 1
            v_startNode = self._startNode
            v_endNode = self._endNode
            if p_isRefX:
                while True:
                    v_node = self.GenerateOneNode('Node' + str(v_index))
                    if v_node is None:
                        break
                    else:
                        v_j1 = True
                        if p_isDefCheck:
                            v_j1 = v_node != v_startNode and v_node != v_endNode
                        if v_j1 and v_node.nodePos.x == p_x:
                            v_list.append(v_node)
                            v_index += 1
            else:
                while True:
                    v_node = self.GenerateOneNode('Node' + str(v_index))
                    if v_node is None:
                        break
                    else:
                        v_j1 = True
                        if p_isDefCheck:
                            v_j1 = v_node != v_startNode and v_node != v_endNode
                        if v_j1 and v_node.nodePos.y == p_y:
                            v_list.append(v_node)
                            v_index += 1
            return v_list
    
        def GenerateNodes(self, p_count, p_isRandom=False):
            """
            生成指定数量的非重复Node集
    
            :param p_count: 生成的Node的数量
            :param p_isRandom: 是否随机生成，默认为False
            :return: 返回一个列表
            """
            v_list = []
            v_index = 1
            v_startNode = self._startNode
            v_endNode = self._endNode
            while len(v_list) < p_count:
                v_node = self.GenerateOneNode('Node' + str(v_index), p_isRandom=p_isRandom)
                if v_node is None:
                    break
                else:
                    v_isRepeat = NodeCheck.RepeatCheck(v_list, v_node)
                    if v_isRepeat is False and v_node != v_startNode and v_node != v_endNode:
                        v_list.append(v_node)
                        v_index += 1
            return v_list
    
        def GenerateOneNode(self, p_name: str, p_isRandom=False):
            """
            生成一个指定名称的Node
    
            :param p_name: 生成的Node的名称
            :param p_isRandom: 是否随机生成，默认为False，若为True则为非随机模式生成，将按照起始点从左至右&从下至上的顺序生成
            :return: 默认会返回Node，在非随机生成模式下，当该方法生成完当前网格的所有Node后会进行重置并返回None，请保持对该方法的返回值是否为None的判断，避免陷入死循环
            """
            v_rowsCount = sd.SharedData.rowsCount
            v_colsCount = sd.SharedData.colsCount
            v_x = 0.5
            v_y = 0.5
            if p_isRandom:
                v_i = random.randint(0, v_colsCount - 1)
                v_x = v_i + 0.5
                v_i = random.randint(0, v_rowsCount - 1)
                v_y = v_i + 0.5
            else:
                if self._colIndex < v_colsCount:
                    if self._rowIndex > v_rowsCount:
                        self._rowIndex -= v_rowsCount
                        self._colIndex += 1
                    v_x = (self._colIndex - 1) + 0.5
                    v_y = (self._rowIndex - 1) + 0.5
                    self._rowIndex += 1
                    self._generateCount += 1
                else:
                    if self._rowIndex <= v_rowsCount:
                        v_x = (self._colIndex - 1) + 0.5
                        v_y = (self._rowIndex - 1) + 0.5
                        self._rowIndex += 1
                        self._generateCount += 1
                    else:
                        self._rowIndex = 1
                        self._colIndex = 1
                if self._generateCount > v_rowsCount * v_colsCount:
                    self._generateCount = 0
                    return None
            v_nodePos = NodePosition(v_x, v_y)
            v_node = Node(p_name, v_nodePos)
            return v_node
    
        def GenerateNextNodes(self, p_node: Node):
            """
            获取某个Node下一步可以前往的Node集(NextNode集)
    
            :param p_node: 待生成NextNode集的Node
            :return: 默认返回一个列表，若p_node为None则返回空列表
            """
            v_list = []
            if p_node is not None:
                v_p = p_node.nodePos
                v_posList = [(v_p.x - 1, v_p.y), (v_p.x - 1, v_p.y + 1), (v_p.x, v_p.y + 1), (v_p.x + 1, v_p.y + 1),
                             (v_p.x + 1, v_p.y), (v_p.x + 1, v_p.y - 1), (v_p.x, v_p.y - 1), (v_p.x - 1, v_p.y - 1)]
                v_nameList = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
                for i in range(len(v_posList)):
                    v_nodeName = v_nameList[i] + str(self._nameIndex)
                    v_nodePos = NodePosition(v_posList[i][0], v_posList[i][1])
                    v_node = Node(v_nodeName, v_nodePos)
                    v_list.append(v_node)
                self._nameIndex += 1
            return v_list
    
    
    # Node或Node集的检测
    class NodeCheck:
        @classmethod
        def RepeatCheck(cls, p_list: list[Node], p_node: Node):
            """
            判断Node集中是否存在某个Node
    
            :param p_list: Node集
            :param p_node: 待检测的Node
            :return: 存在返回True，否则返回False
            """
            if p_list is not None and len(p_list) != 0:
                for n in p_list:
                    if n == p_node:
                        return True
            return False
    
        @classmethod
        def OutOfRange(cls, p_node: Node):
            """
            判断Node是否超出了网格限定范围
    
            :param p_node: 待检测的Node
            :return:若超出了范围则返回True，否则返回False
            """
            v_minX = 0.5
            v_minY = 0.5
            v_maxX = (sd.SharedData.colsCount - 1) + 0.5
            v_maxY = (sd.SharedData.rowsCount - 1) + 0.5
            v_x = p_node.nodePos.x
            v_y = p_node.nodePos.y
            if v_minX <= v_x <= v_maxX and v_minY <= v_y <= v_maxY:
                return False
            return True
    
        @classmethod
        def IsContainNodes(cls, p_listA: list[Node], p_listB: list[Node]):
            """
            判断某个Node集（p_listA）是否包含另一个Node集（p_listB）
    
            :param p_listA: 待检测的Node集
            :param p_listB: 被包含的Node集
            :return: 若p_listA包含p_listB则返回True，否则返回False，若p_listA为None也会返回False
            """
            if p_listA is not None and len(p_listA) != 0:
                if p_listB is None or len(p_listB) == 0:
                    return True
                else:
                    for n in p_listB:
                        if cls.RepeatCheck(p_listA, n) is False:
                            return False
                    return True
            return False
    
        @classmethod
        def IsContainBestNodes(cls, p_list: list[Node]):
            """
            检测NextNode集是否存在权值相等的最佳Node
    
            :param p_list: 待检测的NextNode集
            :return: 若NextNode集存在两个及以上的最佳Node，则返回True，否则返回False，若p_list为None或长度小于2，也返回False
            """
            if p_list is not None and len(p_list) >= 2:
                v_list = NodeDeal.SortNodes(p_list)
                v_curNode = v_list[0]
                v_neNode = v_list[1]
                if v_curNode.f == v_neNode.f:
                    return True
                return False
            return False
    
    
    # Node或Node集的处理
    class NodeDeal:
        # 对角线移动一格的代价
        _diagonalCost = 14
        # 上下或左右移动一格的代价
        _nonDiagonalCost = 10
    
        @classmethod
        def RemoveRepeatNode(cls, p_list: list[Node]):
            """
            移除Node集中的重复Node
    
            :param p_list: Node集
            :return: 若p_list为None则返回None，否则返回一个列表
            """
            if p_list is not None and len(p_list) != 0:
                v_list = []
                v_length = len(p_list)
                for i in range(v_length):
                    v_isRepeate = False
                    for j in range(i + 1, v_length):
                        if p_list[i] == p_list[j]:
                            v_isRepeate = True
                            break
                    if v_isRepeate is False:
                        v_list.append(p_list[i])
                return v_list
            return p_list
    
        @classmethod
        def RemoveNode(cls, p_sourceList: list[Node], p_node: Node):
            """
            移除Node集（p_sourceList）中的某个Node（p_node）
    
            :param p_sourceList: 待处理的Node集
            :param p_node: 参考Node
            :return: 返回一个列表
            """
            v_j1 = p_sourceList is not None and p_node is not None
            if v_j1 and len(p_sourceList) != 0:
                v_list = []
                for n in p_sourceList:
                    if n != p_node:
                        v_list.append(n)
                return v_list
            return p_sourceList
    
        @classmethod
        def RemoveNodes(cls, p_sourceList: list[Node], p_refList: list[Node]):
            """
            将一个Node集（p_sourceList）中另一个Node集（p_refList）的元素去除
    
            :param p_sourceList: 待处理的原Node集
            :param p_refList: 参考Node集
            :return: 默认返回一个列表，若p_sourceList或p_refList为None则返回原Node集
            """
            v_j1 = p_sourceList is not None and p_refList is not None
            if v_j1 and len(p_sourceList) != 0 and len(p_refList) != 0:
                v_list = []
                for n in p_sourceList:
                    if NodeCheck.RepeatCheck(p_refList, n) is False:
                        v_list.append(n)
                return v_list
            return p_sourceList
    
        @classmethod
        def RemoveOutOfRangeNode(cls, p_list: list[Node]):
            """
            移除Node集中超出网格范围的Node
    
            :param p_list: 待处理的Node集
            :return: 默认返回一个列表，如果p_list为None则返回None
            """
            if p_list is not None and len(p_list) != 0:
                v_list = []
                for n in p_list:
                    if NodeCheck.OutOfRange(n) is False:
                        v_list.append(n)
                return v_list
            return p_list
    
        @classmethod
        def ReplaceNode(cls, p_list: list[Node], p_node: Node):
            """
            替换Node集中与某个Node相同的Node
    
            :param p_list: Node集
            :param p_node: 用于替换的Node
            :return: 若p_list和p_node为None则返回None，否则返回一个列表
            """
            v_j1 = p_list is not None and p_node is not None
            if v_j1 and len(p_list) != 0:
                v_list = p_list
                if NodeCheck.RepeatCheck(v_list, p_node):
                    for i in range(len(v_list)):
                        if v_list[i] == p_node:
                            v_list[i] = p_node
                return v_list
            return p_list
    
        @classmethod
        def SetWeightValue(cls, p_diagonalCost: int = 14, p_nonDiagonalCost: int = 10):
            """
            设置diagonalCost（对角线移动权值）和nonDiagonalCost（非对角线移动权值）
    
            :param p_diagonalCost: 对角线移动权值，默认为14
            :param p_nonDiagonalCost: 非对角线移动权值，默认为10
            """
            if p_diagonalCost >= 0:
                cls.__diagonalCost = p_diagonalCost
            if p_nonDiagonalCost >= 0:
                cls.__nonDiagonalCost = p_nonDiagonalCost
    
        @classmethod
        def CalculateWeight(cls, p_list: list[Node], p_startNode: Node, p_endNode: Node):
            """
            计算Node集相对起始点和终点的权值
    
            :param p_list: 原Node集
            :param p_startNode: 起始点
            :param p_endNode: 终点
            :return: 默认返回一个列表，若p_list或p_startNode或p_endNode有一个为None则返回原Node集
            """
            v_j1 = p_list is not None and p_startNode is not None and p_endNode is not None
            if v_j1 and len(p_list) != 0:
                v_list = p_list
                for n in v_list:
                    v_g = cls.CalculateG(n, p_startNode)
                    v_h = cls.CalculateH(n, p_endNode)
                    v_f = v_g + v_h
                    if v_f < n.f or n.f == 0:
                        n.SetWeight(int(v_f), int(v_g), int(v_h))
                return v_list
            return p_list
    
        @classmethod
        def CalculateG(cls, p_curNode: Node, p_startNode: Node):
            """
            计算G值，即当前点Node至起始点Node的权值
    
            :param p_curNode: 当前点Node
            :param p_startNode: 起始点Node
            :return: 返回一个整数值
            """
            v_staX = p_startNode.nodePos.x
            v_staY = p_startNode.nodePos.y
            v_curX = p_curNode.nodePos.x
            v_curY = p_curNode.nodePos.y
            if abs(v_curX - v_staX) != abs(v_curY - v_staY):
                v_g = abs(v_curX - v_staX) * cls._nonDiagonalCost + abs(
                    v_curY - v_staY) * cls._nonDiagonalCost
            else:
                v_g = abs(v_curX - v_staX) * cls._diagonalCost
            return v_g
    
        @classmethod
        def CalculateH(cls, p_curNode: Node, p_endNode: Node):
            """
            计算H值，即当前点Node至终点Node的权值
    
            :param p_curNode: 当前点Node
            :param p_endNode: 终点Node
            :return: 返回一个整数值
            """
            v_endX = p_endNode.nodePos.x
            v_endY = p_endNode.nodePos.y
            v_colsCount = sd.SharedData.colsCount
            v_rowsCount = sd.SharedData.rowsCount
            v_curX = p_curNode.nodePos.x
            v_curY = p_curNode.nodePos.y
            v_minCount = v_colsCount if v_colsCount < v_rowsCount else v_rowsCount
            v_listH = []
            if v_curX == v_endX:
                v_h = abs(v_endY - v_curY) * cls._nonDiagonalCost
                v_listH.append(v_h)
            elif v_curY == v_endY:
                v_h = abs(v_endX - v_curX) * cls._nonDiagonalCost
                v_listH.append(v_h)
            elif abs(v_curX - v_endX) == abs(v_curY - v_endY):
                v_h = abs(v_curX - v_endX) * cls._diagonalCost
                v_listH.append(v_h)
            elif v_curY > v_endY:
                for i in range(1, int(v_rowsCount + 0.5 - v_endY)):
                    if i <= v_endX - 0.5:
                        v_x = v_endX - i
                        v_y = v_endY + i
                        if abs(v_curX - v_x) == abs(v_curY - v_y):
                            for j in range(1, v_minCount - 1):
                                v_xA = v_x - j
                                v_yA = v_y - j
                                if v_xA >= 0.5 and v_yA > v_endY:
                                    v_h = (j + i) * cls._diagonalCost
                                    v_listH.append(v_h)
                                    break
                                v_xB = v_x + j
                                v_yB = v_y + j
                                if v_xB < v_endX and v_yB <= v_rowsCount - 0.5:
                                    v_h = (j + i) * cls._diagonalCost
                                    v_listH.append(v_h)
                                    break
                    elif i <= v_colsCount - 0.5 - v_endX:
                        v_x = v_endX + i
                        v_y = v_endY + i
                        if abs(v_curX - v_x) == abs(v_curY - v_y):
                            for j in range(1, v_minCount - 1):
                                v_xA = v_x + j
                                v_yA = v_y - j
                                if v_xA <= v_colsCount - 0.5 and v_yA > v_endY:
                                    v_h = (j + i) * cls._diagonalCost
                                    v_listH.append(v_h)
                                    break
                                v_xB = v_x - j
                                v_yB = v_y + j
                                if v_xB > v_endX and v_yB <= v_rowsCount - 0.5:
                                    v_h = (j + i) * cls._diagonalCost
                                    v_listH.append(v_h)
                                    break
                for i in range(1, int(v_rowsCount + 0.5 - v_endY)):
                    if i <= v_endX - 0.5:
                        v_x = v_endX - i
                        v_y = v_endY + i
                        if v_curY == v_y:
                            if v_curX <= v_x:
                                v_h = abs(v_x - v_curX) * cls._nonDiagonalCost + i * cls._diagonalCost
                                v_listH.append(v_h)
                                break
                            else:
                                v_h = (abs(v_endX - v_curX) + abs(v_curY - v_endY)) * cls._nonDiagonalCost
                                v_listH.append(v_h)
                                break
                        elif v_curX == v_x:
                            v_h = abs(v_y - v_curY) * cls._nonDiagonalCost + i * cls._diagonalCost
                            v_listH.append(v_h)
                            break
                    elif i <= v_colsCount - 0.5 - v_endX:
                        v_x = v_endX + i
                        v_y = v_endY + i
                        if v_curY == v_y:
                            if v_curX >= v_x:
                                v_h = abs(v_curX - v_x) * cls._nonDiagonalCost + i * cls._diagonalCost
                                v_listH.append(v_h)
                                break
                            else:
                                v_h = (abs(v_curX - v_endX) + abs(v_curY - v_endY)) * cls._nonDiagonalCost
                                v_listH.append(v_h)
                                break
                        elif v_curX == v_x:
                            v_h = abs(v_y - v_curY) * cls._nonDiagonalCost + i * cls._diagonalCost
                            v_listH.append(v_h)
                            break
            elif v_curY < v_endY:
                for i in range(1, int(v_endY + 0.5)):
                    if i <= v_endX - 0.5:
                        v_x = v_endX - i
                        v_y = v_endY - i
                        if abs(v_curX - v_x) == abs(v_curY - v_y):
                            for j in range(1, v_minCount - 1):
                                v_xA = v_x + j
                                v_yA = v_y - j
                                if v_xA < v_endX and v_yA >= 0.5:
                                    v_h = (j + i) * cls._diagonalCost
                                    v_listH.append(v_h)
                                    break
                                v_xB = v_x - j
                                v_yB = v_y + j
                                if v_xB >= 0.5 and v_yB < v_endY:
                                    v_h = (j + i) * cls._diagonalCost
                                    v_listH.append(v_h)
                                    break
                    elif i <= v_colsCount - 0.5 - v_endX:
                        v_x = v_endX + i
                        v_y = v_endY - i
                        if abs(v_curX - v_x) == abs(v_curY - v_y):
                            for j in range(1, v_minCount - 1):
                                v_xA = v_x - j
                                v_yA = v_y - j
                                if v_xA > v_endX and v_yA >= 0.5:
                                    v_h = (j + i) * cls._diagonalCost
                                    v_listH.append(v_h)
                                    break
                                v_xB = v_x + j
                                v_yB = v_y + j
                                if v_xB <= v_colsCount - 0.5 and v_yB < v_endY:
                                    v_h = (j + i) * cls._diagonalCost
                                    v_listH.append(v_h)
                                    break
                for i in range(1, int(v_endY + 0.5)):
                    if i <= v_endX - 0.5:
                        v_x = v_endX - i
                        v_y = v_endY - i
                        if v_curY == v_y:
                            if v_curX <= v_x:
                                v_h = abs(v_x - v_curX) * cls._nonDiagonalCost + i * cls._diagonalCost
                                v_listH.append(v_h)
                                break
                            else:
                                v_h = (abs(v_endX - v_curX) + abs(v_endY - v_curY)) * cls._nonDiagonalCost
                                v_listH.append(v_h)
                                break
                        elif v_curX == v_x:
                            v_h = abs(v_y - v_curY) * cls._nonDiagonalCost + i * cls._diagonalCost
                            v_listH.append(v_h)
                            break
                    elif i <= v_colsCount - 0.5 - v_endX:
                        v_x = v_endX + i
                        v_y = v_endY - i
                        if v_curY == v_y:
                            if v_curX >= v_x:
                                v_h = abs(v_curX - v_x) * cls._nonDiagonalCost + i * cls._diagonalCost
                                v_listH.append(v_h)
                                break
                            else:
                                v_h = (abs(v_curX - v_endX) + abs(v_endY - v_curY)) * cls._nonDiagonalCost
                                v_listH.append(v_h)
                                break
                        elif v_curX == v_x:
                            v_h = abs(v_y - v_curY) * cls._nonDiagonalCost + i * cls._diagonalCost
                            v_listH.append(v_h)
                            break
            if len(v_listH) == 0:
                return 0
            else:
                return min(v_listH)
    
        @classmethod
        def SortNodes(cls, p_list: list[Node], p_endMax=True):
            """
            对Node集按照总权值（f）进行排序
    
            :param p_list: 原Node集
            :param p_endMax: 是否按照总权值从小到大排序，默认为True
            :return: 默认返回一个列表，若p_list为None则返回原Node集
            """
            v_list = p_list
            if v_list is not None and len(v_list) != 0:
                if p_endMax:
                    for i in range(0, len(v_list)):
                        for j in range(i + 1, len(v_list)):
                            if v_list[i].f > v_list[j].f:
                                v_node = v_list[i]
                                v_list[i] = v_list[j]
                                v_list[j] = v_node
                else:
                    for i in range(0, len(v_list)):
                        for j in range(i + 1, len(v_list)):
                            if v_list[i].f < v_list[j].f:
                                v_node = v_list[i]
                                v_list[i] = v_list[j]
                                v_list[j] = v_node
            return v_list
    
        @classmethod
        def PrintNodes(cls, p_list: list[Node], p_headStr='', p_sep='--'):
            """
            控制台打印Node集
    
            :param p_headStr: 头部字符串
            :param p_list: 待打印的Node集
            :param p_sep: 每个Node之间的间隔符号，默认为"--"
            """
            v_len = len(p_list)
            v_str = p_headStr
            if p_list is not None and v_len != 0:
                for i in range(v_len):
                    if i < v_len - 1:
                        v_str += str(p_list[i]) + p_sep
                    else:
                        v_str += str(p_list[i])
            print(v_str)

Block.py

from myCodes import Grid as grid
    from myCodes import Node as node
    from myCodes import SharedData as sd
    import threading as th
    from myCodes import SearchPath as sp
    
    
    # 用于生成阻碍物
    class Block:
        _lock = th.Lock()
        _blockCount = 0
        _unCheckedNodes = []
        _checkedNodes = []
        _isImpassable = False
        _generateNum = 0
    
        def __init__(self, p_blcokCount: int):
            """
            :param p_blcokCount: 生成的障碍物的数量
            """
            v_count = int((sd.SharedData.rowsCount * sd.SharedData.colsCount) / 2)
            if p_blcokCount <= v_count:
                self._blockCount = p_blcokCount
            else:
                self._blockCount = v_count
            self._endNode = sd.SharedNodes().GetEndNode()
    
        def __new__(cls, *args, **kwargs):
            if hasattr(Block, '_instance') is False:
                with cls._lock:
                    if hasattr(Block, '_instance') is False:
                        Block._instance = object.__new__(cls)
            return Block._instance
    
        def Create(self):
            """
            用于生成障碍物
            """
            if self._blockCount != 0:
                v_list = []
                v_curNode = sd.SharedNodes().GetStartNode()
                while self._StartImpasseCheck(v_list, v_curNode) is False:
                    v_list = self._SelectNode()
                    self._Reset()
                sd.SharedData.blockInfo = '生成BlockNode集次数:' + str(self._generateNum)
                v_list = self._GenerateBlock(v_list)
                sd.SharedNodes().Submit(v_list)
                self._MarkBlockNode(v_list)
    
        # 生成BlockNode集
        def _SelectNode(self):
            v_list = node.NodeFactory().GenerateNodes(self._blockCount, p_isRandom=True)
            return v_list
    
        # 对所生成的BlockNode集进行检测，若出现死胡同则重新生成BlockNode集
        def _StartImpasseCheck(self, p_list, p_curNode):
            v_isImpassable = self._isImpassable
            v_j1 = p_list is not None and p_curNode is not None and v_isImpassable is False
            v_nextNodes = self._GetNextNodes(p_curNode, p_list)
            if v_j1 and len(p_list) != 0 and len(v_nextNodes) != 0:
                if sp.NodeMove().NextNodesMoveCheck(p_list, v_nextNodes, p_curNode) is False:
                    return False
                v_nextNodes = sp.NodeMove().GetNextNodes(p_list, v_nextNodes, p_curNode)
                v_XNodes = self._GetXNodes(p_curNode.nodePos.x + 1, v_nextNodes)
                v_YNodes = self._GetYNodes(p_curNode.nodePos.y + 1, v_nextNodes)
                v_isContainX = node.NodeCheck.IsContainNodes(p_list, v_XNodes)
                v_isContainY = node.NodeCheck.IsContainNodes(p_list, v_YNodes)
                if v_isContainX and v_isContainY:
                    self._isImpassable = True
                    return False
                elif v_isContainX is False and v_isContainY is False:
                    if v_nextNodes[0] == self._endNode:
                        return True
                    else:
                        return self._StartImpasseCheck(p_list, v_nextNodes[0])
                else:
                    if v_isContainX:
                        v_nextNodes = node.NodeDeal.RemoveNodes(v_nextNodes, v_XNodes)
                    else:
                        v_nextNodes = node.NodeDeal.RemoveNodes(v_nextNodes, v_YNodes)
                    if v_nextNodes[0] == self._endNode:
                        return True
                    else:
                        return self._StartImpasseCheck(p_list, v_nextNodes[0])
            return False
    
        # BlockNode集检测重置
        def _Reset(self):
            self._isImpassable = False
            self._unCheckedNodes = []
            self._checkedNodes = []
            self._generateNum += 1
    
        # 获取处理后的NextNode集
        def _GetNextNodes(self, p_curNode, p_list):
            v_uclist = self._unCheckedNodes
            self._unCheckedNodes = node.NodeDeal.RemoveNode(v_uclist, p_curNode)
            self._checkedNodes.append(p_curNode)
            v_nextNodes = node.NodeFactory().GenerateNextNodes(p_curNode)
            v_nextNodes = node.NodeDeal.RemoveOutOfRangeNode(v_nextNodes)
            v_nextNodes = node.NodeDeal.RemoveNodes(v_nextNodes, self._unCheckedNodes)
            v_nextNodes = node.NodeDeal.RemoveNodes(v_nextNodes, self._checkedNodes)
            v_nextNodes = node.NodeDeal.RemoveNodes(v_nextNodes, p_list)
            v_nextNodes = node.NodeDeal.CalculateWeight(v_nextNodes, p_curNode, sd.SharedNodes().GetEndNode())
            v_nextNodes = node.NodeDeal.SortNodes(v_nextNodes)
            return v_nextNodes
    
        # 获取xNodes
        def _GetXNodes(self, p_x, p_list):
            v_list = []
            for n in p_list:
                v_x = n.nodePos.x
                if v_x == p_x:
                    v_list.append(n)
            return v_list
    
        # 获取yNodes
        def _GetYNodes(self, p_y, p_list):
            v_list = []
            for n in p_list:
                v_y = n.nodePos.y
                if v_y == p_y:
                    v_list.append(n)
            return v_list
    
        # 生成Block
        def _GenerateBlock(self, p_list):
            if p_list is not None and len(p_list) != 0:
                v_list = p_list
                for n in v_list:
                    n.nodeTag = node.NodeTag.BLOCKNODE
                return v_list
            return p_list
    
        # 标记生成Block的Node
        def _MarkBlockNode(self, p_list):
            if p_list is not None and len(p_list) != 0:
                for n in p_list:
                    grid.Grid.Mark(n, sd.SharedData.blockNodeSize, 'ks')

SearchPath.py

from myCodes import SharedData as sd
    from myCodes import Node as node
    import threading as th
    from enum import Enum, unique
    
    
    @unique
    class Direction(Enum):
        LeftUp = 1
        RightUp = 2
        LeftDown = 3
        RightDown = 4
        Left = 5
        Right = 6
        Up = 7
        Down = 8
        NoDirection = 9
    
    
    # Node移动规则类
    class NodeMove:
        _lock = th.Lock()
        _init = False
    
        def __init__(self):
            if self._init is False:
                self._nextNodes = []
                self._init = True
                self._diagonalMoveNode = None
                self._nonDiagonalMoveNode = None
                self._doubleNonDiagonalMoveNode = None
                self._endNode = sd.SharedNodes().GetEndNode()
    
        def __new__(cls, *args, **kwargs):
            if hasattr(NodeMove, '_instance') is False:
                with cls._lock:
                    if hasattr(NodeMove, '_instance') is False:
                        NodeMove._instance = object.__new__(cls)
            return NodeMove._instance
    
        def GetNextNodes(self, p_blockNodes: list[node.Node], p_nextNodes: list[node.Node], p_curNode: node.Node):
            """
            获取经过移动检测的NextNode集
    
            :param p_blockNodes: 障碍物Node集
            :param p_nextNodes: 当前Node的NextNode集
            :param p_curNode: 当前Node
            :return: 返回经过移动检测的NextNode集
            """
            v_list = []
            if self.NextNodesMoveCheck(p_blockNodes, p_nextNodes, p_curNode):
                for n in self._nextNodes:
                    v_list.append(n)
            return v_list
    
        def GetMoveDirection(self, p_curNode: node.Node, p_nextNode: node.Node):
            """
            获取当前Node至下一个Node的移动方向
    
            :param p_curNode: 当前Node
            :param p_nextNode: 下一个Node
            :return: 返回一个Direction枚举值，若p_curNode或p_nextNode为None，则返回Direction中的NoDirection
            """
            v_j1 = p_curNode is not None and p_nextNode is not None
            if v_j1:
                v_curX = p_curNode.nodePos.x
                v_curY = p_curNode.nodePos.y
                v_neX = p_nextNode.nodePos.x
                v_neY = p_nextNode.nodePos.y
                v_X = v_neX - v_curX
                v_Y = v_neY - v_curY
                if v_X < 0 and v_Y == 0:
                    return Direction.Left
                elif v_X < 0 < v_Y:
                    return Direction.LeftUp
                elif v_X == 0 and v_Y > 0:
                    return Direction.Up
                elif v_X > 0 and v_Y > 0:
                    return Direction.RightUp
                elif v_X > 0 and v_Y == 0:
                    return Direction.Right
                elif v_X > 0 > v_Y:
                    return Direction.RightDown
                elif v_X == 0 and v_Y < 0:
                    return Direction.Down
                else:
                    return Direction.LeftDown
            return Direction.NoDirection
    
        def NextNodeMoveCheck(self, p_blockNodes: list[node.Node], p_nextNode: node.Node, p_curNode: node.Node):
            """
            检测当前Node至下一步Node是否可以移动
    
            :param p_blockNodes: 障碍物Node集
            :param p_nextNode: 下一步Node
            :param p_curNode: 当前Node
            :return: 若可移动则返回True，否则返回False
            """
            v_j1 = p_nextNode is not None and p_curNode is not None
            if v_j1:
                v_curX = p_curNode.nodePos.x
                v_curY = p_curNode.nodePos.y
                v_direction = self.GetMoveDirection(p_curNode, p_nextNode)
                if v_direction == Direction.LeftUp:
                    v_x1 = v_curX - 1
                    v_y1 = v_curY
                    v_x2 = v_curX
                    v_y2 = v_curY + 1
                elif v_direction == Direction.RightUp:
                    v_x1 = v_curX + 1
                    v_y1 = v_curY
                    v_x2 = v_curX
                    v_y2 = v_curY + 1
                elif v_direction == Direction.RightDown:
                    v_x1 = v_curX + 1
                    v_y1 = v_curY
                    v_x2 = v_curX
                    v_y2 = v_curY - 1
                elif v_direction == Direction.LeftDown:
                    v_x1 = v_curX - 1
                    v_y1 = v_curY
                    v_x2 = v_curX
                    v_y2 = v_curY - 1
                elif v_direction == Direction.NoDirection:
                    return False
                else:
                    return True
                v_nodeA = node.Node('nodeA', node.NodePosition(v_x1, v_y1))
                v_nodeB = node.Node('nodeB', node.NodePosition(v_x2, v_y2))
                v_isContainA = node.NodeCheck.RepeatCheck(p_blockNodes, v_nodeA)
                v_isContainB = node.NodeCheck.RepeatCheck(p_blockNodes, v_nodeB)
                if v_isContainA or v_isContainB:
                    return False
                else:
                    return True
            return False
    
        def NextNodesMoveCheck(self, p_blockNodes: list[node.Node], p_nextNodes: list[node.Node], p_curNode: node.Node):
            """
            对当前Node的NextNode集进行可移动检测
    
            :param p_blockNodes: 障碍物Node集
            :param p_nextNodes: 当前Node的NextNode集
            :param p_curNode: 当前Node
            :return: 默认返回True，若NextNode集中不存在下一步可移动的Node则返回False，若p_nextNodes为None或为空集也返回False，若p_curNode为None返回False
            """
            if p_nextNodes is None or len(p_nextNodes) == 0 or p_curNode is None:
                return False
            else:
                v_list = []
                for n in p_nextNodes:
                    if self.NextNodeMoveCheck(p_blockNodes, n, p_curNode):
                        v_list.append(n)
                self._nextNodes = v_list
                if len(v_list) == 0:
                    return False
                else:
                    return True
    
        # 对NextNode集进行可替换斜向移动检测
        def _DiagonalMoveCheck(self, p_curNode: node.Node, p_nextNodes: list[node.Node], p_neNextNodes: list[node.Node]):
            v_nextNode = p_nextNodes[0]
            v_neNextNode = p_neNextNodes[0]
            v_blockList = sd.SharedNodes().GetBlockNodes()
            v_nextDirection = self.GetMoveDirection(p_curNode, v_nextNode)
            v_neNextDirection = self.GetMoveDirection(v_nextNode, v_neNextNode)
            v_curDirection = self.GetMoveDirection(p_curNode, v_neNextNode)
            v_j1 = v_nextDirection == Direction.Left or v_nextDirection == Direction.Right
            v_j2 = v_nextDirection == Direction.Up or v_nextDirection == Direction.Down
            v_j3 = v_neNextDirection == Direction.Left or v_neNextDirection == Direction.Right
            v_j4 = v_neNextDirection == Direction.Up or v_neNextDirection == Direction.Down
            v_j5 = v_curDirection == Direction.LeftUp or v_curDirection == Direction.LeftDown
            v_j6 = v_curDirection == Direction.RightUp or v_curDirection == Direction.RightDown
            v_j7 = self.NextNodeMoveCheck(v_blockList, v_neNextNode, p_curNode)
            v_j8 = node.NodeCheck.RepeatCheck(p_nextNodes, v_neNextNode)
            v_j9 = self.NextNodeMoveCheck(v_blockList, v_nextNode, p_curNode)
            if (v_j1 or v_j2) and (v_j3 or v_j4) and (v_j5 or v_j6) and v_j7 and v_j8 and v_j9:
                self._diagonalMoveNode = v_neNextNode
                if node.NodeCheck.RepeatCheck(p_nextNodes, self._endNode):
                    self._diagonalMoveNode = self._endNode
            else:
                self._diagonalMoveNode = None
    
        def GetDiagonalMoveNode(self, p_curNode: node.Node, p_nextNodes: list[node.Node]):
            """
            获取经过可替换斜向移动检测的目标Node
    
            :param p_curNode: 当前Node
            :param p_nextNodes: 当前Node的NextNode集
            :return: 若一次斜向移动可替换两次非斜向移动，则返回斜向移动的目标Node，否则返回None
            """
            v_nextNodes = p_nextNodes
            v_j1 = p_curNode is not None and v_nextNodes is not None
            if v_j1 and len(v_nextNodes) != 0:
                v_neNextNodes = SearchPath().GetNextNodes(v_nextNodes[0])
                v_j3 = v_neNextNodes is not None
                if v_j3 and len(v_neNextNodes) != 0:
                    self._DiagonalMoveCheck(p_curNode, v_nextNodes, v_neNextNodes)
                    return self._diagonalMoveNode
            return None
    
        # 二次可替换非斜向移动检测
        def _DoubleNonDiagonalMoveCheck(self, p_curNode: node.Node, p_nextNodes: list[node.Node],
                                        p_neNextNodes: list[node.Node]):
            v_nextNode = p_nextNodes[0]
            v_neNextNode = p_neNextNodes[0]
            v_blockList = sd.SharedNodes().GetBlockNodes()
            v_nextDirection = self.GetMoveDirection(p_curNode, v_nextNode)
            v_neNextDirection = self.GetMoveDirection(v_nextNode, v_neNextNode)
            v_curDirection = self.GetMoveDirection(p_curNode, v_neNextNode)
            v_j1 = v_nextDirection == Direction.LeftUp and v_neNextDirection == Direction.RightUp
            v_j2 = v_nextDirection == Direction.RightUp and v_neNextDirection == Direction.LeftUp
            v_j3 = v_nextDirection == Direction.LeftDown and v_neNextDirection == Direction.RightDown
            v_j4 = v_nextDirection == Direction.RightDown and v_neNextDirection == Direction.LeftDown
            v_j5 = v_nextDirection == Direction.LeftUp and v_neNextDirection == Direction.LeftDown
            v_j6 = v_nextDirection == Direction.RightUp and v_neNextDirection == Direction.RightDown
            v_j7 = v_nextDirection == Direction.LeftDown and v_neNextDirection == Direction.LeftUp
            v_j8 = v_nextDirection == Direction.RightDown and v_neNextDirection == Direction.RightUp
            v_j9 = v_curDirection == Direction.Left
            v_j10 = v_curDirection == Direction.Up
            v_j11 = v_curDirection == Direction.Right
            v_j12 = v_curDirection == Direction.Down
            v_k1 = (v_j5 or v_j7) and v_j9
            v_k2 = (v_j1 or v_j2) and v_j10
            v_k3 = (v_j6 or v_j8) and v_j11
            v_k4 = (v_j3 or v_j4) and v_j12
            v_x = p_curNode.nodePos.x
            v_y = p_curNode.nodePos.y
            v_nodePos = node.NodePosition(v_nextNode.nodePos.x, v_nextNode.nodePos.y)
            v_node = node.Node(v_nextNode.nodeName, v_nodePos)
            if v_k1:
                v_node.nodePos = node.NodePosition(v_x - 1, v_y)
            elif v_k2:
                v_node.nodePos = node.NodePosition(v_x, v_y + 1)
            elif v_k3:
                v_node.nodePos = node.NodePosition(v_x + 1, v_y)
            elif v_k4:
                v_node.nodePos = node.NodePosition(v_x, v_y - 1)
            v_j13 = self.NextNodeMoveCheck(v_blockList, v_neNextNode, p_curNode)
            v_j14 = self.NextNodeMoveCheck(v_blockList, v_node, p_curNode)
            if (v_k1 or v_k2 or v_k3 or v_k4) and v_j13 and v_j14:
                self._doubleNonDiagonalMoveNode = v_node
                if node.NodeCheck.RepeatCheck(p_nextNodes, self._endNode):
                    self._doubleNonDiagonalMoveNode = self._endNode
            else:
                self._doubleNonDiagonalMoveNode = None
    
        def GetDoubleNonDiagonalMoveNode(self, p_curNode: node.Node, p_nextNodes: list[node.Node]):
            """
            获取经过二次可替换非斜向移动检测的目标Node
    
            :param p_curNode: 当前Node
            :param p_nextNodes: 当前Node的NextNode集
            :return: 若二次斜向移动可替换为二次非斜向移动，则返回非斜向移动的目标Node，否则返回None
            """
            v_nextNodes = p_nextNodes
            v_j1 = p_curNode is not None and v_nextNodes is not None
            if v_j1 and len(v_nextNodes) != 0:
                v_neNextNodes = SearchPath().GetNextNodes(v_nextNodes[0])
                v_j3 = v_neNextNodes is not None
                if v_j3 and len(v_neNextNodes) != 0:
                    self._DoubleNonDiagonalMoveCheck(p_curNode, v_nextNodes, v_neNextNodes)
                    return self._doubleNonDiagonalMoveNode
            return None
    
        def GetDirectionNodes(self, p_curNode: node.Node):
            """
            获取上一个Node与当前Node的方向Node集
    
            :param p_curNode: 当前Node
            :return: 返回一个列表，即上一个Node与当前Node的方向Node集
            """
            if p_curNode is not None and p_curNode.preNode is not None:
                v_preNode = p_curNode.preNode
                v_direction = NodeMove().GetMoveDirection(p_curNode, v_preNode)
                v_curX = p_curNode.nodePos.x
                v_curY = p_curNode.nodePos.y
                v_list = []
                v_LNode = node.Node('LNode', node.NodePosition(v_curX - 1, v_curY))
                v_LUNode = node.Node('LUNode', node.NodePosition(v_curX - 1, v_curY + 1))
                v_UNode = node.Node('UNode', node.NodePosition(v_curX, v_curY + 1))
                v_RUNode = node.Node('RUNode', node.NodePosition(v_curX + 1, v_curY + 1))
                v_RNode = node.Node('RNode', node.NodePosition(v_curX + 1, v_curY))
                v_RDNode = node.Node('RDNode', node.NodePosition(v_curX + 1, v_curY - 1))
                v_DNode = node.Node('DNode', node.NodePosition(v_curX, v_curY - 1))
                v_LDNode = node.Node('LDNode', node.NodePosition(v_curX - 1, v_curY - 1))
                if v_direction == Direction.Left:
                    v_list.extend([v_LDNode, v_LNode, v_LUNode])
                elif v_direction == Direction.LeftUp:
                    v_list.extend([v_LNode, v_LUNode, v_UNode])
                elif v_direction == Direction.Up:
                    v_list.extend([v_LUNode, v_UNode, v_RUNode])
                elif v_direction == Direction.RightUp:
                    v_list.extend([v_UNode, v_RUNode, v_RNode])
                elif v_direction == Direction.Right:
                    v_list.extend([v_RUNode, v_RNode, v_RDNode])
                elif v_direction == Direction.RightDown:
                    v_list.extend([v_RNode, v_RDNode, v_DNode])
                elif v_direction == Direction.Down:
                    v_list.extend([v_RDNode, v_DNode, v_LDNode])
                elif v_direction == Direction.LeftDown:
                    v_list.extend([v_DNode, v_LDNode, v_LNode])
                return v_list
            return None
    
        def DirectionNodeCheck(self, p_curNode: node.Node, p_list: [node.Node]):
            """
            对当前Node的NextNode集进行方向Node集检测
    
            :param p_curNode: 当前Node
            :param p_list: 当前Node的NextNode集
            :return: 返回一个列表，即检测处理后的NextNode集
            """
            v_directionNodes = self.GetDirectionNodes(p_curNode)
            if v_directionNodes is not None and p_list is not None and len(p_list) != 0:
                v_list = []
                for n in p_list:
                    if node.NodeCheck.RepeatCheck(v_directionNodes, n) is False:
                        v_list.append(n)
                return v_list
            return p_list
    
    
    # 查找最佳路径
    class SearchPath:
        _lock = th.Lock()
        _currentNode: node.Node
        # 是否完成了初始化
        _isInit = False
        _isSearchFinish = False
        _nextNode = None
        _SearchNum = 0
        _closeList = []
        _checkedList = []
        _lockedList = []
        # 网格行列数
        _rowsCount = 0
        _colsCount = 0
        # x和y的最小值
        _minX = 0.5
        _minY = 0.5
        # x和y的最大值
        _maxX = 0
        _maxY = 0
        # 终点Node
        _endNode: node.Node
    
        def __init__(self):
            if self._isInit is False:
                self._currentNode = sd.SharedNodes().GetStartNode()
                self._nextNode = self._currentNode
                self._rowsCount = sd.SharedData.rowsCount
                self._colsCount = sd.SharedData.colsCount
                self._maxX = self._colsCount - 0.5
                self._maxY = self._rowsCount - 0.5
                self._endNode = sd.SharedNodes().GetEndNode()
                self._blockList = sd.SharedNodes().GetBlockNodes()
                self._isInit = True
    
        def __new__(cls, *args, **kwargs):
            if hasattr(SearchPath, '_instance') is False:
                with cls._lock:
                    if hasattr(SearchPath, '_instance') is False:
                        SearchPath._instance = object.__new__(cls)
            return SearchPath._instance
    
        def Search(self, p_isPrint=False):
            """
            查找最佳路径
    
            :param p_isPrint: 是否在控制台打印最佳路径的Node集信息,默认为False
            """
            while self._isSearchFinish is False:
                self._GetPathNodes()
                if self._SearchNum >= 5:
                    break
            sd.SharedNodes().Submit(self._closeList)
            if p_isPrint:
                node.NodeDeal.PrintNodes(self._closeList, '-->')
    
        # 获取路径Node集
        def _GetPathNodes(self):
            self._SearchNum += 1
            while self._UpdateCurrentNode():
                v_nextNodes = self.GetNextNodes(self._currentNode)
                v_nextNodes = self._NextNodesCheck(self._currentNode, v_nextNodes)
                self._NodesApplication(v_nextNodes)
            if self._isSearchFinish is False:
                self._Reset()
    
        def GetNextNodes(self, p_curNode):
            """
            获取经过基本处理的当前Node的NextNode集
    
            :param p_curNode: 当前Node
            :return: 返回一个列表
            """
            v_list = node.NodeFactory().GenerateNextNodes(p_curNode)
            v_list = self._NodesFilter(v_list)
            v_list = node.NodeDeal.CalculateWeight(v_list, self._currentNode, self._endNode)
            v_list = node.NodeDeal.SortNodes(v_list)
            v_list = NodeMove().GetNextNodes(self._blockList, v_list, p_curNode)
            return v_list
    
        # 对NextNode集进行移动规则检测
        def _NextNodesCheck(self, p_curNode, p_list):
            v_list = p_list
            v_node = NodeMove().GetDoubleNonDiagonalMoveNode(p_curNode, v_list)
            if v_node is not None:
                v_list.insert(0, v_node)
            v_node = NodeMove().GetDiagonalMoveNode(p_curNode, v_list)
            if v_node is not None:
                v_list.insert(0, v_node)
            v_list = NodeMove().DirectionNodeCheck(p_curNode, v_list)
            return v_list
    
        # 重置
        def _Reset(self):
            self._closeList = []
            self._isStart = False
            self._nextNode = sd.SharedNodes().GetStartNode()
            self._checkedList = []
    
        # 对NextNode集进行筛选
        def _NodesFilter(self, p_list):
            if p_list is not None and len(p_list) != 0:
                v_list2 = []
                v_list1 = node.NodeDeal.RemoveOutOfRangeNode(p_list)
                for n in v_list1:
                    v_isInCheckedList = node.NodeCheck.RepeatCheck(self._checkedList, n)
                    v_isInCloseList = node.NodeCheck.RepeatCheck(self._closeList, n)
                    v_isInBlockList = node.NodeCheck.RepeatCheck(self._blockList, n)
                    v_isInLockedList = node.NodeCheck.RepeatCheck(self._lockedList, n)
                    v_j1 = v_isInCloseList is False and v_isInBlockList is False
                    v_j2 = v_isInCheckedList is False and v_isInLockedList is False
                    if v_j1 and v_j2:
                        v_list2.append(n)
                return v_list2
            return p_list
    
        # 应用经过基本处理和移动规则检测的NextNode集
        def _NodesApplication(self, p_list):
            if p_list is not None and len(p_list) != 0:
                v_j1 = node.NodeCheck.RepeatCheck(p_list, self._endNode)
                v_j2 = NodeMove().NextNodeMoveCheck(self._blockList, self._endNode, self._currentNode)
                if v_j1 and v_j2:
                    self._nextNode = self._endNode
                    self._isSearchFinish = True
                else:
                    v_list = self._GetDirectionNodes(self._currentNode)
                    self._checkedList.extend(v_list)
                    self._checkedList = node.NodeDeal.RemoveRepeatNode(self._checkedList)
                    self._nextNode = p_list[0]
            else:
                self._nextNode = None
    
        # 获取上一个Node和当前Node的方向Node集
        def _GetDirectionNodes(self, p_curNode):
            v_directionNodes = []
            if p_curNode is not None:
                v_directionNodes = NodeMove().GetDirectionNodes(p_curNode)
            return v_directionNodes
    
        # 更新当前Node
        def _UpdateCurrentNode(self):
            if self._nextNode is None:
                self._lockedList.append(self._currentNode)
                self._lockedList = node.NodeDeal.RemoveRepeatNode(self._lockedList)
                return False
            self._currentNode.nextNode = self._nextNode
            self._nextNode.preNode = self._currentNode
            self._currentNode = self._nextNode
            v_isInCloseList = node.NodeCheck.RepeatCheck(self._closeList, self._currentNode)
            if v_isInCloseList is False:
                self._closeList.append(self._currentNode)
                if self._currentNode == self._endNode:
                    self._isSearchFinish = True
                    return False
                return True
            return False

SharedData.py

from myCodes import Node as node
    import threading as th
    
    
    # 共享信息类
    class SharedData:
        # 网格行列数
        startNodeSize = 0
        endNodeSize = 0
        blockNodeSize = 0
        pathNodeSize = 0
        arrowWidth = 0
        fontSize = 0
        rowsCount = 0
        colsCount = 0
        blockInfo = ''
    
        @classmethod
        def GetSizes(cls, p_rowsCount: int, p_colsCount: int):
            """
            获取默认尺寸元组
    
            :param p_rowsCount: 网格行数
            :param p_colsCount: 网格列数
            :return: 返回一个元组
            """
            if p_rowsCount == 3:
                if p_colsCount == 3:
                    v_sizes = (60, 60, 102, 40, 0.05, 15)
                elif p_colsCount == 4:
                    v_sizes = (55, 55, 102, 35, 0.04, 14)
                elif p_colsCount == 5:
                    v_sizes = (50, 50, 88, 30, 0.03, 13)
                elif p_colsCount == 6:
                    v_sizes = (45, 45, 72, 25, 0.02, 12)
                elif p_colsCount == 7:
                    v_sizes = (40, 40, 62, 20, 0.02, 11)
                else:
                    v_sizes = ()
            elif p_rowsCount == 4:
                if p_colsCount == 3 or 4 or 5:
                    v_sizes = (55, 55, 75, 35, 0.04, 14)
                elif p_colsCount == 6:
                    v_sizes = (50, 50, 72, 30, 0.03, 13)
                elif p_colsCount == 7:
                    v_sizes = (45, 45, 62, 25, 0.03, 12)
                else:
                    v_sizes = ()
            elif p_rowsCount == 5:
                if p_colsCount == 3 or 4 or 5 or 6:
                    v_sizes = (45, 45, 60, 25, 0.03, 12)
                elif p_colsCount == 7:
                    v_sizes = (45, 45, 62, 25, 0.03, 12)
                else:
                    v_sizes = ()
            elif p_rowsCount == 6:
                if p_colsCount == 3 or 4 or 5 or 6 or 7:
                    v_sizes = (35, 35, 50, 15, 0.02, 10)
                else:
                    v_sizes = ()
            elif p_rowsCount == 7:
                if p_colsCount == 3 or 4 or 5 or 6 or 7:
                    v_sizes = (30, 30, 42, 10, 0.01, 9)
                else:
                    v_sizes = ()
            else:
                v_sizes = ()
            return v_sizes
    
    
    # 共享Node和Node集
    class SharedNodes:
        _instanceLock = th.Lock()
        _lock = th.Lock()
        _sharedNodes = []
        _pathNodes = []
        _blockNodes = []
        _isUpdatePathNodes = False
        _isUpdateBlockNodes = False
        _startNode: node.Node
        _endNode: node.Node
    
        def __init__(self):
            node.NodeFactory()
    
        def __new__(cls, *args, **kwargs):
            if hasattr(SharedNodes, '_instance') is False:
                with cls._instanceLock:
                    if hasattr(SharedNodes, '_instance') is False:
                        SharedNodes._instance = object.__new__(cls)
            return SharedNodes._instance
    
        # 起始点Node的设置
        def SetStartNode(self, p_node: node.Node, p_password: str = ''):
            """
            设置起始点Node
    
            :param p_node: 起始点Node
            :param p_password: 调用密码
            """
            if p_node is not None and p_password == 'SNSET':
                self._startNode = p_node
    
        # 终点Node的设置
        def SetEndNode(self, p_node: node.Node, p_password: str = ''):
            """
            设置终点Node
    
            :param p_node: 终点Node
            :param p_password: 调用密码
            """
            if p_node is not None and p_password == 'ENSET':
                self._endNode = p_node
    
        def GetStartNode(self):
            """
            获取起始点Node
    
            :return: 返回Node
            """
            v_node = node.Node(self._startNode.nodeName, self._startNode.nodePos)
            v_node.f = self._startNode.f
            v_node.g = self._startNode.g
            v_node.h = self._startNode.h
            v_node.nodeTag = self._startNode.nodeTag
            return v_node
    
        def GetEndNode(self):
            """
            获取终点Node
    
            :return: 返回Node
            """
            v_node = node.Node(self._endNode.nodeName, self._endNode.nodePos)
            v_node.f = self._endNode.f
            v_node.g = self._endNode.g
            v_node.h = self._endNode.h
            v_node.nodeTag = self._endNode.nodeTag
            return v_node
    
        def GetPathNodes(self):
            # 起初该方法是直接返回cls.__pathNodes，这就导致了数据安全性的问题，使得在外部可以直接修改这里pathNodes的数据，所以正确的做法应该像现在这样
            # 声明一个新的列表，然后将cls.__pathNodes中的值添加进去，再将新的列表作为返回值传递出去，这说明在Python中直接传递内部的静态变量会传递其引用
            """
            获取PathNode集
    
            :return: 返回一个列表
            """
            self._UpdateNodes(node.NodeTag.PATHNODE)
            v_pathNodes = []
            for n in self._pathNodes:
                v_pathNodes.append(n)
            return v_pathNodes
    
        def GetBlockNodes(self):
            """
            获取BlockNode集
    
            :return: 返回一个列表
            """
            self._UpdateNodes(node.NodeTag.BLOCKNODE)
            v_blockNodes = []
            for n in self._blockNodes:
                v_blockNodes.append(n)
            return v_blockNodes
    
        def Submit(self, p_list: list[node.Node]):
            """
            通过该方法可以实现Node集的添加、删除、修改，建议与GetPathNodes或GetBlockNodes方法配套使用
    
            :param p_list: 修改后的Node集
            :return: 无返回值
            """
            v_list = node.NodeDeal.RemoveRepeatNode(p_list)
            v_list = self._PollutionNodeCheck(v_list)
            self._ReplaceSharedNodes(v_list)
            self._AddToSharedNodes(v_list)
            v_tag = self._GetNodesType(v_list)
            self._DeleteSharedNodes(v_list, v_tag)
            if v_tag == node.NodeTag.PATHNODE:
                self._isUpdatePathNodes = False
            else:
                self._isUpdateBlockNodes = False
            self._UpdateNodes(v_tag)
    
        # 更新PathNode集和BlockNode集
        def _UpdateNodes(self, p_tag):
            if p_tag == node.NodeTag.PATHNODE:
                if self._isUpdatePathNodes is False:
                    with self._lock:
                        v_list = []
                        for n in self._sharedNodes:
                            if n.nodeTag == node.NodeTag.PATHNODE:
                                v_list.append(n)
                        self._pathNodes = v_list
                    self._isUpdatePathNodes = True
            else:
                if self._isUpdateBlockNodes is False:
                    with self._lock:
                        v_list = []
                        for n in self._sharedNodes:
                            if n.nodeTag == node.NodeTag.BLOCKNODE:
                                v_list.append(n)
                        self._blockNodes = v_list
                    self._isUpdateBlockNodes = True
    
        # 脏数据清理
        def _PollutionNodeCheck(self, p_list):
            if p_list is not None and len(p_list) != 0:
                v_tag = self._GetNodesType(p_list)
                if v_tag is None:
                    return p_list
                v_list = []
                for n in p_list:
                    if n.nodeTag == v_tag:
                        v_list.append(n)
                return v_list
            return p_list
    
        # 获取当前Node集的种类：PathNode集或BlockNode集
        def _GetNodesType(self, p_list):
            if p_list is not None and len(p_list) != 0:
                v_pathNodeCount = 0
                v_blockNodeCount = 0
                for n in p_list:
                    if n.nodeTag == node.NodeTag.PATHNODE:
                        v_pathNodeCount += 1
                    else:
                        v_blockNodeCount += 1
                if v_pathNodeCount > v_blockNodeCount:
                    return node.NodeTag.PATHNODE
                elif v_pathNodeCount < v_blockNodeCount:
                    return node.NodeTag.BLOCKNODE
                else:
                    return None
            return None
    
        # Node集的修改功能
        def _ReplaceSharedNodes(self, p_list):
            if p_list is not None and len(p_list) != 0:
                with self._lock:
                    v_list = self._sharedNodes
                    for n in p_list:
                        v_list = node.NodeDeal.ReplaceNode(v_list, n)
                    self._sharedNodes = v_list
    
        # Node集的添加功能
        def _AddToSharedNodes(self, p_list):
            if p_list is not None and len(p_list) != 0:
                with self._lock:
                    v_list = []
                    for n in p_list:
                        if node.NodeCheck.RepeatCheck(self._sharedNodes, n) is False:
                            v_list.append(n)
                    self._sharedNodes.extend(v_list)
    
        # Node集的删除功能
        def _DeleteSharedNodes(self, p_list: list, p_tag: node.NodeTag):
            if p_list is not None and len(p_list) != 0:
                with self._lock:
                    if p_tag == node.NodeTag.PATHNODE:
                        v_nodes = self._pathNodes
                    else:
                        v_nodes = self._blockNodes
                    for n in v_nodes:
                        if node.NodeCheck.RepeatCheck(p_list, n) is False:
                            v_index = self._sharedNodes.index(n)
                            del self._sharedNodes[v_index]

Main.py

from myCodes import SearchPath as sp
    from myCodes import Grid as grid
    from myCodes import Block as block
    
    # 创建网格，传递行数和列数
    g = grid.Grid(7, 7)
    # 生成障碍物
    block.Block(30).Create()
    # 查找最佳路径
    sp.SearchPath().Search()
    # 绘制图象
    g.Draw()

##### 代码解说 #####

本篇中我们需要重点关注的是这三个类：NodeMove、NodeDeal、SearchPath，NodeMove类主要负责移动规则的制定和检测，NodeDeal类主要负责Node以及Node集相关的处理，SearchPath类主要负责最佳路径的查找。在NodeMove类中包括这几个重要的方法，GetNextNodes用于获取经过可移动检测的NextNode集，GetMoveDirection用于获取当前Node至下一步Node的方向，NextNodeMoveCheck用于检测当前Node至下一步Node是否可移动，NextNodesMoveCheck用于检测当前Node的NextNode集中是否存在可移动的Node，GetDiagonalMoveNode用于获取经过可替换斜向移动检测的目标Node，GetDoubleNonDiagonalMoveNode用于获取经过二次可替换非斜向移动检测的目标Node，GetDirectionNodes用于获取上一个Node至当前Node的方向Node集，DirectionNodeCheck用于对当前Node的NextNode集进行方向Node集检测。在NodeDeal类中包括这几个重要的方法，SetWeightValue用于设置一次斜向移动和一次非斜向移动的权值，CalculateWeight用于对Node集进行权值计算，CalculateG用于计算Node的G值，CalculateH用于计算Node的H值，当然还包括其它的一些Node集处理方法。SearchPath类中的Search方法负责调度和组合查找最佳路径相关的方法。我们虽已完成了基本的寻路算法，但是这只是一种简单模拟的情景，也就是我们在一个网格中，生成了障碍物，然后我们需要根据移动规则来找到从起始点到终点的最佳路径，但是这只是静态的情景，在游戏中，我们把起始点比作敌人，终点比作玩家，那么玩家通常是在不断移动的，所以我们需要在终点进行移动的同时动态调整路径，以实现对终点的追踪，我们将在后续的文章中继续对这个问题进行探讨。

**下一篇将针对路径的动态规划问题进行进一步的探索和实现**

**如果这篇文章对你有帮助，请给作者点个赞吧！**

[a963799fc6dc44eda2b57217ffa49eb5.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/6b37470e180445ce8dc2432600dacbbd.png
[0038242034344b418229b80cf8856dc7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e53c41c5b73b44d995b99120d9da96dd.png
[7ce30d5a9bee45b68cfcbdb8b63e4d0f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9bb4d8552b154608b4dae0b56e3ea39f.png
[e28cb37e0b80419a972edfbf90b8b90a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4102071d6901481fb69c13fb4c23b7af.png
[4c3e67c939fa4787a1361a21dc3cfe1e.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/38798e4ef38049a5a61cabb37c4c7cc5.png
[0f15b0a4f0824d5ea1db9b86e120bc70.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/488b231ba208431b9b8f60380043f452.png
[b8c54b4058e34d48af1548c210228657.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ce6907083a4b4f09b81af2f5f2779f01.png
[d7620feb9ae54ec184c41e9d1b243ac0.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/6cb3e83b6bdf4fbb908fa97ab1c82bef.png