我正在使用A *进行寻路，并创建了一个非常有限的图形，以便快速轻松地进行遍历和寻路 .
我如何将它表示为一个数据结构，可以通过python中的A *轻松地从P0到P1遍历？
一切都是相对于点P0和P1，它们可以镜像或相互旋转90度 .
这些点位于实际坐标处，其他节点相等于我们的两个点 . 节点必须记住它们的真实坐标，以便一旦选择了路径，就可以很容易地绘制它 .
边缘上的重量是预先加权的，以使得到的路径具有我喜欢的美学外观 . 权重不会改变，因此这些权重可以预先生成 . 但是，空间内可能存在动态影响某些边缘权重的对象（因此需要进行寻路） .
寻路将在每一帧发生，因此每1/25秒 . 因此提高效率 .
这是我想要组合的算法：
-
找到单元格之间矩形的短边和长边，找出对齐方式 .
-
计算每个节点和边的坐标 .
-
对边缘施加预重量 .
-
为被阻止的任何节点或边缘添加额外的权重 .
-
使用A *算法查找有利于最小化距离的路径的最低成本路径 .
并且提醒您，典型的A *实现有三个我需要提供的用户可维护部分：
def move_cost(self, c1, c2, pred=None, start=None, goal=None):
""" Compute the cost of movement from one coordinate to another."""
def estimate(self, c1, c2):
""" Compute the cost of movement from one coordinate to
another. Often euclidian distance."""
def successors(self, c):
""" Compute the successors of coordinate 'c': all the
coordinates that can be reached by one step from 'c'."""
如何生成和遍历此数据结构？
1 回答
这是一个庞大而复杂的问题，可以通过分解为较小的问题而受益 . 这里有一些想法可以帮助您区分您提出的一些子问题：
图形结构的遍历不依赖于几何，仅取决于分配给每条边的成本 . 如果您愿意，此费用可包括距离 .
由于路径查找算法与几何无关（但可能包括其成本函数中的距离），因此节点的几何布局是一个单独的问题 . 您可以将节点坐标视为分配给每个节点的任意属性，可用于计算成本（如果您希望成本与距离相关） .
遍历的数据结构将是具有节点和边类的图形对象，并允许您分配和编辑分配给每条边的权重，或者在您想要创建'blocks'时添加和删除边 .
如果您打算更改用于计算路径的源节点和目标节点，则应使用双向图 .
你说"there may be objects within the space that dynamically affect the weight of some edges" . 这些对象的位置和功能确定它们影响权重的时间和程度将是另一个单独的任务 .
这是您需要的主要内容：
undirected graph structure （包括节点，边，属性以及访问成本函数以解决成本最低路径的能力）
cost function . 这应该将边缘作为参数，并且如果需要，应该从与该边缘相关联的节点读取属性以计算成本 .
干扰对象，我称之为' attractors ' .
'effect' function 确定吸引子如何编辑图形结构或边缘权重 . 这可能包括距离搜索，该距离搜索确定落在吸引子的特定范围内的节点或边缘 .
Generating the initial coordinates and weights .
undirected graph structure 使用NetworkX非常容易实现 . NetworkX允许您将任意属性附加到节点和边缘，许多示例都有详细记录，并包含multiple least-cost pathfinding algorithms . NetworkX还允许您指定自定义成本函数以确定边缘遍历成本 .