Привет, я довольно новичок в области поиска пути, и я искал ответ на свой вопрос по всем сетям, поэтому решил, что пора спросить экспертов:
Моя среда состоит из 2D прямоугольник angular карта со стенами и юнитами для обхода среды (нет столкновений между юнитами, но они не могут go проходить сквозь стены) Юниты в окружающей среде движутся по очереди по прямой линии, но они могут двигаться по скорость от 0 до unit.movespeed (например, 5) (у вас есть контроль над скоростью движения для каждого движения). (размер карты в диапазоне от 20,20 до 200,200 ячеек, но вы можете перемещаться в местоположения с плавающей запятой, добавлять стены можно в таком месте, как, например, стена [(x = 10,75, y = 9,34), (x = 33,56, y = 62.43])
В сумме каждого тика вы говорите юниту перемещаться в пункт назначения (x, y) типа float
Я пробовал A * и вектор на основе цели алгоритмы поиска пути , но проблема, с которой я постоянно сталкиваюсь, состоит в том, чтобы выяснить, насколько быстро они должны двигаться, потому что, очевидно, оптимальная скорость движения должна быть максимальной, но если они всегда движутся с максимальной скоростью, они склонны к удару в стену, потому что эти алгоритмы не принимайте во внимание переменную скорость движения. Любые идеи - изображение проблемы скорости движения с * звездой и векторной задачей поиска пути на основе цели
Код :
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))