AIGameDev Column: Improving Development Methodology
Another installment of my Developer Discussion column at AIGameDev.com. In Can Beavis and Butthead Improve Your Game Development Methodology, I reminisce a little about the radio call-in show "Rockline". Many of the callers asked the bands how they approached writing their songs... lyrics or music first? I turn that question into one to ask of game developers... and specifically game AI programmers. How do we write our code? Bottom up or top down? Somewhere in between? Read the whole column to see how it all played out.
Christer Ericson, Director of Tools and Technology at Sony Santa Monica (the God of War team), has posted a teaser of sorts on his blog, realtimecollisiondetection.net. In Don't follow the shortest path!, he points out the near fanatical restriction to have the heuristic in A* be admissible, which is defined as not overestimating the theoretical path cost to the goal.
When the heuristic (h) is admissible, A* will return the shortest possible path. However, it also takes longer than when h is not admissible by the above definition. Even when not admissible, A* will find the path, but it may not necessarily be the shortest. His point is that we are spending a lot of calculation time achieving that shortest path when plenty of other paths would do.
When h(x) is admissible, meaning it doesn't overestimate the true cost of reaching a goal, A* is guaranteed to find a shortest path (if one exists). And herein lies the problem: much too much effort is spent in games in finding the shortest paths! There is a near obsession with admissible heuristics, which is completely misguided! Who the heck cares about the shortest path?! In our everyday lives we rarely, if ever, take a shortest path. Instead, we often optimize for search effort, taking a path we're familiar with (which we've chunked or otherwise memorized so as to require no search). Well, the same applies to games and the A* algorithm. We can reduce search effort, sometimes drastically, by forfeiting the guarantee of an optimal shortest-path using nonadmissible heuristics.
He quotes a few other researchers in the column and makes a couple of other points. While I like the idea, I wish that he would have shown some examples of why this sort of fanaticism is unwarranted... or at least overrated. Thought-provoking read, however.
In my opinion, he's on the right track. In my weekly Developer Discussion column I have even made similar points about our addiction to exactness where it is not necessary and speed where it is not warranted. There are times when we are either simply not solving the right problem or we are approaching it with a level of granularity that significantly overshoots what it is we are trying to emulate. Christer makes that point briefly above when he points out that we humans rarely take the exact shortest path. When weighed against the diminishing returns of calculating it, is it worth it?
Using Java apps of Conway's famous "Game of Life" and variants on it, they describe and show, in very simple terms, how emergence... er... emerges from very simple rules. The individual blocks don't understand the big picture... nor do they care. They just follow their own local rules. However, we perceive behaviors and interactions that aren't really there.
Peter Molyneux's Significant Scientific Acheivement!
Damn. Listen to Peter go! Peter Molyneux, of Lionhead, was interviewed by Wired. In true Molyneux fashion, it was not only a challenge for him to keep his mouth restrained on the actual subject of the interview, the upcoming Fable 2, but he was already launching into his brand of lofty advance marketing for what he states will be his next title. The nuggets on Fable were interesting, but the headline-grabber of the interview was this:
"I think it's such a significant scientific achievement that it will be on the cover of Wired," he says with a twinkle in his eye.
What the heck does that mean? Significant scientific achievement sounds awfully strong. The thing is, with Peter, you don't know if he's just puffing up or if there is something behind that. Black & White, for example, did make a few people in the game world, especially the AI programmers, think a little bit. Was that a significant scientific achievement, however? Not really. In fact, I have a hard time thinking of what advances in game AI or simulation could be considered as such. So really, that leaves us with no yardstick with which to compare Peter's comment to.
"My next game will not be Fable 3. It's not a game I can talk to you about right now, but: AI, simulation, the way characters interact -- we've had smart people working on that stuff for over a decade with the Fable games and Black and White." His next game consolidates all of what they have learned, he says.
I guess at that point his ubiquitous "PR handler" jumped in and muzzled him.
The question, as always, with Peter is... how seriously do you take him? I wrote a brief post about Peter's new game back in early March. In the interview I referenced there, he said that you would be able to "replay your life." Of course, I'm not entirely sure what that means. I don't believe the interviewer was either.
Now I know some of the dudes from Lionhead. And I know a few who used to work at Lionhead. I haven't talked to them about this specific project... and I won't push buttons - I'm not a journalist. However, in considering what I have heard from them in the past about how things work over there, this project of Peter's could either be a very focused, miracle-maker, or it could still be wandering in the conceptual wilderness without a true direction. It sounds like Peter knows where he's headed however.
On a side note, this reminds me that I never did type up my notes and perceptions of Fable 2 as presented by Peter at GDC 2008. I wonder if that is still relevant? Oh well. Hopefully I will have some time to play catch-up here soon.
Yet another entry in my weekly Developer Discussion column at AIGameDev.com. In The Little-Used Tools of Game AI, I continue an informal poll from the 2008 GDC AI Roundtables. We were all asked what types of technologies and algorithms we were using in commercial games.
I used a metaphor of a Swiss Army Knife... lots of cool tools that mostly go unused. Here's a blurb from the intro.
Looking through web sites, books, and the various conferences such as GDC and AIIDE, there is an endless parade of esoteric, seemingly mystical techniques. As perpetual students in our rapidly-changing art, we read and attend with a reverent demeanor of an exploratory scientist. We soak up all the knowledge and ponder the applications and implications. We engage in heady, philosophical discussions with our peers. We exclaim our exuberance and proclaim our allegiance to new methodologies. And then, upon returning home to our individual, pragmatic realities. We resign ourselves to the relatively bland, yet utilitarian knife and screwdriver: Finite State Machines and Pathfinding.
And what of the other tools in the Swiss Army Knife of game AI? What about the planning and fuzzy logic? The lofty towers of neural networks and genetic algorithms? Game theory and reasoning under uncertainty? Influence maps? Minimax plays a killer game of Tic Tac Toe, right? Flocking? We've all seen articles on flocking! Not being used? Wow... there sure are a lot of tools in this knife. We can all see places where they may come in handy. Granted, some of them may be like trying to cut firewood with a 2-inch saw - but aren't some of them truly useful? So why don't we use them in the real world of creating our pretend worlds rather than simply pretending we are going to use them in the real world?
Jump on over to AIGameDev and read the full column. And, since it is a developer discussion column, please take a moment to continue the poll and post a comment.
Alex Champandard, at AIGameDev has posted a nice video analysis detailing some of the complicating issues surrounding the inclusion of destructible cover in an FPS game. He uses video from a recent trailer from the upcoming Brothers in Arms 2. As always, Alex details things rather well. He offers an off-the-cuff solution without getting terribly technical. I can understand why he can't "solve" the problem... it is usually something that is very game and engine specific. Regardless, it shows the issue itself very well.
This reminds me of a conversation that was had at the AI Game Programmers Dinner at the 2008 GDC. There was a brief exchange where we were talking about points of visibility in the games that were represented in the room. Many games tend to use around 6 points... a rectangle representing shoulders and perhaps thighs, one for the center of the body and one for the head. Others may add a few more here or there. I asked Christian Gyrling (Naughty Dog) how many they used in "Uncharted: Drake's Fortune"... his answer? 20. That's a LOT of ray casts. Admittedly, this was 20 points on the player's body to determine if the enemy AIs could see him. However, the result is the same... 20 potential raycasts for each active enemy NPC. Ouch. (Welcome to the PS3, I suppose.)
I would like to think that specialized graphics hardware and simply more processing power will make this approach more cost-effective in the near future.
Is this something that needs to be explored better, however? And what are some potential solutions to find things that are not there, make sure that behaviors fall within parameters, or look reasonable? And most importantly, how do we make sure that we have explored all the dark nooks and crannies of the potential state space at the far reaches of that combinatorial explosion to make sure that our delicate cosmic balance doesn't get sucked into an algorithmic black hole?
In my article from this last week, I touched on the furor surrounding the $100-million behemoth that is GTA 4... and how, even with that massive budget, one of the bigger gripes about the game is the AI.
Sandbox games - or at least free-roaming RPGs - are becoming more and more prevalent of late. With the likes of the GTA series, Assassin's Creed, the Fables, or Saint's Row, the latest cool thing to do is develop a massive open world where the plot is almost reduced to a mild suggestion. But, there are recurrent themes of developmental difficulty in those projects.
Is it possible for us to do a reasonable job on the AI of "sandbox"-style games? If so, how do we go about it?
Please read the full articles and comment over there... there are already some discussions surrounding my typically controversial topics.
Ok folks, I know this is getting old. I have been having horrible problems with my ISP since early April. I won't name the ISP yet, but you can look it up for yourself, I suppose. I have been with this company for 6 years and things started fairly well. However, in recent years, especially since a buyout, things have been a little more dicey. Well, this latest issue has to do with a server move gone awry. If the issue persists, I won't hesitate to name them... at about the same time as I go shopping for a new ISP - something I don't want to have to waste time doing.
Because the site has been up and down for 5 weeks, I've been a little hesitant about posting. I have plenty of material I want to put on IA on AI and have been wanting to start putting some new observations on Post-Play'em. I have been assured that the ISP issue will be solved soon (although I was told that over a month ago). However, I think that I may just start writing some of this material anyway. Since I use Blogger, everything is stored on their site first anyway. It wouldn't take me much to republish if I were to lose things.
Anyway, for those of you who have been checking the blogs and finding only errors, I apologize. I appreciate your loyalty nonetheless.
Another installment of my Developer Discussion column at AIGameDev.com. In Can Beavis and Butthead Improve Your Game Development Methodology, I reminisce a little about the radio call-in show "Rockline". Many of the callers asked the bands how they approached writing their songs... lyrics or music first? I turn that question into one to ask of game developers... and specifically game AI programmers. How do we write our code? Bottom up or top down? Somewhere in between? Read the whole column to see how it all played out.
