PATHFINDER

Pathfinder – по Эйнар Saukas

Игры ZX-Spectrum, как правило, требуют нахождения кратчайших путей в один экраном, таким образом, 2D сетки площадь меньше, чем 24×32.

Для таких маленьких картах, накладные расходы от использования достаточно сложной эвристики на основе

Алгоритм поиска пути (с точки зрения времени управления структурой данных и памяти) не стоит. Вместо этого, эти карты могут быть легко решены с помощью следующих “Упрощенная Дейкстра” алгоритм:

* Все позиции, которые сосед на целевые места должны быть обозначены

  Значение “1”, так как они 1 шаге от этой цели;

* Все остальные позиции, которые сосед на “1” должны быть отмечены значения

  “2”, так как они в 2 шагах от цели;

* Все остальные позиции, которые сосед “2” должны быть отмечены значения

  “3”, так как они являются 3 шагах от цели;

* … Продолжайте делать это до тех пор, пока не достигнет исходного положения.

Впоследствии, если начальная позиция будет помечен со значением “9”, это означает, что он 9

в нескольких шагах от конечной позиции. Оттуда, вы можете перейти на позиции, что 8 шагов от цели, затем в положение, которое является 7 шагах, и так далее.

Технически, этот алгоритм соответствует следующему псевдокоде:

pathfind (положение ИСТОЧНИК, положение TARGET) {     создать пустую очередь     ясно массив РАССТОЯНИЕ []     Знак РАССТОЯНИЕ [цель] = 0     добавить TARGET в конце ОЧЕРЕДИ     в то время как очередь не пуста         удалить PosX от начала очереди         для каждого безымянной позиции Пози, что это сосед PosX             если букет является такой же, как ИСТОЧНИК затем вернуться “ПУТЬ НАЙДЕНО”             РАССТОЯНИЕ [букет] = расстояние [PosX] + 1             добавить букет до конца очереди     вернуться “НЕТ НИКАКОГО ПУТЬ” }

Очередь упоминалось выше является лишь небольшой кольцевой буфер, и расстояние

Область временного буфера.

“SINGLEPATH”

Программа “SINGLEPATH” является одним из основных реализация этого алгоритма, при условии, чтобы

помочь объяснить, как это работает. Он содержит следующие строки:

* Линии 10-30: Генерирует случайное карту на экране. На данный момент, если вы не

  доволен сгенерированной карте, вы можете просто сохранить экран эмулятора, редактировать   это, а затем импортировать его снова. Вам даже не нужно использовать те же цвета: каждый   символ положение с темной бумаги (цвета 0,1,2,3 без BRIGHT) будет   интерпретируется как препятствия, и все остальное в качестве путей.

* Линии 40-60: Просит позиции источника и назначения.

* Линии 70-210: Выполняет Pathfinder. Во время исполнения соседних позициях сохраняются   в очереди показаны на желтый, уже обработанных позиций в голубой.

* Линии 220-280: Показывает кратчайший путь (если карта имеет верное решение).

“Многолучевого распространения”

Программа “многолучевого распространения” является еще одним основным реализация того же алгоритма, но

поддержки нескольких источников и целей. На практике, это означает только то, расчета дорожки для всей карте, не потрудившись проверить на каждом шагу, если он имеет достиг положения источника.

Поиск пути для нескольких источников и / или целей является очень полезным на практике. Для

Например, если игра Pac-Man занимает текущую позицию игрока, как цели, это Алгоритм будет определить лучший путь для каждого компьютерным управлением противника призрак сразу.

Эта программа содержит следующие строки:

* Линии 10-30: Генерирует случайное карту на экране.

* Линии 40-60: Спрашивает нескольких исходных и целевых позиций.

* Линии 70-120, 200-210: Выполняет Pathfinder. Обратите внимание на то, что число источников   и цели не будет иметь никакого значения в момент обработки карту.

* Линии 130-190: Показывает кратчайший путь от каждого источника в его ближайшую цель.

СДЕЛАТЬ …

Реализация Ассамблея в ближайшее время будет предоставлена ​​…