Search Unity

  1. Unity 2020.2 has been released.
    Dismiss Notice
  2. Good news ✨ We have more Unite Now videos available for you to watch on-demand! Come check them out and ask our experts any questions!
    Dismiss Notice

Virtual oclussion culling for AI in multiplayer game

Discussion in 'General Discussion' started by AndersMalmgren, Nov 28, 2019.

  1. AndersMalmgren

    AndersMalmgren

    Joined:
    Aug 31, 2014
    Posts:
    5,403
    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
     
  2. frosted

    frosted

    Joined:
    Jan 17, 2014
    Posts:
    3,822
    iirc, I used custom raycast system for this - but i think the easiest way is just use renderer isvisible.
     
  3. AndersMalmgren

    AndersMalmgren

    Joined:
    Aug 31, 2014
    Posts:
    5,403
    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
     
  4. frosted

    frosted

    Joined:
    Jan 17, 2014
    Posts:
    3,822
    Why do you think raycasting is too expensive? You're looking at how many players?
     
    YoungerBrother and angrypenguin like this.
  5. AndersMalmgren

    AndersMalmgren

    Joined:
    Aug 31, 2014
    Posts:
    5,403
    12 players 200 bots maybe, plus our server is also a client, potentially
     
  6. Ryiah

    Ryiah

    Joined:
    Oct 11, 2012
    Posts:
    16,385
    Is this where I point to Unity DOTS? :p
     
  7. AndersMalmgren

    AndersMalmgren

    Joined:
    Aug 31, 2014
    Posts:
    5,403
    Umbra is not using racasting for a reason. Its not viable for that kind of task.

    edit: We use ECS already btw
     
  8. frosted

    frosted

    Joined:
    Jan 17, 2014
    Posts:
    3,822
    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.
     
  9. AndersMalmgren

    AndersMalmgren

    Joined:
    Aug 31, 2014
    Posts:
    5,403
    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.
     
  10. frosted

    frosted

    Joined:
    Jan 17, 2014
    Posts:
    3,822
    Well, you still probably want to bake camera - you have dynamic fov or fixed?
     
  11. AndersMalmgren

    AndersMalmgren

    Joined:
    Aug 31, 2014
    Posts:
    5,403
    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
     
  12. frosted

    frosted

    Joined:
    Jan 17, 2014
    Posts:
    3,822
    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?
     
  13. AndersMalmgren

    AndersMalmgren

    Joined:
    Aug 31, 2014
    Posts:
    5,403
    Frustum cull is peanuts? :D Its the occlusion part that is hard :D

    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 :/
     
  14. frosted

    frosted

    Joined:
    Jan 17, 2014
    Posts:
    3,822
    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! :D
     
    AndersMalmgren likes this.
  15. Murgilod

    Murgilod

    Joined:
    Nov 12, 2013
    Posts:
    7,242
    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.
     
    neoshaman likes this.
  16. koirat

    koirat

    Joined:
    Jul 7, 2012
    Posts:
    677
    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 ?
     
  17. AndersMalmgren

    AndersMalmgren

    Joined:
    Aug 31, 2014
    Posts:
    5,403
    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
     
  18. ShilohGames

    ShilohGames

    Joined:
    Mar 24, 2014
    Posts:
    2,843
    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.
     
  19. ShilohGames

    ShilohGames

    Joined:
    Mar 24, 2014
    Posts:
    2,843
    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.
     
  20. frosted

    frosted

    Joined:
    Jan 17, 2014
    Posts:
    3,822
    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)
     
  21. AndersMalmgren

    AndersMalmgren

    Joined:
    Aug 31, 2014
    Posts:
    5,403
    The navmesh would just be used to know were the player/AI can be when baking the quadtree.
     
  22. ShilohGames

    ShilohGames

    Joined:
    Mar 24, 2014
    Posts:
    2,843
    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.
     
  23. AndersMalmgren

    AndersMalmgren

    Joined:
    Aug 31, 2014
    Posts:
    5,403
    The AI is serverside so clients cant do much im afraid
     
  24. ShilohGames

    ShilohGames

    Joined:
    Mar 24, 2014
    Posts:
    2,843
    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.
     
  25. AndersMalmgren

    AndersMalmgren

    Joined:
    Aug 31, 2014
    Posts:
    5,403
    This is for server only so it does not run all logic and animations on all bots plus network them to players.
     
  26. ShilohGames

    ShilohGames

    Joined:
    Mar 24, 2014
    Posts:
    2,843
    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.
     
    Antypodish likes this.
  27. frosted

    frosted

    Joined:
    Jan 17, 2014
    Posts:
    3,822
    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.
     
  28. Murgilod

    Murgilod

    Joined:
    Nov 12, 2013
    Posts:
    7,242
    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.
     
    ShilohGames likes this.
  29. koirat

    koirat

    Joined:
    Jul 7, 2012
    Posts:
    677
    May I know what technique have you used for visibility ?
     
  30. ShilohGames

    ShilohGames

    Joined:
    Mar 24, 2014
    Posts:
    2,843
    Yeah, it definitely would not perform well enough to use once per frame.
     
  31. Murgilod

    Murgilod

    Joined:
    Nov 12, 2013
    Posts:
    7,242
    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.
     
  32. frosted

    frosted

    Joined:
    Jan 17, 2014
    Posts:
    3,822
    Nah, yours was worse. :D

    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.
     
    Last edited: Nov 29, 2019
  33. Murgilod

    Murgilod

    Joined:
    Nov 12, 2013
    Posts:
    7,242
    Oh, no, you misunderstand, I meant mine. I basically gave the least optimal solution possible :v
     
    frosted likes this.
  34. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    3,147
    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.
     
    pcg likes this.
  35. frosted

    frosted

    Joined:
    Jan 17, 2014
    Posts:
    3,822
    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.
     
    angrypenguin likes this.
  36. koirat

    koirat

    Joined:
    Jul 7, 2012
    Posts:
    677
    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.
     
  37. neoshaman

    neoshaman

    Joined:
    Feb 11, 2011
    Posts:
    5,571
  38. koirat

    koirat

    Joined:
    Jul 7, 2012
    Posts:
    677
    So why we don't have it built in ;)
     
unityunity