Каталог решений - Искусственный интеллект для змейки. Часть 1: Кратчайший/длиннейший путь, Гамильтонов цикл

В этой статье я хочу показать различные подходы к решению классической игры Змейка (Источник идеи статьи). Думаю, правила и цель игры всем известны.

 1. Кратчайший путь. Поиск в ширину (Breadth-first search) Вики

Представим поле игры в виде графа. Каждая ячейка поля связана как минимум с 2-мя соседями. Таким образом, перебирая соседей можно найти ячейку с "едой". А после восстановить путь по которому мы до нее дошли. 

Поиск в ширину — один из методов обхода графа. Заключается в том, что сначала рассматриваются все подчиненные узлы одного уровня, а после все подчиненные подчиненных и т.д. Под узлом понимается адрес ячейки со ссылкой на "Родителя" (ячейку через которую мы добрались до узла).

Примерный алгоритм действий:

1. Создать пустой стек и поместить в него узел-источник
2. Пока стек не пустой извлекать по одному узлу с вершины стека
3. Проверить не является ли текущий узел целевым. Если да, то завершить поиск.
4. Перебрать все подчиненные узлы, которые еще не были просмотрены. Добавить их в конец стека и пометить как просмотренные.

Алгоритм отлично работает до тех пор пока "хвост" змеи не начинает перекрывать кратчайший путь.

Серым цветом выделен рассчитанный путь.