Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Подземелье Магов
  
 

Фильтр по датам

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
  
 
Во Флориде и в Королевстве сейчас  02:36[Войти] | [Зарегистрироваться]

Обсуждение материала
Алгоритм поиска пути на карте
Полный текст материала


Другие публикации автора: George Judkin

Цитата или краткий комментарий:

«... Вариант реализации волнового алгоритма. ...»


Важно:
  • Страница предназначена для обсуждения материала, его содержания, полезности, соответствия действительности и так далее. Смысл не в разборке, а в приближении к истине :о) и пользе для всех.
  • Любые другие сообщения или вопросы, а так же личные эмоции в адрес авторов и полемика, не относящаяся к теме обсуждаемого материала, будут удаляться без предупреждения авторов, дабы не мешать жителям нормально общаться.
  • При голосовании учитывайте уровень, на который расчитан материал. "Интересность и полезность" имеет смысл оценивать относительно того, кому именно предназначался материал.
  • Размер одного сообщений не должен превышать 5К. Если Вам нужно сказать больше, сделайте это за два раза. Или, что в данной ситуации правильнее, напишите свою статью.
Всегда легче осудить сделанное, нежели сделать самому. Поэтому, пожалуйста, соблюдайте правила Королевства и уважайте друг друга.



Добавить свое мнение.

Результаты голосования
Оценка содержания

  Содержит полезные и(или) интересные сведения
[1]13100%
 
  Ничего особенно нового и интересного
[2]00%
 
  Написано неверно (обязательно укажите почему)
[3]00%
 
Всего проголосовали: 13

Оценка стиля изложения

  Все понятно, материал читается легко
[1]981.8%
 
  Есть неясности в изложении
[2]218.2%
 
  Непонятно написано, трудно читается
[3]00%
 
Всего проголосовали: 11




Смотрите также материалы по темам:
[Задачи оптимизации] [Программирование игр.]

Комментарии жителей
Отслеживать это обсуждение

Всего сообщений: 53

23-01-2011 22:37
Спасибо за статью - очень позновательно. Я сам занимался моделированием - алгоритм "поиска пути" для новичков очень сложен для понимания, но в статье все доступно описано.
 lod


06-01-2011 04:36
сообщение от автора материала
>>> который автор, почему то, противопоставил варианту Кегелеса
Оба варианта (если судить по названиям) предназначены для одного и того же: для поиска маршрута между двумя точками. В варианте Кеглеса мне не понравился только способ реализации движения волны. При переборе всех клеток на каждом шаге движения волны большую часть времени такая реализация будет "пермалывать воздух": проверять клетки, которые заведомо к волне не относятся.

>>> 1. "Путешественника" при движении заносит в сторону направления, взятого за 0 при обходе по часовой стрелке.
А меня и в реальной жизни тоже заносит. Вправо ;-) Если честно, то не вижу в этом криминала. Нет, можно, конечно, переписать реализацию TestNeighbours так, чтобы перебирать соседей в случайном порядке. Точнее, в псевдослучайном, потому как функция Random :-)

>>> 2. При изменении "проходимости" клеток на карте ВО ВРЕМЯ движения "Путешественника" (случай движения нескольких персонажей одновременно к одной или нескольким точкам финиша), что делать?
"Что делать, что делать... Сухари сушить" (с) Берегись автомобиля
По уму, надо бы было единственность "путешественника" при неизменной карте прописать в ограничения. Но мне показалось, что это очевидно. Молодой был ;-)

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

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

А если закономерности не выявлены или их нет (любая клетка в любой момент может измениться на любую другую клетку), то сидим и курим бамбук ;-)
 Geo


05-01-2011 05:31
Приведенный в статье алгоритм, который автор, почему то, противопоставил варианту Кегелеса, страдает на мой взгляд несколькими, особенностями ограничивающими его применение.

Ниже в порядке сложности их преодоления:

1. "Путешественника" при движении заносит в сторону направления, взятого за 0 при обходе по часовой стрелке.
Это вызвано, конечно, прежде всего самой постановкой, то есть клетками. Они создают ситуацию, когда из точки в точку можно дойти сразу несколькими маршрутами, в каждом из которых одинаковое кол-во клеток. Естественно, что при возможности выбора из нескольких вариантов движения с одинаковой стоимостью, выбирается тот, который подворачивается первым :). То есть тот который автор подворачивает использованием процедуры TestNeighbours и ее атрибута Direction...

2. При изменении "проходимости" клеток на карте ВО ВРЕМЯ движения "Путешественника" (случай движения нескольких персонажей одновременно к одной или нескольким точкам финиша), что делать? Запустить в цикле пересчет маршрутов персонажей после каждого шага каждого перса, с учетом изменения стоимости занятых другими персами клеток карты?
Ведь карта в данном решении это массив записей:


TPathMapCell = record     // Клетка карты пути в которой мы отмечаем:
   Distance : Integer;     // - порядковый номер клетки в маршруте и
   Direction : Integer;    // - направление, с которого приехали на эту клетку.


Если клетка вдруг стала непроходимой, то направление и номер клетки в маршруте утрачены... Цепочка разорвана:) Персу нужен новый маршрут. Или нужно ждать пока старый освободят :)

С другой стороны, в не вполне совершенном по реализации алгоритме Вадима Кегелеса, тем не менее, есть практическое зерно. Пусть даже путем выполнения большого количества циклов, коллега выстраивает вокруг точки финиша по сути некое потенциальное поле, в котором, может падать на этот самый финиш любое количество персов одновременно :) Как это падение реализовать, думаю, объяснять излишне?

Подведу итог, своему выступлению. Если заменить циклы Вадима, на волновой способ заполнения карты (функция FillPathMap), но заполнять ее просто номерами волн, то получится, во всех отношениях замечательный результат...

С глубоким уважением, Дмитрий


30-06-2009 01:45
Спасибо большущее.. хоть один человек всё нормально описал.. Удачи!!!


28-05-2009 02:51
да я это естественно понимаю, я на всякий случай предупредил, что есть такая особенность, связана она с тем, что не проверяется текущая точка, и в волну генерируем только с ближайшей точки.
это никак на работе программы не сказывается, просто есть такой момент. Спасибо вам за ваш код, я его в спокойной обстановке внимательно изучил, все вроде бы и просто, и сложно одновременно. Огромное спасибо вам за то, что вы не поленились изложить такой материал доступно и подробно и с примером. Поиск аналогичных решений по западным сайтам ничего не дал. Кроме дейкстры похоже там ничего не знают.


28-05-2009 01:33
сообщение от автора материала
>>> почему-то можно стартовую точку поставить на точку препятствие
В данной реализации начальная точка не прверяется на предмет того, является она препятствием или нет. Просто непонятно, что должна возвращать функция, если начальная точка является препятствием. Собственно, и конечная тоже не проверяется, просто в этом случае путь найден не будет. Проверка на препятствие выполняется при попытке перейти в следующую клетку. Так что ни на одно препятсвтие (кроме начальной точки) мы просто не сможем попасть.

Что делать? Естественно, проверять начальную точку перед вызовом функции поиска пути. И если это препятствие, то сами решайте, что Вам в этом случае делать. Все же когда я писал эту реализацию, то в голове держал игры, в которых нужно перемещать войска или технику из точки A в точку B. А если что-то в игре не может находится в клетке типа препятсвтие, то и проверять начальную точку нет необходимости.
 Geo


27-05-2009 10:46
Здравствуйте, уважаемый Geo
я тут крутил всяко-разно алгоритм ваш - вертел, и нашел странную особенность, почему-то можно стартовую точку поставить на точку препятствие. И вот понять не могу, как теперь это в приложении отлавливать?


13-05-2009 01:55
да все нормально, сейчас все работает хорошо.
у меня можно пересекать и линии, и если уж сильно приспичит - и углы, просто я на линиях поставил стоимость выше, чем в поле, а на углах, выше, чем на линиях. На повороты, что мы вместе с вами сделали - я выставил промежуточную цену. Еще на некоторых местах графа - я выставил цену выше, чем просто поле, чтобы туда линии лезли меньше. Но это только для красоты.
Спасибо, Вам, еще раз.


13-05-2009 00:55
сообщение от автора материала
>>> Не понятно, только, зачем вы стоимость клетки убрали
Я так понял, что у Вас стоимость движения всегда равна единице, то есть клетки бывают двух видов: препятствия и непрепятствия. Если я понял неверно, то поправьте.
 Geo


13-05-2009 00:24
  Geo
спасибо за наводку, спасибо за код. Не понятно, только, зачем вы стоимость клетки убрали - я оставил, и

if IsObstacle(X,Y) // здесь проверка на то, что клетка (X;Y) является препятствием; сделать Вам

на основе стоимости клеток оставил. Т.к. мне кроме препятствий еще нужны различные свойства узлов графа.


12-05-2009 08:59
сообщение от автора материала
Примечания:

1. Код написан на коленке. Ничего не проверял. Delphi под рукой нет.

2. Для реализации функции GetCost Вам потребуется узнать не занята ли определенная клетка на карте. В реализации я это написал как некую функцию IsObstacle. Вам ее потребуется реализовать, так как я не знаю вашего формата хранения карты. Так как может оказаться, что юнит с картой должен будет ссылаться на PathFind (чтобы вызывать оттуда функции поиска пути), а PathFind должен будет ссылаться на юнит с картой (чтобы могла работать IsObstacle). То есть имеют место перекрестные ссылки. Решается это просто: как минимум, в одном из юнитов ссылка на другой должна будет размещаться разделе uses в implementation, а не в interface. Либо сделать еще лучше: и юнит с картой, и PathFind должны вызываться из какого-то основного юнита. В этом случае только в этом основном юните будут ссылки на оба юнита, в PathFind -- ссылка на юнит с картой, а юниту с картой PathFind вообще не нужен.

3. Значение константы TurnCost подбирайте по своему вкусу. Есть предположение, что если в TurnCost занести значение наибольшего измерения карты (что-то вроде Max(MaqpWidth,MapHeight)), то будет нпайден путь с наименьшим числом поворотов. Доказывать или опровергать данное утверждение мне лениво.

4. Помните, что путь с наименьшим количеством поворотов может быть намного длиннее (если посчитать в клетках), чем путь с большим количеством поворотов. За опитимизацию по некоему успредненному параметру, включающему и длину, и количество поворотов, я не возьмусь. А для разводки проводов это может оказаться важным.

5. Если Вы собираетесь много раз последовательно применять данные функции для построения разводки, то общий результат может существенно зависеть от последовательности выбранных контактов.
 Geo


12-05-2009 08:58
сообщение от автора материала
Ну и втравили Вы меня ;) Ладно, проехали.

Рассматриваем юнит PathFind.

1. В функциях FindPath и MakePathMap выбросить параметр GetCostFunc, то есть объявления будут следующее

function MakePathMap(
  MapWidth,MapHeight : Integer;
  StartX,StartY : Integer) : TPathMap;

function FindPath(
  MapWidth,MapHeight : Integer;
  StartX,StartY,StopX,StopY : Integer;) : TPath;


Соответственно, выбросить из реализации этих функций строку

PathFind.GetCostFunc:=GetCostFunc;


и саму глобальную переменную

GetCostFunc : TGetCostFunc;


Да и тип

TGetCostFunc = Function(X,Y,Direction : Integer) : Integer;


тоже больше не нужен.

2. Функцию GetCost переписываем следующим образом:

const
  TurnCost = 10; // стоимость поворота; выбирайте значение себе по вкусу

function GetCost(X,Y,OldDirection,NewDirection : Integer) : Integer;
begin
//  Direction:=(Direction AND 7); - эта строка и в первоначальной реализации не особо нужна
  Result:=-1; // присвоим сразу типичное значение ошибки, чтобы по IF сразу выходить из функции
  if (X < 0) OR (X >= MapWidth) OR (Y < 0) OR (Y >= MapHeight)
  then
    Exit; // выход за пределы карты
  if IsObstacle(X,Y) // здесь проверка на то, что клетка (X;Y) является препятствием; сделать Вам
  then
    Exit;
  if (NewDirection AND 1) <> 0
  then
    Exit; // нечетные числа -- это движения по диагонали; запрещаем.
  if NewDirection = OldDirection
  then
    Result:=1 // направления совпадают
  else
    if (NewDirection XOR OldDirection) AND 2) <> 0 // это условие поворота
    then
      Result:=TurnCost;
end;


Пояснения к реализации проверки на поворот. После вышибания нечетных чисел для NewDirection у нас остаются только четыре возможных направления: 0, 2, 4, 6. Замечаем, что в числах для горизонтальных направлений (числа 2 и 6) 1-й бит установлен (биты нумеруются с нуля), а ддя вертикальных направлений (числа 0 и 4) 1-й бит сброшен. Операция XOR работает так, что одинаковые биты заменяются нулями, а разные -- единицей. Соответственно, если мы применим опреацию XOR к старому и новому направлениям, то у результата 1-й бит будет установлен, если направление изменилось с горизонтального на вертикальное или с вертикального на горизонтальное, то есть произошел поворот.

3. В процедуре TestNeighbours нужно будет в вызов функции GetCost добавить вызов старого направления (берется из OldWave.Item). Вот так:

  // C:=GetCost(X,Y,D);   было так
  C:=GetCost(X,Y,OldWave.Item.Direction,D); // сделаем так



* * *
Это способ как минимальными затратами привести реализацию к нужному Вам виду. Хотя направшивается потребность существенно переделать, чтобы избежать кучи лишних действий. Например, направления имеет смысл проверять только 4, а не 8. Ну и еще по мелочам.
 Geo


12-05-2009 07:13
Вы сразу бросаетесь кодировать, пытаясь понять, какой бы волшебный оператор вставить, чтобы программа стала работать так, как надо Вам. Иполучается у Вас сущее безобразие, так как этот алгоритм для Ваших целей плохо применим. Почему же сразу плохо применим? Наоборот, очень даже стало классно, когда я ваш код применил в своей программе.
Но это Вы сможете понять только тогда, когда абстрагируетесь от кода и попытаетесь разобраться с принципами рабты самого алгоритма. А именно так и разрабатываются алгоритмы (отсюда и мои аналогии с машинками). А кодирование -- это уже потом.
Это я, слава Богу, тоже понимаю, я и не старался сначала лезть в чужой код - хочу понять что да как.

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

Что можете сделать Вы. Вы можете задать движению с поворотом более выосокую стоимость, чем движению с сохранением направления движения. Например, функция, возвращающая стоимость хода будет возвращать значение 1 для движения с сохранением направления движения, 10 -- для движения с поворотом на 90 градусов в ту или другую сторону, и -1 -- для всех остальных случаев (как я понял, движение по диагонали Вам не требуется, а движение назад не имеет смысла).

Да, именно так я и хочу сделать.

Число 10, кстати, взято от балды. Я только идею подаю, а прорабатывать Вам ее придется самостоятельно. С такой функцией "машинка", двигающаяся по прямой, проскочит 10 клеток прежде, чем повернувшая "машинка" доедет до соседней клетки. Но будет ли найденный таким образом путь путем с минимальным количеством поворотов? Поворотов будет меньше, но за минимальное количество я не поручусь.

А мне и не надо минимальное количество поворотов, надо, просто, чтобы их было меньше. А если увеличить от стоимость поворота от 10 до 100? Тоже не знаю, я не занимался проработкой Вашей задачи. Вы просто не представляете, сколько времени уходит на продумывание, проработку и анализ работы алгоритма. В статье потом, вроде бы, все просто и понятно, а за этими "просто" и "понятно" стоят месяцы работы. Именно поэтому в статье все просто и понятно.
я не профессионал, поэтому действительно, с таким серьезным алгоритмом я пытаюсь разобраться впервые. Хотя могу, конечно, представить. Поэтому я и стараюсь использовать уже наработанные

месяцами работы

решения.


Пардон за лирическое отсутпление.

Вы имеете на него право :)

Итак, Вам нужно изменить функцию, возвращающую стоимость движения указанным выше образом. Для этого ей нужно другие параметры. Чтобы определить наличие поворота Вам, например, потребуется дополнительно предыдущее направление движения.

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

А может быть, Вы захотите передавать признак поворота.

нет, ни к чему. Если абстрагироваться от имеющегося кода, то Вам и координаты, наверное, не нужны (разве что ради препятствий). Ваша стоимость движения определяется только двумя направлениями: предыдущим и новым. Но Вам потребуется и в модуле внести соответствующие изменения, ориентирующие код на работу с другим типовом функции вычисления стоимости. А раз код юнита менять, то можно избавиться от передачи функции извне, так как у Вас стоимость всегда вычисляется одним и тем же сопсобом. То есть, Вы можете всю логику заложить в функции GetCost юнита PathFind.
Это все так, но вы так и не открыли тайны, не направили на путь, помогающий реализовать эту функцию.
Ps [i]Раз уж вы решили создать лирическое отступление, позволю его и я.
Я не программист, в широком смысле этого слова, я инженер, и программки делаю для себя и коллег, появилась задача создать трассировку кабелей, были перепробованы многие варианты, пока я не наткнулся на ваш код, и тут я потерял покой - я пять дней только разбирался как мне прикрутить ваш юнит к своему приложению, что и какая функция делает, правда, до конца так и не понял, но, даже то, что уже получилось - превосходить то, что было в разы. Спасибо.[/i]
Вот такие вот дела.


12-05-2009 03:32
сообщение от автора материала
Вы сразу бросаетесь кодировать, пытаясь понять, какой бы волшебный оператор вставить, чтобы программа стала работать так, как надо Вам. Иполучается у Вас сущее безобразие, так как этот алгоритм для Ваших целей плохо применим. Но это Вы сможете понять только тогда, когда абстрагируетесь от кода и попытаетесь разобраться с принципами рабты самого алгоритма. А именно так и разрабатываются алгоритмы (отсюда и мои аналогии с машинками). А кодирование -- это уже потом.

Данная реализация основана на понятии стоимости хода. То есть у каждого возможного хода имеется некоторая стоимость, а алгоритм пытается найти путь с наименьшей стоимостью. Что можете сделать Вы. Вы можете задать движению с поворотом более выосокую стоимость, чем движению с сохранением направления движения. Например, функция, возвращающая стоимость хода будет возвращать значение 1 для движения с сохранением направления движения, 10 -- для движения с поворотом на 90 градусов в ту или другую сторону, и -1 -- для всех остальных случаев (как я понял, движение по диагонали Вам не требуется, а движение назад не имеет смысла). Число 10, кстати, взято от балды. Я только идею подаю, а прорабатывать Вам ее придется самостоятельно. С такой функцией "машинка", двигающаяся по прямой, проскочит 10 клеток прежде, чем повернувшая "машинка" доедет до соседней клетки. Но будет ли найденный таким образом путь путем с минимальным количеством поворотов? Поворотов будет меньше, но за минимальное количество я не поручусь. А если увеличить от стоимость поворота от 10 до 100? Тоже не знаю, я не занимался проработкой Вашей задачи. Вы просто не представляете, сколько времени уходит на продумывание, проработку и анализ работы алгоритма. В статье потом, вроде бы, все просто и понятно, а за этими "просто" и "понятно" стоят месяцы работы. Именно поэтому в статье все просто и понятно.

Пардон за лирическое отсутпление. Итак, Вам нужно изменить функцию, возвращающую стоимость движения указанным выше образом. Для этого ей нужно другие параметры. Чтобы определить наличие поворота Вам, например, потребуется дополнительно предыдущее направление движения. А может быть, Вы захотите передавать признак поворота. Если абстрагироваться от имеющегося кода, то Вам и координаты, наверное, не нужны (разве что ради препятствий). Ваша стоимость движения определяется только двумя направлениями: предыдущим и новым. Но Вам потребуется и в модуле внести соответствующие изменения, ориентирующие код на работу с другим типовом функции вычисления стоимости. А раз код юнита менять, то можно избавиться от передачи функции извне, так как у Вас стоимость всегда вычисляется одним и тем же сопсобом. То есть, Вы можете всю логику заложить в функции GetCost юнита PathFind.

Вот такие вот дела.
 Geo


12-05-2009 02:36
так как у Вас функция определения стоимости движения для очередного шага будет иметь дополнительный параметр.
Так я и пытаюсь ввести этот дополнительный параметр prevdirection

Только не с банальным вопросом "как сделать", а что-то вроде: "Хочу сделать вот так, пытаюсь реализовать это вот так, но получается почему-то вот этак".

вот я и не могу понять откуда можно получать этот параметр, хотя бы намекните, а работу за себя я делать и не прошу. Уже весь алгоритм вдоль и поперек излазил, и не могу сообразить.
Пробовал делать так

PrevDirection:=OldWave.Item.Direction


но похоже, что неправильно.


12-05-2009 02:11
сообщение от автора материала
Не-а... Не хочу. Это место для обсуждения статьи, а не для ответов на вопросы. А Ваш волпрос требует существенной переработки, так как у Вас функция определения стоимости движения для очередного шага будет иметь дополнительный параметр. Это если навскидку.

У меня нет ни малейшего желания делать за Вас Вашу работу. Если придумаете что-то, но что-то не будет получаться, то добро пожаловать на Круглый Стол. Только не с банальным вопросом "как сделать", а что-то вроде: "Хочу сделать вот так, пытаюсь реализовать это вот так, но получается почему-то вот этак".
 Geo


12-05-2009 02:01
ну неужели никто из гуру не может помочь в этой проблеме? :(


10-05-2009 22:09
[URL=http://ipicture.ru/][IMG]http://pic.ipicture.ru/uploads/090511/nT40SS5TnR.jpg[/IMG][/URL]


10-05-2009 22:05
я так понял, что надо поправить функцию

procedure TestNeighbours;  //проверяем восемь клеток, соседних с клеткой,
var                        // на которую указывает текущий элемент волны.
   X,Y,C,D : Integer;
begin
сс
   for D:=0 to 7 do
     begin
     X:=OldWave.Item.X+DirToDX(D);
     Y:=OldWave.Item.Y+DirToDY(D);
     PrevDirection:=?????
     C:=GetCost(X,Y,D,PrevDirection); // как получить этот PrevDirection


     if (C >= 0) AND (Result[Y,X].Distance < 0) // Если не препятствие и там не
     then                                       // проезжали, то
       NewWave.Add(X,Y,C,D);                    // начинаем движение туда.
     end;
end;


в ней я так понял надо как-то получить PrevDirection и передать в фунцию

function GetCost(X,Y,Direction,PrevDirection : Integer) : Integer;
begin
  Direction:=(Direction AND 7);
  if (X < 0) OR (X >= MapWidth) OR (Y < 0) OR (Y >= MapHeight)
  then
    Result:=-1
  else begin
    Result:=GetCostFunc(X,Y,Direction);
    if Direction<>PevDirection  then    //вот как-то так надо сравнить с направлением
    Result:=Result+1;
end;
end;


Помогите, пожалуйста. А то на схеме получается слишком много поворотов.


08-05-2009 20:42
Спасибо за алгоритм и реализацию. Я пишу аналогичный для строительства дорог AI-игроком в OpenTTD. Легко изменил код для ограничения движения только по горизонтали/вертикали, но есть еще момент, который может пригодиться и другим читателя - потеря скорости на повороте. Т.е. функция GetCost получила еще один параметр - PrevDirection, a TestNeighbour - соответственно теперь его передает.
можно показать как реализовали падение скорости на поворотах? это очень нужная функция - возможно уменьшить количество поворотов.


08-05-2009 02:05
сообщение от автора материала
>>> а, вроде бы понял - извиняюсь за глупый вопрос
То, что вопрос глупый, это мелочь. Главное -- Вы сами нашли, разобрались и поняли ;-)
 Geo


08-05-2009 02:01
а, вроде бы понял - извиняюсь за глупый вопрос-
MovingCost надо было немного поправить и все.


08-05-2009 01:56
так вот и не понятно как эту стоимость-то на движение по диагонали задавать правильно.


08-05-2009 01:05
сообщение от автора материала
О том, как реализовать с минимальными переделками возможность движения только по горизонтали и по вертикали, написано в статье. Тут даже алгоритм менять не надо, надо всего лишь функцию стоимости движения правильную задать.

Можно, конечно, и сам алгоритм поменять, но этого я описывать не буду. Кто хочет, сам разберется и сделает. Там несложно, но понять работу и извилинами пошевелить придется.
 Geo


08-05-2009 00:23
Пожалуйста, напишите, как изменить алгоритм, чтобы возможны были перемещения только по вертикали и горизонатали.
Заранее спасибо, код, правда, классный.


28-11-2007 10:45
сообщение от автора материала
>>> Немного неудачно выполнена сама программа...
Э-э-э... А можно чуть подробнее? Мне же интересно ;-)

Кстати, что Вы понимаете под программой: модуль с реализацией алгоритма или демонстрационный пример? Если демонстрационный пример, то про него я уже здесь в обсуждении говорил, что "Не надо детально рассматривать исходник демонстрационного примера: он написан на скорость"
 Geo


28-11-2007 09:38
Немного неудачно выполнена сама программа... но не будем об этом ^_^. У меня уже была ранее собственная реализация этого алгоритма, но уж очень ресурсоемкая. Переделал эту - результат просто супер!


28-11-2007 09:26
Статья очень интересная, спасибо.


21-10-2007 10:17
сообщение от автора материала
Немного непонятно, можно чуть подробнее? Правильно ли я понял, что Вы в своей модели изменяете скорость движения при изменении направления? То есть, если сначала двигались, допустим, вверх, а следующий ход делаем направо, то скорость падает, так?
 Geo


21-10-2007 06:28
Спасибо за алгоритм и реализацию. Я пишу аналогичный для строительства дорог AI-игроком в OpenTTD. Легко изменил код для ограничения движения только по горизонтали/вертикали, но есть еще момент, который может пригодиться и другим читателя - потеря скорости на повороте. Т.е. функция GetCost получила еще один параметр - PrevDirection, a TestNeighbour - соответственно теперь его передает.


07-12-2005 12:09
сообщение от автора материала
>>> А что же делать если карта не 10х10, а хотя бы 512х512 (еще лучше 1024х1024)?
Ну, во-первых, в моей демке карта не 10х10, а 40х40. К тому же, первый раз я этот адгоритм разрабатывал для карты 112х112. И все работало нормально. Для того чтобы посмотреть скорость работы можете взять демонстрашку, переделать на 512х512 или любые другие размеры и посмотреть, что получится. У меня на дико перегруженном P-III-600 карта путей строилась за 3-4 секунды. В принципе, не такой уж и "тихий час".

Что еще можно сказать об эффективности алгоритмов... Классический алгоитм Дейкстры имеет квадратичную сходимость -- O(n^2). Лучшие алгоритмы, если мне не изменяет память, -- что-то порядка O(n*log(n)). И это очень хороший результат. Особенно, если сравнивать с NP-полными задачами.

Несколько слов о применении к большим картам. Вы просто не сможете видеть на экране целиком карту размерами 1024х1024. Если размер ячейки хотя бы 4х4, то у Вас на экране поместится порядка 200х200. Использовать клетки меньшего размера не имеет смысла, так как ничего не будет видно. Если же Вы будете искать маршрут, скроллируя карту, то у Вас на скроллинг уйдет больше времени, чем на поиск маршрута.

Кстати, хочу обратить Ваше внимание на то, что в моем модуле реализовано два способа поиска. В демонстрашке используется первый, когда сначала строится вся карта путей из заданной точки, а потом просто выбирается нужный. Это сделано потому, что в демонстрашке карта маленькая и возможно такое пижонство, когда выбор маршрута поспевает за движением мышки. Но есть и второй способ, когда карта путей строится только до тех пор, пока не будет найден путь в конечную точку. При наличии больших карт с учетом ограничений на их отображение, второй вариант будет более предпочтительным. Мы просто выбираем объект и кликаем в конечную точку для него. Путь считается только после того, как указаны начальная и конечная точки. И пусть карта будет 1024х1024, но просчитывать в большинстве случаев придется те самые 200х200.

>>> Кроме времени есть еще один аспект - ресурсы. Что с ними-то делать?
А зачем с ними что-то делать? Реализация по отношению к ресурсам не такая уж и жадная. По большому счету ресурсы уходят только на массив. Остальным можно пренебречь. А массив -- это 8 байт на клетку. Для карты
1024х1024 получится 8М, но Вы же собираетесь игру делать. Значит Вам тоже нужна карта. И в более-менее сложной игре расходы памяти будут существенно больше, чем 8 байт на клетку карты.

Кстати, если не секрет, то что Вам показалось неясным? Дело в том, что я данный алгоритм привел только потому, что он более наглядный, более простой в понимании, чем остальные. Именно в расчете на тех людей, у которых могут возникнуть трудности с тем же самым алгоритмом Дейкстры.
 Geo


07-12-2005 09:22
А что же делать если карта не 10х10, а хотя бы 512х512 (еще лучше 1024х1024)?
Ведь начнется тихий час (день, неделя...)
Интересно, реально ли за приемлемое время найти точное решение? Или хотя бы решение с приемлемой (заданной точностью)?

Кроме времени есть еще один аспект - ресурсы. Что с ними-то делать?
К сожелению, нельзя минимизировать и то и другое
Сообщение не подписано


13-09-2005 21:09
сообщение от автора материала
Немного подумал и пришел к выводу, что A* в большинстве случаев будет более эффективным. Уступать волновому алгоритму он будет только в том случае, когда достаточно большой участок правильного пути будет направлен от цели. Соответствено, определение разницы между лабиринтом и "нелабиринтом" можно не приводить :-)
 Geo


13-09-2005 17:40
сообщение от автора материала
>>> Кстати можно машинки обозвать фотонами...))))
Ну, Вы же сами написали, что "школьного курса физики не достаточно". Не так уж и много здесь таких, кто хорошо помнит ВУЗовский курс оптики (разве что, Антон Григорьев; но это, скорее, исключение, чем правило :-)
 Geo


13-09-2005 17:40
сообщение от автора материала
Похоже, что приведенные предложения ("Одна из целей написания статьи -- заставить людей думать головой" и "Мысль была та, что не нужно бросаться использовать готовые универсальные решения, когда ...") были неверно поняты. Попробую объяснить.

Извините за лирическое отступление, но Вам не приходилось читать "Иллюзии" Ричарда Баха? Там автор опровергает одни утверждения (устоявшиеся и незыблемые) и формулирует новые. Но делает он это вовсе не за тем, чтобы навязать новые догмы. Когда опровергают что-то старое и выдвигают новое, человек поневоле начинает спорить, отстаивая привычный ему вариант. А спорить -- это значит думать. Именно это я имел в виду. Сейчас очень много людей привыкли использовать готовые решения (интернет этому способствует). Выдвигая диаметрально потивоположный подход, я пытаюсь заставить этих людей сравнивать два варианта и самостоятельно определять их сильные и слабые стороны. В результате они должны прийти к комбинированному варианту. Если ребенок любит компот, но ненавидит котлеты, то акцентировать внимание на пользе компота не стоит. Нужно доказывать преимущество котлет. А от компота он и так не откажется :-)

>>> Кстати - все таки, какже вас так проняло, чо алгоритм Дейкстры привел вас к "изобретению"  волнового алгоритма?
Вы меня опять неверно поняли. Я наоборот шел от волнового алгоритма. Обобщал его на другие случаи, оптимизировал, а в результате получил некоторые общие моменты с алгоритмом Дейкстры (как верно подметил Trurl).

>>> возможно это и будет самое ценное что мы от Вас узнали по данной теме
Два момента. Во-первых, а кто такие "мы"? Под именем "Борис Телеснин" скрывается целый коллектив (как Бурбаки)? Или Вы -- потомок Николая Романова?

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


13-09-2005 17:39
сообщение от автора материала
>>> Поподробней пожалста- чо то я ничо похожего не увидал....
И кстати, в чем собственно оптимизация?

Уточняю, что имеется в виду именно алгоритм Дейкстры, а не A*. В нем на каждом шаге выбирается та точка среди непройденных, расстояние до которой минимально. У меня получается то же самое, когда я каждый шаг начинаю с той "машинки", которая до своей клетки доедет первой (вместо классической волны, которая равномерно ползет во все стороны). Отличие от Дейкстры: в общем случае на каждом шаге рассматриваются все непройденные клетки. Из всех непройденных клеток ищется минимум. Я же знаю, что на клеточной карте минимум достигается именно в клетках, соседних с фронтом волны. Это позволяет существенно сократить пространство выбора следующей для рассмотрения клетки.

Кстати, именно это делает алгоритм неприменимым для игр, в которых есть телепортация (типа, Heroes of Might and Magic). Хотя в них при поиске оптимального маршрута телепортация тоже не учитывается.

>>> Волновой алгоритм будет более эффективен только в случае если А* обойдет все точки.(это только необходимость)
Ой, ли? Представьте себе карту с препятствием в виде расчески, повернутой зубьями вверх. И Вам надо найти путь сверху вниз между двумя точками, расположенными примерно в середине этой расчески. Сначала преимуществом будет обладать центральный коридор, потом примыкающие к нему и т.д. В конце концов, путь будет найден. Но какой ценой?!

>>> Слабость волнового алгоритма как раз в его сути, то есть в том что иногда приходится "бегать" по одной и той же точке не в силах с нее сойти.
Извините пожалуйста, Вы какой волновой алгоритм рассматриваете? Какой-то классический или приведенный в статье? У меня наличие медленных клеток никак не тормозит процесс поиска. Кстати, в первом варианте реализации машинка из фронта волны снималась, не дожидаясь окончания движения, если за это время другие машинки успевали проехать по всем ее соседним клеткам. В данной реализации этот момент был выброшен для упрощения понимания, так как статья все же писалась для людей с не очень сильной подготовкой.

>>> Что касается пересеченной карты одного типа местности (звучит слегка нелепо),то здесь волновой алгоритм выигрывает только в лабиринте
Вы можете дать строгое определение, чем отличается лабиринт от "нелабиринта"?

Немного теории... "Качество работы алгоритма сильно зависит от качества эвристического приближения h(n). Если h близко к истинной стоимости оставшегося пути, то эффективность будет очень высокой" (http://algolist.manual.ru/maths/graphs/shortpath/smartmove.php). Вот где собака зарыта. Естественно, на слабопересеченной местности A* будет обставлять всех, так как эвристическое приближение (геометрическое расстояние до цели) практически совпадает со стоимостью реального маршрута. В противном случае -- далеко не факт.
 Geo


13-09-2005 11:12
Кстати - аналогия со светом , будет совсем реальной. Ибо свет в различных средах занимается как раз "поиском наименьшего пути", и называется этот факт "принципом наименьшего времени Ферма". При этом аналогия ну проста полная , так как "неуспевшие фотоны" никто никогда не видит...


Правда школьного курса физики не достаточно, осталось только уточнить у создателя идеальный алгоритм...., то есть тот которым пользуются фотоны на самом деле, может они как раз Дейкстру пользуют(шутка) ...

Кстати можно машинки обозвать фотонами...))))

Сообщение не подписано


13-09-2005 09:30
предыдущая месага - моя...

"Одна из целей написания статьи -- заставить людей думать головой"

А зачем им думать, если все так "проста и понятна", да еще и программа работает - только откомпилять?
Странный однакож способ обучения.

"Мысль была та, что не нужно бросаться использовать готовые универсальные решения, когда ... "
Эта мысль также ошибочна, как и прямо противоположная ей (типа - "чтобы вы не делали - все это уже сделано и можна найти в гугле").
Ибо она также безкомпромисна.

Правильная мысль - "всегда стоит спросить гугл, даже если вы сами нашли решение, при этом лучше если решение вы находите все-таки сами".

Кстати - все таки, какже вас так проняло, чо алгоритм Дейкстры привел вас к "изобретению"  волнового алгоритма? .... вот где связь не улавливается... Изложите пожалста цепь рассуждений- возможно это и будет самое ценное что мы от Вас узнали по данной теме...





13-09-2005 09:09
1)"за счет оптимизации получилось в некоторой степени похоже на алгоритм Дейкстры"
Поподробней пожалста- чо то я ничо похожего не увидал....
И кстати, в чем собственно оптимизация?

2) Волновой алгоритм будет более эффективен только в случае если А* обойдет все точки.(это только необходимость)

Слабость волнового алгоритма как раз в его сути, то есть в том что иногда приходится "бегать" по одной и той же точке не в силах с нее сойти. То есть цикл(по точкам фазы) на каждом шаге ему гарантирован. В этом смысле - чем больше точек с "малой скоростью" тем ему хуже. Грубо говоря быстродействие A* может быть выше в порядки раз.
Как раз на картах с "много различных типов территорий".

Что касается пересеченной карты одного типа местности (звучит слегка нелепо),то здесь волновой алгоритм выигрывает только в лабиринте...


Сообщение не подписано


10-09-2005 17:35
сообщение от автора материала
Сначала небольшое лирическое отступление.

Одни мой знакомый как-то писал игру и пожаловался, что никак не может придумать нормальный алгоритм поиска пути, Сказал, что порылся в интернете и решил попробовать алгоритм Дейкстры. Тут меня проняло, и я за ночь сочинил ему алгоритм (основанный на волновом принципе) и накатал демонстрационную программу. Именно тот случай лег в основу данной статьи. Мысль была та, что не нужно бросаться использовать готовые универсальные решения, когда можно чуть-чуть напрячь извилины и получить приемлемый результат для своего конкретного случая.

Позже я оказался на Королевстве и за короткий промежуток времени получил два вопроса, касающихся поиска пути. Отсылки к имеющимся публикациям на эту тему к успеху не привели. Нашел и послал свой старый код, но там я сам сейчас не сразу могу разобраться. Так возникла идея этой статьи. Пришлось аккуратно переписать код, снабдив его подробными комментариями. Был реализован отдельный модуль, который может использоваться в других проектах. Была также реализована идея с картой пути, которую подбросил Александр Широков широко известный в узких кругах под ником Strelok (за что ему отдельное спасибо).

Одна из целей написания статьи -- заставить людей думать головой, а не рыскать в интернете в поисках готовых решений. Именно ради этой цели написано вступление, в котором я (при ближайшем рассмотрении) несколько переборщил.

Теперь по существу. Действительно, за счет оптимизации получилось в некоторой степени похоже на алгоритм Дейкстры, хотя отталкивался я именно от волнового алгоритма. Зато реализация такова, что нет нужды проверять при попадании в клетку минимальность пути: первое попадание гарантированно является минимальным. Кроме того, знание топологии позволяет несколько упростить реализацию алгоритма.

Насчет соотнесения с A*. Насколько я понимаю, этот алгоритм будет более эффективным по сравнению с моим на слабо пересеченной карте. Если же препятствия много либо очень много различных типов территорий, влияющих на скорость движения, то мой алгоритм покажет лучший результат. Кроме того, A* несколько сложнее в понимании. Я с ним детально не разбирался, но есть некоторые сомнения, что он ищет минимальный путь (тут я могу и ошибиться). Мой алгоритм достаточно прост и гарантированно находит минимальный путь, имея при этом достаточно неплохие характеристики.
 Geo


05-09-2005 11:02
Прямо в начале статьи прочитал что:
>А для поиска пути на квадратной сетке наиболее >эффективным является так называемый “волновой >алгоритм”. Так как учитывает особенности
> топологии
(про топологию это я так сократил)
Всязи счем возражение - A* гораздо более учитывает эти особенности и (в зависимости от карты) легко может быть даже более эффективен.

К тому же весь учеть топологии в вашем случае сводится к строке "for D:=0 to 7 do" то есть просто к обходу  всех соседей. Вообще говоря вашему алгоритму просто все равно на каком графе искать путь (с точностью до обхода соседних узлов).

Короче в этих ваших утверждениях - явный перебор


26-08-2005 04:31
сообщение от автора материала
Я плохо помню алгоритм Дейкстры, так что если нужны отличия с точностью до мелочей, то почитайте сами. Основное отличие, как я понимаю, заключается в том, что мы не пытаемся выбрать наиболее оптимальное направление движения на каждои маге, а движемся равномерно во всех направлениях.
 Geo


26-08-2005 04:25
Интересно, а чем описанный алгоритм отличается от алгоритма Дейкстры?


22-07-2005 00:00
Обалдеть! Да... работает...
Прошу прощения за невнимательность.
Огромное спасибо за разъяснения.
Вопросов больше нет :)


21-07-2005 05:37
сообщение от автора материала
Невнимательно читаете описание. Там сказано, что в модели движения, реализованной в демонстрационной программе, при движении по диагонали стоимость перемещения увеличивается в полтора раза.

Второй момент: судя по всему, маршрут движения искался для движения из левого верхнего угла в правый нижний, а не наоборот. Для данной карты это существенно, именно этим обусловлена петля в конце дороги ближе к правому верхнему углу.

Итак, для маршрута, найденного программой:

4*1.5+4+4+4+4+4+4*1.5+4+4+2*1.5+2+2+2+2+4+4*1.5+4+4+4=
=6+4+4+4+4+4+6+4+4+3+2+2+2+2+4+6+4+4+4=73

Для Вашего маршрута:

4*1.5+4+4+4+4+4+4*1.5+4*1.5+6*1.5+2*1.5+2+4*1.5+4*1.5+4+4+4=
=6+4+4+4+4+4+6+6+9+3+2+6+6+4+4+4=76

Для того, чтобы программа нашла Ваш маршрут, откройте в демке файл Main.pas, найдите реализацию функции MovingCost

function MovingCost(X,Y,Direction : Integer) : Integer;
begin
  Result:=TerrainParams[Form1.FData[Y,X].TerrainType].MoveCost;
  if ((Direction AND 1) = 1) AND (Result > 0)
  then
    Result:=Result+(Result SHR 1);
end;



и выбросьте оттуда все, кроме первой строки. Вот так:

function MovingCost(X,Y,Direction : Integer) : Integer;
begin
  Result:=TerrainParams[Form1.FData[Y,X].TerrainType].MoveCost;
end;



После этого домножения на 1.5 при движении по диагонали не будет, и программа найдет Ваш маршрут.
 Geo


21-07-2005 00:31
прошу прощения, ошибся в названии программы не FindPathDemo, а PathFindDemo.


21-07-2005 00:29
Вот еще какой вопрос у меня появился. А программа не ставит целью нахождение САМОГО короткого пути? Например такой массив:
Х, 4, 0, 4, 4, 4, 4, 4
4, 4, 0, 4, 4, 2, 4, 4
4, 4, 0, 4, 6, 2, 4, 4
4, 4, 0, 4, 6, 2, 0, 4
4, 4, 0, 4, 6, 2, 0, 4
4, 4, 0, 4, 6, 2, 0, 4
4, 4, 0, 4, 6, 2, 0, 4
4, 4, 4, 4, 4, 4, 0, Х

где 0 - стена, 2 - дорога 4 - земля, 6 - песок, Х - пункты прибытия и выхода.
Программа FindPathDemo предлагает нам следующий путь:

Х, 4, 0, 4, 4, 4, 4, 4
4, х, 0, 4, 4, 2, 4, 4
4, х, 0, 4, 6, х, х, 4
4, х, 0, 4, 6, х, 0, х
4, х, 0, 4, 6, х, 0, х
4, х, 0, 4, 6, х, 0, х
4, х, 0, 4, 6, х, 0, х
4, 4, х, х, х, 4, 0, Х

Нетрудно посчитать, что время затраченное на данный путь равно 4+4+4+4+4+2+2+2+2+2+4+4+4+4+4+4+4+4+4 = 66
А между тем, самый короткий путь занимает 62 единицы времени и выглядит он следующим образом:

Х, 4, 0, 4, 4, 4, 4, 4
4, х, 0, 4, 4, 2, 4, 4
4, х, 0, 4, 6, 2, х, 4
4, х, 0, 4, 6, х, 0, х
4, х, 0, 4, 6, х, 0, х
4, х, 0, 4, х, 2, 0, х
4, х, 0, х, 6, 2, 0, х
4, 4, х, 4, 4, 4, 0, Х


21-07-2005 00:00
Ух-ты! Здорово!
Спасибо за терпение :)
Ну, чтож, после нескольких прочтений и чертежей на бумаге, кажется разобрался. Пришлось попотеть. Как все хитро-то....


19-07-2005 16:15
сообщение от автора материала
Что-то механизм авторизации иногда сбоит :( Там ограничение по времени что ли?
 Geo


19-07-2005 16:13
Вообще-то я постарался в описании написать как можно более понятно. И откомментировал практически каждую строчку. Объяснить еще понятнее будет затруднительно. Но я попробую еще раз.

Сначала о геометрии. Рассматривается карта с квадратной сеткой. Из каждой клетки возможно выполнить перемещение в одну из восьми соседних клеток (вверх, вниз, влево, вправо и четыре клетки по диагонали).

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

Берем начальную точку и пускаем из нее по одной машинке в каждом возможном направлении (исключаем непроходимые препятствия и край карты). Состояние каждой машинки (направление, в котором она едет, и время, за которое она доедет) представлено одним элементом типа TWaveCell в OldWave -- экземпляре класса TWave, созданном для хранения текущего состояния всех машинок.

Дальше, по идее, мы должны запустить цикл по времени и на каждом шаге цикла проверять, не доехала ли какая-либо машинка до соседней клетки. Но я этот момент упростил: так как за время движения никаких изменений не происходит, то можно рассматривать состояние системы после того, как первая машинка доедет до соседней клетки. Для определения этого промежутка времени служит свойство TWave.MinCost, которое содержит минимальное время, за которое хотя бы одна из имеющихся машинок доедет до своей клетки. Соответственно, перебираем все машинки и смотрим для них значение свойства Cost, хранящего количество единиц времени, оставшееся до того, как машинка доедет до клетки. Если это время больше, чем MinCost, то значит машинка еще не доехала: вычитаем из значения ее поля Cost прошедший интервал времени и заносим новое положение машинки в новую фазу волны (NewWave). Если же это время равно MinCost, то значит по истечении промежутка времени MinCost данная машинка доедет до своей клетки. И вот тут возможны варианты.

Возможно, по этой клетке уже проехали раньше. В этом случае машинка больше не нужна, так как к финишу первой она уже не придет. Ее больше не рассматриваем.

Возможно эта клетка является конечной клеткой. Так как по этой клетке еше никто не проехал, значит маршрут движения данной машинки является минимальным. Остальные машинки можно не рассматривать. Осталось только восставновить маршрут движения машинки-победительницы. Он и будет искомым маршрутом.

Если же первые два случая не подходят, значит мы должны повторить начальные действия алгоритма, рассматривая данную клетку в качестве начальной, то есть выпустить из этой клетки по одной машинке в каждом возможном направлении. Единственное отличие состоит в том, что из перечня возможных направлений исключаются не только направления, ведущие за край карты и в клетку с препятствием, но и направления, ведущие в клетку, по которой уже проехали раньше. Каждая новая машинка заносится в NewWave. Если же окажется, что нет ни одного возможного направления, то эту клетку больше не рассматриваем (тупиковая ветка). После того, как мы перебрали все машинки из OldWave, применяем тот же алгоритм к новой фазе волны. Если же в какой-то момент времени не останется ни одной машинки, значит нужного пути не существует.

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

Вот, собственно говоря, и вся идея алгоритма. Остальное -- реализация. Но если не получается разобраться в реализации, то это говорит о недостаточном владении Паскалем. Тут я уже ничего поделать не могу. Изучай язык.

Да, и еще... Не надо детально рассматривать исходник демонстрационного примера: он написан на скорость и, соответственно, я при этом абсолютно не заботился о том, будет данный пример понятным или нет. Я заботился о читаемости только модуля PathFind.pas.
Сообщение не подписано


18-07-2005 05:41
Все хорошо написано, и пример отлычный - работает. Только вот, не понял я ничего. Нельзя ли на пальцах объяснить как именно приведенный алгоритм работает. Куда машинка в начале едит, что при этом получается, куда потом и все такое... Пытался рассмотреть пример, чуть голову не сломал, и вроде просто все, а ничего понять не могу. Уж простите меня невдалого, очень хочется знать как же эти машинки-то до цели добираются.


30-03-2005 02:16
сообщение от автора материала
Спасибо за добрые слова.

Всем почему-то нравится аналогия с машинками. А аналогия была введена от безысходности и долго-долго выдумывалась. Иначе просто невозможно объяснить, почему, если стоимость движения для разных клеток может отличаться, то не получится просто помечать граничные точки.
 Geo


30-03-2005 02:07
Статья содержит готовый модуль для использования, причем сделан модуль довольно гибким и понятным.
Огромный плюс - наличие уместных комментариев.
З.Ы. Еще понравилась аналогия между волновым поиском пути и толпой машинок:)


Добавьте свое cообщение

Вашe имя:  [Войти]
Ваш адрес (e-mail):На Королевстве все адреса защищаются от спам-роботов
контрольный вопрос:
Кто съел Красную шапочку?
в качестве ответа на вопрос или загадку следует давать только одно слово в именительном падеже и именно в такой форме, как оно используется в оригинале.
Надоело отвечать на странные вопросы? Зарегистрируйтесь на сайте.

Оценка содержания
 
Содержит полезные и(или) интересные сведения
 
Ничего особенно нового и интересного
 
Написано неверно (обязательно укажите почему)


Оценка стиля изложения
 
Все понятно, материал читается легко
 
Есть неясности в изложении
 
Непонятно написано, трудно читается

Текст:
Жирный шрифт  Наклонный шрифт  Подчеркнутый шрифт  Выравнивание по центру  Список  Заголовок  Разделительная линия  Код  Маленький шрифт  Крупный шрифт  Цитирование блока текста  Строчное цитирование
  • вопрос Круглого стола № XXX

  • вопрос № YYY в тесте № XXX Рыцарской Квинтаны

  • сообщение № YYY в теме № XXX Базарной площади
  • обсуждение темы № YYY Базарной площади
  •  
     Правила оформления сообщений на Королевстве
      
    Время на сайте: GMT минус 5 часов

    Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter.
    Функция может не работать в некоторых версиях броузеров.

    Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
    Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

     
    © При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
    Все используемые на сайте торговые марки являются собственностью их производителей.

    Яндекс цитирования