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

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

 

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

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

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

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

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

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

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

 

2. Поиск в глубину (Depth-first search) Вики

Другой способ обхода графа, который ,как правило, будет приводить к более запутанному и сложному пути.

Поиск в глубину отличается тем, что сначала рассматриваются максимально далекие подчиненные текущего узла. 

Отличие алгоритма от поиска в ширину будет минимальным: на шаге 2 берем узел не с вершины, а со дна стека.

3. Длиннейший путь

Если наша цель максимизировать количество очков, то можно удлинить путь к еде включая в него максимальное число соседних узлов.

Для этого получим кратчайший путь (поиском в ширину) и будем рассматривать каждые 2 узла пути. Если есть возможность, то включаем в путь 2 соседних.Повторяем упражнение пока расширение возможно.

 

Результат увеличился, тем не менее, хвост все еще продолжает мешать.

4. Гамильтонов цикл Вики

Гамильтонов цикл — замкнутый цикл, который проходит через каждую вершину графа по одному разу.

Если нас не волнует количество шагов, то можно посчитать длиннейший путь не к еде, а к хвосту. Т.к. длиннейший путь проходит по большинству ячеек поля, то еда будет съедена по пути, не зависимо от ее расположения.

В зависимости от расположения змеи могут образовываться недостижимые ячейки, поэтому, строго говоря,  данный алгоритм не соответствует определению Гамильтонова цикла.

5. Гамильтонов цикл 2

Самый простой алгоритм из описанных, обладает 100% эффективностью и не требует никаких расчетов.

Подойдет для любого прямоугольного поля на котором нет препятствий.

Если нас действительно не волнует число шагов, то можно просто ходить по зацикленному пути:

 

Обработка протестирована на 8.3.12.1595, 8.3.12.1855