• Advertisement
Sign in to follow this  

Optimize field of vision algorithm in a grid tiled map

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