Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Цуканов Б.И. "Время в психике человека" (Медицина)

Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Яблоков Н.П. "Криминалистика" (Юриспруденция)
Реклама

Секреты разработки игр в Macromedia Flash MX - Макар Дж.

Макар Дж. Секреты разработки игр в Macromedia Flash MX — М.: КУДИЦ-ОБРАЗ , 2004. — 608 c.
ISBN 0-201-77021-0
Скачать (прямая ссылка): sekretirazrabotkiigr2004.djvu
Предыдущая << 1 .. 76 77 78 79 80 81 < 82 > 83 84 85 86 87 88 .. 210 >> Следующая

ния, мы выбираем расстояние. Другими системами измерения могут быть в
Щ*ва 9. Искусственный интеллект
245
я поиска пути, занимающего кратчайшее время на прохождение) или ко игн
о канистр бензина (для поиска пути, на который требуется минимальное
ш Ь не топлива для автомобиля). Стоимости перемещения между одной плиткой
I се вертикальным или горизонтальным соседом мы будем присваивать значе-
мс, равное 1 (1 фут, 1 миля, 1 плитка - не имеет значения). Стоимость
перемещения между одной плиткой и соседней по диагонали составляет 1.41.
Число . II представляет собой дистанцию между центрами двух соседних
плиток ж* чиагонали.
Эвристика представляет собой лучшее предположение, как далеко центр тещей
плитки (которую вы проверяете при поиске) находится от плитки назна-Ьиия.
Вы можете сделать это предположение довольно просто, используя про-|г ю
логику. После посещения каждому узлу назначается значение счета f.
I f - g + h
¦мчепие h представляет собой эвристику - лучшее предположение о
расстоянии ^ еду этой плиткой и целью. Значение g представляет собой
сумму счета каждого ia, посещенного вдоль пути к текущему узлу. Это может
быть наилучшим обра-1 понято по аналогии. Скажем, вы планируете поездку
из Нью-Йорка в Париж. i ограничены в бюджете, поэтому вы хотите найти
путь, который будет наименее ¦рогим. Вы можете представить Нью-Йорк,
Лондон, Лиссабон, Брюссель, Мадрид | 11ариж в качестве узлов. В процессе
вашего исследования вы вычисляете стои-Ьс гь от Нью-Йорка до Лондона и
сохраняете ее. Но вы также рассчитываете стоить путешествия из Лиссабона
до Нью-Йорка, из Лондона в Париж, и так далее. | конце, если вы
применяете другие правила (еще не обсужденные) с алгоритмом
* вы находите лучший путь (по стоимости). Давайте предположим, что
этот путь ||>олегает через Нью-Йорк - Мадрид - Лондон - Париж. В Нью-
Йорке (как для всех ов) f - g + h. Помните, что g представляет собой
сумму всех / из предыдущих ов. Поскольку Нью-Йорк является начальным
узлом, не имеющим родительских ов, то в Нью-Йорке g=0. Для Мадрида также
f = g + h (как для всех узлов), ом случае g не равно 0, потому что Мадрид
был посещен из другого узла. Зна-рине g включает f из Нью-Йорка. Таким
образом, g является общей стоимостью ¦юега до текущего узла. Если бы вы
действительно отправились в это путешест-bi , то g было бы значением
потраченной суммы денег до вашего текущего места вождения.
В этом месте следует упомянуть одну из наиболее удивительных особенно-и
алгоритма А* - метод, которым он обрабатывает физические особенности
тпости. Выше я сказал, что стоимость прохождения от одной плитки к дру-п
равна 1 или 1.41. Это истинно для всех плиток равного размера, но это вы-
246
Часть 2. Исследование cJ
оказывание не всегда истинно. Скажем, некоторые из плиток сделаны из вой
Вы, вероятно, не хотите послать вашего персонажа через воду, если это не
яв/ ется абсолютно необходимым. Так что вы присваиваете значение, скажем
I любому переходу узла (перемещению из одного узла в другой), который
испо* зует воду. Это не гарантирует, что путь не будет проходить через
воду. Но Г даст исключительное предпочтение путям, которые не проходят по
воде, вода представляет собой поток, полностью пересекающий карту и через
него i моста, то алгоритм А* в конечном счете дает вам путь через воду.
Однако е" есть мост и он достаточно близко, то А* даст вам путь,
включающий в со. мост. С другой стороны, если ваш персонаж является
наполовину человек! а наполовину рыбой, то он может предпочесть воду. В
этом случае вы мож дать для суши меньшую стоимость, чем для воды. Держа
все это в голо: я должен, вероятно, изменить мое первоначальное
утверждение, что А* всеп ищет кратчайший путь. Теперь, когда вы знаете
больше, я могу дополнител определить, что А* будет всегда находить путь с
наименьшим счетом. Во м гих случаях (таких, как эти карты, в которых нет
изменений местности, подоП1 реализациям, использованным позднее в данном
разделе) путь с наименьш счетом также приводит к кратчайшему пути.
Разъяснение А*, почти на обычном языке
Давайте посмотрим на сам алгоритм на псевдокоде.
1 AStar.Search
2 create open array
3 create closed array
4 s . g = 0
5 s.h = findHeuristic( s.x, s.у )
6 s.f=s.g+s.h
7 s.parent = null
8 push s into open array
9 set keepSearching to true
10 while keepSearching
11 pop node n from open
12 if n is the goal node
13 build path from start to finish
14 set keepSearching to false
15 for each neighbor m of n
16 newg = n.g + cost( n, newx, newy )
17 if m has not been visited
18 m.g = n . f
19 m.h = findHeuristic( newx, newy )
20 m.f=m.g+m.h
21 m..parent = n
ыва 9 Искусственный интеллект
247
22
23
24
else
add it to the open array sort the open array
if newg < m.g
26
27
m. parent = n
m. g
newg
28
29
m . f' = m.g + m.h sort the open array if m is in closed
30
31
32
33
34
35
push n into the closed array if search time > max time set keepSearching
Предыдущая << 1 .. 76 77 78 79 80 81 < 82 > 83 84 85 86 87 88 .. 210 >> Следующая