Fast Pathfinding via Symmetry Breaking

This paper at AI Game Dev has immediate and natural application to roguelikes, and uses a number of techniques I've not seen discussed elsewhere. The headline quote is 'up to 30 times improvement on A*'.

I can see RSR being extended for Dijkstra maps, by storing the map cost at each rectangle corner, instead of every grid, and interpolating if required. (Paging Pender).

More Angband poetry

There was a fine fellow named Keldon [1]
Whose AI for Angband worked seldom
Quite the way you expect
Hid in rooms and forget
That you'd hit them and shot them and shelled them

[1] Apparently Keldon Jones of the Keldon Jones AI fame, may have gone onto bigger and better things...

Pathfinding Collaboration

For those of you obsessed with A* pathfinding, you'll appreciate the cold water poured on the idea this thread on rec.games.roguelike.development. And then take yourself straight to this collabourative diffusion example before you get obsessed by the trap of perfect pathfinding.

Pathfinding Redux

There is an ongoing discussion in the comments of the recent pathfinding post I did that you may want to read. Or contribute to for that matter.

The point I was making was that there can be so many complications to try to get pathfinding right, that you are probably better off coming up with a simple solution that works most of the time (such as making monsters always advance) than trying to capture all of the complexity aiming for a perfect algorithm. Your time can be more valuably spent elsewhere.

The Trap of Perfect Pathfinding

I'm firmly of the belief that there is no such thing as a perfect pathfinding algorithm. I've mentioned this during the article series on Unangband AI, but I'm working on improving traps in Unangband at the moment (a corrollory to getting druidic ongoing spell effects working), and it's very clear that in order to handle the complexity I want traps to have will overly complicate any attempt to build a 'correct' pathfinding algorithm.

I've just added the ability to avoid traps, as well as disarm them. Avoiding traps will become a more important requirement when I added ranged traps to the game (using a different implementation to NPPAngband ranged traps), but for the moment, think of it as particular trap types will not trigger if the player is in a particular state. If you are flying, you won't trigger pits or trap doors. If you are invisible, you won't trigger silent watchers. If you are in darkness, you won't trigger shafts of light. And so on.

My favourite is surreal paintings: you won't trigger these traps if you can see the painting. Which is just the kind of mess with your head weirdness that a magical scene that comes to life when you aren't looking should convey.

An important part of this concept is ensuring that the player can learn the various ways of avoiding traps. To do this, I try to make many of the trap types result in the game condition that then allows you to avoid the trap. This allows you to learn the associated way of avoiding the trap. For instance, one effect shafts of light can do is darken the room - which brings on the condition of darkness that prevents them from working. Similarly, magical symbols don't affect you if you have run out (or nearly run out) of mana. And an early magical symbol effect will be to drain you of mana.

Here's where the complication comes in: I want to make monsters avoid traps under the same scenarios as the player - to help the player learn these associations further. But this means that correct pathfinding will not only require knowing about the monster's permanent abilities, but their temporary ones. Which complicates pathfinding, because I need to model future effects. In particular, magical symbols will mean I'll need to model the monster's regeneration of mana, to determine whether they can safely cross an area filled with magical symbols (or more importantly, a single magical symbol with an area effect).

I've always had this problem, of course, because of dynamic terrain. Consider the following scenario and tell me how to design a pathfinding algorithm to handle it:

A monster runs into the room to attack the player standing in the doorway. Half way across, the player pulls a lever that floods the floor of the room with oil, then pulls out a match. Should the monster: a) keep advancing, b) retreat or c) stand still waiting for the player's next move? What other factors need to be considered?

Left4Dead Week: The AI Director – Part Three – The Rise and Fall

Left4Dead week will feature one short piece on Left4Dead each day this week to celebrate the full release of the game.

A number of reviews have highlighted the sophistication of the spawn system, so that you never see the director spawning zombies directly - they always appear off screen and then rush you.

What reviewers don't seem to have mentioned as frequently is the way the level design aids and abets this. If you're in a wide open area, you can be sure the zombies will be clambering over a nearby fence, crashing through windows or running over a rooftop. And in enclosed areas, you'll find holes in the ceiling from which they'll pour. The most elegantly designed area for this is the start of the first map for No Mercy, which features in the demo.

An in a post 9/11 world, Valve can't be ignorant of the significance of watching bodies falling through space.

(No Mercy has the best opening area of any of the first maps. For the best opening sequence of a final map, you'll need to play through Dead Air. At which point one of my fellow players yelled Game Over man, Game Over! the second time we watched it through.)

Left4Dead Week: An Open Question for the former Turtle Rock Studios

Left4Dead week will feature one short piece on Left4Dead each day this week to celebrate the full release of the game.

I see Left4Dead has inherited what I like to think of as the ‘grenade problem’. What I mean by this is that the investment required to get the AI to use grenades correctly is too high to justify; and unlike many other AI problems, an intermediate implementation (that is getting the AI to pickup and throw grenades badly) is worse than no implementation at all.

Ironically, the friendly AI bots in Counter Strike seem to use grenades reasonably well, and Turtle Rock Studios implemented this as well. So I was wondering what the issue behind not doing the same in Left4Dead was? And I suspect it is a simple return on investment problem. Left4Dead is intended as a coop game and friendly AI using grenades was well down the list.

(Other than that, great job guys).

[Edit: Robin has suggested an interesting alternative in the comments].

Left4Dead Week: The AI Director – Part Two – The Zombies

Left4Dead week will feature one short piece on Left4Dead each day this week to celebrate the full release of the game.

The problem with the AI director is that I think the implementation works too well for zombies, and won’t be adaptable enough for anything else. The quiet, eerie moments of being unsure whether an area will be filled with mindless undead, crouched shivering in a corner, leaning helplessly against a wall or vomiting up raw chunks of flesh, or completely empty; the variation in threats from rushing hordes, against the lesser special zombies (boomer, smoker or hunter), the adrenal rush of fighting a tank or trying to creep past a witch.

Contrast this with Half-Life 2, where there is a similar variety in enemies, but all of which are pre-figured by the environment you are moving through: no mix of head crabs, combine and Ant Lions together would make as much sense. And the simplicity of the zombie AI will make it hard to have a similar flood, of say, Nazis en mass. Any more intelligence in the enemies than that which the zombies display would dilute the flood to a surge or trickle, as they found alternate routes, held back or hid within the level to wait for you. The techniques used by the ALife in S.T.A.L.K.E.R. makes more sense for the most games: where each enemy has a distinct personality and set of goals to move through large free roaming levels.

Left4Dead Week: The AI Director – Part One – The Musical

Left4Dead week will feature one short piece on Left4Dead each day this week to celebrate the full release of the game.

The AI director works well, especially in conjunction with the musical cues which are used to tell you when you are about to be swarmed with undead en mass. I suspect some of these cues will become repetitive over time – it would be good to mix them up a little with sound cues for the same effect (such as the sound of zombies crashing through a wall, or baying for blood in the distance). I also missed the sound of other people fighting the zombie apocalypse: surely the four survivors can’t be the only people trying to escape the city. The Miles Sound system API in Source works well for this as demonstrated by the sound of gunfire in the distance in Day of Defeat or Half-Life 2.

Brainworks: Sitting on the Fence

By far and away the best game AI blog I read on a regular basis is Brainworks, by Ted Vessenes. BrainWorks is also a Quake 3 mod that Ted worked on for developing a realistic AI - that is an AI that plays like a real person would. This is in itself a complex problem - the vast majority of bots in games haven't had the development time and thought put in to get to this level of simulation. Whereas Brainworks bots look realistic even when you see their game play from their point of view.

There is something special about reading a blog by someone who has got inside a particular problem domain and really worked through the decisions and compromises required to get the problem solved. I hope with the Unangband game design articles that I'm doing a little bit of the same for you.

Imperfect machines

I don't often mention artificial intelligence news, even though I've written extensively on the Unangband AI, because there is a great blog AI Game Dev which already covers the state of the art in AI game development. But I've just read a couple of articles which re-iterate in more depth a couple of points I made about the Unangband AI, which I haven't seen mentioned much elsewhere.

Terren Suydam writes about the need for emergent behaviour in AI on Machines Like Us, because of the failure of existing AI techniques.

Soren Johnson has just put up the slides from his GDC seminar Playing to Lose, which discusses how you should make the AI in a single player game lose in an entertaining way, as opposed to try to win.

Both of these talk about forgetting about traditional AI techniques and trying to do something a little different. I find discussion of A* algorithms and goal planners quite dry and not very useful, which is why I tried to give a helicopter view of the Unangband AI as opposed to drilling down into detail. I will at some point write some more on the 4GAI that the Unangband AI is based on, as several people have requested this.

[Edit: Links to Soren Johnson's talk can be found here.