netlib.narod.ru< Назад | Оглавление | Далее >

Простое решение

Простейшее решение задачи, изображенной на рис. 12.1 можно записать в виде следующего псевдокода:

Если мы слева от цели, перемещаемся вправо
Если мы справа от цели, перемещаемся влево
Если мы выше цели, перемещаемся вниз
Если мы ниже цели, перемещаемся вверх

Если вы будете следовать приведенному выше псевдокоду, то первый шаг на приведенной в примере карте будет выглядеть так, как показано на рис. 12.2.


Рис. 12.2. Работа простого алгоритма поиска пути

Рис. 12.2. Работа простого алгоритма поиска пути


На рис. 12.2 вы проверяете местоположение игрока и, выяснив, что он находится слева от цели, перемещаете его вправо на одну клетку. Этот процесс повторяется, пока вы не достигнете цели, как показано на рис. 12.3.


Рис. 12.3. Общее решение проблемы поиска пути

Рис. 12.3. Общее решение проблемы поиска пути


На рис. 12.3 видно, как псевдокод помог нам достичь цели. Каждый раз код выполнял проверку и обнаруживал, что игрок находится слева от цели. В результате программа перемещала игрока на один квадрат вправо, пока он не достиг цели. Замечательный результат, но что произойдет, если карта будет выглядеть так, как показано на рис. 12.4?


Рис. 12.4. Более сложный путь

Рис. 12.4. Более сложный путь


Путь на рис. 12.4 несколько сложнее. Здесь между начальным и конечным пунктами расположено небольшое препятствие. Насколько хорошо простой код справляется с этой проблемой? Не так хорошо, как хотелось бы. Простое решение замечательно начинает работу, но терпит полную неудачу как только сталкивается со стеной. Вы можете попробовать несколько способов справиться с этой проблемой, например, такой:

Пока не достигли цели
   Если мы слева от цели, перемещаемся вправо
   Если мы справа от цели, перемещаемся влево
   Если мы выше цели, перемещаемся вниз
   Если мы ниже цели, перемещаемся вверх
   Если путь заблокирован, перемещаемся в случайном направлении
Конец цикла

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


netlib.narod.ru< Назад | Оглавление | Далее >

Сайт управляется системой uCoz