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.

If you anticipate a large persistent game world, and you don't want to end up with some game server crashing due to overload, then you have to design from the ground up a game world that is partitioned in chunks. This is in particular true if you want to run your game servers in the cloud, where each individual VM is relatively week, and memory and CPU are at a premium.

I think the biggest challenge here is that the player receives all the parts around the location of the avatar, but mobs/monsters are normally located in the server itself, and can only directly access the data about the part of the world that the server own. So how can we make the AI behave realistically in that context?

It can send queries to the other servers that own the neighboring parts, but that sounds rather network intensive and latency prone.

It would probably be more performant for each mob AI to be spread over the neighboring parts, and proactively send the relevant info to the part that contains the actual mob atm. That would also reduce the stress in a mob crossing a border between two parts, and therefore "switching server".

Have you heard of any AI design that solves those issues? Some kind of distributed AI brain? Maybe some kind of "agent" community working together through message passing?

share|improve this question
1  
what form of partitioning? each form has different advantages, and disadvantages. as well as having different ways of cutting space, and some lend more to iterative knowledge of the surrounding space in question. while others have to be force fed information about other "sections" –  gardian06 Jun 3 '12 at 13:58
    
some systems handle this by limiting activity around the edges, but not sure if this applies to your environment. –  nycynik Jun 3 '12 at 14:00
    
I want to use a square grid. All partitions are the same size (in virtual world space, not in amount of data), and not very big, to better distribute the load. They should be big enough that seeing one neighboring partition on all sides is enough for the AI perception. I probably won't be able to get away with fully hidden borders, but it should be seamless for the player up to the edge of it's perception, if not for the mobs. –  Sebastien Diot Jun 3 '12 at 14:20
    
@sebastienDiot when you say "one neighboring partition on all sides is enough" are you taking into account diagonals? I would probably suggest a scale-able n rather then 1 though if your grid partitions are big enough 1 might be fine. this could could come up in the tuning/balancing phase for consideration –  gardian06 Jun 3 '12 at 15:26
    
@gardian06 Yes, also the diagonal. So 8 neighbors (or 26 if it was split in all 3 dimensions). The problem with variable chunk size is that it makes "addressing" a lot more complicated. I prefer to have them all the same logical size. If they have little or no content, then they just take up (much) less ram. –  Sebastien Diot Jun 4 '12 at 11:03
add comment

2 Answers 2

up vote 2 down vote accepted

Spacial partitioning is a big subject with entire books devoted to it which makes a general form answer difficult, but I will try to address each one of the major types. I will talk about the collision resolution to talk about the agent resolution (an agent field of vision is essentially a collision test)

Tree Based Partitioning(BSP, Quadtree, OctTree):

I know that BSP would typically get its own section, but it acts similar enough to the others so it is here. for collisions these tend to have fast resolution at the leaves, but can have slow resolution when the object in question is across the root partition (though this is an edge case) it eliminate some of the benefits of the tree partitioning.

when using such for AI applications these have the same benefits as the collisions, but are far more likely to experience the edge cases of crossing partitions mainly because agent field of view is a bigger radius then the collisions, and tree partitioning tends to lend itself more to objects that are equal, or smaller then the surrounding objects. though you could spend some time optimizing n (depth from root).

If your planning to have a different AI controller for each leaf. this will require a great deal of messaging due to the high likelihood of the edge cases, and if your basing all messages on player/enemy-agent location then you will have to not only know what leaves are adjacent (which is counter intuitive to the vary structure to have a graph underneath a tree), or do the AI FOV tests from the player, but that means you would have to do back end checks for if you want mod dynamics, or group level behavior.

Hierarchic Based Partitioning (BVH)

You could lump these in with tree based, but they have a different methodology of construction (leaf to root instead of root to leaf), and a disadvantage (wrt AI) that is unique to them so I am breaking it off. these are vary fast for things that are spread out, and converge quickly know what is adjacent, and relatively easy to move things around, but can suffer from maybe having to be rebuilt every physics iteration.

for AI this is a late resolution system because the system is designed to not really do anything until your at a leaf (typically only 2 objects), and doesn't care about distance from one to another until it is making its root for the next parent (as these are usually built from leaf to root), and then you don't actually know where the entity is wrt to the dimensions of the leaf.

for this approach it is best if every agent had their own controller, but I would greatly discourage from using this approach for AI as its drawback is quite enormous for the purpose of AI unless you are going to run it twice with FOV data as apposed to collision data which apart from reusing existing code artifacts has little merit.

Grid based

for collisions (presuming that geometry accommodates) this approach tends to having a graph feel to it, and is designed specifically to alleviate the problems of a tree partitioning edge case (mainly because an object in more then one grid section means that a collision will happen. though these do have a draw back of being data intensive. where a tree based system would rarely have nothing in a node, and a BVH would never have nothing in a node. the grid system is essentially a 2-3 dimensional array of object arrays, and has a high likelihood that a majority of them will be empty.

Not to lose objectivity, but I would greatly endorse this system for AI. even though it can have a large memory foot print for collisions it lends itself easily to FOV tests (and could even replace the FOV tests with an adjacency test (is there a player n nodes away then react). though this approach does disallow for a unified controller system in that you would either have to overlay a tree onto the grid which loses versatility if the tree has to great of an n.

there are other spacial partitioning systems, but they do not come to mind if someone would wish to add them in an edit it is acceptable

general recommendation (this can be taken as conjecture)

a high suggestion if feasible would be to have a zone type system (areaX is a zone with its own stuff, and then adjacent areaY is a zone with its own stuff), and then inside each zone have a grid. these zones can be based on a secondary partitioning system. composition of systems is not unheard of, and is quite extensible, but just avoid redundancy of systems (systemX does all the work, but needs to cross reference systemY that needs to do the same extent of work).

When the discussion gets to the point of AI controllers (one controller for many agents, or agent groups) the point of grids do not lend themselves to unified controllers, but what you can do is have a controller for a group of agents (this is where mobs can come in), and then when one agent in the group "locates" the player/enemy agent the entire group can react. though maybe a threat processing, or something

[tangent] for some originality have the agent controller for the group do a threat calculation on the enemy, and then have tiers of responses. so you don't have the classic "playerX pulls the mob while the other players setup to ambush the mob"[/tangent]

share|improve this answer
    
Thank you. A very detailed answer. –  Sebastien Diot Jun 4 '12 at 11:14
    
I'm not sure why this answer has been accepted when it doesn't really address the AI part or the communication between separate servers. –  Kylotan Jun 4 '12 at 13:31
    
@kylotan technically based on the recommendation of a zone system (whether those zones are on one server or multiple) now if a group can cross zones or not that is more design question, and if each group has its own controller then there is no real need for communicating across servers unless there is a want for a hierarchy of group level behavior. –  gardian06 Jun 4 '12 at 18:55
    
These are exactly the issues mentioned in the question though: "mob AI to be spread over the neighboring parts", "distributed AI brain", "'agent' community working together through message passing", etc. –  Kylotan Jun 4 '12 at 19:28
add comment

I have never done this before but these are my two cents:

The AI Pathfinding algorithm is limited to a relatively small area around the mobs' spawn location e.g. 1km radius. If the player runs out of this area, the mob gives up chase. This is usually what is observed. This means that the player-visible areas and the pathfinding map the mob use are different maps. Also means you can design in a way where no mobs will cross servers.

The algorithm also does not need the massive data of texture, geometries etc that the player sees. The algorithm only needs to see a very simplified representation of the mob's immediate area so while only small part of the game world (textures, geometries, music etc) is loaded, for the player's view, a larger but simplified "obstacle map" for each mob can be loaded.

Mobs usually also can have fixed waypoint sets. If you have a large number of these waypoints, then the mob can appear to walk randomly.

If a Mob is chasing the player, the same "obstacle map" can be used for player collision detection and mob AI pathfinding (or player-chasing).

One thing I observed in WoW (although I can be wrong) is that if you ride on a very fast flying mount and try to run away from a mob's fireball, it appears that the fireball track your taken path so that it does not need to do it's own path finding.

If your AI algorithm is deterministic, you may not have to synchronise mob locations (that often) across servers for areas near the seamless boundary. Alternatively, just don't make it seamless, do a "now loading map..." splash screen when travelling across servers. On the otherhand, you still may have to sync the mob locations server to clients at some point so you might be able to reuse that code.

share|improve this answer
    
Quite interesting generally, but I don't think I can apply it in my case. –  Sebastien Diot Jun 4 '12 at 11:15
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.