Глава 12. Поиск пути

Краткий обзор

Вы когда нибудь думали о том, что требуется чтобы из пункта А попасть в пункт В? Просыпались ли вы когда-нибудь в 6 утра, с ужасной головной болью, думая о том, как вы попали в пункт С? Решение этой, кажущейся на первый взгляд элементарной, задачи достаточно сложно. Хотя существует много способов снять шкуру с кошки, не все они одинаковы. Одни методы требуют больших вычислительных мощностей, а другие дольше выполняются. Ключ здесь — соблюдение баланса между скоростью и использованием процессора. Чтобы помочь вам принять обоснованное решение, относительно того, какой метод использовать, я рассмотрю в этой главе следующие темы:

• Задача поиска пути.
• Простое решение.
• Поиск пути по алгоритму A*.
• Реализация в коде.