170. Creating a 3D dungeon (think Quake)

I’ve been meaning to create a 3D dungeon for a long time, and now I finally did it.

And in the process, I had some surprises that I wanted to share with you, mainly that Codea copes well with surprisingly big maps.

I’ll talk about those, and about the design process, in this post.

If you

• know 3D already, I hope you will find this useful
• plan to to learn 3D graphics, then you should find this interesting, it’s not too technical

It does involve meshes and shaders, but as I’ve said many times, they aren’t nearly as scary as they look. If I can use them, I’m sure you can.

The scope

I want a large dungeon with realistic walls, floor and ceiling, and realistic lighting, that I can walk through. I am not trying to create an actual game, which would involve creating animated characters, and which is much harder. It is really just the first stage of a Quake type game.

The map

I am not much of a graphic designer, so I found a map on the net. It has 23 rooms and 29 connecting corridors. I pasted it into Excel and carefully marked up all the interiors in red, as shown below. Maybe I should have started with a smaller map, but here we go, anyway..

Each dot is going to be a 10 pixel square, making the map about 925,000 pixels in total.

Coding the map

Any time you program a map-based game, you have to decide how to code the map. We need

• a set of walls that connect together in a mesh to make the dungeon
• a way of preventing the player walking through walls

One approach is to store the positions of all the interiors (the red dots). This is good for controlling where the player walks, but not so good for figuring out where the walls go.

In fact, I started with the first problem – creating a mesh of walls – because drawing speed is going to be crucial in a map this size. So I want all the walls to be defined as efficiently as possible.

This means my focus is on the yellow outline round the map, which is where the walls go.

Each square above is 10 pixels across, so what I’ll do is draw a wall through the middle of each yellow square. A wall is just a standing rectangle which is one pixel thick, so it is rather like a very thin fence, that runs through the middle of all the yellow squares.

My immediate problem is that rectangles are made of straight lines, and the yellow outline has many zigs and zags. So I need a separate rectangle for each zig and each zag. Adding rectangles to a mesh is not difficult, but it will take a long time to code all the positions of every straight yellow line above.

I wrote some VBA code in Excel that wrote the coding text for me when I selected a yellow strip of cells, so I just had to select each line, and Excel calculated the positions for me. It also wrote me code that when copied into Codea, stores each rectangle in a vec4 variable (just a set of 4 numbers, that’s all) with the start and end positions of each line. The height (y axis) is the same for the whole wall, so all I need is the

• x (width – left and right in the map above)
• z (depth – up and down in the map above)

positions for the start and end of each wall. So each vec4 codes for one wall segment. (If this isn’t clear, don’t worry, it’s not that important).

Creating the mesh

I wrote a function that adds a rectangle to a mesh, and then pushed all my map data through it. The whole mesh uses a single wall texture. More on this below.

I added a roof and floor as a separate mesh because they use a different earth like texture. Each of them is a single enormous rectangle that covers the entire map.

Texturing the mesh

Somewhat surprisingly, texturing meshes (in other words, overlaying a picture on the wireframe mesh) can be one of the most difficult things about 3D.

The first problem is that images are never the right scale. They can be too large or too small for your scene. So you nearly always have to rescale them.

That’s not all. Suppose your rescaled image is 73 pixels by 84 pixels. And suppose we want to overlay it on a rectangle which is 100 pixels wide by 20 pixels high. If you know anything about meshes, you’ll know you have to tell them which part of the image goes over which part of the rectangle. And if you need multiple copies of the image, as in the example I just gave, you need to break your rectangle up into smaller rectangles, each one the size of the image (the last one will be fractional). That is just nightmarish for a map this size.

That’s where shaders come in. I am using a tiling shader which will take an image and tile it (ie use it multiple times, including fractions) over any rectangle, with no fuss. So for example, I can set up one rectangle for the whole roof, give it and the texture to the shader, and it tiles the image across that huge map.

If you’d like this shader, I wrote about it here.

Lighting the mesh

You can use fancy lighting – and I’ve written a number of posts on that – but I wanted to try a very simple and obvious light, where maximum brightness is at the player position, and it reduces linearly to nil at a specified distance. This looks a lot like lamplight (example here).

Because the distance needs to be calculated for each pixel, it needs to happen in a fragment shader. I combined that with my texture tiling shader above.

Flickering light

It’s quite easy to make a light flicker. You simply vary the radius of the light. The trick is not to do it too sharply or too randomly, and the noise function is perfect for this.

My code for the light radius was as follows (in the draw function)

range = StartRange * (1 + flicker% * noise(ElapsedTime))

So I vary the “normal” radius (StartRange) by multiplying flicker% by a noise value. flicker% is chosen to give the right amount of flicker (I used 0.3).

The noise function gives you values that vary between -0.5 and +0.5. By varying the number you give it, you get different results, and if you give it a sequence of numbers, eg 0.1, 0.2, 0.3, you will get results that fluctuate fairly smoothly (the closer your sequence numbers are to each other, the smoother will be the result). So the noise function is really useful.

Walking and navigating

I kept this very simple. A touch on the left or right of the screen turns you 3 degrees (to avoid jerky turning, I only turn 0.25 degrees per frame, until I’ve turned the right amount), and a touch at the top or bottom makes you go forward or back.

How do you avoid walking through walls? I created a 2D table in memory, the same size as the map, and as I use the rectangle coordinates to create the mesh, I mark each square that contains wall. Then when I’m walking, I calculate which square I’m going to be in after the next move, and if it’s a wall, then I can’t move.

Processing speed (frames per second)

I fully expected that drawing such a complicated map, nearly 1 million pixels square, and with many more pixels in all the dungeon walls, plus the lighting. would slow my iPad3 to a crawl.

After all, there are 1,350 vertices (that’s not so bad), and close to 5 million pixels to be drawn.

In fact, I had planned to only draw the part of the map closest to the player, so I would figure out which room he was in, and have a table that told me what neighbouring rooms or corridors I needed to draw as well.

But that wasn’t necessary.

My iPad3 draws the dungeon at a blistering 50-55 frames per second, which I find utterly amazing. I realise that OpenGL does a good job of ignoring anything that won’t be seen, but I didn’t expect it to be this good.

So I didn’t need to only draw part of the dungeon…

Adding objects

This is where the real problems start.

First, it is very difficult to create a 3D object in something like Maya or Blender. Then if you want to animate it as well…. And then there’s importing a 3D object file and converting it into mesh vertices….

I haven’t tried that in this case, but I did “billboard” a few statue pictures. So called billboards are 2D pictures which you rotate to always keep them facing the camera, so it’s not obvious they are only 2D drawings. This works brilliantly for things like trees, which don’t have any obvious front or back side, so you don’t notice them rotating. The statues I put in the dungeon look a bit odd if they always face the camera no matter where you are, but I guess it’s a magical dungeon…

Finally

I usually post code, but it is a bit messy, and there is nothing really that I haven’t covered in other posts. If you want to know about anything specific , just ask.

I wanted to post a video, because it looks really good, but Codea’s built in video recorder couldn’t cope, and the Reflector app I’ve used before to mirror the iPad screen onto a PC, also had a lot of lighting artifacts that spoiled it. So, sorry, I can’t do it.

But it is great that Codea can draw a dungeon so effectively. It makes a 3D dungeon game feasible, if you can figure out how to draw and animate characters!

And if you are using 3D, or plan to do so, I cannot recommend the tiling shader highly enough. It is utterly amazing.

PS I ran both the wall and floor images through my seamless image app (covered in my previous post) so that when they were tiled, the joins would not be obvious.