C ++ находит n точек максимально близко к заданному xy - PullRequest
Новая
       3

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

0 голосов
/ 23 февраля 2012

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

Например, когда я посылаю 9 военнослужащих, я хочу, чтобы у них были ЦЕЛИ, подобные этим: 

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

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

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

Ответы [ 2 ]

1 голос
/ 23 февраля 2012

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

1 голос
/ 23 февраля 2012

Вы можете использовать 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
...