Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

In a virtual place, fully network driven, with an arbitrary number of players and an arbitrary number of enemies, what data should be cached in the server memory, in order to optimize smooth AI simulation?

Trying to explain, lets say player A sees player B to E, and enemy A to G. Each of those players, see player A, but not necessarily each other. Same applies to enemies. Think of this question from a topdown perspective please.

In many cases, for example, when a player shoots his gun, the server handles the sound as a radial "signal" that every other entity within reach "hear" and react upon.

Doing these searches all the time for a whole area, containing possibly a lot of unrelated players and enemies, seems to be an issue, when the budget for each AI agent is so small.

Should every entity cache whatever enters and exits from its radius of awareness? Is there a great way to trace the entities close by without flooding the memory with such caches?

What about other AI related problems that may arise, after assuming the previous one works well? We're talking about environments with possibly hundreds of enemies, a swarm.

share|improve this question
    
It depends quite a bit on the number of players and AI and such in the game. For instance, MMOs use things like scene graphs for quick searching who is close to what for things like you mention above whereas an FPS game that is only tracking maybe 30 things total, that would be overkill and just a linked list of 30 entities is likely enough. Can you be a bit more specific in your settings? With just 5 players and 7 AI, I would say you do not need to do anything special besides have all 13 entities loaded into memory as normal. –  James Mar 21 '12 at 23:27
    
An absolutely average case of the game world is as such: over 20 regions, as in city plus surroundings. Each region is what we re considering here and it is recursively subdivided by areas, in a scene graph fashion as you said. An area can be still be bigger than the entity's awareness, and may perfectly hold 100 enemies or more, and ANY number of players. Sure there are empty areas, but also overcrowded ones –  Grimshaw Mar 22 '12 at 0:23
1  
I am quite interested by the feedback on this question. –  Coyote Mar 22 '12 at 0:45
add comment

1 Answer 1

There are multiple ways of doing this, but they depend on wherever you will have a large amount of interactions or a very dense population.

Unfortunately if you want your simulation to keep a good precision you will need to handle most events generated by all actors and find all/most actors requiring notification.

Cheap area collisions

Concerning the problem with awareness areas you can solve it using simple collision detection.

In a 2d world doing collision detection on circles is "cheap". For example the operation to detect if a point is in a circle only takes 2 subtractions, 2 multiplications and an addition. You don't need to do the square root as you can store and compare the square radius of your area with the square distance directly.

If you use the 2d circle in a 3d world it will basically work as a cylinder. It can be a convenient way of creating areas if height is not very important.

Events oriented radius

If the volume of events (firefight, movement...) is low you can try to detect each actor affected by each event. Your events will generate areas (where they can be heard).

This is the simplest method to implement, it's also the most flexible as you can pickup bullet/projectile impacts originating from actors outside of an area of awareness.

On the other hand once the volume of events increases you might have to either reduce the number of events triggering area scans or reduce the number of actors scanned per event.

-> You can also create small (event) zones where all events are registered together and processed in bulks (i.e. 2 bullet impacts and a foot step happening in one zone will use only one scan and be sent to all impacted entities). <-

Actor oriented areas

You can use the "awareness area" principle. IE if an actor collides with the awareness area (circle) of another actor you simply add the colliding actor to a list of potentially interacting actors. Depending on how your engine is built, you can then register for sound messages and other events originating from the actors in the list.

To check for visual contact, you can also do your visual scans only on the list of registered actors.

You don't have to check for awareness area changes every tick. You can do it from time to time, every 5 to 30 ticks for example.

If the lists start growing you can limit them to a maximum size. But then you will have to prioritize the actors to add/exchange in the lists.

Mixed approach

You can mix both approaches. You can register actors in awareness areas for events like foot steps, engine noses, etc... And other events (projectiles impacts, explosions, etc...) can trigger scans based on their importance. There is a much higher chance someone will hear a grenade explosion than a bullet impact, so the grenade explosion should trigger a more extensive scan than the bullet impact.

I would recommend you start implementing the event radius first. Once this one works and you are able to reduce/increase the precision of this method at will you can start implementing the actor awareness areas. This way you will be able to start moving some events to the second system.

Context pools

Not all actors need to be notified of all events. For example an Anti-Aircraft turret doesn't need to be notified about bullet impacts and foot steps around it, even the presence of ground units could be ignored for some units.

If you find many such special cases you can create different pool of awareness areas. An actor can make his awareness area active in multiple pools. For example you might want your ground units to react to ground units only while some missile and laser equipped units could react to air units as well. Aircrafts never need to be notified about ground impacts other than explosions...

Of course you don't need to create multiple "lists" for the pools. You can simply use a bit mask and set the right mask for each actor/area. This way you can filter with a simple or before checking the distance.

Aggregation

If you see the lists in each awareness area grow and memory is scarce you can aggregate awareness areas for groups of enemies (teams, squads, platoons, flocks, swarms...) as long as they remain close to each other. This way an entire squad can register for events or other actors/groups entering its awareness area.

Basically the group entity becomes a substitute/proxy for all scans while all members of the group are removed from the pools.

This principle can also be applied to all units inside a vehicle.

Proximity activations

If the server is really overpopulated with bots (and you really need to keep them all alive), then you can only activate awareness/AI on those within a special "activation area around each player". This way bots (or groups) inside one or more activation area keep themselves and their awareness area activated (in the collision pool). Otherwise their awareness area is removed from the pool(s) of active areas.

The frequency at which those "activation areas" scan for "awareness areas" can vary depending on the speed of the player. A player traveling at higher speed will trigger more activations than a player camping a zone (needed at least to activate roaming bots and deactivate bots who leave the area).

Also you can deactivate a player's activation area if he boards a vehicle and assign an activation area to the vehicle if it doesn't have one. This way 10 players traveling in the same vehicle don't need to have 10 activation areas.

Delegation

If you don't fear cheaters and other trouble makers you can delegate some of the event detection to the client application.

The server can periodically send a list of nearby actors (bots and players) which will be notified by client apps. The client application will have to do the scanning and event detection for all events generated by the player. The it can for example send the list of actors to notify about a shot, a bullet impact or foot steps.

This is an option, it can be valid depending on the kind of game you are making. This is a theoretical idea and I would not recommend doing this until you have full control over the delegated clients (bot servers or secured clients).


I hope this helps.

share|improve this answer
    
Your answer seems to define most of the methods that are out there, fantastic! Making a mix of all seems a good choice, for such a performance critical application, everything should be done in detail, avoiding overkill here and there. Also, I really think if the client is authoritative over ANYTHING, it can and will be cheated :P –  Grimshaw Mar 22 '12 at 19:35
    
Yeah... but if you can delegate some stuff to the client now you will be able to delegate to secondary servers later on if you want, restricting the delegation only to the servers and disabling it on the clients. Just an idea though :) –  Coyote Mar 22 '12 at 22:22
    
Its a good idea, but players will always exploit when it gets competitive... Im more in favor of using the client processing power for eye candy and stuff to enhance the experience, sound, graphics etc The server doesnt need to track everything, some things the client can assume without allowing cheating. Anyway, thanks a LOT for the answer, again, it will help balancing things! –  Grimshaw Mar 22 '12 at 22:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.