Looking around corners

Coding the camera in a dungeon crawler

Do you know why in the old days first-person dungeon crawlers only allowed you to turn (and look) in ninety-degree increments, straight along an axis of the map?

To answer the question, I need to explain how rotation is handled in 3D game cameras. Or more exactly, outside of them.

Wait, what? Think about it: when you're facing (say) north, and rotate 45 degrees clockwise to face northeast, everything in your field of view rotates by the same amount in the opposite direction. Relativity in action!

Figure 1: the relative motion of objects in a camera's field of view.

If you got that, you're most of the way there, because that's how 3D works in all computer graphics: the camera stays put and all the world rotates around it instead.

As for how that works, Wikipedia will happily tell you all about rotation matrices; but in code, all you need to rotate a point in a 2D plane is these two lines:

x1 = x * cos(angle) - y * sin(angle)
y1 = x * sin(angle) + y * cos(angle)

In case you did click through to get the gory details, the Greek letter Φ from mathematical notation is the angle, which by the way should be in radians. Not that you need to know that for what I'll show you below. You do need to know that the rotation always happens around the origin of the axes, the (0, 0) point where X and Y intersect. To rotate around some other point, you first need to apply an offset to all the relevant coordinates, such that the center of rotation ends up on the origin. In fact, that's like half of what a game camera does.

(To rotate in three dimensions, you simply take the X, Y and Z coordinates two by two and apply the above formula to each pair in turn. Luckily, in most games we can get by with only looking around, not so much up and down.)

Thing is, to rotate by arbitrary angles you need to do a bunch of calculations every time for each point on the map you're interested in; worse, sine and cosine are expensive functions. Not the kind of math you want to try and do on a home computer from the 1980s. But here we get lucky again: for rotating in ninety-degree steps, we can take a shortcut.

Figure 2: rotating points in a plane by 90° only swaps around signs and coordinates.

How so? Place a point on the X axis, and another on Y, no matter where; now rotate both 90 degrees counter-clockwise. What do you notice? The first point's old X has become its new Y, and the second's old Y is now its new X... except with changed sign. It's the same formula as above, except reduced to:

x1 = x * 0 - y * 1
y1 = x * 1 + y * 0

Look at the factors, and you'll see why it's called a unit matrix: we don't even do much with the numbers, we just swap them around and negate one of them. In fact you can probably figure out how to do it for the other directions.

This simple trick, plus textbook perspective projection, allowed some of the earliest RPGs to make you feel like you were really there, back when even wireframe 3D was not for the faint of heart. There's just one downside: you're playing around on a chessboard, yet can't look or move diagonally at all. Kind of limiting.

So what would be the correct factors to rotate points on a plane map in 45-degree increments? Not having much of a head for math, my first instinct was to use a sort of "half-unit" matrix, where the old X and Y both contribute in equal amounts to the new values:

x1 = x * 0.5 - y * 0.5
y1 = x * 0.5 + y * 0.5

It appeared to work as expected on first sight. Rotated points seemed to end up where they were supposed to, at least angle-wise. They did kind of "jump" too close to the camera sometimes, but I dismissed it as a visual artifact. From a first-person view it was hard to spot anyway.

Turns out I had the right idea, but the wrong multiplier.

Figure 3: rotating points in a plane by 45° follows a 5-7 rule.

To see why, place a point one unit along the X axis, at position (1, 0). Now rotate it by 45 degrees counter-clockwise. You can do it with a compass on quad paper, or with a vector drawing program. Either way, you'll notice the point ends up at roughly (0.7, 0.7) and not (0.5, 0.5)! It makes sense once you realize 0.7 is about half of the unit square's diagonal, which is 1.414, better known as √2. Sure enough, if you place the original point at (0.7, 0) instead, it will end up at (0.5, 0.5) after rotation.

My "half-unit" matrix turned out to be more of a 70% matrix. Same principle:

x1 = x * 0.7 - y * 0.7
y1 = x * 0.7 + y * 0.7

Of course, the problem with that is, now you can't avoid crunching the numbers anymore. In floating point, no less. Which is why few classic RPGs went there. Those that did used long tables of precomputed values, and that wasn't all. They also had to deal with the fact that once you can look diagonally, it's no longer possible to rely on a few premade wall pieces that fit together like Lego bricks. Now you have to deal with sprite scaling. Which takes a lot of space when you have to store pre-scaled versions for each possible distance from the camera. Another scarce resource on 8-bit machines.

Fast forward to the 21st century, when CPUs in common use all have floating point units, and can scale sprites in real time in software (no, seriously). What used to require advanced programming techniques can now be done trivially in like a hundred lines of code or so.

At this point you might ask why not allow any angle of rotation and real-time play and just make a shooter-style RPG like in the (early) 1990s.

Um, I dunno. Because there's still value in games that take place on a chessboard? Turn-based games that give you time to think? Games where you have to move carefully square by square?

At which point you don't need more than eight directions... and accepting this new limit still keeps the code dead simple. Which in turn gets it out of the way and allows you to focus on adding content.

Create immersive games through better art and writing. Technology is only an enabler. And often a little bit of it goes a long way.