• Advertisement
Sign in to follow this  

FPS Bot Ideas(long)

This topic is 4836 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey everyone. I'm working on a bot that currently runs in multiple engines(Q3 & HL) using a common codebase, and interface layers written for each engine that define functions and pass their pointers to the bot.dll I've got a decent amount of experience in bot coding and this new framework is aiming to be both multi-game but multi-mod, and very flexible with scripting and the like. Typically in bots each bot can do tracelines to other entities to determine visibility whenever they need it. Too many tracelines can become expensive, but they are pretty necessary. I've been trying to think of a way to do this more efficiently, and I have an idea I'd like to get feedback on. Basically what I was considering is writing a class that is updated every 20-100ms that loops through all the game entities once, skips the one that don't matter to the bot, and compiles the ones that are useful into a data structure(std::multimap) on the bot side, keyed by an enum or something that represents what they are. This would basically be a trimmed down list of entities that matter most to the bot, and new entity types could easily be added to the search function and the bots would have access to them by their enum id. The next step in this update process would be to loop through this list of useful entities, and using view-cone checks, PVS functions in the engine and/or tracelines, to generate a list for each client in the game of visible entities, so instead of each bot that wants to find an entity looping through the hundreds of game entities looking for specific objects within range and visible at various parts in the code, the bot will have a list updated regularly that he can do searches based on key values. In my head, it seems like this setup could potentially be more efficient than each bot calling a find entity function from the game when it is looking for something. On one hand, if the bots do alot of entity searches and visibility checks, this concept could potentially save a good amount of processing, on the other hand, if they don't do alot of entity searches and visibility checks, the overhead of building the database would still be there, but I'm not sure this is an issue cuz just about anything useful when building bot AI requires visibility checks and stuff. just as some extra info, both HL and Q3 when searching for specific entities, loop through an array of entities, ususally several hundred entities big looking for the entities you want. So every time you search for something you potentially loop through all of the entities, especially if you're looking for the closest one, possibly doing distance calculations with each search depending on what you are trying to do. With my above idea, this could be done at 20-100ms intervals and the entity list could be looped through once and the visibility lists built for each bot and organized so it's easily searchable by an id or something, so if a bot wants to find all the projectiles, he can look them up quickly by TYPE_PROJECTILE or something in a multimap and can immediately do what he needs to do with them, rather than testing them there for visibility and stuff, cuz by design they would be visible if they're in this list. Anyone have any thoughts on this or any additional ideas? Thanks J

Share this post


Link to post
Share on other sites
Advertisement
Uhh, anyone? I guess if I'm not trying to make an MMORPG by myself it's tuff to get a reply? :)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
if you're not working on anything completly out of this world and/or completly abstract,its tuff to get any replies.:)
By entities,you mean the adversaries right?If thats the case,determining the distance between the bots before anything else seems to be a good idea to me.I mean,visbility or not,if they are too far apart,theres no use.Thing would be to make the tracelines,but only for the two or so closest "entities".That way,not only does it save time,but it also gives a realistic view to this,since the bot will seem to be "preoccupied" by one confrontation at a time!
Thats just my idea though,no doubt theres better.

Share this post


Link to post
Share on other sites
I think you answer your question yourself... yes it's a good idea to cache visibility info.

I demonstrate something similar in the example in my new book. Each bot caches visibility info in its "short term memory" once every 200 milliseconds or so and then all queries are made to the memory instead of the engine. It's much more efficient and enpowers the design because you can easily implement stuff like the bot not forgetting an enemy as soon as it goes out of sight etc

Share this post


Link to post
Share on other sites
More than just the enemy bots and clients, by entities I mean live projectiles(grenades/rockets/...) In the near future I plan to implement some dynamic object avoidance which basically means I'm going to have to build a list of object anyways, so that would take advantage of this concept as well. It sounds efficient, I was asking to see if anyone else could come up with any flaws that I didn't think of.

Thanks for the responses.

Share this post


Link to post
Share on other sites
"More than just the enemy bots and clients, by entities I mean live projectiles(grenades/rockets/...)"

yes, I know :)

Share this post


Link to post
Share on other sites
Quote:
Original post by fup
"More than just the enemy bots and clients, by entities I mean live projectiles(grenades/rockets/...)"

yes, I know :)


That part was for the AP.

Share this post


Link to post
Share on other sites
You definitely are headed down the right path in attempting to reduce the number of expensive operations. Without knowing the specifics of your game though, it is difficult to make suggestions about how best to do this.

For instance, instead of building a collection of all relevant objects every x ms, it may make sense to cache 'on demand', as this should at most take as long as doing a pre-process step.

Another possibility would be to sort all of your objects into 'sub lists' on creation. For instance, when a rocket is fired, add it to a global 'projectile' list. When your AIs want to know how potential dangers, they could scan this list and cache the results for 200 ms. The intent here is to insert into the appropriate lists when created instead of doing repeated scans per AI. Again, this depends on where your bottlenecks are.

Share this post


Link to post
Share on other sites
Slightly off topic, but how do you actually write a bot for Q3? I know for HL there was Botman's codebase, but is there something similar in Q3?

Share this post


Link to post
Share on other sites
BrianL, since the game handles the creation and management of the various entities, I don't really have the option to divide them into seperate lists from the start, so this approach is to loop through the games entity list and build my own generic list with the relevant types at certain intervals. These lists could be quickly searchable by type enumerations or something, so when the bot needs to know about the visible projectiles for example, he will already have a list of visible projectiles, and won't have to do another search through the games entity list.

MDI, the Enemy Territory SDK demonstrates enough AI code to see how to get a bot up and running. The bot I'm doing is specifically for ET and an ET mod, but its very much the same as Q3, and ET is a free game, so is a good candidate for mods and bots. The bot sdk I'm doing is independant of the game. Right now it's working in ET and Halflife.

Share this post


Link to post
Share on other sites
This bot is going to be pretty bad ass from what it sounds like. I think your idea sounds pretty good, I would of never thought of it. If you need anything let me know. Best of luck!!!

Share this post


Link to post
Share on other sites
A few comments:
- looping through hundreds of entities often is negligible compared to the actual casting of rays / tracelines
- visibility often is symmetric: if NPC A can see NPC B's head, you could save a ray by assuming that NPC B can see NPC A when NPC B is looking in NPC A's general direction.
- it might be more efficient to batch (and sort) all rays to be cast from one NPC because of application level and CPU level caching
- correct visibility probably is less relevant for health packs and for friendly NPCs than for opposing NPCs. I wouldn't bother checking visibility for healthpacks.
- some entities do not require additional visibility checks once they have been perceived because their position can easily be predicted (rockets, trip-mines).
- consider modeling 'information overload' and 'focus': an NPC performing a close-combat knife fight shouldn't be interested in spotting other threats 50m away. Similarly, an NPC tracking four threats that are nearby and in of front of him probably won't be capable of spotting a more distant threat at the edge of his field of view.

William

[Edited by - WilliamvanderSterren on October 26, 2004 1:37:59 PM]

Share this post


Link to post
Share on other sites
Lots of good ideas there William. DrEvil, one very minor warning:

Iterating through object lists and intersect tests can vary wildly in cost between engines/games. Be sure you need some of these optimizations before you implement them. Depending on the engine and the data, some may have little gain.

For instance, if your visibility tests use a quadtree or an kdtree under the hood, there may be enough data moving into the cpu cache that batching your intersect tests may not gain much at all. The gain may also depend on the scale of the level or the complexity of the geometry.

It may be best to build a few test cases based on your expected entity load/density/geometry to compare different directions. I am definitely not suggesting any of these ideas are bad; their value just depends heavily on the code complexity they introduce as well as the gain you see for using them.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement