Category: Development

After writing about “luck manipulation” in tool-assisted speed runs, I got to thinking about the subject of pseudo-random number generation. This is a topic that comes up, briefly yet inevitably, on every game engine project in existence, and I think it’s a good example of a situation where implementation choices are not always as cut and dried as conventional wisdom would have you believe.

The contemporary random number generator of choice is the snappily-named Mersenne Twister. It has an unimaginably large period, good equidistribution characteristics, and has passed many different randomness tests. It is also reputed to be faster than many runtime library implementations of rand(). I know that it has been used in game projects, as well as more widely in the scientific research community. So why isn’t using the Mersenne Twister an automatic slam dunk decision that nobody should ever think about?

First off, it is not suitable for cryptography, because observation of a number of results allows an attacker to predict future random numbers. This isn’t normally a concern for me in the projects that I write, and it usually is not a concern in game engines in general. So I’ll put this concern aside.

A somewhat more practical concern involves the amount of storage used for the state of the random number generator. It needs to store 624 words of data as the state of the machine, which is about 2.5K for each random number generator. This doesn’t sound like a lot, but when you consider that one might want to use this algorithm in a tightly resource-constrained environment (say, on an embedded processor), even a couple of K can be a concern. An application may have multiple random number generators, which would exacerbate this problem. (For example, in a game engine, you might have one random number generator for gameplay events and things that would need to be reproducible in a replay system, and another for things like special effects which do not impact gameplay.) The Gamasutra article linked above notes that the buffer size can be reduced for a tradeoff in the period of the random number generator — I didn’t rigorously check this idea against the original paper, but it sounds like a reasonable compromise.

A final concern involves execution speed. The algorithm generates 624 numbers at a time, and stores them in the state array. The process of extracting numbers out of the state array is pretty straightforward — it’s just a bunch of logical operations and shifts. When the supply of generated numbers is exhausted, the generation process is run again. However, the generation process is considerably more expensive than the extraction process. The result is a situation where the execution time of generating a random number may vary considerably from call to call. This is often undesirable, because it makes the performance characteristics of code using the Mersenne Twister harder to understand. (For example, when looking at profiling statistics, hotspots might “migrate” based on what section of the code had to stop and generate a new set of 624 numbers.)

So the moral of this story is that, like always, a tool should be selected based on a project’s particular needs and limitations, and not necessarily based on some objective notion of quality. Oh, and another take-away would be that sometimes the best tool for a job is actually a set of techniques. In this case, the humble linear congruential generator may act as a worthy complement to the otherwise stellar Twister.

I read an e-mail thread recently on the sweng-gamedev mailing list which jogged my memory about one of my most hated development clichés — “proven technology.” Why do I hate this phrase so much?

The phrase implies a certain obvious correctness — nobody ever got fired for buying IBM, right? It conveniently ignores any facts or questions about the current proposed usage, in favor of simply aping another project (whose circumstances may have been completely different). It’s an argument that’s easily “defensible” by other straw man arguments — “are you trying to say that XYZ isn’t successful?”

The only thing proven by “proven technology” is that it isn’t completely terrible, because somebody managed to ship something with it. That’s it. If you’re ever trying to convince me to use something, you better come with something better than this. 😉

I recently saw a link to this blog entry by Christer Ericson (of SCEA), which is a pretty amusing rip on an academic who has tut-tutted the game development community about poor AI. (Definitely check out the video linked in the blog entry to get the proper context for this entry.)

I frequently see gamers calling for more time, attention, and resources to be spent on “AI.” Unfortunately, I think the term has been diluted, such that it is now an umbrella term for a wide variety of techniques and problems, ranging from pathfinding to scripted sequences all the way to learning AIs. This may be a shocking statement to some, but I feel that what academia views as AI (tilted more towards the latter end of the scale) is not appropriate for many types of games. Actually, let me rephrase that: AI is not a good value proposition for many game development projects — the “bang for the buck” ratio is poor.

Why is this? Here are a couple of factors that come into play:

• It’s hard to schedule “interesting AI,” partly because it can be very dependent on other systems being complete or usable to be functional at all.
• It is difficult to quantify the benefit of “better” AI. As a matter of fact, sometimes it’s hard to decide the direction in which to move towards a “better” AI!
• The more complicated an AI is, the harder it tends to be to test and verify. (Not always true, but this is frequently the case.)

I’m going to use the crude term “proper AI” to refer to AI more complicated than state machines and rand(), usually incorporating more academic and simulation-oriented techniques, to differentiate it from the typical, highly pragmatic game AI approaches. I feel that “proper” AI is most important for games that:

• skew towards the simulation end of the spectrum — games that require realistic behavior in a wide variety of circumstances that cannot easily be pre-programmed.
• have plausible ways of demonstrating different AI behaviors in meaningful ways for a player. If the player can’t perceive AI, they can’t appreciate it.

In a corridor-based shooter, for example, developing “proper” AI (capable of operating in any area of the game, with any weapon, etc.) won’t significantly enhance the gameplay experience, and so it should be shelved in favor of scripted encounters. The genre’s conventions usually dictate enemies who will be alive for no longer than 30 seconds (of fun), maximum. I don’t care what kind of “proper” AI you put into a game actor — if their lifespan is less than 30 seconds, they aren’t going to show off any whiz-bang behavior that will be appreciated by the player before they get mowed down. It’s like meeting someone in real life, where you can only get a superficial impression of someone in 30 seconds, built up from visual appearances as well as maybe a few words or sentences exchanged. Fortunately, the appearance of doing something intelligent (through scripting), combined with other cues (audio and gestures), is just as effective at projecting the illusion of an intelligent adversary as “proper” AI. Eliza could probably hold up to 30 seconds of scrutiny — for many games, that’s perfectly adequate.

For other genres, though, “proper” AI can be quite important. For example, in a flight simulator game that includes combat, satisfying gameplay is very dependent on quality AI. The perception that an enemy (or ally) is cheating in a game of this type can really ruin the player experience, and yet the AI must be competent enough to provide a sufficient challenge to a player. Simulating pilot (and electronic) perception, squad tactics and communication, and air combat doctrine may be critical goals (particularly for a military simulation).

Another genre which pretty obviously demands better AI is that of Sims-type games. The player spends a lot of time watching and interacting with agents that are supposed to be simulated human beings, so they better act in realistic and interesting ways. No surprises here.

The roundabout point that I am trying to get at is that I think it’s most useful to think of AI in games as serving the needs of a specific gameplay idea, not something that’s inherently fun by itself. It seems like many attempts at creating more “realistic” or “better” AIs for games lose sight of the fact that they don’t really make a game much better — AI researchers get too attached to the idea of “it’s really thinking!” and lose sight of the real goal of game development, which is to make fun games. Likewise, I think that forum dwellers who cajole developers to put in “better AI” aren’t seeing the whole picture either. Game developers will use better AI approaches when they can be demonstrated to better meet the needs of gameplay, and are sufficiently well-understood to lower production risks — it’s that simple.

The Neverwinter Nights 2: Mask of the Betrayer expansion pack is out in the US now, so go pick up a copy. 🙂

(I didn’t work on it directly, but I did help out at various stages consulting on bug fixes and feature additions, particularly relating to the toolset.)