python - 具有可变移动速度的 2D 寻路？

Question

嗨，我对寻路领域很陌生，我已经在整个互联网上搜索了我的问题的答案，所以我想是时候问专家了：

我的环境由一个 2D 矩形地图组成，其中包含墙壁和用于穿越环境的单元（单元之间没有碰撞，但它们不能穿过墙壁） 环境中的单元以基于回合的方式沿直线移动，但它们可以移动速度为 0 到 unit.movespeed（例如 5）（您可以控制每次移动的移动速度）。（地图大小的范围是从 20,20 到 200,200 个单元格，但您可以移动到浮点位置添加墙壁可以在例如 wall[(x=10.75,y=9.34),(x=33.56,y= 62.43])

在夏季的每一个滴答声中，你告诉一个单位移动到浮点类型的目的地 (x,y)

我已经尝试过 A* 和基于目标的矢量寻路算法，但我一直遇到的问题是弄清楚它们应该移动多快，因为显然，最佳移动速度应该是最大速度，但如果它们总是以最大速度移动，它们很容易撞墙，因为这些算法没有考虑到可变的移动速度。有任何想法吗？带有 a* 星和基于目标的矢量寻路问题的 movespeed 问题的图像

代码：

class Cell:
    def __init__(self,coords,vector=None,distance=None,obstacle=False):
        self.coords = coords
        self.vector = vector
        self.distance = distance
        self.obstacle = obstacle
class VectorMap:

    def __init__(self,unit, dest, map=HardCoded._make_map()):
        self.size = Coords(len(map), len(map[0]))
        self.map = map
        VectorMap.map_converter()
        self.unit = unit
        self.dest = dest

    def _create_vector_map(self):
        return self._cell_def(1,self.map[self.dest])

    def _cell_def(self,dist,current_cell):
        neighbors = [Coords(0, 1), Coords(0, -1), Coords(1, 0), Coords(-1, 0), Coords(1, 1), Coords(1, -1),
                     Coords(-1, 1), Coords(-1, -1)]
        for neighbor in neighbors:
            #check if out of range of arr then return map
            if current_cell.coords.y + neighbor.y < self.size[1] and current_cell.coords.x + neighbor.x < self.size[0]:
                neighbor_cell = self.map[current_cell.coords.x + neighbor.x][current_cell.coords.y + neighbor.y]
            if neighbor_cell.obstacle:
                continue
            neighbor_cell.distance = dist
            #neighbor_cell.vector = current_cell
            return self._cell_def(self.map,dist+1,neighbor_cell)

    def map_converter(self):
        nmap = []
        for x,element in enumerate(self.map):
            tmap = []
            for y,value in enumerate(element):
                tmap.append(Cell(Coords(x,y),vector=None,distance=None,obstacle=False if value == 0 else True))
            nmap.append(tmap)
        self.map = nmap
        self._create_vector_map()
        for x,c in enumerate(self.map):
            for y,cell in enumerate(c):
                cell.vector = Coords(0,0)
                right_tile_distance = (self.map[x+1][y].distance if x+1 < self.size.x else self.map[x][y].distance)
                up_tile_distance = (self.map[x][y+1].distance if y+1 < self.size.y else self.map[x][y].distance)
                cell.vector.x = (self.map[x-1][y].distance if x is not 0 else self.map[x][y].distance) - right_tile_distance
                cell.vector.y = up_tile_distance - (self.map[x][y-1].distance if y is not 0 else self.map[x][y].distance)
                if cell.vector.x == 0 and right_tile_distance < self.map[x][y].distance:
                    cell.vector.x = 1
                if cell.vector.y == 0 and up_tile_distance < self.map[x][y].distance:
                    cell.vector.y = 1


                cell.vector = Util.normalize(cell.vector)


    def vetor_move(self):
        vector = self.map[self.unit.coords.x][self.unit.coords.y].vector
        movespeed = self.desired_movespeed()
        dest = Coords(vector.x * movespeed,vector.y * movespeed)
        return Action(mechanic='move', params=[dest], report='Moving With Maths')

    def desired_movespeed(self):
        pass

class Util:
    @staticmethod
    def normalize(vector):
        norm=np.linalg.norm(vector,ord=1)
        if norm == 0:
            norm = np.finfo(vector.dtype).eps
        return Coords(*(vector/norm))

标签： python2dpath-finding