A*

Может мне кто-нибудь по-человечески
объяснить алгоритм A*.
А то я прочитал перевод статьи
Smart Moves и нефига непонял.

А о какой именно статье идет речь?

http://algolist.manual.ru/games/smartmove.php
Алгоритмы поиска пути.

Попробуй вот это почитать (более понятно, имхо): http://pmg-ru.narod.ru/russian/navigato.htm (и на этом-же сайте прочие статьи, там есть ещё по теме)..

[tt] Пусть надо пройти от A до B. Нам необходим массив направлений такого
же размера что и карта с ландшафтом. Так же необходимо иметь два
списка с координатами (X,Y) свободных секций карты. Количество
элементов в них зависит от размера карты. Представьте себе, что Вы
стоите в точке A и льете воду. Вода постепенно заполняет все
свободные секции и Вы запоминаете координаты этих секций, и то откуда
на эти секции пролилась вода. Когда вода достигнет точки B, можно
узнать откуда она пролилась на точку B, и так возвращаясь Вы
достигаете точки A.
1. Добавить позицию A в список 1.

 2. Установить текущим список 1.

 3. Вокруг текущей точки в текущем списке ищите секции по
    специальному звездообразному шаблону: Вверх, Вправо, Вниз,
    Влево, Вверх-Влево, Вверх-Вправо, Вниз-Вправо, Вниз-Влево.

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

 5. Повторяйте пункты 3-4 до тех пор пока все свободные ячейки
    относительно текущей позиции не будут добавлены в текущий
    список.

 6. Повторяйте пункты 3-5 до тех пор, пока все координаты в текущем
    списке не будут оценены.

 7. Замените текущий список на другой ( инвертируя выбор текущего
    списка ).

 8. Повторяйте пункты 3-7 до тех пор, пока точка B не будет
    достигнута.

 9. Вернитесь из точки B в точку A с использованием массива
    направлений по найденому маршруту.[/tt]

Всеравно непонятно
Что тут подразумевается под списком.
Я непонял зачем иметь именно ДВА списка.
Ещё вопрос по пункту 6 что значит "оценены".
Пока всё.

оба эти два примера не удачны

посмотри на английском a* informed search lection ppt

Я перестал читать после А* самый оптимальный
правда они забыли про Ida* SMA*

Цитата

оба эти два примера не удачны
 
посмотри на английском a* informed search lection ppt
 
Я перестал читать после А* самый оптимальный
правда они забыли про Ida* SMA*

2 esperanto
Ух ты как круто
Человек по русски не врубаеться а ты его
хочешь отправить английские доки читать - оригинально.
Кроме того где это искать - "a* informed search lection ppt ".
Я посмотрел по поисковикам  и ничего не нашёл.

Цитата Mixxx, 28.06.03, 21:17:03

2 esperanto
Ух ты как круто
1) Человек по русски не врубаеться а ты его
хочешь отправить английские доки читать - оригинально.

2)Кроме того где это искать - "a* informed search lection ppt ".
Я посмотрел по поисковикам  и ничего не нашёл.

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

2) кто ищет тот всегда найдет гуугл Z.B
  http://www.creighton.edu/~davereed/csc650.S02/Lectures/search.ppt

посмотри тут
а проблема тут на мой взгляд в том что самую удачную книгу по ИИ еще не перевели на русский, да и вообще по проблематики их мало на русском

Вообще-то с английским у меня очень плохо - в школе учил немецкий
Ну хорошо, черт с ней с  этой А -звёздочкой.
Задам вопрос более общо:
Какой алгоритм лучше применить
для поиска пути в игрушке (с  матрицей 24*40  )
и какова его идея  (желательно поподробнее)
Может быть какую-нибудь модификацию волнового алгоритма предложите?

Попробуй это: http://pub1.nm.ru/pub/pascal/MOVING.ZIP

Для 24х40 волновой алгортим с буфером фронтов волны подойдёт - тормозить не будет. Фронт - это когда на каждой итерации просматривается не весь буфер для распостранения волны, а только те клетки, что были заполнены в предыдущей итерации (существенно повышает скорость).

2 Jin X Красивая прога
2 All
Если оставить как у Jin X то трудоёмкость
кубическая если сделать так как предлагает
Shiru_Otaku  то трудоёмкость упадёт до квадратной
но это всеравно много (В моей игрушке события быстро развиваються);
Как сделать ещё быстрее.

Я использовал то что предлагаю в игре типа lode runner, для того чтобы враги бегали за игроком. При 10-ке врагов на пне-100 игра не тормозила. Просто не надо вызывать поиск пути каждый кадр...

Цитата

Я использовал то что предлагаю в игре типа lode runner, для того чтобы враги бегали за игроком. При 10-ке врагов на пне-100 игра не тормозила. Просто не надо вызывать поиск пути каждый кадр..

Ну дык, lode runner там проходимых клеток гораздо меньше чем непроходимых.
По воздуху же человечки летать немогут.
А в моей игре проходимых клеток обычно намного больше  чем непроходимых.
Кроме того - как ты узнавал в какой момент  надо вызывать алгоритм поиска
ведь преследуемый человечек быстро бегает.

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

Цитата

Для вызова поиска пути использовалось что-то типа вейпоинтов..

А поподробнее и что такое  вейпоинт?

а я зато же изобрёл волновой алгоритм ещё год назад, я тогда ещё не знал о том, что его изобрели до меня, можешь посмотреть как он работает: http://wormball.narod.ru/tmtworms.rar
только надо поставить active ball в true и нажать start, тогда змейки будут стремиться к твёрдым знакам.

Его, по-моему, каждый кто сталкивался с проблемами поиска пути, изобретал:)

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

Рекомендую попробовать, т.к. реализация всей программы - около 20-30 строчек...