C++ нахождение n точек как можно ближе к заданному xy

Question

В играх RTS, когда вы перемещаете некоторые юниты, они находят путь и идут к местам, которые находятся ближе всего к выбранному месту. Я не знаю, как выбрать эти места, я имею в виду целевые точки для каждой единицы.

Например, когда я посылаю 9 солдат, я хочу, чтобы у них ЗАДАЧ, как это:

. - empty, 
T - targets for units, 
O - the place that I've choosen to move them, target for unit too 
..... 
.TTT. 
.TOT. 
.TTT. 
..... 

алгоритм Pathfinding готов, просто мне нужно создать список (или вектор) целевых точек, один для каждой единицы. Я не хочу, полный код, но только некоторые советы и идеи ... Ну, я должны помнить, что не все места проходимые ...

Thanx за любые ответы и извините за мой плохой английский ...

Answer 1

Вы можете использовать BFS из выделенной точки. «Заполните» выбранную плиту блоком, если это плитка, которая может удерживать блок [не препятствие]. Продолжайте делать это, пока не исчерпаете количество единиц.

В псевдокоде:

selectTargetLocation(point,units): 
    currUnit <- 0 
    queue<- new queue 
    visited <- {} 
    map<unit,point> <- empty map 
    queue.push(point) 
    while (queue.empty() == false): 
    current <- queue.takeFirst() 
    visited.add(current) 
    for each p such that p and current are neighbors: //insert neighbors to queue 
      if p is not in visited: 
       queue.push(p) 
    if current is not an obstacle: 
     map.put(unit[currUnit++],current) 
    if (currUnit == units.length) break //break when exhausted all units 
    return map 

Answer 2

Моя идея была бы так: первое, испытание, если адресат занят, или блок уже имеет этот пункт назначения. Если это так, вам нужно найти закрытую точку, которая бесплатна. Вы можете нажать все близкие точки на очередь, на текущую точку и т. Д., Подобно алгоритму заполнения), пока не найдете точку, которая не занята. Затем найдите путь к этому местоположению.