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

«У тебя 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Мб)
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 67

    +14
    туда бы ботов и рокетланч…
      +9
      И частичную разрушаемость стен…
        +2
        В старой версии была.
        Тогда все было иначе:
        скриншот
        +1
        Бот есть.
        Выстрелы умерли вместе с введением дискретных координат — я не знаю как их нормально реализовать. Единственное, что я придумал — нарисовать каждого игрока своим цветом, а все остальное — черным. После этого нарисовать все и посмотреть на цвет в прицеле. Это настолько криво, что не хочется даже начинать. Если кто-нибудь расскажет как реализованы выстрелы на современных и не очень движках — буду очень благодарен.
          +2
          P.S. не дискретных, а непрерывных
            0
            Выстрел — это запуск небольшого тела (снаряда) с некоторой скоростью в некотором направлении. Скорость конечна (если это не лазер, но их пока не смотрим), а дальше — определение коллизий на каждом шаге времени, если снаряд попал в препятствие, он детонирует. Если в зоне взрыва оказывается игрок, ему защитывается урон.

            Для пулемёта скорость снаряда выше, а радиус взрыва меньше, для ракетницы — наоборот.
              +1
              Спасибо, будет время — реализую.
                0
                определение коллизий на каждом шаге времени

                не получится, что оно будет пролетать сквозь игрока?
                  +1
                  Может и такое получиться. Вообще, обработка коллизий — обширная тема. Я предложил простейший вариант.
                    +2
                    вообще, существует такая штука как CCD но тут она не нужна принципиально, достаточно рейкаста (выпустить лучик)
            0
            Если поставить лампочку в точку камеры и настроить attenuation, то во-первых, не сливалось бы все (да и картинка стала бы приятнее), а во-вторых плеер видел бы отчетливо только ближайшие развилки и мог бы по яркости определять, куда дальше стоит двигаться.
              0
              Спасибо, я постараюсь реализовать. Освещения нет, потому что я с ним не разобрался)
              +1
              Попробуйте добавить затемнение по глубине. Т.Е. те точки, что дальше от игрока чуть темнее. Игра очень преобразится и появится объём.
                0
                ответил выше
                +20
                Не часто нынче встретишь школьника решившегося на такое. Молодец.
                  +5
                  Напомнило фильм куб. Сюда бы смертельных ловушек. Почти portal будет
                    0
                    Что-то такое делал в майнкрафте =)
                      +1
                      Эх, под мак бы :(
                        0
                        Попилить исходники немного — и должно заработать.
                          0
                          По идее должно под маком заработать. Qt под мак есть.
                          Хотя не гарантирую — я не пробовал, у меня нет нигде мака.
                            0
                            Попробую собрать под мак.
                              +1
                              Собрал с некоторыми правками кода, но клиент не запустился, увы. Точнее, запустился и тут же крашнулся после подключения.
                                0
                                Вы правильно расположили файлы?
                                Labyrus/bin/Client
                                Labyrus/bin/imageformats
                                Labyrus/bin/dlls
                                Labyrus/skins/Skin1/…

                                Также возможны некоторые проблемы с папкой imageformats.
                                А вообще, вероятно баг где-то в реализации потоков.
                                У меня тоже иногда падает после старта, но редко — отловить не удается. Видимо это надо дебажить на маке)
                                  +2
                                  Насчёт правильного расположения файлов надо бы где-то написать ;)

                                  Попробую попозже.
                            +1
                            Если есть желание собрать и подебажить, можно применить сей патч:
                            gist.github.com/silvansky/5451074
                              0
                              Спасибо, применил патч.
                            0
                            А что за процент показывает прогресс? Количество посещенных клеток по отношению к их общему количеству?
                              0
                              Да.
                              А прогресс бота показывает то же самое, но со времени последнего старта бота(у него своя память — он будет по новой все проходить)
                              0
                              Текстурки бы получше, да освещение посчитать. В принципе вообще постообработку на шейдерах бы сделать. Еще рекомендую посмотреть в сторону Qt3D, он умеет модельки грузить.
                                0
                                Текстурки — моя головная боль.
                                Нету ни навыков, ни желания. Все, что я пытался сделать выглядело гораздо хуже, чем то, что выложил.
                                +5
                                ЗЫ, кстати, напомнило мне вот это.
                                  0
                                  Напомнило SCP
                                    0
                                    Не знаю, баг или фича, но я застрял в стене:
                                    s3.postimg.org/ecar12adt/image.png
                                      0
                                      А у меня вообще текстуры не грузятся :( fff.jpg
                                        0
                                        Интересно…
                                        Сколько систем — столько багов)
                                        0
                                        По идее должны пройти 4 секунды и произойти рестарт.
                                        Но, судя по скрину, вас отключило от сервера.
                                        Без сервера рестарт не работает.
                                        0
                                        Зачем показывать прогресс? Ведь по нему можно определить, куда идти.
                                          0
                                          Ну да, можно. Можно определить был ты в данной клетке или нет. Это не так уж и много — компас, показывающий изначально зеленой стрелкой на выход дает больше. Вообще, я показываю прогресс, потому что раньше лабиринт был одноэтажным. Тогда я показывал там поля про патроны, гранаты (снос стенок), стенки (построение стенок) и статус (живой/мертвый). Эти поля умерли, но выглядело оно очень красиво. Поэтому я оставил в левом нижнем углу хоть что-то — прогресс и этаж.
                                            0
                                            если на выходе из лабиринта разместить фото Памелы, то мотивация дойти до конца резко увеличится.

                                            так же на пути на выход можно размещать кусочки фото и показывать собранное из кусочков фото, по мере прохождения лабиринта, где-нить в уголке…

                                            п.с. вспоминаю старый стрип-покер. как давно это было… CGA… 8086… оторваться было не возможно…
                                          0
                                          Понял, что в линуксе с зависимостями все тоже не так прекрасно — их пришлось вычислять опытным путем и с помощью аналогичных программ на Qt.


                                          В смысле? Вы либо используете библиотеку, либо нет. Соответственно, либо линкуете, либо нет. Ничего сложного.
                                          Откройте для себя pkg-config.
                                            0
                                            В системе ArchLinux в репозитории AUR программы компилируются из исходников.
                                            Под моей системой все прекрасно работало, я был уверен, что зависимость одна — Qt5-base.
                                            Однако, при установке на системе, в которой не было Qt, ничего не скомпилилось — не хватало каких-то библиотек.
                                            Опытным путем я выяснил, что нужен пакет icu.
                                            Насколько я понял, это какая-то внутренняя зависимость Qt5, про которую никто ничего не написал.
                                              +2
                                              Так у вас и есть зависимость только от Qt. Ничего удивительного в том, что программа не собирается, если нет Qt.

                                              Существуют прямые зависимости и косвенные:
                                              • Прямые зависимости (для проекта) — это библиотеки, которые проект непосредственно использует.
                                              • Косвенные зависимости (для проекта) — это прямые и косвенные зависимости для библиотек, которые использует проект.


                                              Так вот, ICU это библиотека для поддержки юникода и средств интернационализации, и Qt может быть собрана без поддержки этой библиотеки. Ваш «Лабирит» вполне себе переживёт такой расклад.

                                              Отслеживайте только прямые зависимости, косвенные зависимости должны быть автоматически разрешены при разрешении прямых (рекурсивно). На этом принципе построены все современные менеджеры пакетов.
                                                +1
                                                На машине, на которой не было qt — он поставился как зависимость.

                                                Но вы правы: icu идет, как зависимость Qt5-base. Видимо, в старой версии версии пакета этой зависимости не было. Или кто-то не обновил систему.

                                                Обновил PKGBUILD.

                                            0
                                            О как! Интересно! Надобно дома попробовать. А в будущем git будет использоваться для контроля версий? Ибо было бы время, закоммитил бы пару патчей, а к git'у уже слишком привык. На всякие svn и cvs даже за печеньки не переманишь… :)
                                              0
                                              P.S. с друзьями just for fun & experience пилили когда-то кросс-платформенный клон Arkanoid'а. Начинал друг по урокам, потом стали пилить совместно всей компахой. Arkilloid, ежели интересно.
                                                0
                                                Ну так в конце статьи есть ссылка на гиториус. Всё там уже в гите ;)
                                                  0
                                                  Да-да, видел :)) Мой вопрос был связан с тем, что в статье есть некоторая неоднозначность относительно git, вот я и вопросил, будет ли он использован при разработке в будущем :)
                                                    0
                                                    Поработал с Git, могу с чистой совестью сказать: Git — не для меня. Да простит меня Линус.


                                                    Я хотел сказать, что использование git — не совсем то, что мне нужно. Один разработчик. Ни одного отката. Только для AUR по сути, да для сохранения бэкапов кода. И идеологию коммитов я что-то не очень понял. Но переходить на другую систему контроля версий — не дай бог.

                                                    Git был выбран, так как единственный сайт, дающий систему контроля версий, про который я знал — gitorious.org
                                                      0
                                                      Кстати говоря, только что собрал с git'а… Побегал)) Весьма напомнило ту игрушку-лабиринт трёхмерный (обычно из прозрачного пластика) с шариком :) Один раз правда клиент упал в сегфолт, но я не был вооружён дебаггером :)
                                                        +1
                                                        Но переходить на другую систему контроля версий — не дай бог.
                                                        А почему? На начальной стадии (когда нет хуков, CI, и большого количества alias’ов), а также нет привычки, VCS менять очень легко. Mercurial дружелюбнее — он хотя бы не торчит кишками наружу. Имеет возможность импорта из git (дополнение hg-git или встроенная команда hg convert).

                                                        И идеологию коммитов я что-то не очень понял.
                                                        А что именно не поняли? Тут всё просто — делаете одно логически завершённое изменение (вроде «добавил возможность иметь две разные текстуры поверхности стены») и фиксируете его. Коммит должен содержать только одно значимое изменение (лучше иметь только одно независимое изменение, но я всё же часто засовываю в коммит мелкие исправления вроде опечаток в комментариях или indentation). Что считать значимым — решаете вы. Под «независимым» следует понимать изменение, которое вы можете кратко и понятно описать одним достаточно коротким (github режет первую строку по границе в 78 символов) предложением. Если вы пишете нормальные комментарии к изменениям, то можете, глядя в git log/hg log и копируя оттуда фразы, составлять описание сделанных в новой версии изменений.

                                                        Только для AUR по сути, да для сохранения бэкапов кода.
                                                        Есть ещё плюсы: bitbucket/github даёт в нагрузку удобный TODO лист (он же bug tracker, но при отсутствии пользователей это просто TODO), у первого он более удобен. Сам mercurial/git даёт более простое развёртывание и обновление на других машинах и восстановление в случае различных ошибок (в т.ч. испорченного вашими исилиями кода). Последнее преимущество для одного разработчика — возможность прогона тестов перед фиксацией изменения (git/mercurial) или же перед загрузкой зафиксированных изменений на сервер (только mercurial).

                                                        Про то, как сказанное соотносится с gitorius я не скажу — использую только git+github и mercurial+bitbucket.
                                                          0
                                                          А почему? На начальной стадии (когда нет хуков, CI, и большого количества alias’ов), а также нет привычки, VCS менять очень легко. Mercurial дружелюбнее — он хотя бы не торчит кишками наружу. Имеет возможность импорта из git (дополнение hg-git или встроенная команда hg convert).

                                                          Про Mercurial просто ничего не знаю. Насколько я понял, смысла переходить на нету. Привычка уже есть. Переезжать на github, в частности, нет ни малейшего желания.

                                                          А что именно не поняли? Тут всё просто — делаете одно логически завершённое изменение (вроде «добавил возможность иметь две разные текстуры поверхности стены») и фиксируете его. Коммит должен содержать только одно значимое изменение (лучше иметь только одно независимое изменение, но я всё же часто засовываю в коммит мелкие исправления вроде опечаток в комментариях или indentation). Что считать значимым — решаете вы. Под «независимым» следует понимать изменение, которое вы можете кратко и понятно описать одним достаточно коротким (github режет первую строку по границе в 78 символов) предложением. Если вы пишете нормальные комментарии к изменениям, то можете, глядя в git log/hg log и копируя оттуда фразы, составлять описание сделанных в новой версии изменений.


                                                          Это если вы нормальный разработчик)
                                                          А если вы одиночка, и за коммитами никто не следит, то смысла, вроде как, особого нет. Написал что-то завершенное — отправил на сервер. Логичнее, чем перед этим создавать коммит, а потом уже отправлять.
                                                          А про changelog'и я просто не думал. Все-таки Labyrus изначально назывался maze. И делался исключительно для саморазвития.

                                                          Есть ещё плюсы: bitbucket/github даёт в нагрузку удобный TODO лист (он же bug tracker, но при отсутствии пользователей это просто TODO), у первого он более удобен. Сам mercurial/git даёт более простое развёртывание и обновление на других машинах и восстановление в случае различных ошибок (в т.ч. испорченного вашими исилиями кода). Последнее преимущество для одного разработчика — возможность прогона тестов перед фиксацией изменения (git/mercurial) или же перед загрузкой зафиксированных изменений на сервер (только mercurial).

                                                          Про то, как сказанное соотносится с gitorius я не скажу — использую только git+github и mercurial+bitbucket.


                                                          Единственное, что дает gitorious, помимо того, что предоставляет git, это wiki. По крайней мере, я больше ничего на нем не нашел)
                                                          А вообще, перед написанием статьи я зарегистрировался на sourceforge.
                                                          Вот его возможности меня поразили. Чего только стоит возможность добавлять скриншоты. Я думаю, что если я буду впредь заниматься чем-либо подобным, я буду использовать sourceforge + svn.
                                                            0
                                                            буду использовать sourceforge + svn

                                                            Лучше git + github + github pages, имхо.
                                                            И, кстати, скриншоты можно на гитхабе и без pages вставлять.
                                                              0
                                                              Интересно. Правильно я понимаю, что на github pages можно загружать свои файлы?
                                                              Т.е. по сути github отличается от sourceforge только отсутствием возможности использовать mercurial/svn?
                                                                +1
                                                                Ну, в указанном мной примере я лишь загрузил .png в репозиторий и с помощью Markdown вставил в Readme.
                                                                Но на github pages можно сделать полноценный сайт, с картинками и прочим.

                                                                Кстати о sourceforge. Он, как по мне, морально и технологически устарел. Он тяжеловесен и крив дизайном.

                                                                Я для себя выбрал гитхаб для opensource и bitbucket для личных проектов — оба очень удобны.
                                                                  0
                                                                  > Кстати о sourceforge. Он, как по мне, морально и технологически устарел. Он тяжеловесен и крив дизайном.

                                                                  Они недавно сделали большое обновление и переехали на что‐то более приличное. Правда я уже практически перестал использовать sourceforge к этому времени (использую только как hosting для репозиториев), так что оценить изменения лучше не могу, но новый интерфейс определённо приятнее.

                                                                  > Я для себя выбрал гитхаб для opensource и bitbucket для личных проектов — оба очень удобны.

                                                                  Как ни странно, я тоже (помимо старых, тоже личных, проектов на sourceforge). Точнее, я бы с радостью перетащил на bitbucket всё, но для этого надо перетащить туда же всех. Правда, у меня «личный» — «начатый мною», а не «не opensource», а «opensource» на github — исключительно чужой opensource. У github слишком плохой bug tracker, а у git плохой CLI. У bitbucket для совместных проектов есть один большой минус: я не знаю бесплатной системы CI для него навроде travis. Остальные мешающие минусы они уже убрали (добавили комментарии к строкам в diff’ах и markdown вместо wiki в комментариях).
                                                  0
                                                  Побегал и набрал прогресс 125%… я думал, что такое может быть только на выборах.
                                                    0
                                                    Странный эффект…
                                                    Я правильно понимаю, что у вас не обнулялся прогресс после рестартов?
                                                    Была такая бага в какой-то старой версии.
                                                      0
                                                      У меня до 229% получилось :) Можно было и дальше накапливать.
                                                      0
                                                      Текстура вырвиглазная, все сливается в один фон. И сделайте, что ли, поребрик другого цвета по краям стенок, чтобы издалека были видны.
                                                      0
                                                      Неправильно, конечно, что карта мира целиком отправляется клиенту, да и коллизии проверяются на его же стороне.
                                                        0
                                                        Неужели исходники читали?
                                                        Ну да, неправильно. Я из принципа KISS. Просто писать все это на стороне сервера тяжелее. А для того, чтобы мне все это аукнулось, нужно, чтобы была достаточная аудитория, чтобы кто-нибудь захотел ее сломать. А когда ломать некому, то и защиту писать как-то неохота)
                                                        +3
                                                        Не нашёл нормального способа завершения сервера после запуска labyrus-server-gui.exe, приходиться убивать процессы. Консольный вариант нормально работает.

                                                        Дизайн интерфейса ужасен. Есть простое правило: если не можешь сделать нормальный интерфейс, то сделай его простым.
                                                        Я бы сделал примерно так


                                                        В Qt можно узнать ширину в пикселях для текста, поэтому легко сделать, чтобы текст не вылезал в моём примере.
                                                        Курсивом лучше не делать текст, он заметно хуже выглядит.
                                                        Цвет текста тоже играет большую роль.
                                                          0
                                                          Забавно, в линуксе все прекрасно работает. После закрытия консоли, сервер завершается. А я решил, что если у меня работает, то и под виндой заработает. Сейчас проверил — действительно под виндой не работает. Удивительно, так как в той части кода нету никакой зависимости кода от системы.
                                                          Но, вообще, labyrus-server-gui.exe перед стартом нового, убивает предыдущий сервер, так что сильно мешать это не должно. Хотя, разумеется, это баг.

                                                          Насчет дизайна — ну не дизайнер я)
                                                          Как смог — так сделал. Буду знать про простой интерфейс. Спасибо, за интересный скрин.
                                                          0
                                                          По поводу генерации – алгоритмов великое множество. Вот здесь есть довольно симпатичная презентация.
                                                          • UFO just landed and posted this here
                                                              0
                                                              Трехмерный лабиринт? Забавно)

                                                              Only users with full accounts can post comments. Log in, please.