«У тебя 2 минуты, чтобы создать лабиринт, на выход из которого нужна минута.»
Коб, «Начало»
Примерно год назад мне стало интересно нарисовать лабиринт, на прохождение которого требуется хоть какое-то время. Я долго пытался это сделать, однако столкнулся с множеством проблем:
- От выхода такой лабиринт проходился на «раз-два».
- Увидеть и понять, идешь ты по правильному пути, или нет, можно было почти всегда.
- На рисование лабиринта уходило очень много времени.
Тогда я решил написать программу, которая будет скрывать то, что видеть не положено и, заодно, генерить лабиринты.
А потом поднял лабиринт в 3D с помощью OpenGL.
А затем добавил в него сеть, потоки и этажи.
Итак, встречайте:
Labyrus — открытая кроссплатформенная многопоточная сетевая игра, написанная с использованием OpenGl и Qt.
Обозначения
Лабиринт состоит из «клеток». Стенки могут стоять только между клетками.
n — ширина лабиринта,
n — длина лабиринта (основание лабиринта — квадрат),
h — высота лабиринта.
Генерация карты
Сначала создается полый кубик. Затем создается список всех возможных стенок внутри этого кубика в случайном порядке. После этого по-очереди пытаемся добавить стенки. После каждого добавления карта проверяется на связность dfs'ом. Итого получается дерево.
Оценка времени работы
количество клеток: n * n * h,
количество стенок: 3 * n * n * h,
время работы dfs'а: n ^ 4 * h ^ 2 (не оптимально храню граф),
время генерации: O(n ^ 6 * h ^ 3).
В принципе, генерацию можно значительно ускорить. Но:
- Лень писать.
- Карта, на прохождение которой требуется ~10 минут, генерится за 0.4 с, что, в принципе, выполняет поставленную задачу. (Оправдание лени)
Лабиринт с h=1. Режим разработчика. Вид сверху.
Описание исполняемых файлов
- labyrus-server: генерирует лабиринт и ожидает соединения.
- labyrus-server-gui: GUI к серверу — для тех, кто не любит консоль.
- labyrus-client: клиентская часть игры — игра идет именно в ней (требует запущенный сервер)
- labyrus-switchlanguage: для смены языка (по умолчанию системный). Для тех, кому нравятся приложения на %language%. Естественно, работают только те языки, которые я встроил (английский и русский).
Управление
- Управление стандартное — стрелочки и клавиши [wasd].
- Чат и команды — нажать [enter]команда[enter].
- В полноэкранном режиме доступна мышка.
- Переход в полноэкранный режим и обратно — горячая клавиша z.
- Открыть меню — escape.
- На Control — бинокль. Просто мне было интересно его написать.
- В режиме разработчика (debug mode) доступны клавиши [qe] — вертикальный взлет и приземление, без теста пересечений со стенками.
Общая схема
Сначала нужно поднять сервер. Затем игроки подключаются к серверу. В момент, когда подключается заданное на сервере количество игроков, начинается игра. Все падают вниз сквозь стены на старт. Изначально вы ориентированы на выход. Он расположен всегда на том же этаже, что и вы — в противоположном углу. При параметре --strong дальнейшие подключения невозможны. Выигрывает игрок, первым дошедший до выхода. После того, как последний игрок доходит до финиша, генерится новая карта, и игра перезапускается.
Системные требования
Как их определять я не знаю, но вроде не большие. Аппаратное ускорение OpenGL приветствуется. (~40000 полигонов в самом большом лабиринте)
Комментарии
За время написания проекта, я научился куче новых вещей:
- Серьезно продвинулся в освоении Qt.
- Научился как-то работать с OpenGl.
- Поработал с Git, могу с чистой совестью сказать: Git — не для меня. Да простит меня Линус.
- Понял, что стоит сначала хоть как-то проектировать программу, ибо в какой-то момент приходится переделывать слишком много вещей. В частности, переход от дискретных координат к вещественным был очень болезненным и унес с собой возможность ставить и сносить стены.
- Напоролся на кучу интересных и не очень багов. В частности, скомпилировать Labyrus на Qt5 под виндой так и не удалось.
- Понял, что в линуксе с зависимостями все тоже не так прекрасно — их пришлось вычислять опытным путем и с помощью аналогичных программ на Qt.
- Понял, насколько важны тестировщики.
- Очень интересно было узнать, как пишутся пересечения объектов.
- Понял, почему в играх обычно разрешения экрана фиксированы. У меня они не фиксированы, и переход в полноэкранный режим происходит без перезапуска программы. Реализовать это было тяжело. К тому же это создает кучу багов, которые я оставляю на совести пользователей. Т.е., если ты бежал вперед и переключился на другое окно — будь готов увидеть, как ты продолжаешь бежать.
- Написал бота, который проходит лабиринт. Очень интересно, как писать по-настоящему сложных ботов.
… А также познал 9 кругов ада дебага приложения, которое:
- Графическое.
- OpenGL.
- Qt. (Не понятно кто вызвал этот слот, и почему программа упала где-то внутри Qt-части)
- Многопоточное.
- Сетевое.
- Кроссплатформенное. (под линуксом компилится, по виндой — нет. Но ifdef'ы зарешали)
- Многоязычное (русский + анлийский). Qt, конечно, предоставляет замечательную систему перевода, но когда на одном языке текст помещается в нужную область, а на другом нет — это ужасно.
- Состоит из многих файлов (загрузка графики и перехват вывода другой программы). Я очень долго не понимал, почему у меня под виндой все работает, а у других белые текстуры. В итоге выяснилось, что не хватало каких-то левых библиотек.
- Требует контроля версий. Нет, Git я, конечно, осилил. Но вот, как узнавать версию в стиле xx.xx.xx-buildxx, не имею ни малейшего представления. Пока что нормально сделано только для ArchLinux. Там хотя бы дата создания пакета есть.
Авторство
Проект написан мной полностью, без использования каких-либо движков, за исключением:- Скины — спасибо моей маме.
- Функции begin2d() end2d() — взяты с сайта gamedev.ru.
- За тестирование спасибо моему однокласснику danpol.
Демо
Исходники
Windows (Qt4)
Linux-x86 (Qt4)
Linux-x86_64 (Qt5)
ArchLinux (AUR) (Qt5)
UPD 27 апреля:
Я ухитрился выложить кучу лишних файлов в архиве для винды.
LabyrusPortable.zip обновлен (-8Мб)
