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

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

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

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

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

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

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

этим горитмом и провести вас через него.
Search!
search time (ms): |3678
Алгоритм поиска пути А* ищет путь из точки А в точку В
На иллюстрации выше вы можете видеть основное применение алгори! А*. То,
что вы видите, представляет собой сетку 20 20. Белые ячейки являй*
пустыми. Черные ячейки содержат стены. Серая ячейка в верхнем левом yif
(точка А) является начальной позицией персонажа; темно-серая ячейка в ш
нем правом углу (точка В) является конечным положением персонажа. Све
серый путь, соединяющий эти две точки, является путем, созданным алгор
мом поиска пути А*.
>ва 9. Искусственный интеллект
243
От всего попахивает алгоритмом А*
пдеоигры являются индустрией, в которой крутятся многие миллиарды дол-
|ров. Так что вы можете представить, как много денег было потрачено
попытки найти лучшие и быстрые алгоритмы поиска пути. В конце концов, мо
многочисленные разновидности А*. Эти разновидности обычно являются :•
'зультатом оптимизаций и модификаций алгоритма А*. В этом разделе мы It
предлагаем никаких оптимизаций или значительных модификаций алгоритма А*;
мы представляем его в базовой форме.
;1горитм А*
I шако, прежде чем мы продолжим погружаться в детали алгоритма, вам нужно
и гь еше несколько вещей о том, как мы собираемся действовать и какими :ч
чствами. Я написал реализацию алгоритма А* на ActionScript и включил два
•I ила примера на CD, которые используют этот код ActionScript, - но я не
буду ! т.яснять код ActionScript строка за строкой; вместо этого я
собираюсь расска-пь вам, как использовать то, что я создал. Я рассмотрю в
деталях сам алго-IIIM, используя псевдокод, и затем сделаю некоторые
общие ссылки и ActionScript. Псевдокод является представлением алгоритма
в кодоподобной iipMe (вид типа наброска главы). Это означает, что вы
должны сделать код без 1'идания ему специфического синтаксиса. Это
означает, что ваш псевдокод I зависит от особенностей языка; Java-
программисты, программисты a ActionScript, программисты на C++ - любые
программисты могут читать понимать его. Одна из прелестей псевдо-кода
состоит в том, что он имеет тен-сицию быть довольно коротким. Например,
псевдокод, использованный здесь, гавляет всего лишь 30 строк, но
алгоритм, написанный на ActionScript, со-гржит около 170 строк. В псевдо-
коде вы могли бы иметь строку, которая ин-прмирует читателя об удалении
элемента из массива, но в реальном коде вы >'лжны были бы проходить в
цикле через массив для поиска элемента и после-N ющего удаления его, что
потребовало бы несколько строк кода. а. Я изучил алгоритм А* на
псевдокоде, найденном на gamasutra.com iMlf (см. Дополнение Е для ссылок
по поиску пути). Мой псевдокод алгоритма А* подобен тому, что я нашел на
Gamasutra (www.gamasutra.com), но не тот же самый. Если два человека
садятся и пишут набросок сценария для Звездных войн: Эпизод 2, эти
наброски, вероятно, будут иметь одинаковое содержание, но различаться в
деталях. То же самое здесь: есть два различных описания одного алгоритма.
244
Часть 2. Исследование о
Разветвление поиска пути
Хотя первоначально он использовался для поиска пути, алгоритм А* в дейст
тельности имеет более общее назначение. Вы можете использовать его для ш
иска решений многих видов проблем. Мое понимание А* в применеш: к поиску
пути является довольно твердым, но мое общее понимание А* отно тельно
других его применений является, ну, в общем, незначительным. Если
интересуетесь использованием алгоритма А* для задач, отличающихся от по
ка пути, вы можете, вероятно, найти большое количество ресурсов на са" в
Интернет, чтобы получить дополнительную помощь в этом вопросе.
Основная терминология и функциональность алгоритма А*
Как многие основанные на математике концепции, алгоритм поиска пути А*
пользует набор терминов, с которыми вы должны познакомиться в процессе
рассмотрения. Эти термины описывают состояния, действия и результаты, к
рые следуют за этим процессом.
• Узел представляет текущее состояние системы. В поиске пути текущее
j стояние - это просто плитка, которую мы проверяем в данный мом В
дальнейшем нашем рассмотрении узел является плиткой.
• Действие раскрывания узла означает, что (в коде) вы посещаете
каждого I седа узла.
• Эвристикой в А* называется тренировочная гипотеза, основанная на
выб[ пой единице измерения, которая дает в результате число. (Это
довольно определенно, правда? Мы еще поговорим об эвристике позднее.)
• Стоимость является числовым значением, которое мы назначаем дсйс
перемещения от одного узла к другому.
• Счет представляет собой сумму стоимости и эвристики в каждом узле,
к рый вы посетили на пути к текущему узлу.
Используя эти термины, давайте посмотрим, как они применяются в ал гори
и, более обобщенно, как работает алгоритм А*. Как вы теперь знаете, A*
hi кратчайший путь между двумя точками. Но какую систему измерения мы
пользуем? Время? Расстояние? Число шагов? В то время как А* может быть
пользован для поиска в соответствии с наиболее подходящей системой изм
Предыдущая << 1 .. 75 76 77 78 79 80 < 81 > 82 83 84 85 86 87 .. 210 >> Следующая