Sign in to follow this  

How to compute % of target visibility/cover?

This topic is 470 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Like I said in my other topic:

 

http://www.gamedev.net/topic/681684-tactics-rpgs-with-an-actual-game-world-exploration-etc/#entry5308559

 

Even going beyond the tactics game style, how one go about computing how much of someones volume/silhouete is visible from a point of view?

 

It sounds very complex to me, makes me think that most tactics games probably cheat a lot with this, like making very limited level design, or not taking much into consideration...

 

I started thinking on this with the idea of having spheres characters moving on world made of AABBs, but the boxes not needing to be aligned with anything, and can be positioned freely also in vertical, so I dont think its possible to have some hackish way of doing this?

 

The simplest way I though of is shooting a lot of minimum size projectils against the target in a way that it would hit the target evenly all over its circle silhouete, and see how much of the projectiles actually hit..

 

The other way is image based: render the target only in a unique color, count its pixels, render all obstacles, depth enable, ortho camera (on the pos of the gun barrel), and count the pixels of the target again?

 

Am I overthinking this? How youd do it?

Share this post


Link to post
Share on other sites

Start here: http://ncase.me/sight-and-light/

 

If you have your visibility volumes worked out then you can just calculate visibility/cover geometrically on a simple collision primitive. If you put an AABB around the target then work out your visibility you can just figure what percentage of the AABB overlaps the visibility volume. If you do it in 2 dimensions it should be straightforward. You're just comparing the volume of the overlap with the volume of the AABB. If that's not precise enough for you then a circles could work too.

Share this post


Link to post
Share on other sites
You listed my suggestion. Shoot many different rays at your target and see how many hit. One thing I would add would be to add some randomization to it. Don't shoot the same rays every frame but randomly pick new ones. You can then smooth out the jitter in the %hit signal using a low pass filter.

Share this post


Link to post
Share on other sites

World of Tanks actually talks about how they determine visibility here:  http://wiki.wargaming.net/en/Battle_Mechanics#Visibility_Checkpoints

They do it much as you suggested, by casting out 'thick' rays at several different points on a vehicle.  Many games do this for humanoids too, casting rays to each of the limbs.  I think the newer Fallouts do this, but I'd have to double check by blocking an arm behind cover and seeing if I could still shoot it with VATS

 

I have implemented the render method myself for an XNA game that I never released.  It's a little slow, so I wouldn't recommend it for a real time game, but it's kind of neat how detailed it can get.  You can speed it up by using a smaller viewport and rendering only the collisionboxes of the models and not the actual models.  I'm not entirely sure how much Ortho really buys you, depends on if you are calculating the to-hit based upon how much is actually outside of cover (ortho), or how much the shooter can see of the target (perspective).  But it's not expensive to do things Ortho, so it's mostly a philosophical debate=)

 

The other method is the X-com style, where you have discrete cover types.  Half cover and Full cover, and then you check if there is any intervening cover between the two characters. 

 

 

EDIT:  One other thing I did for the Render method, was different colors for different cover types, I had 'soft' and 'hard' cover as two different color channels and blended everything.  (Ie Red == target, Blue == Hard, Green == Soft)

 

EDIT2:  And checking the OP's original link, looks like JRPG/TBS, in which case I'd lean more towards X-com style, it's more helpful for players to know what kind of cover they'll get in discrete chunks over small percentages.

Edited by ferrous

Share this post


Link to post
Share on other sites

You listed my suggestion. Shoot many different rays at your target and see how many hit. One thing I would add would be to add some randomization to it. Don't shoot the same rays every frame but randomly pick new ones. You can then smooth out the jitter in the %hit signal using a low pass filter.

Exactly this. Trace rays uniformly randomly distributed within the cone that contains the bounding sphere, you can find code to generate those rays online. To get the true % visible, you need to test each ray against the object neglecting occluders, then test the ray with the occluders (but only if the first ray hit the target object). This handles the case where the object isn't close to spherical and so some of the rays will miss the target regardless of any occluders.

 

You can trace many fewer rays (like 10x fewer) if you smooth the resulting output over many frames using a technique like Exponential smoothing. You probably can get away with using only 10-20 rays per frame with decent results. Another thing you might add would be to change the number of rays based on the size of the cone - wider angle cones need more rays. The number of rays should be proportional to the angular area covered by the cone to keep a constant density of rays.

Edited by Aressera

Share this post


Link to post
Share on other sites
Many games do this for humanoids too, casting rays to each of the limbs.

 

raycasting is definitely the way. a method similar to the above would help minimize the number of rays required.  maybe 6 for a humaniod: head, torso, and 4 limbs.

 

BBOX corners for hull and turret could suffice for a tank. but that's still 16 rays.

 

"fat rays" is an interesting concept...

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

You listed my suggestion. Shoot many different rays at your target and see how many hit. One thing I would add would be to add some randomization to it. Don't shoot the same rays every frame but randomly pick new ones. You can then smooth out the jitter in the %hit signal using a low pass filter.

Exactly this. Trace rays uniformly randomly distributed within the cone that contains the bounding sphere, you can find code to generate those rays online. To get the true % visible, you need to test each ray against the object neglecting occluders, then test the ray with the occluders (but only if the first ray hit the target object). This handles the case where the object isn't close to spherical and so some of the rays will miss the target regardless of any occluders.

You can trace many fewer rays (like 10x fewer) if you smooth the resulting output over many frames using a technique like Exponential smoothing. You probably can get away with using only 10-20 rays per frame with decent results. Another thing you might add would be to change the number of rays based on the size of the cone - wider angle cones need more rays. The number of rays should be proportional to the angular area covered by the cone to keep a constant density of rays.

To build on Arresera and HappyCoder's point, one tricky but important aspect to consider with this method is the generation of jittered rays that have a uniform random distribution. (Reading up on quasi montecarlo methods is definitely on my todo list!) however, if you take the time and think it through, you may be able devise your own technique that give you acceptable results. This particular article once helped the wheels in my head start churning, and just might do the same for you

http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter17.html

My other hack was even more brute force. I used blender to create an uvsphere with a very high vertex count (and a radius of one so the vertices would be normalized), cut it in half to make a hemisphere, use the decimate modifier to bring down the number of vertices and then exported these vertices to/read them from a text file. To jitter them, I would merely rotate them around the pole axis at varying angles.

Share this post


Link to post
Share on other sites

This topic is 470 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this