# Effective way to check if an Entity/Player enters a region/trigger

I was wondering how multiplayer games detect if you enter a special region. Let's assume there is a huge map that is so big that simply checking it would become a huge performance issue.

I've seen bukkit (a modding API for Minecraft servers) firing an Event on every single move. I don't think that larger games do the same because even if you have only a few coordinates you are interested in, you have to loop through a few trigger zone to see if the player is inside your region - for every player. This seems like an extremely CPU-intense operation to me even though I've never developed something like that.

Is there a special algorithm that is used by larger games to accomplish this? The only thing I could imagine is to split up the world into multiple parts and to register the event not on the movement itself but on all the parts that are covered by your area and only check for areas that are registered in the current part.

And another thing I would like to know: How could you detect when someone must have entered a trigger but you never saw him directly in it since his client only sent you an move packet shortly before entering and after leaving the trigger area. Drawing a line and calculate all colliding parts seems rather CPU intensive if you have to perform it every time.

• Just like you'd do with a physics engine for detecting a collision. Some physics engines support this functionality with "triggers" or "sensors". They're objects that just trigger an event when there's a "collision" but don't react to the collision. – MichaelHouse Jul 1 '13 at 0:37

This is just another category of collision detection. Your server needs to be able to tell if two bounding shapes are colliding for any number of reasons and this needs to be efficient; there are many ways to achieve this. The world is then capable of having thousands of entities (including triggers) and information about which ones are currently in contact are cheaply calculated. Then idea you mention is a very rudimentary form of spatial partitioning. More complicated and dynamic methods such as kd-trees, bsp trees, octrees, spatial hashiing and dynamic bounding volume hierarchies are typically used in real games.

Games like Minecraft use a form of fixed-size chunks that act somewhat like a spatial hash. In Bukkit, presumably it limits checks to chunks - if you are in chunk (1,4) and a trigger covers chunks (19,45)-(21,47) then there is obviously no need to even consider testing your avatar against the trigger. The game will only compare your avatar to triggers that it already knows coincide with the chunk you're in. I think this is what you said your idea was, though it's hard to tell exactly what you meant.

The case of a player entering and leaving a trigger area in one update cycle doesn't really happen. The server uses discrete updates in most cases, meaning that it looks at the player's position at specific time intervals. In the general case, it checks the position after each movement. The player is simply not allowed to move fast enough - nor are triggers allowed to be small enough - that the player is able to enter and leave a trigger with a single position update.

In Minecraft again, assuming we cared about triggers as small as a single block, the player is simple not capable of moving by a whole block or more in a single iteration of the game's physics cycle. More generally, entities can only move at a smallish fraction of the block size per update cycle. Mechanics like pistons can break these rules but then there are a lot of potential bugs with such mechanics. The game can also special-case some updates or use a smaller update cycle than normal (e.g., if the player moves 1 whole block at a time, the game checks the player's original position, the ending position, and position halfway between).

More generally, especially for MMOS and even an increasing number of action games, the client does not send position updates to the server. The client sends input commands to the server such as "move forward." The server then calculates the player's new position, does whatever post-movement checks are necessary, and then sends the result back to the client. The client may have also processed the move (to hide network latency and make the game feel smoother) so the client is then responsible for lag compensation and prediction correction, handling any discrepancies in its predicted movement and the server authoritative movement its received afterward.

• Even though there are other good answers I like yours the most since you were the only one who provided me platform independet and concrete methods: kd-trees, bsp trees, octrees, spatial hashiing and dynamic bounding volume hierarchies. Thanks – Chris Jul 2 '13 at 11:19

A method I use for dividing scenes up, is to create a zone, which is essentially just an invisible cube, within this cube you can have sub-zones which are children to the parent zone. Depending on the environment you are rendering, you can optimize in relation to how you partition your world with these zones.

If you have an internal environment, you can make the building a parent zone, each room a zone and then create a portal in the doorway of each zone. Essentially, the portal checks to see if it is within your view volume and if so, renders the geometry on the other side of the portal. If you have several doorways in view, this means you can see each portal, and the contents of each room rendered visibly, but this is a local optimization, however this does relate.

In an external environment, you can register the players within zones and the players that are visible and of immediate effect to them. Once they enter this zone, the agents and players visible to the player are of high priority, so you prioritize the amount of data you process in relation to their actions over agents and players of a greater distance (or not at all if they are in a separate zone).

A quick method is a AABB collision detection with the zone, or use four points(like you're catching them in a net) and do your localized data streaming for that area as previously mentioned.

You do not need to fire an event constantly to check if they have left/entered a zone, as it is network based, you can check against child objects in the zone after so much movement has been detected, in relation to the size of the environment and then increase your checks as they draw closer to the zone limits, but this only works if zones are connected.

If you have "layers" of zone sizes, you can quickly isolate the location of an agent or player, then recursively traverse the relevant zones that are contained within each other, to find the player. This saves you traversing all zones in the environment to find them, and you can do checks in relation to what you need. If you need their rough location, find a "top layer" zone, one of the largest, but if you need their exact location, traverse down to the "bottom layer" zones, that pin point them in relation to objects.

So:

1. Register player location in zone, check zone verts, approximate player location in relation to objects (cache data, only upate if change occurs), you now have cached data you can use to locate/reference.

2. Traverse zone tree starting from top, checking if depth of information is enough(do we need their rough location in an area, or their exact transform, acceleration and velocity), traverse tree.

3. Register other players in zone, reference those from primarily player, prioritize data packet size over closer players, approximate players further away, ignore external zones (or high approximation depending on environment)

4. Do other checking here(this will validate what information we need). Check player location in relation to objects (are we leaving the zone?) if not, 2, else 1.

What you are looking for is called collision detection, and there are a ton of solutions to this.

First off, collision detect can sometimes be built into a physics engine. But it can also be its own separate system often referred to as a collision layer. A game can have multiple layers so some object sets only collide with other object sets.

Collision detection is often a multistep processes, especially objects are irregularly shaped polygons. Here are two decent articles over collision detection: http://www.gamasutra.com/view/feature/3190/advanced_collision_detection_.php http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

To sum them, up collision detection can be separated into two main steps, rough and fine. Rough is where each object has a radius equal to the distance from the center to the farthest point. Then distance is calculated between two object centers. If that distance is less than their two radii, then the objects may be colliding. This is a very simple calculation, and for some applications is enough. After rough collision, fine collision is calculated. There are many algorithms used for fine collision and they are a trade off between speed and accuracy. Some games, like physic puzzles, require extremely accurate collisions, but others may sacrifice some accuracy for speed. Some fine collision calculations include:

1. More circles. Place small circles on each point around the border of the object and then calculate distance again.
2. Overlap. There are multiple ways to calculate overlap, and if two polygons are overlapping then they are colliding.
3. Penetration depth. Some engines might not care about the exact moment when the objects collide, but how far they collide with each other.

Now calculating collision between every object every frame gets expensive fast. Often objects are grouped together to trim down the number of calculations. (Two objects far apart are not colliding and don't need to be checked.) The most common method for grouping is using a quadtree for 2D or octtree for 3D. This involves separating the game space into sub regions, placing all of the objects in those regions. The sub regions may be further subdivided based on the quadtree implementation. Then collision is only checked between objects in a particular region and possibly adjacent regions. This vastly reduces the number of needed calculations. Check out this article about quadtrees and collision: http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

If you decide to use a framework for you game (XNA, Lbigdx, Unity, etc) you might be able to use their collision system. This can be a deciding factor on what framework to use, as some are better than others at collision. If you are writing a game from scratch then there are many libraries than can be imported to do collision detection. Box2D has implementations in most languages, and is a decent choice for both collision and physics.

• This is a good answer. – MichaelHouse Jul 1 '13 at 0:38