Game/AI

Strategies for Innovation

Andrew Stern posted the following question in the "Radical reconceptions of our notions of story" thread. This question seemed to me to deserve its own thread (with my apologies for the minor edits and reformatting). -- Paul T



What are realistic strategies for game developers to innovate, particularly in AI?

Are the bloggers here satisfied or comfortable with the current pace of, climate for, or strategies for, AI innovation in games?

More pointedly, are project-by-project incremental AI improvements a strategy that will work in the long run? The way game dev jobs are structured, can substantial progress towards, say, more fully-realized virtual characters of the nature I suggested in my first comment, be made in the long-term within the slivers of R&D time given to you during game production?

I'm sure it varies from company to company, project to project, but what's your gut feeling about how it's all going to play out over time?

endorphin

Just a quick update on procedural animation theme mentioned in the Useful Middleware thread. I've been looking into NaturalMotion's endorphin quite a bit this week, and I felt obliged to post some thoughts here.

In the span of about 30 seconds, I was able to get a couple of human characters flailing around, knocking each other over, getting pushed around by various forces, and colliding with various objects in complex sequences, all at a level of quality that I think most professional animators would be happy with. No animation skill was required (which is fortunate, because I don't have any).

endorphin seems a bit limited right now by the fact that it's mainly useful for generating animations for human characters falling, stumbling, and generally getting knocked around in various ways. If you're not focused on human characters, or if you need animations not handled by endorphin's existing palette of Behaviors (say, attack animations, locomotion animations, or emotes/taunts), you're going to have to do it the old-fashioned way.

Still, though, endorphin is a huge step in the right direction. I'm really interested to see what new Behaviors will show up in the next release, and I'm encouraged that the next major endorphin release will apparently allow users to create their own Behaviors.

I'm also super curious as to what other kinds of tools might tackle the procedural animation problem from a different angle. As I mentioned in the Useful Middleware thread, there's been some very interesting work done on procedural locomotion animation for birds and fish. Speaking hypothetically, if you were in possession of a stick, and you also had all of the possibilities arrayed in front of you, you'd clearly have to drop that stick immediately, because the very thought of shaking that stick at all those possibilities is utterly preposterous.

Also, NaturalMotion released a new, free, time-unlimited Learning Edition of endorphin just a few days ago.

We highly recommend this product and/or service.

Radical reconceptions of our notions of story

It's late here in the UK, and my gargantuan AIGPW3 article is nearly done. I need to go to bed but I'm wired with writing. Time for a blog post.

When I started reading this new Gamasutra feature on stories in games, I figured it would be just another shallow review of Hollywood screenwriting for games developers, naively assuming that if game stories are constructed like movie stories then we would have better games. If only it were that simple! There seems a whole conference circuit industry of Hollywood refugees making a fast buck telling games developers basic things about filmcraft, with no comprehension of the fundamental changes in our concepts of storytelling that games are crying out for.

As it happened, Sutherland's article was much more mature and perceptive than I was expecting. Guess I should have realised that when it said he was from Microsoft Games Studios and not ThirdRateHollywoodConsulting Inc.! Anyway, as with all non-trivial discussions of story in games, the article raises more questions than it answers. Most pressing of all, is the brief discussion of gaming's central difference from the movies:

"the empathy problem is now solved, but it has been replaced by a more difficult problem: the storyteller has lost direct control of the hero. How do you define character if you're not making the choices? The answer is open-ended: writers and designers need to find new Zen, passive-aggressive ways to think about this, and to create webs of choice that are still channeled into compelling stories. We've done a little of this with branching outcomes, but that's nothing compared to what's possible. Even with a linear story structure, we can create a world in which there are several interesting ways to make the one correct choice."

Well, that justifies the plethora of talks at AIIDE2005 on stories and planning, but I do wonder to myself if we're really seeing the full implications of this shift yet. Most work on interactive narrative sees the relationship between player action and writer-constructed story as a conflict between the new development Sutherland describes and the classical models of story that we already understand. Hence the predominance of "story is destroyed" (the full effect of Fable's player-defined character is restricted to the story-free environment of its villages), or "player-defined character is destroyed" (the string of pearls story structure negates player choice at chapter transitions), or insanely ambitious "drama manager" planning approaches (the planner fights with the player trying to constantly rebuild dramatic narrative around his disruptive actions).

Perhaps more radical reconceptions of our notions of story are required to resolve this perceived conflict?

Innovating everywhere except where they're looking

I was led today to a read of Bruce Sterling's talk at the GDC in 1991, remarkable for its continued relevance nearly 15 years on, amonst other things regarding its criticism of the 'filmic' narrative aspirations of modern triple-A titles:

"A good science fiction story is not a "good story" with a polite whiff of rocket fuel in it. A good science fiction story is something that knows it is science fiction and plunges through that and comes roaring out of the other side. Computer entertainment should not be more like movies, it shouldn't be more like books, it should be more like computer entertainment."

Suddenly Bruce's attack on 'the wonderful power of storytelling' reminded me of a recent blog post from Ron Gilbert, where he laments the thematic constriction of today's mainstream PC games:

"Army guy with gun, Creepy horror guy covered in blood with gun, Big Orc with gun-sword, Skinny chick with sword and combat-thong. My eyes glazed over after a few passes up and down the aisle as I waited for one of them to seduce me into a purchase, but it never happened."

If Bruce has a point, that great games are not about great stories, just as great SF writing is not about imitating Shakespeare or Euripides, then perhaps there is actually far more progress being made in today's triple-A dev studios than most are given credit for? Ok, maybe the stories are the same male teenage power fantasies, but what about the gameplay? What about the immersion? What about the delivery of the same old narrative in ever more complex real-time interactions? Maybe we're actually doing what Bruce instructed more than we realise? Maybe the graphical adventure game genre died because it wasn't?

Pathfinding Algorithms & Search Space Representations Demo

Here's a pathfinding demo I wrote in 2003 that some readers may find useful (and thanks again to Damian for hosting this!).

The demo allows you to freely mix and match any of four different search algorithms (Breadth-First, Best-First, Dijkstra's, and A*) with any of ten different search space representations (4-way grid, 8-way grid, hex grid, quadtree, corner graph, waypoint graph, navigation mesh, and oh so much more).

You can also execute any of the four search algorithms as a bidirectional search.

Click on the image below to download.

EDIT (12/26/07): To anyone looking to get their hands on the source code for this, I regret to inform you that I recently lost it all in a hard drive crash ...

Supreme Commander

Jeff, Adam, and Greg, welcome to the blog! Tons of great stuff in the preceding posts, which I'll comment on when I have the time.

I posted this a few days ago but decided to remove and revise it, so I apologize to anyone for whom this looks familiar.

Some fine folks I used to work with are working on a brand new game, and it looks spectacular.

Normally I try not to make public comments about other peoples' games, but I think I'm OK in this case, since I'm saying good things about a game that I'm pretty sure I've been waiting my whole life to play.

There are some games that make you think about games in a whole new way, and Supreme Commander's spiritual predecessor, Total Annihilation, is one of them.

TA is not a typical real-time strategy game in the mold of games like StarCraft or Age of Empires. It's really a very different kind of game, and it's not immediately obvious the first time you play it. It's one of the few games I actively push my colleagues to play because there's so much to be learned from it (all entirely in the name of research, I assure you ...)

Some of my most cherished gaming memories are of TA game sessions -- games so epic in scope that even now they seem more like alternate lifetimes than games. In particular, I'll never forget the many tender moments when I was crushed beneath the iron boot of GPG's producer, Jake McMahon, in massive, eight-hour games of TA.

Imagine, if you will, Yours Truly in a role something like the protagonist in a War of the Worlds movie, always one small step from extinction, and Jake in the role of the seemingly omnipotent invasion force, always building, crushing, expanding, encircling, occupying all positions on the map simultaneously, such that any attempt to push Jake out of any part of the map is like trying to kick a hole in the ocean.

Imagine, if you will, a game which begins with building just enough solar panels and metal extractors to start one's base, and then planting your very first radar tower barely 3 minutes into the game ... and seeing Jake's forces smeared across the minimap like so many flakes of new-fallen snow, already populating every available acre of the terrain.

In short, his kung fu is strong.

My hat's off to the Gas Powered Games crew. I want to take this opportunity publicly congratulate GPG for making the game they've always wanted to make ... and I've always wanted to play.

Supreme Commander is going to rock my world.

Kool AIIDE

...and in the spirit of Rob's post, here are my AIIDE05 slides too, on Agent Architecture Considerations for Real-Time Planning in Games How to Plan in Real-Time and Keep Your Job. And the related paper.

Well since you're here, Adam...

... and since you're not going to tell us anything about project Dimitri, I thought I'd re-post a paper I'm sure we've all seen before, Richard Evans' and Thomas Barnet Lamb's GDC 2002 paper on Implementing Wittgenstein.

Heh heh. I remember back when I was at the media lab we were all a little shocked by this approach -- surely this technique of modeling the agents as SECONDARY to the activities they participate in violates the sacred agent/world abstraction barrier (which is the only thing that lets virtual robotics researchers like us sleep at night). Of course we didn't understand the first thing about the practicalities of full-fledged game AI system at the time, and now that I've been working on commercial games for a couple years, I find myself throwing principle out the window on a regular basis.

But maybe the BEST thing about this article is that it starts with the philosophy of Witgenstein and Heidegger and ends with pseudocode. I love that about our field: nowhere else does pie-in-the-sky philosophy have such immediate, practical influence! Marvin Minsky likes to say that "the problem with philosophers is that they never build anything." This is true, because as soon as they do we start calling them AI programmers. Look at what happened to you, Adam!

Genre-broadening greetings to all

With so many big names from today's professional game AI community getting involved here, it's an honour to be amongst you guys. However, I kind of feel guilty now for further breaking up the FPS AI coven you've got going! The last two years I've been working closely with that mysterious third person, rendering the player character on screen at all times! Crazy stuff, I know. Rob and I must be nuts.

Quick bio then. An Oxford philosophy background and subsequent wanderings, led eventually to the Evolutionary and Adaptive Systems MSc at the University Of Sussex, UK. This was followed by 1 year at AI middleware business startup Pariveda and then a job at Lionhead Studios. This led to leadership of the village AI team on Microsoft's Fable, and now the lead AI post on Lionhead's mysterious project Dimitri.

Somewhat amusingly, during my time at Pariveda in 2002 I built a demo which modded the AI in Ion Storm's Deus Ex to add group combat tactics and improved spatial reasoning to the human NPCs. This seems odd now as of course Paul was doing this for real at Ion Storm for a while, and Damian is probably the current world expert on spatial reasoning for FPS combat! Perhaps I should summarise my current theoretical interests at this stage, but that'll have to wait. I'm sure further posts will make it fairly clear ;)

Finally, well done Paul for spotting this talk I gave recently - now that's out of the bag, I shall be posting up the slides up here in the near future.

Greetings from I-90

hola AImigos,

Thanks for the blog-vitation Damian! I guess my life as a game AI guy has come ironically full circle. Years ago I started reading publications from the Synthetic Characters group at the Media Lab, which influenced how we architected our AI systems for NOLF2, and to a greater degree FEAR. Now I find myself writing for naimad's blog, and heading to the Media Lab myself.

I have a habit of putting my foot in my mouth when someone hands me a microphone, so I can only imagine where blogging will get me. There are already a bunch of interesting threads here that I would like to respond to, but I'm preoccupied at the moment wrapping up work on FEAR, and preparing to move from one end of I-90 to the other (Seattle to Boston). For now I'll just post the obligatory bio.

I've been developing AI systems for games since 1996; most recently at Monolith Productions, where I've had the privilege of working with the team behind NOLF2 and FEAR. My work has focused on developing re-usable, modular architectures to support goal-oriented behavior. My colleague at Monolith, Brian Legge, has made countless improvements to these architectures, and reused them on other games. Lately I've been excited about planning. Inspired by our adventures with chaotic goal-oriented behavior on NOLF2, and some interesting discussions in the Goal Oriented Action Planning (GOAP) group of the AIISC, I decided to take the plunge and implement FEAR's AI with a GOAP system. We hope game players will find that this approach to AI provides a noticeably more dynamic, over the top combat experience. Time will tell...

My decision to head back into academia does not indicate any lack of interest in games. I'd just like to dive into research for a while, and explore solutions to the problems I found most interesting (and challenging) while working on FEAR; communication and coordination within groups of autonomous agents. I'll be joining the Cognitive Machines research group, which aims to create machines that can communicate on human terms.

Meanwhile, I'm glad to see the future of FPS AI tech in the capable hands of smart dudes like Damian, Paul, Brian, and Greg.

And then there were 6 ...

Welcome to two more esteemed writers: Greg Alt from Surreal Software and Adam Russell from Lionhead. Game/AI has officially gone intercontinental!

And Speaking of Interactive Storytelling...

...Michael Mateas and Andrew Stern just released the final version of their one-act interactive drama Facade.

Congrats on the release! :) It was really cool to witness its development over the years - and I'm curious to see what the web discussion will be like following the release, and subsequent slashdotting... :)

Stories and Planning

Well I probably missed my window to post an actual AIIDE postmortem – I don’t think I really had anything that original to say that hasn’t been said here or elsewhere already.

I will say, however, I was pretty surprised by the emphasis (was it an entire day?) on planning techniques for interactive stories.

It’s an interesting thought, and I have no doubt that part of the reason there are so many people working on it is that there are few clearer uses for planning in this field (dare I say that planning is yet another AI technology in search of an application? For games, I mean.) Jeff, of course, has made fruitful – and nonobvious – use of it in FEAR, which I think has a lot of us really excited.

I’m much more skeptical of the thought of applying planning to story-tellling. As I see it, there are two major production hurdles preventing this, commercially speaking. The first is – and I don’t think this is nothing – that design would rather die than allow the story to be taken out of its hands (for any game that is story-driven, that is, which I would venture to say, something like Halo IS). So, okay, we’re probably not talking about making a mainstream commercial game around this thing – in fact, we probably have to resign ourselves to the fact that the kind of story that will come out of this technology will be a pretty loose sort of story – not the tight, energetic narrative of Bruckheimer, but the loose, perhaps rambling, slower-paced, more circuitous narrative of, say, Malick. So okay … we’re not talking commercially mainstream.

But that doesn’t get us around the second production problem, which I think cuts more to the heart of the matter: most planning-in-story-telling approaches are about finding a path through a complicated scene-space, a space, in fact so complicated that a greedy (say, an FSM) or scripted approach just becomes too difficult to author. But I don’t think we’ve seen any such scene space in a game yet (commercial or otherwise), and creating such a space has the potential to be mind-bogglingly expensive (speaking of the content explosion).

I remember hearing Hal Barwood at some talk or another express regret (or it sounded like regret anyway) at the decision to provide three major story branches for “Indiana Jones and the Fate of Atlantis” – early in the game, the player is asked to choose between the “brains”, “brawn” and “teamwork” paths, each of which provided an almost completely distinct sequence of puzzles and story events that only reconverged at the very end. It was, almost literally, three games in one. Totally not worth it, claimed Mr. Barwood, because most players went down one path and stopped playing, making the production-cost-per-minute-of-play for the average player astronomically high. This is precisely the reason we avoid branching storylines in our games – why divide your production energy between two branches when you could cut one and the other twice as good? Especially when no player will miss the one you cut!

Now that’s just talking about branching – imagine the horrible production-cost-per-minute-of-play of a single path through a story SPACE. Can we expect to see more than 10% of everything that was authored in a single play-through? And if we DO see more than 10%, I maintain, using planning is overkill! Quite the Catch-22, eh?

My skepticism notwishtanding, I hope that I’m proven wrong. I give credit to the Façade guys, because it’s clear that they’re quite aware of this problem with their own work. The smart thing they do, of course, is to tackle it on a design level as well as a technical/pipeline level. Their experience is only 15 minutes long, so you can almost be GARANTEED that a player will play it multiple times, since the commitment threshold is so low (of course you still need to make sure that your story-space is sufficiently fleshed out that a radically different experience could POTENTIALLY be had on a second playing – otherwise why will the player be encouraged to play a third time?) On the content creation side, I’m eager to see what progress they make in creating an efficient pipeline to shovel content into their engine. If the threshold for creating this content goes down, I guess the whole approach becomes practical. But unless we’re talking about text-based interactive drama experience, I don’t think we’re there yet.

Game/AI ... Now with Less Gloom!

The sun is shining in Seattle. The birds are singing, people are out on the streets laughing and playing and generally acting happy. In honor of this levity (and at PaulT’s common sense urging) I’ve changed the color scheme of our blog. No longer will visitors sink into a confused depression when they read our latest post. Now they’ll turn away with a spring in their step!

Speaking of that, there’s a spring in mine, because I’ve just added the venerable Jeff Orkin to our list of authors, filling out a commanding quadrumvirate of writers for our site.

I am massively excited about all this. As PaulT pointed out, many blogs, whatever their proclaimed intentions, turn out to be a form public psychotherapy. This blog, I’m sorry to admit, is no exception to that rule. The therapy that my own psyche needed was something – ANYTHING – to break through the isolation of your average crunch. I’ve been having a great time lately reconnecting with the academic and industry AI communities again after the long winter of Halo2 (including meeting up again with Jeff and Rob and finally meeting PaulT for the first time). And I’ve thought, wow, wouldn’t it be great if we could keep all this interesting discourse going even after we all got pulled back into our production cycles? Hence the blog, which I hope will be great source of ideas, debate, and general intellectual masturbation to its authors and anyone else willing to listen.

Hmm ... but speaking of that I wonder whether we should drop pretenses and call this the Game/FPSAI site, given who we've got writing for it. Oh no, I'm sorry, we have Rob Zubek onboard. He can be our token sim-programmer, and thus justify our claims to generality.