От всего попахивает алгоритмом A*
Видео игры являются индустрией, в которой крутятся многие миллиарды долларов. Так что вы можете представить, как много денег было потрачено на попытки найти лучшие и быстрые алгоритмы поиска пути. В конце концов, это многочисленные разновидности A*. Эти разновидности обычно являются результатом оптимизаций и модификаций алгоритма A*. В этом разделе мы не предлагаем никаких оптимизаций или значительных модификаций алгоритма A*; мы представляем его в базовой форме.
Алгоритм A*
Однако, прежде чем мы продолжим погружаться в детали алгоритма вам нужно знать еще несколько вещей о том, как мы собираемся действовать и какими средствами. Я написал реализацию алгоритма A* на ActionScript и включил два файла примера на CD, которые используют этот код ActionScript – но я не буду объяснять код ActionScript строка за строкой; вместо этого я собираюсь рассказать вам как использовать то, что я создал. Я рассмотрю в деталях сам алгоритм, используя псевдо-код, и затем сделаю некоторые общие ссылки на ActionScript. Псевдокод является представлением алгоритма в кодо-подобной форме (вид типа наброска главы). Это означает, что вы должны сделать кода без придания ему специфического синтаксиса. Это означает, что ваш псевдо-код не зависит от особенностей языка; Java-программисты, программисты на ActionScript, программисты на C++ - любые программисты могут читать и понимать его. Одна из прелестей псевдо-кода состоит в том, что он имеет тенденцию быть довольно коротким. Например, псевдо-код, использованный здесь, составляет всего лишь 30 строк, но алгоритм, написанный на ActionScript содержит около 170 строк. В псевдо-коде вы могли бы иметь строку, которая информирует читателя об удалении элемента из массива, но в реальном коде вы должны были бы проходить в цикле через массив для поиска элемента и последующего удаления его, что потребовало бы несколько строк кода.
Я изучил алгоритм A* на псевдо-коде, найденном на gamasutra
Русская версия