Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Right now I'm using Bresenham's line algorithm for line of sight. The problem is I've found an edge case where players can look through walls. Occurs when the player looks between two corners of a wall with a gap on the other side at specific angles.

Line of sight edge case

The result I want is for the tile between two walls to be marked invalid as so.

Desired result

What is the fastest way to modify Bresenham's line algorithm to solve this? If there isn't a good solution, is there a better suited algorithm? Any ideas are welcome. Please note the solution should also be capable of supporting 3d.

Edit: My simple solution was to check if both corners are closed when a line's x and y coordinates change. For the working source code and an interactive demo of the completed product please see http://ashblue.github.io/javascript-pathfinding/

share|improve this question
2  
Does it make a difference if you switch start and end point? Maybe then you could just accept results if both calculations return a non obstructed line of sight. You also might find some of the LOS articles helpful over at RogueBasin. –  thalador May 31 '13 at 6:49
1  
Either way, those two black blocks diagonal at 4-5 are not connected into a wall in the first place, and I say this because you are implicitly allowing diagonal movement. You must either square off that diagonal to make it a contiguous wall or make your line walker square off its diagonal moves instead of going purely diagonal like 2-3 and 4-5. –  Patrick Hughes May 31 '13 at 6:51
    
Flipping it sounded like a good idea, but it doesn't resolve the issue. Only thing I can think of is to check and see if one of the two corners are empty. Seems expensive though. –  Ash Blue May 31 '13 at 6:55
5  
"Seems expensive" is never enough of a justification to not try something. "Will be too expensive" generally is, assuming that you can prove that something will be too slow. –  Mokosha May 31 '13 at 6:58
3  
Only change to the algorithm required is that if both X and Y are changing on the same step then first change X and then change Y, this would eliminate the diagonals altogether. –  Patrick Hughes May 31 '13 at 17:34
show 4 more comments

2 Answers 2

up vote 6 down vote accepted

Eric Lippert wrote an excellent series on generating line-of-sight in C# with Shadow Casting on a rectangular planar grid..

Amongst other issues, Eric dealt with various questions that must be answered about the line-of-sight requirements, which give different results, and gives examples of a couple of different results. One of the articles deals in depth with a "looking around the corner" circumstance which occurred in an early version of his algorithm.

I have adapted Eric's algorithm to a hexagonal grid here, and successfully used it on large hexagonal grids (> 400 x 700) with an extensive visibility radius (> 60 hexes). This implementation calculates and displays complete field-of-view as fast as I can blink, using a single i7 CPU. This is certainly fast enough for any uses I expect to put it to.

Update - Line-of-sight with elevation:
The hex-grid implementation linked to above calculates line-of-sight with elevation, not just obstacles. The documentation notes also discuss an additional decision which must be made in regards to the elevation calculations: The target height and observer height. The default selection is to make both equal, which creates symmetric field-of-view, but ground-to-ground and observer-eyes to ground can alse be selected. (The code is Open Source under MIT Licence)

share|improve this answer
    
I'm really digging Shadow Casting, but I've run into a problem. Having trouble finding any information on scaling the algorithm to operate with a z-axis. Sorry to mention this, but do you have any suggested resources for making it work in 3d? –  Ash Blue Jun 1 '13 at 6:49
    
@AshBlue: see addendum above –  Pieter Geerkens Jun 1 '13 at 12:35
    
I am looking at your codebase. It has great stuff in it, but I don't seem to find a Bresenham-like line drawing algorithm adapted to hexes. Do you do it with LOS? –  Ef Es Jun 9 '13 at 4:09
    
@EfEs: FieldOfView is the returned object; ShadowCastingFov*.cs generates the field-of-view by casting shadows. If you have specific questions about the code, those might be best asked in the Discussions section of the site; more general questions I am happy to answer here. –  Pieter Geerkens Jun 9 '13 at 6:39
    
@PieterGeerkens You can find the question here gamedev.stackexchange.com/questions/57087/… –  Ef Es Jun 9 '13 at 7:56
show 2 more comments

What if for LOS calculation you have a separate "higher resolution" grid that fills in the corner gaps. I was thinking something like this:

enter image description here

The left is the original block section of 4 squares.

The right is the "high resolution" version, as you can see each original square was subdivided into quaters and one of the corners has been filled in. I'm not sure offhand the algorithm to generate that, but it can be pre-computed from the current map.

It does mean that the coordinate space is quadrupled but I don't envision that being a significant performance issue.

share|improve this answer
    
Pretty sure the higher resolution would look exactly the same as the original. When dividing a grid into a smaller grid, you get the same visual representation, just with a smaller grid. Each single square just becomes 4 smaller squares in the same spot. –  Byte56 May 31 '13 at 14:24
    
@Byte56 Correct, I meant that additional logic would be applied after dividing it to add in the extra blocks to that copy. The logic to do that is an exercise left to the reader. –  Davy8 May 31 '13 at 16:46
    
You could easily generate the high res grid by blurring the original. Then define a threshold of, say, 0.5 for high res cells to be filled or not. Thus, using a high res grid feels quite hacky to me at all. –  danijar Jun 1 '13 at 12:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.