Most efficient way to determine if an entity is in a player's field of vision?

Question

So I'm creating a real time multiplayer game.. and I only want entity data to be sent to a user if it's in their field of vision + a little more. (It's third person so it would be a giant box around a person)

What would be the most efficient way to do this? The only thing I could think of is have a giant box around the player and then loop through every entity to see if it's in the box and if it is send the data to the player, but doing that for a lot of players would be way too extensive on the server side.

So what's a workaround to this?

Answer 1

Quake was one of the first games to deal with this problem, and many of the techniques it used are potentially still valid even today.

It's source code is freely available and can be studied (it is also quite grim reading in places).

To summarize some of the techniques:

• Visibility for each map was precalculated so that fast checks could be made for which entities are visible to each player, and only visible entities need be sent.

• Because the client and server potentially tick at different rates, everything potentially visible, irrespective of field-of-view, is sent.

• Baseline states and deltas are used so that only data which has actually changed need be sent. Clients can work from a local copy of anything which is unchanged.

These were valid on low-bandwidth dial-up connections back in the late 1990s so can make a good starting point for today, and can also serve to illustrate areas that you probably don't need to be worrying about. An example of the latter is the fact that the server sends entities irrespective of field-of-view: use of baselines and deltas means that the actual data sent can be kept quite small, and this is probably not a problem.

Answer 2

Ill break it down for you...

Your goal is to find if an entity is 3-dimensional space is visible in the camera's view. Remember that your entity exists in the world space (model space), and your camera represents the screen space (or clip space). So, your goal is to transform your objects 3-dimensional coordinates to the screens location (2-dimensional). This is called world-to-screen.

Steps:

1) Calculate the view projection matrix.

vec4 viewProjectionMatrix = projectionMatrix * viewMatrix;

2) Calculate the clip space coordinates.

vec3 clipSpacePos = entityPos * viewProjectionMatrix;

3) Calculate the coordinates on screen.

vec2 windowPos = ((clipSpacePos.xy + 1) / 2) * viewSize;

EDIT 1

If your y-axis is top to bottom, then do 1 - clipSpacePos.y.

EDIT 2

The same concept can be applied in your source code of the server.

Answer 3

You can split the map into big boxes. Like this:

Then for each box, keep an updated list of the entities inside.

So when you want to know what's in the king's field of view (let's assume he sees one field far), just send all the entities in the green boxes.

You can further improve on this by choosing a smart box layout that's based on the level design.