I'm working on a fairly basic line of sight system using Bresenham's line algorithm (http://en.wikipedia.org/wiki/Bresenham's_line_algorithm) for my isometric tile game. I first build a circle around the origin tile with a radius based on the current visual range of the map (larger for daytime, smaller for night/raining etc) I draw a line of tiles from the origin to each tile discovered in the circle, and then trace each line from the origin to discover blocked tiles, and to "darken" all tiles behind them in that line(out of sight). But I have a problem! Some tiles get missed in the sweep because of the way the algorithm builds the line. I can build an additional circle that is 1 radius smaller than the first, and it will always clear up the missing tiles.. but this is very redundant as it is tracking many of the same lines that the first circle did. My questions are: A) Is this, in general, an effective method of on-the-fly LOS detection? Walls and objects in the world can be destroyed, so I need a method which works on the fly, and not just during map creation. Note that I am not using the circle/line algorithm every time I want to detect LOS -- I have a pre-built array of lines based on the map's current view distance that start at (0,0) as the observer; I just plug in the current working tile's location. I am very pleased with the LOS results generated by this method (but only when using the double circles with redundant lines). B) Is there another method which would produce like results, but also deal with my "missing tile" problem?

It's a little unclear what your purpose is. Are you just trying to mark tiles as unpathable?

If so, then it's infinitely easier (and more efficient) just to flood fill across the tiles from the player's current position out to the radius. A flood fill would just take a virtual player object and recursively move him through the radial area. (http://en.wikipedia.org/wiki/Flood_fill) Basically:

Clear tile visited flags.

move virtual player from start to all adjacent positions.
From each adjacent position move it to all other adjacent positions.
etc (wheee recursion!)

Each time a tile is sucessfully visited mark it visited.
Exit conditions for the recursion are: tile not pathable, tile already visited by the floodfill, tile outside of radius.

-me

I am wanting to detect 360 degrees of LOS from an observer at a tile, and black out all tiles which would be "behind" a blocking object from the observer's perspective.

So I need something which

A) Finds all visible paths from the observer outward
B) Allows the "blacking out" of a visual path once it has passed a blocking object

Or just do a true line-cast. You know the extents of the tile so draw a straight line from the player to each tile. Do a collision check with each tile along the way, if it intersect a tile and that tile is line-check opaque, then the target tile is blacked out. There's a small enough number of tiles that you could just test each tile in the radius with each line and it probably wouldn't cost that much (that's the naive implementation).

The source of your problem is that you're using a line _drawing_ algorithm and treating the tiles as individual pixels. But your tiles aren't points, they have a significant area.

-me

I may be misunderstanding, but is the flood fill just finding which tiles would in the visible radius, and not actual lines of sight from the observer? Here are screens from my current program:

This is how it looks with a single circle, and a line of sight to each of the extreme points of the circle's edge:




This is with the double circle (one inside the other) with lines of sight drawn to each point in the edge of the circles. I also added in how it looks with "blocking" objects, and the "blocked vision" behind them (green tiles are blocked visually)


The blocking objects were randomly tossed in, and the visual shadows were made on the fly.

Quote:Original post by Palidine
Or just do a true line-cast. You know the extents of the tile so draw a straight line from the player to each tile.

I could do this, yes, but that would be many more calculations that I thought was needed since I would be checking the same tiles over and over as I moved outward towards the edges of the circle. My idea was to just make a single line trace to the extreme edge, which used many less line checks.

Quote:The source of your problem is that you're using a line _drawing_ algorithm and treating the tiles as individual pixels. But your tiles aren't points, they have a significant area.

I could do a ray cast which ignored the tiles and detected on a per-pixel basis if it was passing through an object, but that becomes more detailed than I want or need. Having a line made up of tiles (or in the algorithm's case, really, really big pixels) was enough for me to detect LOS.

I guess I am just looking for any other possible solutions, and wondering if my method is more retarded than it needs to be =D

Thanks for your input too, by the way.

1) You're correct about flood-fill being the wrong algorithm in this case. I misunderstood what you were trying to do.

2) What you're doing is essentially occlusion culling. Tiles that are occluded by other tiles are not visible. Couple ways to do that:

a) raycast with enough straight lines so that all tiles are covered
b) do it the 3D way where you treat the player as a light source and you have occluding tiles cast shadows (any tile in shadow is not visible).

(a) is going to be easier to implement, (b) may potentially be faster.

You're making your life more difficult by doing "lines as tiles" because as you point out the system doesn't work for a single radius of tiles.

If your system works with the 2 radii then I'd say just leave it as is until it becomes a performance problem (i.e. in a profiler you identify this algorithm as being the primary cause of low framerate)

-me

Quote:Original post by Extrarius
You problem is bresenham's line algorithm - it is designed to discretize the line, which means that tiles the line only barely passes through are missed as you've noticed.

You might want to adapt something like A Fast Voxel Traversal Algorithm for Ray Tracing to your situation, or you might just want to modify Xiaolin Wu's line algorithm which considers every 'pixel' the line touches.

Excellent! Wu's method is exactly what I needed, and will take about 5 minutes to implement on top of the current algorithm I'm using. Thanks!