|
|
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Better Pathfinding AI
In addition to adding great new features, many upcoming games simply have improved on existing AI features, particularly in the area of pathfinding. No one likes screaming at the stupidity of unit movement. Despite the seemingly simple nature of the problem, pathfinding in games has become a big topic in recent years. Many games (including our own Age of Empires) have been roasted for bad pathfinding. In the next year, we will likely see more true 3D games, necessitating the use of pathfinding algorithms that work in three dimensions rather than a hacked-up 2.5 dimensions (two dimensions with a small number of third-dimension planes at fixed heights). Pathing and moving true 3D flying units is much harder than moving units around on the ground, due to the desire to have units bank and turn realistically. So far, no one has proffered a simple solution for pathing in true 3D while taking into account things such as turn radius and other movement restrictions. Instead, most games path without any movement restrictions, use movement restrictions when possible while the unit follows the path, and resort to a contrived turn-in-place approach when movement restrictions conflict with the path.
To help compensate for the addition of this extra calculation complexity, we will likely see innovations in the way standard pathfinding algorithms (such as A*) are used. For example, I expect developers will begin to time-slice pathfinding systems so that particularly long routes can be computed over multiple game-world updates and renders. This task can get complicated in a world with dynamic terrain and many moving units, but it can be done if you're willing to spend the memory on it. And improving paths while still maintaining high frame rates is a big advantage. Also upcoming are more hierarchical pathfinding techniques. Different pathfinding algorithms or data sets can be tuned to a particular need (for example, long or short paths). A hierarchical approach also allows paths to be generated at progressively more detailed levels on an as-needed basis. Hierarchical AI Not surprisingly, RTS games have some of the most demanding AI needs. Their AI has to meet a player's expectations of a challenging strategy game, yet still make decisions within milliseconds in order to meet the game's frame-rate requirements. Hierarchical approaches to AI have been successful in helping address these needs. In hierarchical RTS AI, there are different layers to the AI. The strategic AI makes high-level decisions such as "What units should I train?" The tactical AI executes the orders given by the strategic AI in the best possible way, deciding things such as where to train the units requested by the strategic AI. Usually, the strategic AI is evaluated far less frequently than the tactical AI. There's often a third layer, which we'll call entity AI. Entity AI represents the physical entities in the game, such as units or groups, and is manipulated by the tactical AI. Thus, the entity AI is usually processed more frequently than the tactical AI (particularly if the entity AI has combined AI and animation responsibility). As the genre matures, RTS developers are finding more interesting ways to use this type of system. The upcoming Homeworld sequel, Cataclysm, builds heavily on the idea of combining simple AI behaviors. Unit aggression stances are used typically to control how far units pursue enemies. That concept is combined with the simple idea of patrolling between two waypoints. So, if the units are set in an aggressive stance while patrolling, they will attack any targets they come across. However, if the units are set in an evasive stance, they will avoid enemy contact during patrols. While this isn't hard to do (assuming the code is written well), it's an example of how the entity AI can evolve to become more complex. The Conquerors features another example of behavior combination. In AoK, your villagers stand around loafing after finishing that lumber camp on the edge of your town. In The Conquerors, villagers are smarter; they begin chopping wood after finishing constructing a lumber camp. Again, this seems simple, but it makes for a much better game (and was one of the most well-received features by AoK fans at E3). Features such as this can also help offload responsibility from the oft-overburdened tactical AI. If the tactical AI can rely on villagers to keep working after building a resource drop-site, it can remove another round of villager-tasking from its plate. A little farther out on the RTS horizon are our own RTS3 and Blizzard's Warcraft 3. Both will rely heavily on autonomous agent behavior (a fancy name for entity AI). Similar to combining simple behaviors, an event-driven hierarchical entity AI can alleviate a lot of needless AI polling by executing code only when there is a reason to do something. This frees up processor time for more AI, graphics, and other tasks. A comprehensive group-AI system also makes it a lot easier to implement features such as group-based protection. Imagine that you've ordered a group of melee units to protect some ranged units. If the ranged units aren't in danger or actively taking damage, you probably want the melee units to go beat on something. However, as soon as the ranged units take damage, you want the guarding melee units to rush over and stomp the attacking units. This is possible in a non-group-AI system, but it requires very clunky data structures and is a lot harder to achieve. And if it's a lot harder to code, then it will take longer to develop and be less robust (read: really, really buggy). On the other hand, if you have a group system you can simply pass the damage notification up to the group and let it quickly iterate through its guarding units, commanding them to attack the evil enemy units as necessary. Fun versus Difficulty One long-standing AI question is, "To cheat or not to cheat?" It used to be that game developers had to bypass the game rules that bound players in order to empower the AI. Weak AI can hurt the game experience, and allowing the computer to cheat was the only way around that problem. Happily, that's been changing over the last few years. Several games have been released in which the AI has at least some difficulty levels that don't cheat (Age of Empires, for example). This has all been done under the assumption that increased difficulty means more fun. A better, more difficult AI is more fun to play against, right? Not always.
Fresh from of a frustration-filled game against a few of The Conquerors' AI opponents, Tim Deen (one of Ensemble's designers) sent out an e-mail declaring that he really wished we'd focus on making the AI more fun to play against for the RTS3 project. Some healthy discussion ensued and we discussed the relative complexity of making an AI player harder to play against versus more fun. The consensus was that it was a lot easier to make an AI more difficult to play against. So, being good lazy programmers, we had done just that without really giving it much thought. As we start to build AI systems that can stomp good players into the ground fair and square, we need to look at the next step. That next step should be making the game fun. Since it's not much fun to play against an AI that never has a chance to beat you, the AI has to be able to put up a really good fight. Naturally, we have tools to do that, and it's easy to measure the success of that approach using lots of fun spreadsheets and graphs. It's more difficult -- and, more significantly, considerably more subjective -- to make an AI fun to play against. Conveniently, many of the tools that we already have from building difficult AIs can be leveraged to make the game more fun to play. Unreal Tournament has some great bot code that can really compete with the best players. Yet, it's also fun to play against. It intentionally makes mistakes and doesn't always do the best thing it can. While that may not be the most interesting thing from an academic AI perspective, it's a lot more fun than getting shot in the back every single time. In our RTS3 project, we're going to use the XS scripting language to control the level of difficulty. Since we have an idea of how long we'd like each game to take, our AI designers can check things such as game time, how many of the CP's units have been killed, how many of the human player's units were killed by the CP, or the score of the game to see who's "winning." Armed with that information, they can scale back the quality of the AI to make sure the game doesn't drag out long after the outcome is really determined. If you start to augment that ability with other features such as game history logging, you have the makings of a good opponent that quickly scales to your initial difficulty level and continues to give you a challenging game even as you get better. The next year or so still looks to have a heavy focus on graphics, particularly as Xbox, Playstation 2, Gamecube, and the good old PC continue to vie for visual supremacy. But, perhaps less glamorously, AI keeps chugging along and is getting better. As more developers dig into AI and realize that good AI is just as difficult as pushing tons of polygons to the screen, AI is getting increased attention. Almost every developer at E3 had an answer to the question, "So what new AI stuff are you doing with this game?" You can't get much cooler than that, which is why I'm optimistic about the continuing improvement and refinement of AI in games. ________________________________________________________
|
|
|
Features
