Geekly Articles each Day
📜 ⬆️ ⬇️

Labyrus: 3D maze

"You have 2 minutes to create a maze, the exit from which you need a minute."
Kob, "Start"



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

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 picked up a maze in 3D using OpenGL.
And then he added a network, streams and floors.
So, meet:

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

Legend


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

Card generation


First, a hollow die is created. Then a list of all possible walls inside this cube is created in a random order. After that, in turn, trying to add walls. After each addition, the map is checked for connectivity by dfs. Total it turns out a tree.

Evaluation of work time


number of cells: n * n * h ,
number of walls: 3 * n * n * h ,
dfs operation 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. The card, which takes ~ 10 minutes to complete, is generated in 0.4 s, which, in principle, performs the task. (Justification of laziness)



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

Description of executable files



Control



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. All fall down through the walls at the start. Initially you are exit oriented. It is always located on the same floor as you - in the opposite corner. With the --strong parameter no further connections are possible. Wins the player who first reached the exit. After the last player reaches the finish line, a new card is generated and the game is restarted.



System requirements


How to define them, I do not know, but it seems not great. OpenGL hardware acceleration is welcome. (~ 40000 polygons in the largest maze)

Comments


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


  1. Seriously advanced in the development of Qt.
  2. I learned how to work with OpenGl.
  3. I worked with Git, I can say with a clear conscience: Git is not for me. God forgive me Linus.
  4. I realized that it is worthwhile to first somehow design a 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 took with it the opportunity to build 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 good - they had to be calculated by experience and with the help of similar Qt programs.
  7. Understand how important testers are.
  8. It was very interesting to learn how to write the intersection of objects.
  9. I understand why in games, screen resolutions are usually fixed. In my case, they are not fixed, and the transition to full screen mode occurs without restarting the program. It was hard to implement. In addition, it 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 ready to see how you continue to run.
  10. Wrote a bot that runs a maze. Very interesting how to write really complex bots.

... And also I learned 9 laps of hell debug application, which:


  1. Graphic.
  2. OpenGL.
  3. Qt. (It’s not clear who called this slot, and why the program fell somewhere inside the Qt-part)
  4. Multithreaded
  5. Network.
  6. Cross platform (compile under Linux, not under Windows. But ifdefs are resolved)
  7. Multilingual (Russian + English). Qt, of course, provides a great translation system, but when text is placed in the right area in one language and not in the other, this is terrible.
  8. It consists of many files (loading graphics and intercepting the output of another program). I didn’t understand for a long time why everything works under Windows, while others have white textures. As a result, it turned out that some left-wing libraries were missing.
  9. Requires version control. No, Git, of course, I mastered. But here, how to find out 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.

Authorship

The project was written by me completely, without using any engines, except for:
  1. Skins - thanks to my mom.
  2. The begin2d () end2d () functions are taken from gamedev.ru.
  3. For testing thanks to my classmate danpol .

Demo




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

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

Source: https://habr.com/ru/post/177807/

More articles:


All Articles