I haven’t written a roguelike in a long, long time. Last time, I used the traditional light-per-room model for lighting from the original Rogue; these days, I don’t find that at all satisfactory. It’s time for a proper shadowcaster.

And, to be plain, I’d forgotten how much of a hassle a shadowcaster actually is. I went to dig up maybe some example code, but the good answers were few and far between; there are several each at various roguelike sites like Dungeondweller, but the articles are written to widely varying levels of quality, most without source, and with no apparent method to compare between methods. Most of them an experienced programmer can ignore out of hand, but one of the algorithms up there is just repeated line of sight, which is dead slow. It’s enough to make a man think about writing another tutorial…

Luckily, I know what’s up, so I’m going to implement recursive shadowcasting. There’s a not-half-bad implementation in this tutorial by Gordon Lipford, but in several places he sacrifices efficiency or power for readability. Right thing to do for a tutorial. Wrong thing to do for production code. (He also has several unexplained actions here and there, writes pseudocode where interactions aren’t clear, and requires the reader to reimplement several structures from explanations, but whatever.) At any rate, his method is efficient, flexible, and less painful to implement than some of its competition, so I’m running with it.

One of the very cool things about Lipford’s method is that it’s arc-angle based. As a result, objects don’t actually have to fit a tile; rays are radiated. That means that anti-aliasing one’s shadows is in fact realistic; I’m halfway done with that in my shadowcaster now. Other things could be added, but I’ve decided to skip them for now. One of the really neat things about this modified method, though, which uprises from the line of sight algorithm is that I have accurate overhead cover rules and a good set of premise data to work in the notion of “perception.”

Simulating perception accurately is traditionally a problem for AI behavior, but in a Roguelike it’s a bigger problem than usual. Because roguelikes offer such complex tactical situations, and because speed in varying environments is such an issue, players often want to “lose” the predators by hiding. Lots of the common methods for handling roguelike behavior involve simple distance calculations, meaning monsters can semi-effectively follow you through visual obstacles which otherwise should confuse them, such as walls. Sometimes this is of great tactical advantage to the player; s/he can use slight speed or distance advantages to get around a wall with a u-turn, then rely on the monster keeping the nearest mathematical distance and walk the other way down the wall, acquiring some safety.

Now, I’m all for cheating on the player’s behalf; one of these days I’ll blog about it at length. However, there’s cheating and there’s cheating. Some of it keeps little nagging things from ruining gameplay; that’s good cheating. Being lax on player bullet collision, and being overstrict on player personal collision, means that the player “just barely gets by” when oftentimes they shouldn’t, and “just barely makes the shot” when oftentimes they shouldn’t. You can just crank the game difficulty to compensate, and it leads to a player never feeling like they were ripped off or cheated. The Japanese game company Treasure are absolute masters of this careful balance (sorry, AFAIK they don’t have an English-language page. Just pretend you can read it.) But, there’s another kind of cheating that game programmers do. Actually, there are several others; I’m gonna skip stuff like giving opponent AI information it shouldn’t have to keep it competitive. Right now, what I’m going to talk about is sacrificing realism for computation time.

There are several problems with cheating to save computation time. Some of them are reconcilable; others aren’t. Generally the least controllable issue here is that oftentimes you just can’t afford the raw horsepower to do what you want to do correctly. First person shooters in the 286/386 era are a prime example; Wolfenstein and DooM got by just fine with blitting, but given modern standards they look positively silly. The important bit here, though, is that Wolfenstein and DooM’s approximations were good enough™ they did not adversely impact the game, and until they were made outdated by the horsepower required for a more accurate solution, the impositions their techniques created generally didn’t impact the game. (There are a few exceptions, notably the 2d+height map preventing truly 3d maps, but that was more of an engine issue than an issue of approach, so whatever.)

Horsepower aside, though, there are also issues of sloth or ignorance. In fact, field of view algorithms provide an excellent example even compounded above the previous example. Gee, can you guess what I’m gonna start going on about?

The fact of the matter is that on a complex 2d planar map, even implemented well, field of vision code is moderately expensive. Hansjörg Malthaner brags, and rightfully so, that his field of view implementation can crank out a 59×59 area in under 2ms on a 400mHz k6/2. Whereas that may sound like hopelessly antiquated equipment by today’s standards, please remember that that’s talking about the field of view for just one creature; even dealing with a machine that can push 16x what that does, when you’re dealing with (say) 256 creatures – and that’s not terribly unlikely in a Roguelike at deeper levels – you’re still looking at around 32ms, just to figure out what monsters can see what. That’s before you consider anything like, say, what the monsters’ responses would be. And, to put that in perspective, we’re talking about a full two frames at 60fps (the rate at which most console hardware runs) – that’s slow enough to see a stutter, even on modern hardware.

And – I cannot emphasize this enough – Hansjörg’s implementation is good. This is not the upshot of some naïve bumbling. This is what kind of speeds one should expect.

Now, granted, this is a fairly severe situation. For one, 59×59 implies sight radius 29, which is big by anyone’s standards, and since we’re talking about area which is exponential and a workload tied to a surface unit instead of an edge, and since that workload is also exponential, then having an area that big is pretty serious. Also, games other than roguelikes don’t usually have low to middling hundreds of active, thinking opponents at a time (well, inasfar as roguelike creatures think, really, but that’s beside the point.) But, as we all know, I’m working on the Nintendo DS, which is a 67mHz ARM9; when we’re there, we’re just not talking about cutting edge computational power, and therefore speed seriously matters to me. Granted that the field of view in my game is much smaller, it’s still a pretty big issue.

This is where the kung-fu comes in. See, there are other repurcussions to choosing a field of vision mechanism other than speed. Granted speed is what we’re interested in here, but there are other things to be considered. That is, for example, why I’m not implementing the giant goto map generator of Jesse Welton’s. Instead, what I’m doing is going to give me view regions for specific tiles; that information will be enough to implement a much, much stronger perception algorithm, by gauging what fraction of a tile is visible. That way I can have monsters with very long sight who won’t notice you sneaking up on them around corners, or monsters who only see six or seven tiles away, but who notice absolutely everything in range. It should make far more satisfactory AI chase behavior, especially since I’m going to be tracking actual creature knowledge.

Anyway, that’s just what I’m working on in Southgate at the moment. New topics soon.