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

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?

• It seems like you could use any frustum culling method for this - just expand either the frustum or the bounding volume you're testing to get the "+ a little more" part. If you search for frustum culling you should find plenty of efficient solutions - evaluating all of them and picking one for you is a bit out of scope for an answer here. ;) Once you've picked an approach that suits your situation, if you run into any trouble implementing it, feel free to edit this question to show us where you've gotten stuck and we'll do our best to help. – DMGregory Feb 11 '17 at 22:51
• @DMGregory - the server would need knowledge of the view frustum of each client; just something that the OP would need to be aware of. – Maximus Minimus Feb 11 '17 at 23:11

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.

• >the server sends entities irrespective of field-of-view: So you're saying if there's 50 people on a map you should just broadcast the data to all of them? My server started lagging once I got +30 connections and the only data it was sending was user id, x, and y so far. – joe Feb 12 '17 at 1:02
• @joe - and yet it worked for Quake. Of course you don't broadcast the data to all of them; please note the first point I made about "which entities are visible to each player". – Maximus Minimus Feb 12 '17 at 9:08
• @joe That seems quite far off for network load. 30 times user id, x, and y, are still just one packet each. With that kind of load, you can have a server handle thousands of users. In other words, your performance issue isn't sending the packets, it's something else. – Peter - Unban Robert Harvey Mar 23 '17 at 21:26

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.

• Don't forget that the OP is asking for this to happen on a server in a multiplayer game. Different clients will almost certainly be running at different resolutions and aspect ratios, as well as be located at different world-space positions and orientations. You really need to take that into account in any solution. – Maximus Minimus Feb 11 '17 at 23:10
• Missed that point. A smart server should know information about the clients view, so it can determine what the client renders. – Oliver Yasuna Feb 11 '17 at 23:18
• There is a tradeoff between server processing overhead and just sending everything, however. – Maximus Minimus Feb 11 '17 at 23:38
• @LeComteduMerde-fou very good point. If the OP wants the server to process this, then it must – Oliver Yasuna Feb 11 '17 at 23:56
• It's 2d btw should have added that. – joe Feb 12 '17 at 0:51

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.