Программирование игр для Windows. Советы профессионала

       

Алгоритмы Поиска. Выслеживание игрока


«Мозги», которые мы сконструировали, получились достаточно умными, так что существо даже получило шанс выжить- И теперь я хочу поговорить о другой довольно простой вещи — как должен быть организован поиск.

Вспомним историю Тезея с Минотавром. Жил когда-то давным-давно Минотавр (человек с головой быка), который преследовал Тезея. В общем, Тезей украл у Минотавра... не помню точно — CD-ROM, или что-то там еще... Тезей попал в ловушку (в действительности, подрядчик, построивший ее, называл ее лабиринтом), но успел выбраться наружу прежде, чем Минотавр его настиг. Вопрос состоит в том, как нужно двигаться по лабиринту, чтобы найти путь к выходу или любой произвольной точке лабиринта, и при этом не застрять в нем навсегда? Давайте взглянем на рисунок 13.8, где изображен пример лабиринта. Существует простой алгоритм, обозначенный здесь как Алгоритм 13.7, который поможет вам найти выход из любого лабиринта. Будьте внимательны, в один прекрасный момент он может вам сильно пригодиться!

Алгоритм 13.7. Путь наружу.

do {

Двигайтесь вдоль правой стены

если встретился проход,

поверните направо

если попали в тупик,

развернитесь на 180 градусов

}пока не выйдете из лабиринта

Этот алгоритм работает безупречно: попробуйте его у себя дома. Стартуйте из любого угла вашей квартиры и следуйте алгоритму. Возможно, при известных обстоятельствах вы даже найдете путь к каждой двери.

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



Содержание раздела