Pull to refresh

Labyrus: 3D лабиринт

Reading time 4 min
Views 17K
«У тебя 2 минуты, чтобы создать лабиринт, на выход из которого нужна минута.»
Коб, «Начало»



Примерно год назад мне стало интересно нарисовать лабиринт, на прохождение которого требуется хоть какое-то время. Я долго пытался это сделать, однако столкнулся с множеством проблем:
  1. От выхода такой лабиринт проходился на «раз-два».
  2. Увидеть и понять, идешь ты по правильному пути, или нет, можно было почти всегда.
  3. На рисование лабиринта уходило очень много времени.

Тогда я решил написать программу, которая будет скрывать то, что видеть не положено и, заодно, генерить лабиринты.
А потом поднял лабиринт в 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).

В принципе, генерацию можно значительно ускорить. Но:
  1. Лень писать.
  2. Карта, на прохождение которой требуется ~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 полигонов в самом большом лабиринте)

Комментарии


За время написания проекта, я научился куче новых вещей:


  1. Серьезно продвинулся в освоении Qt.
  2. Научился как-то работать с OpenGl.
  3. Поработал с Git, могу с чистой совестью сказать: Git — не для меня. Да простит меня Линус.
  4. Понял, что стоит сначала хоть как-то проектировать программу, ибо в какой-то момент приходится переделывать слишком много вещей. В частности, переход от дискретных координат к вещественным был очень болезненным и унес с собой возможность ставить и сносить стены.
  5. Напоролся на кучу интересных и не очень багов. В частности, скомпилировать Labyrus на Qt5 под виндой так и не удалось.
  6. Понял, что в линуксе с зависимостями все тоже не так прекрасно — их пришлось вычислять опытным путем и с помощью аналогичных программ на Qt.
  7. Понял, насколько важны тестировщики.
  8. Очень интересно было узнать, как пишутся пересечения объектов.
  9. Понял, почему в играх обычно разрешения экрана фиксированы. У меня они не фиксированы, и переход в полноэкранный режим происходит без перезапуска программы. Реализовать это было тяжело. К тому же это создает кучу багов, которые я оставляю на совести пользователей. Т.е., если ты бежал вперед и переключился на другое окно — будь готов увидеть, как ты продолжаешь бежать.
  10. Написал бота, который проходит лабиринт. Очень интересно, как писать по-настоящему сложных ботов.

… А также познал 9 кругов ада дебага приложения, которое:


  1. Графическое.
  2. OpenGL.
  3. Qt. (Не понятно кто вызвал этот слот, и почему программа упала где-то внутри Qt-части)
  4. Многопоточное.
  5. Сетевое.
  6. Кроссплатформенное. (под линуксом компилится, по виндой — нет. Но ifdef'ы зарешали)
  7. Многоязычное (русский + анлийский). Qt, конечно, предоставляет замечательную систему перевода, но когда на одном языке текст помещается в нужную область, а на другом нет — это ужасно.
  8. Состоит из многих файлов (загрузка графики и перехват вывода другой программы). Я очень долго не понимал, почему у меня под виндой все работает, а у других белые текстуры. В итоге выяснилось, что не хватало каких-то левых библиотек.
  9. Требует контроля версий. Нет, Git я, конечно, осилил. Но вот, как узнавать версию в стиле xx.xx.xx-buildxx, не имею ни малейшего представления. Пока что нормально сделано только для ArchLinux. Там хотя бы дата создания пакета есть.

Авторство

Проект написан мной полностью, без использования каких-либо движков, за исключением:
  1. Скины — спасибо моей маме.
  2. Функции begin2d() end2d() — взяты с сайта gamedev.ru.
  3. За тестирование спасибо моему однокласснику danpol.

Демо




Исходники
Windows (Qt4)
Linux-x86 (Qt4)
Linux-x86_64 (Qt5)
ArchLinux (AUR) (Qt5)

UPD 27 апреля:
Я ухитрился выложить кучу лишних файлов в архиве для винды.
LabyrusPortable.zip обновлен (-8Мб)
Tags:
Hubs:
+57
Comments 67
Comments Comments 67

Articles