Calculating visible tiles
Imagine I have a square grid of tiles, some you can see over, some you can't. I can calculate visibility between any two given points by using the Bresenham algorithm - all well and good. But how do I find all the visible tiles within a given distance of a point? The naive approach of testing each tile individually using the same LOS algorithm is obviously going to waste time covering the inner tiles over and over again, so is there a better way?
I've seen this article, but it looks a bit awkward and I'd rather not have to have a table of precalculated occlusion maps if possible.
Does anybody else have an alternative? Accuracy is not necessarily as important as ease of implementation, providing it's roughly correct. (ie. I don't mind if a 40% visible tile is counted as totally invisible, for example.)
Just how big of a map are talking about here? You're probably going to spend a lot more time rendering the tiles that you will do calculating the visibilty even using a naive bresenham.
I implemented a raycasting algorithm for one of the Ludum Dare Competion making a rotating line of sight algorithm. I have no problems with gaps in the outer range (the range was not that far though). I guess there were probably some tiles in the closer range which got tested more than once though.
The only slightly tricky part (boast) was to find an acceptable value for the angle between the rays i casted.
I guess making the ray casting algorithm won't be too much of a problem for you, but you can take a look at the source of the game at my homepage. Look in FunStuff, the second entry, "Silent Hunter". The interesting part is in Level.cpp in the function CastLightRay.
This function takes a position, start and end angle and the radius and operates the raycasting function.
The only slightly tricky part (boast) was to find an acceptable value for the angle between the rays i casted.
I guess making the ray casting algorithm won't be too much of a problem for you, but you can take a look at the source of the game at my homepage. Look in FunStuff, the second entry, "Silent Hunter". The interesting part is in Level.cpp in the function CastLightRay.
This function takes a position, start and end angle and the radius and operates the raycasting function.
SiCrane - The amount of the tile map to be examined at any one time is only going to have a radius of about 31x31 tiles, but I should point out that I am going to be performing this visibility check a hell of a lot. It's actually part of some research rather than a game as such, hence the unusual performance requirements.
Endurion - I think your algorithm is fundamentally similar to my current one, so I wouldn't gain much from it. But then it's likely that apart from a few extra checks, what I'm doing is close to optimal anyway, I suppose.
Endurion - I think your algorithm is fundamentally similar to my current one, so I wouldn't gain much from it. But then it's likely that apart from a few extra checks, what I'm doing is close to optimal anyway, I suppose.
Isn't this the same problem as is faced in those old 3D FPS games similar to Wolfenstein 3D, except with an overhead 360 degree field of view instead of the limited view of Wolf3D? I'm pretty sure Wolf3D used a 2D raycasting method on a grid to determine which part of each wall to draw, so I'm assuming that this method runs in real time.
I'm also sure I've seen something similar in my work with robotics and occupancy grids, but I can't remember exactly what is was that I'm thinking of.
I suppose you could also do some sort of flood fill algorithm, where you mark each tile as being visible and then compare its neighbours, but there's possibly some special cases where this algorithm will give you the incorrect result (I haven't thought through all scenarios yet, and I'm not thinking too deeply at the moment, sorry!)
I'm also sure I've seen something similar in my work with robotics and occupancy grids, but I can't remember exactly what is was that I'm thinking of.
I suppose you could also do some sort of flood fill algorithm, where you mark each tile as being visible and then compare its neighbours, but there's possibly some special cases where this algorithm will give you the incorrect result (I haven't thought through all scenarios yet, and I'm not thinking too deeply at the moment, sorry!)
My friend ran into this problem last year when programming a 2D strategy game. Their initial approach ran in O(n^4) time and took 30 seconds to run (in Java). They did solve this problem, but I don't remember the algorithm. Next time I have class with him (Friday, coincidentally enough, in my Algorithms class) I'll ask what he used to overcome this.
If you only have a few "can't see over" tiles [compared to the rest] the best sort of algorithm should probably be something like:
The 2nd loop can be constricted by not testing already occluded tiles, since a farther tile which is invisible will never occlude anything 'new'. Thus 'closer' tiles should be tested first. It should be pretty easy to setup too.
Let me know how well this works.
for each distance(tile)<max(los){ assume_visible;}for each "can't see over tile" while distance(tile)<max(los) AND tile.is_visible(){ min_slope = binary_search(); // should be binary search, might be better option... max_slope = ...; line1=plot_line([cant_see_over_tile], min_slope, distance[max(los) - distance(origin, tile)] ); line2=plot_line([cant_see_over_tile], max_slope, distance[max(los) - distance(origin, tile)] ); flood_fill(line1, line2, invisible());}The 2nd loop can be constricted by not testing already occluded tiles, since a farther tile which is invisible will never occlude anything 'new'. Thus 'closer' tiles should be tested first. It should be pretty easy to setup too.
Let me know how well this works.
I'm not sure if this is too simpleminded/obvious, but anyway....
This simple early-out scheme got rid of roughly 2/3 the LOS tests in a quick test app.
<edit> Ignore the following. It's extremely inaccurate / It doesn't work. </edit>
Now that I think about it, shouldn't just doing the accurate LOS test for every tile as follows be even faster/as fast as you could possibly hope for?
-individual tests sorted from center to border (seperated by quadrant as demonstrated above)
-"backward" per test (start at target, heading back to the source)
-and stopping as soon as you hit an already determined tile (which should be instantly true, given the above two conditions)
[Edited by - samv on September 3, 2005 3:18:51 AM]
This simple early-out scheme got rid of roughly 2/3 the LOS tests in a quick test app.
/*Assumptions:-The visibility is to be calculated for rectangle from (0,0) to (MAX_X-1,MAX_Y-1). (Easily generalizable)-(START_X,START_Y) denotes the view position / source.-TraceVisibility() will do an accurate LOS test*/void calcVisibilityAxis(){ bool visible; visible=true; for(int i=START_X; i<MAX_X; i++) { if(obstacle_at(i,START_Y)) visible=false; set_visibility_at(i,START_Y,visible); } visible=true; for(int i=START_X; i>=0; i--) { if(obstacle_at(i,START_Y)) visible=false; set_visibility_at(i,START_Y,visible); } visible=true; for(int j=START_Y; j<MAX_Y; j++) { if(obstacle_at(START_X,j)) visible=false; set_visibility_at(START_X,j,visible); } visible=true; for(int j=START_Y; j>=0; j--) { if(obstacle_at(START_X,j)) visible=false; set_visibility_at(START_X,j,visible); }}void calcVisibilityQuadrant(int dx,int dy){ for(int i=START_X+dx; (0<=i) && (i<MAX_X); i+=dx) for(int j=START_Y+dy; (0<=j) && (j<MAX_Y); j+=dy) { bool visible; if(obstacle_at(i,j)) visible=false; else if(visibility_at(i-dx,j) && visibility_at(i,j-dy) && visibility_at(i-dx,j-dy)) visible=true; else if(!visibility_at(i-dx,j) && !visibility_at(i,j-dy) && !visibility_at(i-dx,j-dy)) visible=false; else visible=TraceVisibility(i,j); set_visibility_at(i,j,visible); }}void calcVisibility(){ calcVisibilityAxis(); calcVisibilityQuadrant(+1,+1); calcVisibilityQuadrant(+1,-1); calcVisibilityQuadrant(-1,+1); calcVisibilityQuadrant(-1,-1);}<edit> Ignore the following. It's extremely inaccurate / It doesn't work. </edit>
Now that I think about it, shouldn't just doing the accurate LOS test for every tile as follows be even faster/as fast as you could possibly hope for?
-individual tests sorted from center to border (seperated by quadrant as demonstrated above)
-"backward" per test (start at target, heading back to the source)
-and stopping as soon as you hit an already determined tile (which should be instantly true, given the above two conditions)
[Edited by - samv on September 3, 2005 3:18:51 AM]
Sorry for neglecting this thread. I've had a few very busy days, which including implementing and testing my implementation of this algorithm.
Trapper Zoid - in theory a breadth-first flood fill sort of thing should perform the least checks (ie. checking each tile only once). However the overhead of remembering/calculating the angle between the origin and each square, and calculating whether the next square is occuded by this one or not, would probably have cancelled out that benefit.
Telastyn - is that basically a sort of shadow-casting algorithm? It seems to be quite a nifty approach, although I probably have too many obstacles for it to be efficient. Not to mention that I've never had to work out how to do an efficient flood-fill before. :) I can imagine that it would work very well with a few dynamic obstacles which move across a static map with precomputed visibility.
samv - I must admit I looked over your code 3 times and didn't understand it. :) I am not very good with geometry. Can you explain what it is actually doing?
I ended up implementing the algorithm by casting a ray from the origin to every point on the perimeter. In theory, for a square map, this covers each square inside at least once. (I proved it to myself once by mathematical induction and once using trigonometry and calculus, but I'll be damned if I can explain how in plain English. :) )
With my numbers, this approach does about 2x as many comparisons as the theoretical minimum but about 6x fewer comparisons than an exhaustive 'plot line to each possible square' algorithm, and with no significant overhead or storage requirement.
I also added in 8 checks to quickly reject 1/8th of the points on the perimeter based on obstacles directly adjacent to the origin. This worked quickly enough for me, running it several thousand times a second. It overestimates the number of visible squares due to the overlap near the origin, but in this system bias isn't a significant problem as long as it's relatively uniform. (I could eliminate that with a quick bitfield array check later, if needed.)
Trapper Zoid - in theory a breadth-first flood fill sort of thing should perform the least checks (ie. checking each tile only once). However the overhead of remembering/calculating the angle between the origin and each square, and calculating whether the next square is occuded by this one or not, would probably have cancelled out that benefit.
Telastyn - is that basically a sort of shadow-casting algorithm? It seems to be quite a nifty approach, although I probably have too many obstacles for it to be efficient. Not to mention that I've never had to work out how to do an efficient flood-fill before. :) I can imagine that it would work very well with a few dynamic obstacles which move across a static map with precomputed visibility.
samv - I must admit I looked over your code 3 times and didn't understand it. :) I am not very good with geometry. Can you explain what it is actually doing?
I ended up implementing the algorithm by casting a ray from the origin to every point on the perimeter. In theory, for a square map, this covers each square inside at least once. (I proved it to myself once by mathematical induction and once using trigonometry and calculus, but I'll be damned if I can explain how in plain English. :) )
With my numbers, this approach does about 2x as many comparisons as the theoretical minimum but about 6x fewer comparisons than an exhaustive 'plot line to each possible square' algorithm, and with no significant overhead or storage requirement.
I also added in 8 checks to quickly reject 1/8th of the points on the perimeter based on obstacles directly adjacent to the origin. This worked quickly enough for me, running it several thousand times a second. It overestimates the number of visible squares due to the overlap near the origin, but in this system bias isn't a significant problem as long as it's relatively uniform. (I could eliminate that with a quick bitfield array check later, if needed.)
Sure. I simply divide the tile-board into different regions:
The 4 regions ^,v,<,v are handled first (the call to calcVisibilityAxis()). It's simply one ray per axis.
Next are the 4 quadrants (the 4 calls to calcVisibilityQuadrant(?,?)).For example calcVisibilityQuadrant(-1,-1); scans quadrant a. The tiles of the quadrant are scanned from center outwards: (first tile 1, then tile 2, and so on)
The purpose of this is, that for each tile T, you already know if the adjacent tiles x, y and d are visible or not:
If all of these tiles (x,y and d) are visible, then T must be visible, too. If none of them are visible, then T cannot be visible.
If just some are visible then you need to do a full LOS test.
(Slightly more advanced trick: Actually if the vector T-S is closer to the X-Axis than to the Y-Axis, it suffices to know that x and d are both (in)visible (respectively y and d or just d for the other cases))
I don't know how your obstacle distribution is, so it's difficult to guess how well this works for you. To give you an idea, this map:
gives these results (using the slightly more advanced test):
I hope this helps. Tell me if I'm still too cryptic. [SMILE]
< edit> FYI: This totals to 26 Obstacles in a 900 tile (30x30) map. 110 full LOS tests are needed. 790 tiles are handled by the early out tests. </edit>
[Edited by - samv on September 7, 2005 8:03:05 AM]
aaaaaa^bbbbbbaaaaaa^bbbbbbaaaaaa^bbbbbb<<<<<<S>>>>>>ccccccvddddddccccccvddddddccccccvddddddLegend:S: The source position^,v,<,>: the 4 "axes"a,b,c,d: the 4 quadrantsThe 4 regions ^,v,<,v are handled first (the call to calcVisibilityAxis()). It's simply one ray per axis.
Next are the 4 quadrants (the 4 calls to calcVisibilityQuadrant(?,?)).For example calcVisibilityQuadrant(-1,-1); scans quadrant a. The tiles of the quadrant are scanned from center outwards: (first tile 1, then tile 2, and so on)
^ ...87^654321^<<<<<<S>>>>>> v v vThe purpose of this is, that for each tile T, you already know if the adjacent tiles x, y and d are visible or not:
^ Tx ^ yd ^<<<<<<S>>>>>> v v vIf all of these tiles (x,y and d) are visible, then T must be visible, too. If none of them are visible, then T cannot be visible.
If just some are visible then you need to do a full LOS test.
(Slightly more advanced trick: Actually if the vector T-S is closer to the X-Axis than to the Y-Axis, it suffices to know that x and d are both (in)visible (respectively y and d or just d for the other cases))
I don't know how your obstacle distribution is, so it's difficult to guess how well this works for you. To give you an idea, this map:
------------------------------ Legend: - empty tile------------------------------ O ObstacleO-----O-----OO---------------- S Source------------O--------------O----------------------------O-----------------------------------------O----------------------------------S---------OO--------------------------------------------------------O-----------------------------O------------O-----------------------------O----------------O---O--------O----------------O---O--------O---------O------O---O------------------O------------------------OOOOOO---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------gives these results (using the slightly more advanced test):
--.xX-----.xx#.--------------- Legend: O Obstacle---.XX-----Xx#.--------------- S SourceO----.O----.OO--------------.X # Invisible on axis..----------O--------------Oxx X Full LOS test needed -> InvisiblexxX...--------------------OXX. . Full LOS test needed -> VisibleXXxxxxX.---------------------- x Early out test helped -> Invisible--.XXXXXO---------------...... - Early out test helped -> Visible-------------S---------OO#####------------------------......---------------------OXX.--------------------------OxxxXXXXX--.XO-----------------.Xxxxxxx.XxxO----------------O.-.OxxxxxxxxO----------------OxX.OxxxxxxxxO---------O------OxxxOxxxxxxxX----------O.-----.XxxxxxxxxxX------OOOOOO.------.XxxxxxxX.------.xxxx#xX-------.Xxxxxx--------Xxxxx#xx.-------.Xxxxx-------.xxxxx#xx.--------.Xxxx-------Xxxxxx#xx.---------.Xxx------.xxxxxx#xx.----------.Xx------Xxxxxxx#xxX-----------..-----.xxxxxxx#xxx.-----------------Xxxxxxxx#xxx.----------------.xxxxxxxx#xxx.----------------Xxxxxxxxx#xxxX---------------.xxxxxxxxx#xxxx.--------------Xxxxxxxxxx#xxxx.-------------.xxxxxxxxxx#xxxx.-----------I hope this helps. Tell me if I'm still too cryptic. [SMILE]
< edit> FYI: This totals to 26 Obstacles in a 900 tile (30x30) map. 110 full LOS tests are needed. 790 tiles are handled by the early out tests. </edit>
[Edited by - samv on September 7, 2005 8:03:05 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
