NavMesh - LoS and "Containing"

Question

For a gameserver/backend, I have a navmesh for "walkable" areas in form of points/triangles.

Now I want to check every gametick if the client is still in a legit place and if he shots/casts a spell, if his target is in line of sight.

I found several possibilities, but I am not sure what is performance-wise ideal.

To check if the player is still in the allowed area (and not wallhacking) I would check if his position is in one of the triangles with a algorithm using barycentric coordinates like this: https://github.com/SebLague/Gamedev-Maths/blob/master/PointInTriangle.cs But this would mean that every gametick I have to check soooo much triangles.

To check if its LoS I could either check if the line from the player to its target crosses one of the "border" lines of the mesh (which have no other triangle next to it). Those border lines could be computed at bake time and are just a static list for each level. But still it would be a lot lines per check. Second option I found would be to start a Simple Stupid Funnel Algorithm (http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html) until LoS is broken.

The questions now are: How does a good gameserver handle this/can it be optimised? What way to check is the best/fastest? Is it common to only check if the position is legit every now and then or every gametick?

The Levels are fairly simple (~300 mesh-triangles, ~200 border lines, 10 players, 10 npcs maybe)

Answer 1

Firstly, ~300 triangles or ~200 border lines is peanuts to a modern computer. You're unlikely to see problematic inefficiencies with such a tiny amount of data to process each tick.

To check if the player is still in the allowed area (and not wallhacking) I would check if his position is in one of the triangles with a algorithm using barycentric coordinates like this: https://github.com/SebLague/Gamedev-Maths/blob/master/PointInTriangle.cs But this would mean that every gametick I have to check soooo much triangles.

Would you really? If the player is running with speed s, then you only need to check the triangles within s * dt of the last player position you validated, not every triangle in the map. In fact, much of the time, the player will still be in the same triangle as they were in the previous tick, so your very first check will succeed and you're done without looking at even a second triangle.

As is usually the case with spatial checks, a spatial partition helps here. If you break your map into cells in a way that lets you quickly determine which cell your player is in (eg. if you use a regular grid of bins, you can just divide and round their position), then you can limit your triangle checks to only the triangles that overlap that cell. The rest couldn't possibly contain this point so we don't even need to check them.

You can store your navmesh itself in a spatial partition data structure so the set of triangles touching a cell is available on demand without searching. In some implementations (eg. BSP trees), your navmesh and the partition could even be the same structure, where each cell/leaf node corresponds to one navmesh or obstacle polygon.

But still it would be a lot lines per check.

Again, you don't need to check every line, just the ones that could potentially be in the line of sight. We can use a spatial partition to narrow the list.

You start with the set of lines touching the same cell as the player position. If none of those block the line of sight, you march your los ray into the next cell of the spatial partition along its path, and check the lines touching that cell, repeating until you reach the cell containing the target. Now you've checked only the obstacles that come close to the line of sight, rather than every obstacle in the map.