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

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

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

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

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

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


c++ points algorithm
person noisy cat    schedule 23.02.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

arrow_upward
1
arrow_downward

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

person Tibi    schedule 23.02.2012
comment
Это точно BFS, за исключением того, что вы не поддерживаете набор visted, что может привести к (1) избыточному вычислению [вы будете вычислять слишком много раз одни и те же точки]. (2) В итоге вы можете разместить 2 юнита на одной плитке. - person amit; 23.02.2012
comment
@amit Хм, прочитав несколько статей о BFS, я понял, что ты прав :D Статья в Википедии сложная (с графиками, а не картой), поэтому я подумал, что это не то же самое :D - person noisy cat; 23.02.2012
comment
Fill — это алгоритм BFS, так что да, это BFS... Однако я предпочитаю думать о BFS в виде графика, а не многомерной сетки. Существует алгоритм Lee, который также очень похож на BFS и используется для поиска кратчайшего пути в сетке. - person Tibi; 23.02.2012
comment
Подожди, есть идея. Если бы я просто отправил их в одно место, А если место занято, просто остановитесь там, где вы находитесь? - person noisy cat; 23.02.2012
comment
@kittyPL: это приведет к избыточным вычислениям, вам придется вычислять одно и то же n раз [где n — количество отправленных единиц]. Обычно в играх RTS [насколько мне известно] производительность является проблемой. - person amit; 23.02.2012
comment
Или нет... Они стоят в очереди :/ - person noisy cat; 23.02.2012
comment
И что? Может быть, считать одну дорогу на всех, только концовку поменять? - person noisy cat; 23.02.2012
comment
Это довольно сложно... вам нужно иметь какую-то проверку на столкновение во время движения, и если есть столкновение, найти другой путь. Ваша идея слишком усложнила бы систему столкновений. - person Tibi; 23.02.2012
comment
У меня есть проверка на столкновение :D Если вы используете Windows, я могу отправить двоичные файлы, если нужно, вы можете проверить это тогда... - person noisy cat; 23.02.2012
comment
Нет необходимости... Я тоже работаю над проектом стратегической игры, я не могу дождаться, когда моя графика заработает, так что я мог бы поработать над этими вещами :D - person Tibi; 23.02.2012
comment
Можешь показать мне свою работу? Мне не нужен код, просто чтобы посмотреть, как у тебя дела :D Я очень горжусь своим генератором карт полуострова :) - person noisy cat; 23.02.2012
comment
На данный момент это не так много, просто программа для чтения текстур png с использованием libpng, некоторые базовые классы для юнитов и кое-что из opengl. Так горжусь собой прямо сейчас, потому что, наконец, текстуры png работают :D - person Tibi; 23.02.2012
comment
давайте продолжим это обсуждение в чате - person noisy cat; 23.02.2012