Главная » Статьи » Excel » Макросы и программы VBA

Строим лабиринт и пишем программу для поиска выхода

Что это?

Перед вами симулятор лабиринтов на базе Excel. Вы можете создавать лабиринты любой сложности и оттачивать на них свои алгоритмы поиска выхода. Я сделал его в качестве развлечения. Получилось довольно забавно.

Правила

  1. Стены легко рисуются при помощи единичек. Остальное сделает условное форматирование.

  2. Точку старта вы определяете сами через активную ячейку.

  3. Кнопка "Старт" запускает ваш алгоритм поиска выхода

  4. Те ячейки, на которых вы побывали в процессе поиска, помечаются зеленым цветом.

  5. Кнопка "Очистка" подготавливает лабиринт к новому забегу.

  6. Если текущая позиция игрока и выход из лабиринта находятся на одной линии, между ними нет преград, а игрок исследует это направление на возможность сделать туда ход, то в этом случае фиксируется нахождение выхода из лабиринта. Вообще же в коде определена константа ExitCondition=100. Если стандартная подпрограмма Can_I_Move(Direction) определяет, что в направлении Direction между текущей позицией игрока и ближайшей преградой (любая константа на листе или его граница) более 100 ячеек, то фиксируется факт выхода за пределы лабиринта, а алгоритм останавливается.

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

    • Процедура MyFindExit, которую вы можете использовать в качестве контейнера для своего алгоритма.

    • Константы направлений движения (direction): dRight = 1, dDown = 2, dLeft = 3 и dUp = 4

    • Функция Can_I_Move(Direction), которая возвращает ноль, если в направлении Direction находтся стена, либо количество ходов, которое вы можете сделать до ближайшей стены, но не более границы видимости (константа VisibilityLimit = 4)

    • Функция Was_I_Here(Direction), которая возвращает -1, если вы не ходили раньше на смежную клетку в указанном направлении, 1 - если вы там уже были (сколько раз вы там были узнать возможности нет), 0 - если в этом направлении есть препятствие.

    • Разрешается создать для нужд алгоритма 2-4 целочисленных переменных и 1-2 логических переменных.

    • Количество ходов в алгоритме желательно подсчитывать. Алгоритм прекращает работу, если сделано ходов больше, чем в константе IterationsLimit, а выход ещё не найден.

    • Вы можете прервать работу алгоритма через Ctrl+Break

    • Пауза между ходами регулируется константой WaitAfterMove, которая по умолчанию равна 50 милисек.

Чего хотелось бы?

Хотелось бы взглянуть на ваши универсальные алгоритмы поиска выхода из лабиринтов. Любых лабиринтов, в которых есть выход. Я написал свой алгоритм, но он получился довольно громоздким. Я оставил его в файле, но рекомендую попытаться написать свой алгоритм. Я знаю, что у вас получится гораздо лучше! Тем более, что наблюдать за процессом поиска выхода довольно занятно. Жду ваших замечательных идей!

Скачать

Скачать


Категория: Макросы и программы VBA | Добавил: dsb75 (10.09.2014) | Автор: Батьянов Денис E W
Просмотров: 2553 | Комментарии: 10 | Теги: VBA | Рейтинг: 0.0/0
Всего комментариев: 10
6 MCH   (11.09.2014 12:56)
Памяти можно выделять не очень много, лабиринт ведь где-то хранится, можно сразу в нем и производить вычисления и хранить информацию о волне.
Память выделяется под стек. Я с запасом указал размер стека равной площади лабиринта, что гарантированно хватит для хранения волны. Но, как правило, волна существенно меньше, и можно столько памяти не выделять.

Реализацию делал без особой оптимизации (уже нашел пару лишних строк в коде).

0
7 dsb75   (11.09.2014 18:12)
Я про то, что алгоритм эффективный, но не спортивный. Гораздо интересней написать автономный алгоритм, у которого есть некое вариативное поведение в зависимости от ситуации, но нет полного знания о всём лабиринте.

8 MCH   (11.09.2014 19:10)
В таком случае имеет смысл реализовать алгоритм Люка-Тремо

0
3 dsb75   (10.09.2014 22:47)
Тот алгоритм, который у меня сейчас есть, несовершенен. Отчасти он основан на методе правой руки + усовершенствования.

1 MCH   (10.09.2014 21:10)
Волновой алгоритм не рассматривается для поиска выхода из лабиринта?

0
2 dsb75   (10.09.2014 22:45)
Михаил, не рассматривал. Там разве не надо использовать сложные структуры данных? Предложите реализацию...

4 MCH   (11.09.2014 02:17)
ну как-то так: https://yadi.sk/i/vCQfmepvbQ2ZU

0
5 dsb75   (11.09.2014 09:47)
Да, алгоритм, конечно, зверский по эффективности, но он задействует кучу ресурсов памяти, что, на мой взгляд, не совсем честно.
Спасибо большое за этот пример, очень интересно!

10 MCH   (12.09.2014 22:03)
Протестировал оба алгоритма на лабиринте 601*601
https://yadi.sk/i/aXc7g_IUbSypR

Волновой - достаточно быстро находит решение
Алгоритм одной руки обходит почти половину лабиринта, делая 125 тыс шагов

0
9 dsb75   (11.09.2014 21:34)
Вот это мне понравилось:
a = Range(Cells(1, 1), ActiveSheet.UsedRange).Value

Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Яндекс.Метрика