Virtual oclussion culling for AI in multiplayer game

Anyone know of a ready to use system for a server to determine if any player sees a bot?

I could develop something custom,but it feels a common problem that someone should have fixed already

 

iirc, I used custom raycast system for this - but i think the easiest way is just use renderer isvisible.

 

Raycasting (not baked) is too expensive for oclussion culling. renderer isvible requires a camera

edit: If I do it custom I will use a quad tree in combo with navmesh and raycasting to determin viability between quads

 

Why do you think raycasting is too expensive? You're looking at how many players?

 

12 players 200 bots maybe, plus our server is also a client, potentially

 

Is this where I point to Unity DOTS?

 

Umbra is not using racasting for a reason. Its not viable for that kind of task.

edit: We use ECS already btw

 

Oh, thats a ton of bots. Yeah, you need a more robust/high performance system.

I wouldn't expect this to be an off the shelf problem, since dealing with visibility between 200+ dynamic element pairs is a kind of unique situation.

You would probably need to bake a lot of raycasts to build out culling volumes. Use that to filter batches, then use minimal raycasts to verify the pairings that cleared your initial filters.

 

Yeah, I need something like Umbra but without the camera. I can recreate a crude umbra system with a quadtree and raycast every other cell in the tree at baketime.

 

Well, you still probably want to bake camera - you have dynamic fov or fixed?

 

its a FPS shooter, camera is completely dynamic. But I can use the navmesh plus 2.5 meters up to get a good queryable area.

edit: so a 2d quad tree is enough, but baked with 3D raycasting at bake time

 

I mean, when you're testing visibility - do you need to actually do proper camera rotation check + frustum cull, or are you just testing for obstructions?

 

Frustum cull is peanuts? Its the occlusion part that is hard

edit: At runtime I just need a crude visublity check like umbra, it needs to be inclusive. like umbra

edit2: if we had access to Umbra API Im sure they support virtual cameras. But the entire umbra API is hidden for us :/

 

Yeah thats true, frustum cull would just be a quick filtering check.

Was about to say the same thing - its really a shame there's no umbra access.

I'd actually be interested in this kind of thing, hand rolling occlusion probably isn't super complex, but I'd like to follow a real effort to implement a solid system.

So if you really dive in, share some progress here!

 

Give each bot a camera; render players as red, environment as black, and other bots as white; render to a texture; convert the rendertexture to texture2d; use a for loop with GetPixel() for each texture/bot. Easy-peasy.

 

First of all I think that what he need is to know if particular bot sees the particular player.
And his post is just a mistake.

And rendering to texture is just not viable option.

The fact is that visibility is super difficult problem
You will have a hard time finding such a system, I was looking for one myself.
I was more lucky since I have a tower defence kind of game. So I can store visibility for my towers once calculated.

The biggest question is how big is your environment and how precise your visibility must be. Is the center point of bot/player satisfactory ?

 

No, AI detection is already implemented so it's not a mistake, here is a demo of that.

This is so we only send AI state info to relevant players and alos disable animation etc for bots that are irrelevant

 

One possible optimization would be to come up with a way to create a bunch of zones in the map, and then only send individual players data based on which zones they should be able to see. This could be done using bounding volumes or it could be done using a simple 2D grid. This approach would not be perfect, but it would at least cull the data activity for many of the units. In the simplest form, you could simply use this to disable animations for units behind the player, but enable the animations for all of the units in front of the player regardless of actual ability to see the specific units.

 

Actually, since this is for checking to see if a player can see other units, this idea could actually work well as an additional hidden camera in the game client.

 

These suggestions are bad.

The best bad suggestion would be having clients send visibility data to server (you distribute the work here). But that's also bad.

Anders is correct that building out proper occlusion system w a quad tree or spatial hash is right direction. I dont think using navmesh raycasts as optimization will help (but it depends on specifics)

 

The navmesh would just be used to know were the player/AI can be when baking the quadtree.

 

The thing to be careful of is not overloading the server. Sending visibility data from client to server might actually create a new bottleneck. For scalability reasons, you would probably want to keep as much of this on the client as possible.

 

The AI is serverside so clients cant do much im afraid

 

Ok. The way you described this it sounded like you wanted a way for player clients to determine if they could see bots so the game clients could enable/disable animations on the client side. Is that what you are trying to do, or something else?

If you are also trying to reduce network data for other units the player cannot see, then you would either need to have the players tell the server who they can see or have the server compute that information.

 

This is for server only so it does not run all logic and animations on all bots plus network them to players.

 

For that, you could create a low CPU cost simple 2D grid on the server side. Just compute basic checks. For example, if the unit is in the same grid as the player or if the unit is generally in front of the player, then send the player details about that unit. If the unit is behind the player, then do not send details. You could even tweak details sending based on range, but that be tricky when scopes are involved.

If you wanted to get more elaborate, you could break the functionality up between client and server using a client request for more details on certain units or certain zones in the grid.

One thing I like to do when designing custom network optimizations is frequently send core data, and then less frequently send highly detailed data. Core data would typically be unit positions. Highly detailed data would include unit rotation, head look target, weapon selected, animation pose, health, etc. Anyway, by splitting data up that way, there can be some hybrid client-server optimization where the client knows the position of all of the other units and can use that data to selectively request more specific details as needed.

 

This is actually a pretty well traveled space. Just prebake the raycasts into volumes, cull the frustum for the initial pass, query the volumes for filtering (quadtree), then followup with raycasts for precision test.

The reason that most off shelf solutions probably wouldn't be fully suitable is because you want a server to do visibility tests and most off shelf are client driven using unity camera, etc. Although you could pick up one for help on building out the volumes, I think @AndersMalmgren probably has enough experience to know how that works, maybe read a couple articles to brush up on details.

For adequate performance, I don't think it'd be very hard to actually set this all up. For really top quality performance, I'm sure there's a lot of optimization and things can get tricky. I don't think our example needs to be best of breed though.

 

It'd actually be the worst option possible. This is actually the most ridiculously overengineered and underoptimized option possible. GetPixel (don't even use this, ever. if you have to use anything, use GetPixels) is ridiculously slow and has to be done on the CPU.

 

May I know what technique have you used for visibility ?

 

Yeah, it definitely would not perform well enough to use once per frame.

 

I had a heavily optimized photo system in a prototype and I was coming in pretty hard exporting in less than 10 frames. Mind that it was both taking photos, saving them, and also running an analysis on them.

 

Nah, yours was worse.

I just did a quick scan of a few occlusion culling papers, and the approaches they use are pretty complex. Doing something best of breed for this would be a pretty significant effort.

My gut says the following should work (but maybe it's naive):

Building the quad/octtree:

• Pick a rough size for each of your volumes. Probably like 3m.
• Mentally subdivide each volume into 9 places where a dude could be standing.
• Raycast from each of the 9 sub squares into each of the 9 subsquares.
  • If all visible, then mark visible
  • If partial obstruction then mark 'require raycast'
  • If all visible then mark 'all visible'

(- Other option would be to subdivide the volume if you get a mixed result)

You have a dictionary that maps each volume pair with the visibility to each other pair. (If this ends up being too much memory then you need something a little more sophisticated). I think you probably want a single dictionary with a key that represents each unique pairing of two volumes.

Get the volume id from each dude, query the volume pair from the two ids.

Now you know if visible or occluded or if you need a raycast to do the final determination.

Potential problems:

• There is the possibility for some false positive or false negative, if you are ok with some small error then things are easier, if you need perfect precision then things get harder (or require more raycasts to verify).
• Keeping the volumes one size is nice because you can easily convert a position to a volume, if you want to further subdivide the volumes then you need to walk the quad/oct tree to determine which volume a dude is standing in. You may want to use a spatial hash or something.

----
Thinking this through a bit more - if you go with consistent sized volumes you don't even need quadtree or whatever. You just have a converter from position to a specific volume. This can be done by just dividing the position x, z (and y if needed) by the size of the volume.

So like, if you got a character at x:23, z:52 and you have 3m volumes, then the cell would be at 7, 17 (23/3, 52/3). Ez pz.

Finally, the biggest problem with this overall is "consistent volumes" - your geometry won't fit nicely into this grid, so there will be a lot of suboptimal bits. Personally, I would prefer the simplicity that consistent volumes offer, but if you really need something more optimized, then taking on extra complexity might be needed.

 

Oh, no, you misunderstand, I meant mine. I basically gave the least optimal solution possible :v

 

Just use the job based raycasting. RaycastCommand/SpherecastComment. You don't need DOTS for this just basic job usage. Easily can do several hundred per frame and it's going to be far simpler to setup then some custom spatial solution which doesn't really solve this problem well anyways.

 

I actually kind of agree w/ this. I would definitely profile a straight up raycast solution to see if its really too expensive.

I think you could also prototype my occlusion proposal in a few hours too just to see how it compares. I would not expect that system to be particularly time consuming (assuming it works well enough).

If you have experience in dealing with that kind of spatial breakdown, it's really pretty simple.

 

Problem with raycast is that you are checking a single point, not a whole character.
You can approximate with a spherecast but it is still not precise.

 

https://www.guerrilla-games.com/read/practical-occlusion-culling-on-ps3

https://www.guerrilla-games.com/read/practical-occlusion-culling-in-killzone-3

 

So why we don't have it built in