Erik Novales

Category: Games

  • When Better Isn’t Necessarily Better

    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.

  • A Game So Nice, I Played It Twice

    Puzzle Quest recently joined the elite ranks of “games that I have played to completion more than once.” Months ago, I had played and finished the Nintendo DS version of the game — I enjoyed it so much that when the Xbox Live Arcade version was released in October, I bought it again and replayed it. I recently polished off the campaign mode and got all of the achievements (with the help of Sandy, who got probably the hardest achievement, the Master Craftsman achievement), so now I think I can safely say that I’m done with Puzzle Quest.

    I briefly thought about doing some analysis on optimal play at the top of the game board, since I think it’s the one aspect of the game that’s dominated by chance more than any other. I also haven’t really found any good existing analysis out there — I only found analyses of character builds, along with speculation that Puzzle Quest is a game that’s “vulnerable” to optimal AI play in multiplayer. (I disagree, because the many different character builds and spells make it difficult to truly play optimally. I frankly find it hard to conceive of a Puzzle Quest AI that can play the match-3 game optimally and utilize all spells correctly and with maximum effectiveness.) I think that I’m lacking the motivation to follow through with a project like that, but we’ll see. Apparently the PC version is moddable, and the game is driven by XML files and Lua scripts, which should make it easier to find information about piece drop probabilities.

    There aren’t that many games that I play more than once — I have such a huge backlog that I naturally gravitate towards trying to clear some more of that, rather than playing an old game again. I know that I’ve played Jagged Alliance 2 and the Fallout games multiple times, but beyond that, I’m having a hard time coming up with additional substantive (>1 hour) games that I’ve replayed.

  • In Pursuit of Perfection

    A few weeks ago, me and Sandy went to see The King of Kong, which I can wholeheartedly recommend to just about anyone. As reviews have noted, it’s really more a movie about the people involved rather than the focus of their competition. In the movie, there is a segment that is an interview with one of the judges at Twin Galaxies, in which he discusses the workload of the job, and the backlog of submissions that he had to work through. I thought one of his comments was interesting — something along the lines of, “Most people never get a chance to see a world record being broken — I’m lucky, because I see it happen all the time.” While most people would not place the same importance on a video game world record as they would on, say, a track-and-field event, the sentiment still holds — it is exciting to see something, anything, that’s better than anyone else has done.

    I had seen sites like the Speed Demos Archive before, and had watched some of the shorter and/or more amusing movies. (Seeing Morrowind being completed in 7 minutes, 30 seconds, via exploitation of spells and items, is a hoot.) The amount of effort that goes into some of these videos is staggering — for short games, massive amounts of iteration on a game quickly add up to a large amount of time spent recording videos. For longer games, just getting through them at all, without costly mistakes, is an achievement — never mind the meticulous planning process that precedes any world-record attempt.

    A little bit of reading revealed an important distinction and bifurcation of the “speed run” scene — the demos shown on the Speed Demos Archive are done without any software assistance, and are played in real-time. They are demonstrations of how quickly a human can play games. A second class of speed demos, known as “tool-assisted speed runs,” use a variety of techniques to try and complete a game in the absolute minimum possible time. Some of these techniques include:

    • Slow motion and replay in emulators, to achieve “perfect play.” Damage is only taken in cases where it shortens the length of the run, or allows for shortcuts to be taken due to “damage bumping.”
    • Bug abuse. Almost any bug is fair game for exploitation, it seems, and speed runs frequently abuse these.
    • Luck manipulation in Darkwing Duck “Luck manipulation.” This is, to me, the most impressive technique, and one that shows the lengths to which speed runners will go in order to shorten a demo. Many older games have “flaws” in their use of random number generators, such that the game’s randomness can be exploited by someone determined enough. In short, luck manipulation aims to exploit the behavior of a game’s random number generator for player benefit. For example, this can be used to avoid random encounters in an RPG, ensure that enemies drop certain needed items when killed, or provoke enemies to appear from certain locations onscreen or at certain times.An example of this technique is shown in the image at the right (rehosted from the TASVideos site). Depending on the frame at which the enemy is killed, different items are dropped.Sometimes people go so far as to disassemble the ROM of a game to determine how the random number generator works, in order to construct a faster run. Another example of this technique is an amazing run that produces a Monopoly win in 30 seconds.

    A site known as TASVideos hosts a huge collection of these videos. I’ve spent some time watching a number of these videos, and I enjoyed them quite a bit, particularly for the games that I had played in my youth, where I am familiar with how the game is normally supposed to proceed. Here are some of my recommendations for tool-assisted speed runs worth watching:

  • Crysis Demo Impressions

    There has been quite the deluge of FPS releases and demo releases lately, and it’s been hard to keep up with all of them. I noticed that the single-player demo for Crysis had been released, so after a lengthy download, I sat down to give it a shot. To give a frame of reference for my comments, I’ve never played Far Cry, nor any of its console iterations, so I’m looking at both Crytek‘s design and engine from a fresh perspective.

    Just to get this out of the way quickly — the game looks great. It’s easily the most convincing jungle environment that I’ve seen in an FPS, and there are many nice graphical touches in the environment and on the characters themselves. I should confess that I’m playing the game on a rig that’s a year and a half old, and, consequently, playing on only medium visual detail. (For Vista users, there is apparently a DX10 version which looks quite a bit nicer.) The physical interactivity in the world is also very cool, although it should be noted that this happens less frequently than you would expect — bullets don’t really jostle and knock over things very much. Grenades, though, can shake apart small buildings, and vehicles can drive through buildings as well. It’s pretty funny. There is still numerical instability in the physics, though — it’s fairly easy to get vehicles to do funny things when driving over rough terrain or other objects. But hey, it’s still fun, and that’s what counts, right?

    The gameplay is moderately free-form, in that you are given goals to advance the storyline, but you can go about achieving those goals in whatever manner you choose. This basically boils down to having the freedom to approach objectives from any angle, and using any means necessary to take care of enemies in your path. You can take a rubber raft (with mounted .50 caliber machine gun) around the island, and try and surprise an outpost from behind. Or, you can drive a jeep (with mounted .50 caliber machine gun) straight up the road at the outpost, and go in guns blazing. Or, you can sneak through the jungle and snipe enemies with your silenced rifle. I didn’t have the patience to do much of the latter.

    One gameplay wrinkle involves "powers" that your super-special covert ops suit gives you. At any given time, you can be in armor mode, speed mode, strength mode, or stealth mode. The functions of armor mode and speed mode are fairly obvious. Strength mode gives you a boost when jumping, as well as the ability to hurl items (and people) long distances. Apparently it also greatly reduces recoil when firing, but I didn’t really mess around with it too much. Stealth mode is basically Predator camouflage, although the battery on it seems to run out quite quickly. The various modes of your suit are kind of neat, but I didn’t take the time to configure/figure out a way to switch between them very quickly, which would have made them more useful. The standard method involves holding down the mouse wheel and using a context menu — not exactly something that you can do while on the run.

    The story and dialogue so far are adequate — nothing too special here. It’s pretty much your standard macho sci-fi boilerplate. Apparently EA left the screenplay documents in the demo install, so if you care to have a look, you can spoil yourself to your heart’s content. It took me about an hour to get through the demo mission (which is apparently about a tenth of the game), which ends on an obligatory cliffhanger.

    Overall, I enjoyed the demo. I got a bit of an Operation Flashpoint vibe from the way that you could approach tactical situations in many different ways, and the fact that there are lots of different vehicles around for your use. I’m curious about whether the multiplayer will include cooperative missions, or if it will only contain adversarial multiplayer modes. They do seem to indicate that the mod tools can be used for multiplayer levels as well as single-player levels, but it’s unclear if the game’s networking will really support expansive, scripted missions in multiplayer. I know that there are a lot of challenges in making that kind of stuff work in a multiplayer environment that don’t exist when you’re talking about a single-player game.

    It’s not all roses, though. I do have a list of gripes about the game:

    1. I had a really hard time making out enemies through the foliage. This may be realistic, but the AI doesn’t seem to display much of a disadvantage when fighting in the jungle, which made fights very frustrating for me. I would have to rely on the radar display to locate enemies, rather than spotting them visually.
    2. It’s difficult to locate ammunition pickups amongst the debris of the battlefield. Since almost every object can be picked up, and the HUD displays a message any time you aim at a nearby object, it can be difficult to locate the important stuff, a.k.a. ammo, in a densely-populated area.
    3. The game noticed that I had a wired Xbox 360 controller plugged into my PC, and all of the tutorial prompts referred to buttons on the controller, even though I wasn’t using it to control the game. (I’m actually not sure if the tutorial text would refer directly to keyboard/mouse buttons if the controller wasn’t plugged in, though.)

    I can’t say for sure that I will pick this game up when it hits store shelves, but it looks pretty solid. It’s also interesting to me from a technical perspective because I believe it’s one of the first multi-platform engines that has really started to embrace multi-threading. (Note that I say "started" — from public presentations and technical talks, I believe they are still somewhat hamstrung by their legacy architecture.)

  • Proven to do what?

    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. 😉

  • An unexpected surprise

    I was at Target the other day, buying some household goods, when I decided to detour into the games section. What I found on the PC racks amazed me:

    The PC version of Secret Weapons Over Normandy

    That’s right — almost four years after it came out, I found three copies of the PC version of Secret Weapons Over Normandy on the shelf. They must be dumping the rest of them on the market — I know they haven’t been there very long, as the Target location I was at is fairly new, and from what I know about the distribution business, deals often involve taking old stock off someone’s hands in order to get the latest and greatest.

    I have to say, it was a pleasant surprise to see it on the shelves again after so long.

  • Do good games sell more copies?

    This is a great analysis of PS2 game sales and Metacritic scores for games released through December 2006. There are a few conclusions that I think can be drawn from this:

    • For a game to truly reach blockbuster status, it must be good.
    • There are many games that are good, but which don’t sell many copies.
    • Regardless of what you may have heard about the PS2 install base and how it makes any game project profitable due to its size, there are a lot of games out there that will not make back their development costs. Even if you double the North American sales for a title (generally accepted to be a crude estimate for worldwide sales), many titles are still well south of half a million copies.

    This kind of data really convinces me that Wii development is not the panacea for game developer profitability that some suggest. The mass market still must be regularly “convinced” to buy new games — it’s not like the hardcore market that Microsoft and Sony court, which keeps up-to-date on gaming news of its own volition and buys 10-12 games a year. Smaller-budget Wii games simply aren’t going to get much of a marketing push, and will face stiff competition from their peers as well as Nintendo itself. I’m also convinced that Wii consumers will still overwhelmingly prefer to buy Nintendo-produced games — this has been borne out by the sales figures released so far.

  • Game AI

    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.

  • Mask of the Betrayer is out

    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.)

  • EA Buys Bioware and Pandemic

    The story is here. Since I’ve worked pretty extensively with Bioware‘s stuff before (for Neverwinter Nights 2), I feel somehow obligated to react to this…heh. This is an interesting acquisition, and while I’m not any sort of expert in corporate finance, I do not think that this is necessarily a good move for EA. Why?

    • Some of the projects in development are risky new IP (Mass Effect and Dragon Age) — I say risky because Jade Empire, Bioware‘s first foray into the world of self-owned intellectual property, didn’t exactly set the world on fire sales-wise.
    • Some of the projects have the involvement of competitors to EA. Sega is publishing the Sonic RPG for DS, and Microsoft is publishing Mass Effect. It is unclear if Microsoft has any sort of rights of first refusal for Mass Effect sequels. It is also rumored that the MMO Bioware is working on is Star Wars-related, which would of course involve LucasArts.
    • EA was already set to publish Mercenaries 2 — by buying the developer, they’ve basically increased their risk exposure if it underperforms.
    • One of the projects, Dragon Age, appears to be a niche PC RPG. Now, while developing for the PC has the advantage of not needing to pay the console license “tax,” PC games typically do not sell anywhere near as well as console games. “Niche PC RPG” doesn’t seem to fit in very well with EA’s development philosophies — I can’t think of a single IP that EA has which they have not at least attempted to release across multiple platforms.

    EA has been very keen on creating new IP to exploit — it’s a tired gaming forum cliche, but EA really is a sequel-oriented developer, and, beyond a certain threshold, sequel sales tend to dwindle precipitously. (This doesn’t apply as much to their sports games, which obey rules of their own.) So, from their perspective, maybe paying $855 million for an infusion of new ideas doesn’t seem like such a bad gamble. Given the history of some high-profile EA acquisitions of the past, though, it seems like they are risking yet another situation where the talent flees and EA is left holding an overvalued bag of IP.

    Looking at it from another perspective, EA’s exclusivity deal with the NFL was rumored to be in the neighborhood of $1 billion. Does EA really think that they are going to get anywhere near the same kind of value out of Bioware/Pandemic?