Jump to content
  • Advertisement
Sign in to follow this  
supersuraccoon

Optimize field of vision algorithm in a grid tiled map

This topic is 890 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

I am trying to implement Field of View algorithm in my game and I followed the great tutorial here : sight-and-light and here is what I got so far :
 
lmNd5.png
 
As you can see it works fine for me :)
 
And then I try to use this algorithm in a tiled map. It also works fine but just a little bit slow so I am now trying to find a way to optimize the algorithm.
 
Some information might help to optimize :
 
 - The tiled map is Orthogonal
 - All the tiles have the same size 32 * 32 and are square
 - Tiles marked 0 means empty marked as 1 means a obstacle
 - I have used Connected Component Labelling algorithm for a preprocess :
   - All the obstacles have been merged into several regions
   - I know all the vertices position in each regions
 
Something like this :
 
48LwJ.png
 
 
Say I have 9 connected regions ( 9 polygons ) and 40 vertices in total.
 
Based on the algorithm in the above link, there will be :
 
- ray-cast : 40 * 3   ( 3 ray-cast per vertices in angle +- 0.00001)
- edges : 40 
- edge * ray-cast intersection test : 40 * 40 * 3 == 4800
 
I think there should be a way to reduce the ray cast count and the edges count that I need to do the intersection calculation in a above situation but just could not figure out a good solution.
 
 
Any suggestion will be appreciated, thanks :)
 

Share this post


Link to post
Share on other sites
Advertisement

I used to do this with a canned array of vectors which went thru every point within a fixed max distance. Really it neead be no more than  +/- 0/1 data for X and Y  progression along an angle,  a growing offset for eact vector   (I even reused the same  +/- 0/1 array flopping over its use on each half quandrant   8 similar pattern upon a 45 degree wedge).

 

You grow vector til you hit then the rest is LOS blocked yeyond.

 

Its a low cost processing (simplified math and tight loops).

Share this post


Link to post
Share on other sites

Hmm Amit has a page on this:  http://www.redblobgames.com/articles/visibility/

 

 

Though, also, you probably don't need to do an actual raycast for the initial check, which I think is what wodinoneeye is saying, you could do a bresenham/wu line walk to check if a tile is empty or not.

Edited by ferrous

Share this post


Link to post
Share on other sites
I don't follow the need for tracing 3 rays per vertex? Seems like you could just trace directly to the corners of your geometry and end up with a perfectly viable field?

Share this post


Link to post
Share on other sites

Hmm Amit has a page on this:  http://www.redblobgames.com/articles/visibility/

 

 

Though, also, you probably don't need to do an actual raycast for the initial check, which I think is what wodinoneeye is saying, you could do a bresenham/wu line walk to check if a tile is empty or not.

 

 

Actually its not a 'ray trace' but a precanned set of stepped vectors for a fixed radius grid test (the whole surrounding grid from the centerpoint or limited to only some of the 8 half quadrants if a limited  boresite is used.   That for fast culling of whats NOT within view and then more precise methods can be done on the identified grid edges/boxes  (or the now identified sets of objects within those grid boxes).   Because of the stepping order, you also get a sequence that might be useful for calculating a progressive  partial visibility through intervening obstacles.    I used to make the diagonal cases inclusive of assuming visibility (leaving questionable cases to culling later with more accurate methods).

 

I also used this quick cull method while doing rough influence maps.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!