2d сетка достижимых направлений - PullRequest
Новая
       41

2d сетка достижимых направлений

3 голосов
/ 05 февраля 2011

Допустим, у меня есть двумерная сетка. Поиск пути - это второй шаг в моей проблеме.

Моя вещь, допустим, у меня есть блок в середине сетки. Я хочу, чтобы я мог сказать пользователю: «Это все ваши доступные пункты назначения».

Исходя из того, сколько квадратов может пройти юнит, я хочу показать пользователю: «Это все квадраты, которые вы можете достичь». а затем найдите путь к месту назначения, который выбирает пользователь.

Как лучше всего выполнить первый поиск, чтобы показать доступные пункты назначения?

Местность также может иметь ограничения и бонусы в зависимости от местности.

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

Ура! :)

/ E

Ответы [ 3 ]

4 голосов
/ 05 февраля 2011

Лучшим способом, вероятно, будет поиск в глубину (http://en.wikipedia.org/wiki/Depth_first_search) с ограничением того, как далеко вы можете пройти.

2 голосов
/ 05 февраля 2011

Для каждой точки в сетке хранить:

  • Минимальное расстояние от единицы до этой точки.
  • Следующий шаг к устройству по кратчайшему пути.

Чтобы рассчитать это, выполните поиск в ширину:

  • Установите стоимость расстояния до вашего отряда до 0, и его "указатель пути" не имеет значения / нуль.
  • Создайте очередь и поместите в нее начальную точку.
  • Пока очередь не пуста:
    • Возьмите следующую точку и распространите ее (посмотрите на всех соседей. Если идти к ним через текущую точку выгодно, установите их расстояние / путь и добавьте их в конец очереди)

Не забудьте обратить внимание, чтобы вы остановили поиск после правильного количества шагов, если у вас есть ограничение.

Если вы сделаете это правильно, вы сможете найти все достижимые точки, определить, какова их длина, а также найти кратчайший доступный путь (хотя он хранится «назад»)

Не выполняйте поиск в глубину проблем кратчайшего пути! Скорее всего, вы будете делать многократные вычисления снова и снова. (Если вы не используете более сложные эвристические алгоритмы, такие как A * - но тогда вы уже должны знать, что делаете в любом случае)

1 голос
/ 05 февраля 2011

Пометить подключенные ячейки одинаковыми номерами, а не связанными разными.Вы можете найти двухпроходный алгоритм для маркировки ячеек на http://en.wikipedia.org/wiki/Connected_Component_Labeling.Если количество ячеек отличается, игрок не может добраться до этого места.

...