BentMaze 1.0: A jittered maze and radial culling
One natural fit for my XNA line drawing code is a maze game, since mazes consist of lots of thick lines, and they are easy to generate programmatically. So I had a look at some maze generation algorithms, decided to try the simple depth-first algorithm, and had myself a maze.
My original implementation of the maze generator used recursion, but the recursion was using so much of the system stack that it was blowing up on the Xbox 360 for large mazes. Apparently on Windows you get a larger default stack size, which I suppose is reasonable since PCs tend to have more RAM. Fortunately, it wasn't too hard to change my implementation to an iterative version where I manage my own heap-allocated stack. This was much more stable and probably a bit more efficient, too.
To give the maze a more organic feel, I "jittered" the grid coordinates by a random factor in X and Y. I really like the look of the jittered maze. If I allow X and Y to jitter by about 35% of the cell width, the "grid-ness" starts to fade away, while still guaranteeing an open path through the maze. It starts to look similar to a non-grid-based "amorphous maze" that I ran across, but is easier to generate.
If you crank up the jitter factor too high, though, the lines start overlapping and you get a mess of scribbles (there's a too-much-coffee joke in there somewhere):
Most maze generation algorithms don't have to generate a rectangular maze. If you define a set of cells as off-limits, the algorithm will happily work around them. My program creates a round maze, since circles and roundness seem to be a theme for my XNA code lately. Before generating the maze, I just make a pass through the cells, determine which ones are outside of the circle, and mark them as off-limits. I draw an "X" in each off-limits cell, but I could have just left them blank.
A 50 x 50 maze consists of 3,125 line segments in my program, and unless you're zoomed way out, you only see a tiny percentage of them at a time. So some culling is advisable for improved performance. Culling is the process of eliminating geometry that you can quickly determine to be invisible, to avoid the overhead of sending it through the graphics pipeline. Line.cs has a function to return the distance from a point to the line segment, so the easiest culling routine to hook up was radial culling, meaning that all lines not within some radius of the center of the viewport get eliminated. I added a mode to the program to use a smaller cull radius than is necessary, to make sure the code was working. And I added some text to show how many lines were being drawn:
So we know the coordinates of the lines in world space, and we know the position of the camera in world space, but how do we determine the radius of the circle that exactly encloses the view area, in world space? My approach was to take the upper-right corner of the viewport, which is (1, 1) in clip space, and run it backwards through the projection and view matrices, to get the coordinates in world space. The distance from that point to the camera's position is the radius that I need. Transforming backwards through the transformation pipeline isn't too hard, as long as you have (or can derive) the inverse projection and view matrices. I compute them at the same time that I compute the regular versions, which is easier (and faster) than figuring out the inverse of an arbitrary matrix. The result is a decent culling system. Of course, unless your viewport is literally circular, it's not perfect -- it will fail to cull some lines which are not visible. But it gets you within an order of magnitude of perfect culling, with very little effort. Since I allow rotation of the camera, an axis-aligned bounding box culling system would not be sufficient, and non-axis-aligned bounding box culling would have been a lot more work.
So now I have a nifty maze generator and can move my little orange disc dude (and the camera) around inside it. Next I need to prevent the dude from moving through the walls. Stay tuned!
The code works on the Xbox 360 and Windows (pixel shader 2.0 required). You can select from five different line styles (the animated linear style is quite mind-bending). You can also select from three different culling modes: cull to viewport radius, cull to 1/3 of viewport radius, and no culling. Notice the differences in the number of lines drawn and the improved smoothness, when culling is enabled.
-Mike
Comments
Anonymous
February 05, 2007
The next thing I want to add to my XNA maze game is collision detection, so my little orange disc can'tAnonymous
February 08, 2007
The comment has been removedAnonymous
February 25, 2007
Man, I totally jinxed myself when I predicted that hooking up my RoundLine collision detection / sliding