# Labyrus: 3D Maze

“You have 2 minutes to create a labyrinth that takes a minute to exit.”
Cob, The Beginning

About a year ago, it became interesting for me to draw a maze, the passage of which requires at least some time. I tried to do this for a long time, however, I encountered many problems:
1. From the exit, such a labyrinth was walked “one-two”.
2. It was almost always possible to see and understand whether you were going the right way or not.
3. It took a lot of time to draw the maze.

Then I decided to write a program that will hide what is not supposed to be seen and, at the same time, generate labyrinths.
And then he lifted the maze in 3D using OpenGL.
And then he added a network, streams and floors to it.
So meet:

# Labyrus is an open cross-platform multi-threaded network game written using OpenGl and Qt.

## Designations

The labyrinth consists of "cells". Walls can only stand between cells.
n is the width of the labyrinth,
n is the length of the labyrinth (the base of the labyrinth is a square),
h is the height of the labyrinth.

## Card generation

First, a hollow cube is created. Then a list of all the possible walls inside this cube is created in random order. After this, we try to add walls in turn. After each addition, the card is checked for connectivity by dfs. The total is a tree.

## Estimated work time

number of cells: n * n * h ,
number of walls: 3 * n * n * h ,
dfs operating time: n ^ 4 * h ^ 2 (I do not optimally store the graph),
generation time: O (n ^ 6 * h ^ 3) .

In principle, generation can be significantly accelerated. But:
1. Too lazy to write.
2. A card that takes ~ 10 minutes to complete will be generated in 0.4 s, which, in principle, fulfills the task. (Justification of laziness)

Labyrinth with h = 1. Developer Mode View from above.

## Description of executable files

• labyrus-server: generates a maze and waits for a connection.
• labyrus-server-gui: GUI to the server - for those who do not like the console.
• labyrus-client: the client part of the game - the game goes in it (requires a running server)
• labyrus-switchlanguage: to change the language (default is system). For those who like applications in% language%. Naturally, only those languages ​​that I built in (English and Russian) work.

## Control

• Management is standard - arrows and keys [ wasd ].
• Chat and commands - press [ enter ] command [ enter ].
• In full screen mode, a mouse is available.
• Switch to full screen mode and vice versa - hotkey z .
• Open the menu - escape .
• On Control - binoculars. It was just interesting for me to write it.
• In the developer mode (debug mode), the [ qe ] keys are available - vertical take-off and landing, without the test of intersections with walls.

## General scheme

First you need to raise the server. Then the players connect to the server. At the moment when the number of players specified on the server is connected, the game begins. Everyone falls down through the walls to the start. Initially, you are focused on exiting. It is always located on the same floor as you - in the opposite corner. With the --strong parameter, no further connections are possible. The player who first reached the exit wins. After the last player reaches the finish line, a new map is generated and the game restarts.

## System requirements

I don’t know how to define them, but it’s not big. OpenGL hardware acceleration is welcome. (~ 40,000 polygons in the largest maze)

## During the writing of the project, I learned a bunch of new things:

1. Seriously advanced in the development of Qt.
2. Learned how to work with OpenGl somehow.
3. I worked with Git, I can honestly say: Git is not for me. Forgive me Linus.
4. I realized that it’s worth first to at least somehow design the program, because at some point you have to redo too many things. In particular, the transition from discrete to real coordinates was very painful and carried with it the ability to set and demolish walls.
5. I ran into a bunch of interesting and not very bugs. In particular, it was not possible to compile Labyrus on Qt5 under Windows.
6. I realized that in Linux with dependencies, everything is also not so beautiful - they had to be calculated empirically and using similar programs on Qt.
7. I realized how important testers are.
8. It was very interesting to learn how object intersections are written.
9. I understood why in games usually screen resolutions are fixed. They are not fixed for me, and the transition to full-screen mode occurs without restarting the program. It was hard to implement. In addition, this creates a bunch of bugs that I leave on the conscience of users. That is, if you ran forward and switched to another window - be prepared to see how you continue to run.
10. Wrote a bot that goes through a maze. It is very interesting how to write truly complex bots.

## ... And also I knew 9 circles of hell debag application, which:

1. Graphic.
2. Opengl
3. Qt. (It is not clear who called this slot, and why the program crashed somewhere inside the Qt part)
5. Network
6. Cross-platform. (it compiles under Linux, but not on Windows. But ifdefs did)
7. Multilingual (Russian + English). Qt, of course, provides a wonderful translation system, but when text in one language is placed in the right area, but not in another, it is terrible.
8. It consists of many files (loading graphics and intercepting the output of another program). For a very long time I did not understand why everything works under Windows under me, while others have white textures. As a result, it turned out that some left libraries were missing.
9. Requires version control. No, Git, of course, I mastered. But here, how to recognize the version in the style of xx.xx.xx-buildxx, I have no idea. So far, normally done only for ArchLinux. There is at least a package creation date there.

# Authorship

The project was written by me completely, without the use of any engines, with the exception of:
1. Skins - thanks to my mom.
2. Functions begin2d () end2d () - taken from gamedev.ru.
3. Thank you for testing my classmate danpol .

# Demo

Sources
the Windows (Qt4)
the Linux-the x86 (Qt4)
the Linux-the x86_64 (Qt5)
ArchLinux (the AUR) (Qt5)

UPD April 27:
I managed to put a bunch of extra files in the archive for Windows.
LabyrusPortable.zip updated (-8Mb)