Нахождение самой длинной сетки пути

Question

Я работаю с сеткой равномерной стоимости, которая позволяет только движения в ортогональных направлениях. Это используется в качестве основы для игры змея, где змея должна постоянно двигаться и пытаться съесть яблоки на доске. Расположение пищи и предотвращение столкновений выполняется с использованием классического алгоритма AStar, чтобы найти кратчайший путь между головой змеи и пищей. Тем не менее, этот метод иногда приводит к тому, что змея едет за едой, из-за чего у нее нет четкого пути к следующей еде. Змея оказывается застрявшей в прямоугольнике неправильной формы и не имеет будущего моделирования в этой точке.

Мой вопрос таков: есть ли способ найти самую длинную цепочку ходов внутри неправильного прямоугольника, чтобы дольше оставаться в живых и, возможно, хвост змеи перестал блокировать путь к следующей еде? Я посмотрел на алгоритмы Гамильтона, чтобы попытаться посетить все узлы, но кажется, что нет решения для неправильных форм. Решение не обязательно должно быть идеальным, но оно всегда должно пытаться дать змее наилучший шанс вырваться из ловушки.

Какие-нибудь мысли?

Answer 1

board[][] (Рассмотрим доску как двумерный массив)

Теперь пометьте доску [i][j] = 'S' для клеток, занятых вашими змеями

пустое место для свободных клеток

теперь ваш A* должен дать вам путь от головы вашей змеи к еде. Отметьте все ячейки на этом пути как "#". (Необязательно: Снимите n-1 количество 'S' клеток с хвоста змеи, где n - кратчайший путь от головы змеи до еды. Это потому, что после n шагов хвост змеи также переместился бы)

Теперь для всех будущих позиций (возьмите около 10 случайных точек на доске) посмотрите, сможете ли вы достичь всех этих позиций из позиции еды, используя только пустые ячейки. (Вы можете сделать это в одной DFS). Если вы можете посетить, тогда безопасно использовать выбранный вами путь. В противном случае выберите другой путь.