Recently I was contacted by the project leader for Q3/PMX. As far as the AI for PMX goes, the plan is similar to BrainWorks: they want a solid AI groundwork for Quake 3 that other mods can easily build off of. As it's been nine years since the initial release of Quake 3, computer processing power and memory storage has greatly increased, so Q3/PMX has some pretty cutting edge objectives for new AI technology. In fact, computers these days are so fast that they can run Quake 3 in a browser. As I understand it, one major portion of PMX will be reworking how Quake 3 AI handles its pathing and routing, which has been a major thorn in my side. If that problem were solved, in my mind there would be one hard problem remaining for artificial intelligence in Quake 3:
Where do you go when there are no items on the level?
This might not seem like a big deal at first glance. But remember that bots use items as the primary motivating factors for deciding where to go. The pathing and routing code will tell you how to get from point A to point B, but all of that is meaningless if you don't know what point B is. The typical strategy is for the bot to pick up the items that help it the most and require the least amount of movement. If the bot can't find any enemies, it will head to the nearest generally useful item and hope a target wanders by. Item placement is the core component of goal selection in BrainWorks.
If you take away the items, everything falls apart.
The bots will simply run after enemies and hope to maintain a reasonable distance. Even a marginally competent player could exploit the bot's predictable behavior.
When two human players are in a level that contains no items, however, they don't get confused at all. Instead they strategically run and hide around the map, using cover to create good shots on the opponent while dodging their return fire. What BrainWorks is missing (and all first person shooter AI bots for that matter) is this dynamic tactical movement. You just don't notice it's missing from BrainWorks because of the item pickup code.
It's very difficult to design AI that can recognize and avoid dangerous areas of terrain while simultaneously taking advantage of opponents in those spots. But it's not impossible. And thanks to nine years of increased processing power and memory, I think it could be a reality in today's games.
Here's the basic algorithm I have in mind. The first objective is to create a "danger map" for the level. The danger map estimates how tactically risky it is to be in each area of the level. Note that "area" needs to be relatively small-- roughly one to two square meters on the ground. Too much larger and the algorithm will get muddied, mistaking good regions for bad. Too much larger and the computation will become prohibitive.
It's far too hard to analyze the geometry of a level to create a danger map, although some simple techniques could be used for a first pass analysis. Instead, the AI could analyze statistical data of players on the level, recording where players are when they got shot and where the attacker was when they made the shot. When this data is combined with statistical tracking of how often players are in a given area, you can create an estimate of how likely you are to get shot in a given region, and how likely you are to shoot someone else. The danger map would be generated using actual statistics from hundreds or thousands of hours of play time on the map.
The likeliness of getting shot is your "danger estimate", and the chance of shooting someone else is the complementary "tactical estimate". Using these values, the AI can evaluate which areas it should definitely avoid (high danger) and which areas it should head towards (high tactics). Note that some areas might be both dangerous and valuable. Standing on top of a pillar gives great vantage for shooting nearby targets, but offers very little cover and escape routes. Bots that were high on health might consider maximizing their tactical position more important than minimizing danger, while a wounded bot would do the reverse.
This all sounds well and good on paper, but if it were actually that easy, it would have been done already. You might be wondering what the catch is.
This algorithm requires an awful lot of training data. If you divide the level into one cubic meter boxes and track danger estimates for all of them, it will take a very long time before you have reasonable estimates for the entire map. There are some tricks that can improve the estimates when less data is available, however.
The basic idea is that if you don't have enough information for the current location, you average together the data for nearby locations. You might not know exactly what position (107,523) looks like, but it's probably similar to the data you have for (110,520). If you have enough other sources of nearby information, you can come up with a reasonably good estimate. The less data you have, however, the further away you have to look for estimates, and the less likely that data is relevant.
Once you have a solid danger map, you just have to teach the bots to avoid dangerous spots and seek out high-value spots. The algorithm could even be expanded to learn which tactically advantageous spots are the best at shooting at targets in a particularly dangerous location. In other words, if the bot realized its target was in a pit, it would look for high ground that's specifically good for shooting into that pit. This might sound more sophisticated than any first person shooter AI currently in existance, and it probably is. But I believe that even simple algorithms can give results far better than the current crop of AI code. This is something that could work on today's computers.
Subscribe to:
Post Comments (Atom)
15 comments:
Something else to consider might be thinking about ammo considerations. If there's no pickups on the map, that means that all players have limited ammo before they have to switch to melee.
(at least, I think that's the case; I haven't played Q3 in ages)
What this suggests to me is the possibility of a shot-counting system. I'm a little fuzzy on the details here, but if the bot can identify bullet impact events, either on the environment or itself, then it might not be a big step to say "Everyone spawns with 100 ammo, and he's fired eighty rounds. Can I make some sort of tactical decision based on this information?"
Something similar might be done for enemy health as well.
I would disagree with the notion that FPS games don't take into account such things as strategic fire locations and cover. I have read a non-stop parade of lectures and articles about the methods of doing so in places such as the AI Game Programming Wisdom books. Now do most games do it? No. Do the best ones? Sure... quite a bit.
All in all, Ted, another solid post.
I think Dave leaves out some much older shooters - Counter Strike and Team Fortress Classic bots both had no items, although yes, they have general directions of play, those objectives are so broad in scope it's still a problem (the AI isn't that up to par but can still navigate a level reasonably well).
Deathmatch games also can work - Unreal Tournament with Instagib weapons (meaning no items anywhere) still work reasonably well - the AI won't drastically take cover, but still explores, tracks, hunts, groups depending on the team or free for all structure :)
There's no need to overengineer it if the existing way of navigation (ie; navmesh for CS:S, and nodegraphs for UT) work fine and give reasonable opponents - to increase the complexity, usually increasing the horsepower behind the navmesh or nodegraph is a good idea. Cover in UT doesn't matter as much as CS:S, so that too is something to take into account - LOS checking, etc, as you mention, for tactical games.
Expanding it past multiplayer bots, the vast majority of open world games don't have nodegraphs or set paths, but the AI copes even with no objective (ie; GTA games, Fallout, etc.), and FPS's with open worlds cope too (Far Cry as noted by Dave in his post on it).
In any case, it's interesting to suggest there is a cause to fix a problem - but the problem has existing solutions, just nothing optimal and certainly nothing perfect just yet (the academic world has working models to do this actually but they're far from commercial game standards just yet and use a lot more theory then practice).
I think I've made an implicit assumption which I didn't state in the post. That is that I'm most interested in tactical decisions for bots that play with the same rules as the player(s) in game. This would cover games like Unreal Tournament and Counter Strike, but NOT something like Farcry or Fallout.
The player's expectations of enemies change drastically based on the kinds of enemies they fight, and players have much higher standards for opponents that are supposed to be doing the exact kinds of things the player is doing. So while I think Farcry has done some good work on the tactics end of things, I'm not convinced it would look as good if you applied those strategies to an equal-footing game scenario like UT or Quake. After all, that wasn't the game situation the Farcry AI was designed to be good at.
Related to this is the issue of player speed. In equal-footing FPS games like Quake, UT, and Counter Strike, the player movement speed is generally faster than the NPCs in a game like Farcry. It's not that Farcry's targets are slow, but video game physics requires that players can move fast to make dodging meaningful. If the game is designed around an equal-footing rule set, that means the AI has to move fast too.
The problem is that the faster the AI moves, the more tactical options at their disposal, which means more opportunities to do the right (or wrong) thing. Put another way, maybe the AI in Farcry doesn't have enough speed to get itself into trouble. This is one reason I'm not convinced about their scalability to an equal-footing FPS game.
And analyzing what Andrew says about tactical movement in equal-footing FPS games, his comment is that bots in CS and UT work "reasonably well" using the internal navigation structures alone. They don't do tactical things like take cover, but they still perform strategic actions like exploring.
For the record, I'll note that the "base case" for tactical movement means assuming every space on the board has equal tactical value, not that bots would move at random. So it's not surprisingly that the result is "reasonably good" when the internal routing structure is "reasonably good".
At any rate, to summarize my point, it's that tactical movement is harder in games where the bots play with the same rules as the players because the bots have more options and the players have higher expectations of the bots. And I don't think that tactical problem has been solved very well to date. Certainly other games have made progress on easier versions of the problem, however.
Those were just examples. One better one might be STALKER, which is open world, has very equal enemies (using the same weapons, similar health).
The AI in it does take cover, use grenades (especially with some AI changes, to somewhat deadly effect) and does tactical spacing when attacking - it is somewhat limited, but is a good stab at it (especially since the "bots" don't want to die and will retreat).
I personally didn't think Far Cry was that different between enemies and the player (I couldn't dodge when I played it!), but maybe it is - I know the player has more health (but less accuracy!), but haven't played enough I guess, I only tried it round a friends house.
Again, much slower paced - and cover in it is important of course.
Fast paced games are a different kettle of fish. Counterstrike basically has no cover - there is no leaning, so basically stafing around cover or standing behind something (so your upper body is visible) is usually the best you can manager - noting the bots do attempt this, I think it's got some cover recognition.
UT, Quake ETC is more about dodging. Standing still is death, so cover is just important in blocking LOS for a vital second or so.
Oh, not to say your analysis is directly wrong, but there are decent stabs at it worth looking at over a variety of FPS game types. I've missed out others, STALKER 2 for instance implements more squad based movements from the start which I've played.
Keep up the analysis ;)
Nah, I understand what you're saying. I think you've stumbled upon a really interesting point about the pace of game play though, and how that affects a host of other things (like the value of cover).
This is actually an interesting game design data point. In my opinion, the best computer game ever is Thief. And the pace of Thief makes Far Cry NPCs look like monkeys hopped up on cocaine.
When you have a slower game, one that actively encourages the player to be patient at times, you provide the player more opportunity to think carefully. This means the game balance shifts more towards long term strategic choices and less towards short term tactical decisions. Since long term choices are generally easier for the AI to get right than short term ones, it's easier to end up with a solid game experience.
It might sound counter-intuitive that long term choices are easier for AI than short term choices. Technically stated, what's actually happening is that long term and short term choices are roughly as difficult for a computer. But humans do much better at immediate decisions and worse at longer range things. So when contrasted, humans will perform much better than AIs at quick tasks that require very precise finesse (like finding the exact right place to hide). But for more calculated tasks like where to run, AIs can do a job that's roughly as good as humans will do.
You're quite correct in that regard (which is why Civilization's otherwise good AI is let down by the problems it has doing long term plans - it physically can't sadly).
Hearing some AI research on RTS testing - ie; getting it to find degenerative tactics in the game, led to a lot of long term strategies being aimed for and therefore the short term actions looked bemusing to the player - but in fact still achieved that goal in the end (the example given was trading certain types of goods en masse got a bug where you could sell for a minimum of 1 gold, making that product make infinite money - but only time, and to a player would have looked odd, but was always a winning strategy).
I would have pointed out Thief, but in regards to cover and pathfinding, the first and second games had next to no exploration or pathing AI, and breadcrumb routes (which in some ways was good, the guards were deadly enough anyway).
I love much slower games so I can plan myself (nevermind the AI play more intelligently) - even Call of Duty in this regard beat out other FPS titles for a more permanent place on my PC, not because the AI is amazing, but it's much slower then most FPS games. When a game ends up with exactly the same weapon set as you started with, you know something was done right! (or, at least, different ;) ).
Interestingly enough, coming back to non-FPS games, Company of Heroes and similar cover-based games might be good matches for FPS AI - essentially it was built that way (mainly to look awesome, since stats can always be altered to fix the balance - although this applies less to a FPS). Tactical troops manoeuvres need to be handled on a squad level I think, but for free for all combat games, it can equally be a good methodology to follow a similar route and technology (there's various talks and info around about CoH's system).
I know that Valve's FPS games track death locations and create heat maps of where players are dieing often. With a little more data-mining (where shots are fired from as a separate graph) do you think it'd be possible to use such graphs as information for the bots?
It'd be pretty cool if servers would automatically sync the graphs (say when the server is empty at some set interval) keeping itself up to date.
Horray for slowing the pace of games down. I'm too old for twitch games anyway.
I believe there are lots of FPS Games using influence maps or properties attached to nav data. For example I know that different & official CS Bots tagged "danger zones" and the official ones automatically create cover points.
It's no rocket science and probably used in more games than one would imagine.
However it's just not used that heavily in deathmatch-type games because you don't live long enough to ever appreciate this enemy behaviour. But I remember at least 1 Bot who played the old HLDM using damage experience to weight Items and the best routes to targets.
Anyway, here's a link to an older paper from W. van der Sterren talking about "Dynamic Procedural Tactics" (resulting from Influence Maps more or less):
http://www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf
- Markus
Similar to synching bots to a heatmap stored on the server I outsourced my map to a command server seperate from the game for now. It's for ut2004 and the bots calculate visibility values as the bot goes for a visibility map along with updating deaths and kills. Any idea how to get visibilities dynamically without lagging out the bot with too much ray tracing? I use this info to find spots with low visibility , high probability of a kill, and low danger value. These ( I hope ) are good camping or snipe spots. This only works in the sort of game we're talking about.
This mod is simply amazing!!!
Playing against it on lvl 5 is extremely similar to playing against a live person!
I simply love your mod and overuse it :)
also, can i somehow run this mod, with an other mod? for example: I have a rocket launcher only mod. can i somehow use it and use your bots? :0
To run this with another mod, you would need to have access to their source code, then recompile it with both BrainWorks logic and the mod itself. And of course, if the mod included custom functionality, you'd need to write code so that the bots understand it. For example, to use BrainWorks with Instagib Q3, you'd need both sets of source code AND to inform BrainWorks bots that the railgun now deals infinite damage.
So it's certainly possible for other mod maintainers to integrate BrainWorks in, which is largely why BrainWorks is open source. But you'd have to take it up with them to make that happen.
wow thanks a lot for the explanation. Although i'm not sure that i will go through that many trouble for that.
Also, I wonder if its possible to somehow calculate, whether the bot should grab the power-up or just stay clear- sometimes he tries to grab the mega although he has only 10 hp, while i have 200.. (which seems kind of stupid) :)
Post a Comment