10
\$\begingroup\$

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/

\$\endgroup\$
9
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – thalador
    Commented May 31, 2013 at 6:49
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Patrick Hughes
    Commented May 31, 2013 at 6:51
  • \$\begingroup\$ 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. \$\endgroup\$
    – Ash Blue
    Commented May 31, 2013 at 6:55
  • 5
    \$\begingroup\$ "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. \$\endgroup\$
    – Mokosha
    Commented May 31, 2013 at 6:58
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Patrick Hughes
    Commented May 31, 2013 at 17:34

2 Answers 2

Reset to default
7
\$\begingroup\$

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.

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 also be selected. (The code is Open Source under MIT License)

\$\endgroup\$
7
  • \$\begingroup\$ 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? \$\endgroup\$
    – Ash Blue
    Commented Jun 1, 2013 at 6:49
  • \$\begingroup\$ @AshBlue: see addendum above \$\endgroup\$
    – Pieter Geerkens
    Commented Jun 1, 2013 at 12:35
  • \$\begingroup\$ 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? \$\endgroup\$
    – MLProgrammer-CiM
    Commented Jun 9, 2013 at 4:09
  • \$\begingroup\$ @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. \$\endgroup\$
    – Pieter Geerkens
    Commented Jun 9, 2013 at 6:39
  • \$\begingroup\$ @PieterGeerkens You can find the question here gamedev.stackexchange.com/questions/57087/… \$\endgroup\$
    – MLProgrammer-CiM
    Commented Jun 9, 2013 at 7:56
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – House
    Commented May 31, 2013 at 14:24
  • \$\begingroup\$ @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. \$\endgroup\$
    – David Ly
    Commented May 31, 2013 at 16:46
  • \$\begingroup\$ 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. \$\endgroup\$
    – danijar
    Commented Jun 1, 2013 at 12:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .