Reboot Unbeknownst

When I started thinking about how to randomly generate a maze, I had no idea that its implementation would become the basis for the rest of my project.  I only knew that I had come up with an algorithm, and that I wanted to "put it to paper."  As with the map-builder program, I initially envisioned a two-dimensional display that would simply display the maze.  Pressing any key would cause the maze to be re-generated.

I had used Qt 3 with C++ pretty extensively in a previous employment, and decided I would like to see what Nokia's acquisition and the latest version had to offer.  I toyed with the idea of keeping the entire application two-dimensional, but ultimately decided that I needed more OpenGL practice if I was ever going to get the game to a playable state.

I downloaded the Qt SDK, and started up the Qt Creator IDE.  In no time at all, I had a blank QGLWidget running in my new application.  A few moments after that, I had a simple red triangle showing brightly against the black.  (I don't recall referring to any particular OpenGL tutorial for the simple display, but it's possible I didn't figure it out on my own.)

It was finally time to begin implementing my maze-building algorithm.  I decided to start with an 11x11 array of type Direction, a simple enumeration to define which compass directions were not blocked from a given cell.  I figured that, with a maze of that size, I could determine whether the algorithm worked before extending it to an arbitrary size.

The algorithm was built similar to a simple stack-based maze solver.  I designated one cell as the start, and a set of cells as candidates for the end.  I also designated a set of bounce-back cells, which consisted of the outer border of the maze.  First, a path from the start to one of the end cells was found, randomly stepping from one cell to a neighbor.  Each newly-found cell would be added to the set of bounce-back cells.  If the path stepped into a bounce-back cell, that step would be popped off of the path's stack, and a different step would be attempted.  Likewise, if no valid step could be taken, the step to get to the dead-end cell would be popped off the stack.  Eventually, the winding path would find its way to one of the designated end cells.  At that point, the maze array was updated to keep track of the valid directions available along the path.

A new start point would then be chosen at random from among those cells which had no Direction data, since they were not among the previously-found path cells.  The cells that did contain Direction data were designated in the set of new end cells.  Once again, the outer border would be included in the bounce-back cell set.  The new path would then be determined, just like the initial path had.  This process would repeat until all of the cells in the array had Direction data.

With the maze model now complete and presumed working, I started to work on getting it to display.  I decided that the x/y plane in the QGLWidget would be the ideal place for drawing the maze, using simple lines.  I envisioned a maze centered at (0, 0, 0), with the camera sitting above, looking straight down.  Using GL_LINES, it was simple enough to get the maze drawn, with each cell being a 1x1 square.  I had to go back to some OpenGL tutorials, though, to figure out how to get the "camera" working correctly.

OpenGL doesn't really have a concept of a camera.  It is implied that the scene is viewed from the (0, 0, 0) position, looking along the Z axis, so to see the scene from different positions, the entire scene must be transformed.  In my case, I set up a perspective projection (as opposed to orthographic), with a view angle of 45 degrees in the y direction.  A little bit of trigonometry showed me how far along the Z axis I would have to transform my scene in order to see it.

Digging through the Qt API documentation a little, I found what I needed for rebuilding the maze: keyPressEvent.  I reimplemented the function in my QGLWidget sub-class, and accepted any key press as a trigger.  With the maze newly rebuilt, I didn't notice any change, however.  I needed to tell the widget to repaint itself.  I created a signal on my maze class (and made it a QObject subclass), which I emitted when the maze had finished rebuilding.  I connected that signal to the updateGL slot on the QGLWidget, and found that the display updated correctly each time the maze was rebuilt.

It was a simple matter to enter the third dimension.  I decided that the units I would be using were meters, so that each of the cells in the maze were a m².  I changed GL_LINES to GL_QUADS, added a few more vertices between glBegin and glEnd, and changed the lines into walls, half a meter tall.