1

Змейка отлажена. Пишу бота для своей игры змейка. Для поиска пути использую волновой алгоритм. Волновой алгоритм успешно справляется с поиском пути.

введите сюда описание изображения

Проблемы: Когда змейка наберет достаточный размер и съест еду, после которого змейка оказывается в тупике. Волновой алгоритм уже не подходит, так как нет пути до еды.

введите сюда описание изображения

Для решения нужно:

  1. Предупредить попадание в тупик.

  2. Если уже попал, то найти выход из тупика.

Подскажите алгоритм предупреждения попадания в тупик.

Пока придуман плановый алгоритм для поиска пути.

private Путь ПоискПути()
{

    Путь кратчайшийПуть = ПоискКратчайшегоПути();
    if (кратчайшийПуть != null)
    {
        bool результат = false;
        результат = ПрогнозТупика(кратчайшийПуть);
        if (!результат)
            return кратчайшийПуть;
        else
        {
            Путь путь = НайтиОбходнойПуть();
            if (путь != null)
            {
                return путь;
            }
            else
            {
                return null;
            }
        }
    }
    // в тупике
    else
    {
        Путь путь = НайтиВыходИзТупика();
        if (путь != null)
        {
           return путь;
        }
        else
        {
           return null; 
        }
    }

}

Кому интересен сам проект, ссылка на GitHub

6
  • а не достаточно ли будет просто пересчитывать преграды,включая туда саму змейку? 22 янв 2018 в 10:19
  • ...if (путь != null) { return путь; } else { return null; }, что правда?
    – Ev_Hyper
    22 янв 2018 в 22:37
  • @EV_Hyper, это написано, чтобы вместо null в будущем добавить дополнительный метод поиска. По хорошему туда вызовы исключения добавить надо
    – CuprumBur
    23 янв 2018 в 4:07
  • @РагнарТолстов, тело змейки при просчете пути является преградой. Периодически возникает ситуация, когда следующий шаг, после поедания, ведет в тупик, из которого уже нет выхода
    – CuprumBur
    23 янв 2018 в 5:00
  • Как успехи?.... 26 янв 2018 в 14:19

3 ответа 3

4

Что такое тупик? Тупик это часть пространства с наименьшей площадью.

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

По возможности ещё смотреть будет ли разбиение пространства при определённом ходе, и по возможности избегать разбиений.

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

10
  • тупик - часть пространства игры, из которого нет пути.
    – CuprumBur
    20 янв 2018 в 19:59
  • @CuprumBur пути куда? 20 янв 2018 в 20:01
  • Пути до еды. Каждый ход змейки - это шаг к еде. Без пути до еды, нет пути
    – CuprumBur
    20 янв 2018 в 20:04
  • @CuprumBur Тогда выбирайте ту сторону где больше еды и где больше свободного места. 20 янв 2018 в 20:04
  • Попробую, у Вас будут еще рекомендации для улучшения алгоритма?
    – CuprumBur
    20 янв 2018 в 20:07
1

Сделать функцию хорошести f позиции в зависимости от выбора. То есть при каждом варианте выбора эта функция будет расчитываться.

Эта функция будет состоять из набора модулей (подфункций).

  1. Количество разбиений пространства при выборе.
  2. Объём пространства в которое попадаем.
  3. Количество еды.
  4. Насколько оставшееся пространство соединённое ( самое узкое место 1 клетка, 2,3,4...).

и другие модули которые вы придумаете позже.

Далее каждый модуль вычисляет своё значение и в общей функции все эти значения складываются с определёнными коэффициентами.

f = m1 * k1 + m2 * k2 + ... + mn * kn;

mi это результат вычислений модуля i.
ki это коэффициент, которые задаётся вручную.

Позже можно будет сделать самообучение по этим коэффициентам.

Далее для каждого выбора рассчитываем функцию f и выбираем выбор с наибольшим значением.

1

Просто как идея:

  1. Определяем все кратчайшие маршруты до еды волновым алгоритмом
  2. Для каждого из маршрутов делаем следующее:
    • считаем количество ходов для маршрута (сколько клеток надо проползти)
    • увеличиваем змею спереди на маршрут, уменьшаем сзади на маршрут. Получаем положение змеи, как если бы она подползла к еде
    • проверяем, если мы в тупике - то маршрут не годен, отметаем его. Если не в тупике, то маршрут годен.
  3. Если годных маршрутов больше 0, то берем первый
  4. Если годных маршрутов ноль, то добавляем псевдо-точку где-то подальше от змеи и считаем маршут до неё. В конце возврат в п.1

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.