предисловие
За последние два дня я увидел в Интернете картинку, которая заставляет людей позировать. На картинке изображена игра со змеями. По оценкам, в нее играло большинство людей. Но если это просто игра в змейки, то это не имеет никакого отношения. Суть проблемы в том, что жадная змея на картинке на самом деле жадная XD, она съедает всю еду, которая появляется в прямоугольнике, а потом шикарно заполняет весь прямоугольник, что очень радует глаз. Как CSer, первое, что приходит на ум, это то, что эта вещь реализуется путем написания программ (потому что обычные люди не могут этого сделать. Это решительно позволить программе сделать это). Второе, что приходит на ум, это то, как писать программы для достижения, какой алгоритм использовать? Как только вы начнете думать об этом, начните это делать. Поскольку Talk стоит дешево, вы должны показать мне код. (узнал от дяди Крысы)
Прежде чем мы начнем, давайте взглянем на жадную змею, которая заставляет людей смотреть вверх: (Если динамическая картинка ниже не работает, вы можете щелкнуть правой кнопкой мыши и сохранить ее для просмотра)
Выбор языка
Жизнь коротка, пользуйтесь питоном!Поэтому я особо не думал об этом и сразу перешел на питон.
Первоначальный вариант
Пусть ваша программа запустится первой
Прежде всего, первое, что нам нужно сделать, это не анализировать проблему. Вы должны сначала написать работающую игру про змейку, а потом уже думать об AI-части. Это должно быть очень просто, c\c++ всего сто строк кода (если я правильно помню. Не усложняйте интерфейс, запускайте прямо под консолью), python еще проще, уберите комментарии и пустые строки, 5, 60 строк кода и все готово. И, самое главное, это дело нужно перезаписать в интернете, не нужно изобретать велосипед, достаточно получить копию и модифицировать по своему желанию.
Простая версия
Я не думаю, что писать идеальную версию напрямую — хорошая идея. Поскольку идеальная версия часто должна учитывать множество вещей, ее непосредственное написание обычно полно ошибок. Итак, в начале моей целью было просто позволить программе управлять движением змеи, позволить ей есть пищу, и все. Теперь сформулируем исходный вопрос:
В прямоугольнике в каждый момент есть еда, и жадная змея не должна ударить себя, Найдите дорогу (не обязательно оптимальную) и бегите по ней, чтобы насладиться едой.
Давайте не будем думать о том, что змея будет становиться все длиннее и длиннее, проблема в основном в том, чтобы дать вам начальную точку (голова змеи) и конечную точку (еда), избежать препятствий (тело змеи) и найти возможный путь от начальной точки до конечной точки. Методы, которые мы можем использовать:
- BFS
- DFS
- A*
Пока есть выбор, выбираем сначала самое простое решение, наша текущая цель — заставить программу работать в первую очередь, а оптимизация — другое дело. Итак, начните с BFS. Сначала мы помещаем позицию головы змеи в очередь, затем, пока очередь не пуста, позиция головы очереди удаляется из очереди, а затем в очередь помещаются 4 точки в ее четырех полях, и операция непрерывно зацикливается, пока не будет достигает положения еды. В этом процессе нам нужно обратить внимание на несколько моментов: 1. Посещенные точки больше не посещаются. 2. Сохраняем родительский узел каждой точки (то есть, с какой позиции каждая позиция идет к ней, чтобы мы могли узнать допустимый путь). 3. Расположение тела змеи и четыре стены недоступны.
После нахождения пищи через BFS необходимо лишь переместить змейку по возможному пути. После того, как эта простая версия написана, Snake может какое-то время спокойно работать. Посмотрите на картинку: (Ощущение неровности исходит от программного обеспечения для записи экрана＠_＠)
Чтобы все было как можно проще, я использую модуль curses для рисования прямо из терминала. Как видно из динамических картинок выше, BFS просто используется каждый раз, и в конце концов однажды змея попадет в беду из-за этого безрассудного недальновидного поведения. Более того, даже в это время у него будет только стратегия БФС, что приводит к тому, что поскольку он не может видеть цель (еду) в данный момент, он думает, что так оно и есть в этой жизни, разбивая горшок и ломается, и, наконец, останавливается в определенный момент своей жизни. , больше не идя вперед. (Я люблю говорить о философии XD)
BFS+Wander
После того, как простая версия предыдущего раздела была запущена и запущена, мы поняли, что недостаточно научить змей только одной стратегии. Это такая глупая змея, если ее немного не научить, она умрет за считанные минуты. Итак, я написал функцию блуждания, как следует из названия, когда змея попала в беду, не позволяйте ей больше BFS, но пусть она гуляет, расслабляется и думает о жизни. Это все равно, что идти на работу, когда вы растеряны и растеряны.Не говоря уже о неэффективности, это может еще и помешать вам выйти из затруднительного положения, наоборот, если вы отложите свою работу в это время, остановитесь и пойдите на поездка или что-то в этом роде. Когда я возвращался, я мог внезапно увидеть свет, земля была ровной, а дом был как дом.
Функции блуждания могут быть написаны как угодно, но у них определенно есть свои плюсы и минусы. Я написал две версии, одна из которых делает случайные шаги в случайных направлениях в допустимом диапазоне. То есть направление каждого движения змеи случайно, и общее количество шагов тоже случайно. После того, как странствие закончится, снова зайдите в BFS, чтобы узнать, можете ли вы есть еду.Если вы можете, все будут счастливы. Если не получается, значит, не хватает времени подумать о жизни, так что снова скитайтесь. Этот процесс непрерывно зацикливается. Но точно так же, как «случайный процесс является случайным», у вас «случайный блуждание будет зависать случайным образом». Змеи, которые знают Бродягу, ходят гораздо чаще. Но однажды он рандомизирует себя в тупик. Попав в беду, можно также заблудиться, зайти в тупик, механизма отката нет. Итак, для второй версии функции Бродяги я позволил жадной змее жадничать до конца. После того, как BFS не имеет решения, укажите шаг змеи (случайно сгенерированный шаг) и позвольте ей двигаться шаг за шагом в форме буквы S в пустой области. На этот раз направление движения не случайное, а организованное и дисциплинированное движение. Посмотрите сначала на картинку, а потом расскажите о ее проблеме:
Да, в итоге завис. S-образное движение — это еще и судьба змеи, которая не может избежать смерти. Жадная змея может выжить в течение более длительного периода времени за счет S-образного движения, но поскольку ее стратегия такова:
Не нажимая клавишу ESC: если есть путь между змеей и едой: иди, поешь еще: Побродите некоторое время
Проблема в том, что змея находит путь между собой и едой и бежит, чтобы съесть еду, не говоря ни слова. При этом не учитывается, что ситуация, сложившаяся после приема пищи (змеиное расположение тела), может привести к повешению. (Например, вход в небольшое замкнутое пространство, окруженное собственным змеиным телом)
Итак, чтобы продлить жизнь змее, она должна быть более дальновидной.
Дальновидная версия
Теперь у нас есть младшая версия и немного более глубокое понимание проблемы. Теперь пришло время для более тщательного и тщательного анализа. Во-первых, давайте перечислим некоторые вопросы: (как мозговой штурм, просто запишите, что приходит на ум)
- Между змеей и едой есть прямой путь, что не рекомендуется. так что мне теперь делать?
- Если макет безопасен после того, как змея пойдет есть пищу, должна ли она идти сразу же, чтобы поесть? (Это лучший способ?)
- Как определить, безопасна ли раскладка?
- Что, если между змеей и едой нет пути?
- Является ли кратчайший путь оптимальным? (это явно не так)
- Итак, если схема безопасна, оптимален ли кратчайший путь?
- Кроме кратчайшего пути, что еще мы можем сделать? S-образный? самый длинный?
- Как решить проблему, когда тело змеи становится все длиннее и длиннее?
- Еда появляется случайным образом, возможно ли иметь неразгаданную раскладку?
- Может ли грубая сила получить оптимальную последовательность? (Пусть жадный змей съест как можно больше еды)
Только подумав об этом, возникает много вопросов. На этот раз давайте воспользуемся процессно-ориентированным мышлением с вышеуказанными проблемами, чтобы обосновать мышление. Вначале змея короткая (инициализированная длина равна 1), она видит еду и использует BFS для получения кратчайшей длины пути к еде в каждой позиции прямоугольника. Если бы тело змеи не блокировало ее, это было бы манхэттенское расстояние. Затем я должен сначала решить, безопасно ли есть змей. Поэтому мне нужна виртуальная змея, которая каждый раз будет отвечать за поиск пути. Пусть настоящая змея бежит только в том случае, если это безопасно. Конечно, виртуальная змея не рисуется, она отвечает только за имитацию поиска пути. Итак, как определить безопасный макет? Если вы внимательно посмотрите на экстаз змеи на динамичной картинке в начале статьи, то обнаружите, что хоть тело змеи и очень длинное в конце, она все равно идет своим путем без проблем. Более того, он следует за хвостом змеи! Что ж, это на самом деле несложно объяснить, в процессе движения змея поглощает тело змеи, и за хвостом змеи всегда появляется новое пространство. Не имеет значения, когда змея короткая, когда змея длинная, вы обнаружите, что если хотите выжить, то можете бежать только за змеиным хвостом. В процессе погони за хвостом змеи подумайте, безопасно ли есть пищу. (Картинка ниже представляет собой макет, полученный после определенного BFS, 0 представляет собой еду, число представляет собой расстояние от позиции до еды, знак + представляет собой голову змеи, знак * представляет собой тело змеи, знак - представляет собой змеиный хвост, знак # обозначает пространство, внешний кружок с # обозначает стену)
0 1 2 3 4
1 2 3 # 5
2 3 4 - 6
3 + * * 7
4 5 6 7 8
После вышеприведенного анализа мы можем определить, безопасна ли схема, может ли змея следовать за змеиным хвостом, то есть есть ли путь между головой змеи и змеиным хвостом после того, как змея съела свою пищу. , я думаю, что это безопасно.
Хорошо, продолжайте. После того, как настоящая змея отправила виртуальную змею исследовать путь, она обнаружила, что макет после еды безопасен. Затем настоящая змея идет прямо к еде. Подождите, это хорошая стратегия? не обязательно. Потому что каждый раз, когда змея движется, макет меняется. Изменение макета означает, что может существовать лучшее решение. Например, из-за употребления в пищу змеиного хвоста пища, которую нужно было есть обходным путем, внезапно оказывалась перед змеей. Поэтому после того, как реальная змея сделает шаг, лучше сделать БФС еще раз. Затем примите такое же решение о безопасности, как указано выше, и вперед.
Далее давайте рассмотрим, что если между змеей и едой нет пути? На самом деле, практика была упомянута выше, и следуйте за хвостом змеи. Пока между змеей и едой нет пути, змея следует за хвостом. Точно так же, поскольку макет будет меняться каждый раз, когда вы делаете шаг, вам нужно заново выполнять BFS каждый раз, когда вы делаете шаг, чтобы получить последний макет.
Хорошо, здесь снова возникает проблема. Что, если нет пути между змеей и едой и нет пути между змеей и хвостом? У меня нет другого выбора, кроме как выбрать осуществимый путь. Принцип тот же: делайте шаг за шагом, обновляйте раскладку, а потом судите, есть ли безопасный путь между змеей и едой, если нет, то есть ли путь между головой змеи и змеиным лбом. хвостик;
Некоторые из перечисленных выше проблем связаны со стратегией ходьбы змеи.Вообще говоря, мы будем заставлять змею каждый раз выбирать кратчайший путь. Это когда змеи идут за едой, но когда змеи гоняются за своим хвостом, им не следует так думать. Мы хотим, чтобы змеиная голова двигалась как можно медленнее в процессе погони за змеиным хвостом. Таким образом, между змеиной головой и змеиным хвостом может быть высвобождено больше места, и тем больше пространства может быть развито. Поэтому стратегии ходьбы змей в основном делятся на два типа:
1. Когда цель — еда, иди кратчайшим путем 2. Когда цель — змеиный хвост, идите по самому длинному пути
А третий случай? Когда нет пути с едой и змеиным хвостом, в это время только посильный шаг идти, а самый короткий и самый длинный не связаны. Что касается искусственного придания змее S-образной формы, я не думаю, что это хорошая стратегия, и ее проблемы были проанализированы в исходной версии. (Если, конечно, вы не хотите использовать самый неуязвимый вариант, который состоит в том, чтобы вообще игнорировать еду, позволить змее идти до конца и оставить проход у стены. Таким образом, змея всегда может съесть все. еда отлично доела, а потом заполнила все пространство, но было очень скучно.нет смысла)
Есть также вопрос, упомянутый выше: поскольку еда появляется случайным образом, возможно ли, что решения нет? Ответ: да. Я запустил программу, а затем вывел каждую раскладку в лог, и обнаружил, что там будет что-то вроде этого:
* * * * *
* * - 0 *
* * # + *
* * * * *
* * * * *
Среди них знак + — это голова змеи, знак — — это хвост змеи, знак * — это тело змеи, 0 — еда, знак # — пространство, а знак # снаружи — стена. В этой раскладке еда уже находится перед головой змеи, но можно ли ее есть? не можем! Потому что после того, как она съест еду, длина увеличится на 1, а голова змеи заполнит позицию 0, и макет станет таким:
* * * * *
* * - + *
* * # * *
* * * * *
* * * * *
В это время, поскольку длина змеи увеличивается на 1, хвост змеи не двигается, а голова змеи окружена собой и свисает. Однако у нас все еще есть пустая сетка # unfilled. В соответствии со стратегией, которой мы обучали змею ранее, перед лицом этой ситуации голова змеи будет продолжать преследовать только хвост змеи. макет получился небезопасным, поэтому вместо еды он решил продолжить погоню за хвостом змеи. А потом он просто продолжал работать, и он продолжал работать. Бесконечный цикл, пока вы не нажмете клавишу ESC.
Так как еда появляется случайным образом, возможна описанная выше неразрешимая схема. Конечно, вы также можете получить счастливый конец, где змея заполняет весь прямоугольник.
Последний вопрос выше заключается в том, может ли метод грубой силы получить оптимальную последовательность. Из вышеприведенного анализа его можно получить, но нельзя гарантировать.
Наконец, посмотрите, как бежит змея-мечтатель:
размер прямоугольника 1020, удалите внешнюю границу, которая равна 818. После того, как линукс скачает скрин и потом сконвертирует его в картинку формата GIF, оптимизация больше 40 Мб, и с виндой сравнивать действительно невозможно. При оптимизации следующей командой возникает ощущение, что система оптимизируется с жизнью:
В итоге я все же получил динамическую картинку, синтезированную с помощью AE под Windows, и с помощью последовательности картинок разделить три и пять на два (не забудьте выбрать зацикливание в параметрах формата, иначе картинка не будет воспроизводиться в цикле )
Last but not least
Если вас интересует исходный код, перейдите по следующей ссылке:
https://github.com/Hawstein/snake-ai
Кроме того, программа змейка в этой статье использует модуль curses, который устанавливается по умолчанию в Unix-подобных системах.Для детской обуви этот модуль необходимо установить с помощью Windows.Присылайте адрес: Если нужны проклятия, ткните мне http ://www.lfd.uci.edu/~gohlke/pythonlibs/#curses
Приведенный выше код все еще можно улучшить (сейчас добавляется менее 300 строк комментариев, а при оптимизации их может быть и меньше), а также можно использовать библиотеку pygame или pyglet, чтобы сделать интерфейс более красивым, наслаждайтесь!
Оригинальный адрес: http://www.hawstein.com/posts/snake-ai.html, пожалуйста, укажите оригинальный адрес для перепечатки
Добро пожаловать, чтобы учиться и развиваться вместе со мной с радостью. Отдел исследований и разработок терминала - это учетная запись, основанная на технологиях обучения и коммуникационных технологий. Речь идет о технологиях, продуктах и нашей жизни. Быть самым вдумчивым и со вкусом интернет-разработчиком в Восточном полушарии