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

Uhh, anyone? I guess if I'm not trying to make an MMORPG by myself it's tuff to get a reply? :)

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.

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

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.

"More than just the enemy bots and clients, by entities I mean live projectiles(grenades/rockets/...)"

yes, I know :)

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.

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.

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?

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.