python - 使用 pygame 实现 A* 算法我找到我的单位 "back-tracks"

Question

所以我一直在玩 Pygame，遇到了一个我可以解决的问题，但只是不优雅。

基本上，我在黑色的平原上有一个单位(此时只是一个红色方 block )。如果我单击该单元，然后单击该字段上的任何其他位置，该单元将前进到该点。该算法本身工作得非常完美，即使引入障碍，它也能快速处理路径查找。

我的问题在于我的实现。该单位是一个 16 x 16 的正方形，因此 field 被划分为 16 x 16 的正方形。如果我在运输途中更改设备的目的地，它有时会“回溯”到之前的“路径点”，然后再继续其新路线。

我明白为什么会发生这种情况，路径查找模块将每个方 block 视为网格上的一个点，因此当我将鼠标坐标传递到其中时，点(2,2)的像素坐标实际上是(32,32)路径方法我将它们除以 16 向下舍入整数(因此 (34,37) 变为 (2,2))，因此虽然单位可能位于实际的“网格点”之间，但路径查找模块从其最后一个实际位置找到路径路径点，而不是当前位置。当它将新路线传递给该单元时，该单元必须“原路返回”，以便遵循寻路模块找到的路线

显然，每个进行任何类型的寻路的游戏开发人员都已经解决了这个问题，所以我希望我能找到一个更优雅的解决方案。我不想沿着屏幕上的每个像素找到一条路径，只是路点，但回溯有点令人恼火。有什么建议吗？

下面建议的是相关代码:

在主 .py 文件中

if pygame.mouse.get_pressed()[0]: # if left mouse button pressed
    mouse_x,mouse_y = pygame.mouse.get_pos()
    if selected: # checks if a unit is selected
        unit.getRoute((mouse_x/16,mouse_y/16))

在unit.py文件中

def getRoute(self,target):
    self.route = path((self.x/16,self.y/16), target)

def getNode(self):
    if self.route:
        self.node = route.pop(0)
        dif_x,dif_y = self.node[0] - self.x, self.node[1] - self.y
        if dif_x > 0:
            self.vector_x = self.speed
        if dif_x < 0:
            self.vector_x = self.speed * -1
        else:
            self.vector_x = 0
        if dif_y > 0:
            self.vector_y = self.speed
        if dif_x < 0:
            self.vector_y = self.speed * -1
        else:
            self.vector_y = 0
    else:
        self.node = None
        self.vector_x = 0
        self.vector_y = 0

def update(self):

    if self.route or self.node:
        if self.route and not self.node:
            self.getNode()
        if (self.x,self.y) == self.node:
            self.getNode()

    self.x += self.vector_x
    self.y += self.vector_y
    self.rect.topleft = (self.x,self.y)

Answer 1

您应该以特殊的方式管理这第一步。这是因为即使该单位已经在移动，用它指定的单元格仍然保持不变，直到它到达下一个单元格。

现在我建议您确保在完成一半的移动后立即更新单元的单元格(以便探路器将从下一个单元格而不是前一个单元格搜索路径)。此外，您应该使用类似的方法来管理特殊情况

if unit is standing still
  compute pathfinding as you would normally do
else
  compute pathfinding from the unit cell
  discard the first cell of the pathfinding route (since it would backtrack)
  compute the route directly to the next cell (by drawing a correct path)

当然，这会更容易或更难，具体取决于你有多少运动自由度，如果你只允许正交运动，那么它会很简单，如果你允许对角线运动，那么你应该注意不要越过障碍物(那么这取决于您想要对小故障有多大的容忍度，例如单元与障碍物的一角重叠)。