Hi there

I've found a lot of great articles here and on the web around FPS style games and using the 'cameras' frustum to calculate if something is visible or not.

What my issue is:

Camera is largely irrelevant as i have a math/server side question: given player 1 is at 0,0,0, and player 2 is at 0,1,1 there are no obstacles - given each player has a frustum facing each other - they 'can see' each other (two people looking at each other on a flat surface).

If i introduce obstacles and alter angles - say now P1 can see P2 but P2 cannot see in return - either due to occlusion / blocking by another 3d world object - or for other reasons (angles/etc).

I cannot wrap my head around how i can do these calculations server side with math only - my game has a core mechanic riding on it - but i'm not even sure how to begin researching as most topics seem to worry about culling for the purposes of frame rates etc.

Essentially (and assume this is true): i need server side to know geometries, positions and fields of view; it should then be able to say 'can p1 see p2?', 'can p2 see p1?' - ideally just using the underlying math - something i'm struggling to get when i look at the likes of a unity thread; https://answers.unity.com/questions/8003/how-can-i-know-if-a-gameobject-is-seen-by-a-partic.html

For the record i'm using nodeJS server side (for now); and front end is JS/canvas - i don't mind too much about implementation; if someone has any idea what math i should research or begin looking for it'd be a massive help

thank you, fellow gavedevs

Build a line between the two players. If the line is outside both frustums, they can't see each other. Otherwise trace a ray through the level to see if the ray hits any obstacles in between so view is blocked. If not, any player who has the ray in frustum sees the other player.

Well, I am not really understanding your problem. You can use all the culling techniques usually used to speed up rendering to find out if 2 objects/players can see each other. Since you are only interested in the visibility of a certain object (the other player) you can calculate a reduced frustum that fully encloses the parts of the target object that are inside the full view frustum. Then run the usual occlusion culling algorithms on this reduced frustum.

7 minutes ago, JoeJ said:

Build a line between the two players. If the line is outside both frustums, they can't see each other. Otherwise trace a ray through the level to see if the ray hits any obstacles in between so view is blocked. If not, any player who has the ray in frustum sees the other player.

 I think this solution is a little bit too minimalistic. It will produce a wrong answer if players are only partially inside the frustum or if a fly or other small object that doesn't really block LOS crosses the ray.

Greetings

6 minutes ago, DerTroll said:

I think this solution is a little bit too minimalistic. It will produce a wrong answer if players are only partially inside the frustum or if a fly or other small object that doesn't really block LOS crosses the ray.

Sure, could be solved by jittereing the ray and using a temporal filter like visibility = visibility * 0.95 + newVisibilty * 0.05 (the lag from this would even make ai behaviour more natural)

To jitter the ray use a random position on a bounding capsule around palyers for example, but will require to trace two rays then instead just one.

When using simplified geometry for the purpose (maybe already there for physics / occlusion culling), or having simple geometry like Quake, the minimalistic approach should be good enough, and tiny / dynamic objects like flies could be ignored.

Which usual occlusion culling algorithm would you propose, to handle this at reasonable performance?

21 minutes ago, JoeJ said:

Which usual occlusion culling algorithm would you propose, to handle this at reasonable performance?

Depends on the accuracy that you need and the number of checks. My point was just that I didn't understand the TO's problem if he read (and understood) articles about visibility checks from the cameras POV but doesn't know how to check to objects that are not the camera. It's basically the same problem.

However, you can remove all objects from the test that are behind the target object. Then you have 2 effects when using this reduced frustums. If the object is far away, the frustum gets really small, causing a lot of objects to fail the initial frustum check. Additionally, the frustum gets completely blocked by a single object more frequently, allowing you to exit the entire test early. On the other hand, if the object is really close, you don't need to check so many objects, since the ground you need to cover is rather small.

Of course, if you have a lot of those checks to perform even that might be too much. There are many things you can do to speed things up but I know nothing in particular that doesn't apply also to standard frustum/occlusion culling. The extreme case would be the single ray solution you proposed, but as I said, I think that this might be not accurate enough for what the TO is intending to, but maybe I am wrong.

Greetings

29 minutes ago, DerTroll said:

However, you can remove all objects from the test that are behind the target object. Then you have 2 effects when using this reduced frustums. If the object is far away, the frustum gets really small, causing a lot of objects to fail the initial frustum check. Additionally, the frustum gets completely blocked by a single object more frequently, allowing you to exit the entire test early. On the other hand, if the object is really close, you don't need to check so many objects, since the ground you need to cover is rather small.

Even with those obvious optimizations the problem still requires either poly clipping for an accurate soultion (e.g. the beam tree - one of Cramacks failures), or a discrete sampling approach like rasterizing or raytracing a frame buffer representing the frustum (a narrower frustum is still a frustum). Any of this is challenging even for a single viewport, but much too slow for the line of sight tests needed for many players / bots.

AFAIK, all 3D games use raytracing for this purpose, with a single ray (EDIT: or a few of them, maybe for each larger bone of the skelton?), but i remember 2D games that had accurate clipping solutions.

Explains why the bad guys in games often fail to see me

11 hours ago, JoeJ said:

AFAIK, all 3D games use raytracing for this purpose, with a single ray (EDIT: or a few of them, maybe for each larger bone of the skelton?), but i remember 2D games that had accurate clipping solutions.

I can't tell how it is usually done in the current state of the art 3D games since I am no industry professional. I am just a hobbyist. However, in my experience, when it comes to optimizing performance vs accuracy there is no general solution. If you have to perform such visibility checks in an MMO with hundreds of players and NPCs, you are certainly right. You can't afford much CPU/GPU time on the test. But in contrast, in an offline game with a small number of agents (Alien isolation for example), you can certainly afford more expensive checks to enhance realism, I guess... Also, you don't need to perform a check for every agent in every frame. You can distribute the checks across multiple frames without anybody noticing it.

As I said, I think it depends on your game and if I haven't missed it, the TO does not mention which type of game he is interested in (except FPS).

Quote

11 hours ago, JoeJ said:

Explains why the bad guys in games often fail to see me

 

Stopping to play on "easy"-mode would fix that, I guess.

Greetings

Thanks everyone - i didn't really know what to expect this being my first post - thank goodness nobody said 'LMGTFY' ! :) 

Genre would've helped a lot here, apologies; it's going to be a turn based strategy - which in my mind gives me 'all the time i want' to process these sorts of logic checks.

Essentially (and i am probably smashing a peanut with a hammer here) i want to only send whereabouts data over the network (at the start of a players turn) if they can already see the other player - otherwise fog of war / other objects are hiding the other player.

When P1 executes/confirms his turn i'd like for the server to walk through the movement path running the checks 'can i see P2 yet?' - if it returns true on any of those key frames/movement positions then i'd want to relay to the relevant players[] the location of the other player so that the client in this instance is a dumb/exemplary simulation of the server side logic.

As for the suggestion for tracing a ray - i had thought this - and actually in a simulation (using three.js) i had this working fairly well: https://threejs.org/docs/#api/en/core/Raycaster 

The issue was i had pointed three rays - one to the centre point, one to the right most bounding box edge and one to the left (a little too simple/noddy).

But if i'm honest, even that tech demo i wrote in three.js was a working concept - the main issue was that it was completely front-end client facing code - if you took a look at the doc above for Raycaster you'll see:

	raycaster.setFromCamera( mouse, camera );
...
	var intersects = raycaster.intersectObjects( scene.children );

If i had the math knowledge here to replicate those two functions outside of a framework then i could at the very least take your concept of shooting rays out at random positions on a bounding box as a test; i think this 'would do'.

What i'm struggling with the most here in internetdom is my terminology sucks! i'm not expecting someone to solve this for me - merely a firm hand :)

Thanks again 

2 hours ago, Paul Drage said:

If i had the math knowledge here to replicate those two functions outside of a framework then i could at the very least take your concept of shooting rays out at random positions on a bounding box as a test; i think this 'would do'.

What i'm struggling with the most here in internetdom is my terminology sucks! i'm not expecting someone to solve this for me - merely a firm hand

Just to be completely clear, is the issue you're facing that you want to perform operations on the server side that Three.js could handle for you, but you don't have Three.js available in that setting and you're not sure how to implement equivalent functionality yourself?

3 hours ago, DerTroll said:

Stopping to play on "easy"-mode would fix that, I guess.

Haha, yeah... maybe i should try this - never did

2 hours ago, Paul Drage said:

What i'm struggling with the most here in internetdom is my terminology sucks!

Sounds your game is top down / 2D. I remember nice tutorials about visibility by clipping, for both AI but also to cast shadows. So maybe shadows could be a useful search term as well.