Quick 2D sight area calculation algorithm?

Posted by Rogach on Game Development See other posts from Game Development or by Rogach
Published on 2012-01-04T22:17:35Z Indexed on 2012/10/31 23:18 UTC
Read the original article Hit count: 602

Filed under:
|
|
|
|

I have a matrix of tiles, on some of that tiles there are objects. I want to calculate which tiles are visible to player, and which are not, and I need to do it quite efficiently (so it would compute fast enough even when I have a big matrices (100x100) and lots of objects).

I tried to do it with Besenham's algorithm, but it was slow. Also, it gave me some errors:

----XXX-        ----X**-     ----XXX-
[email protected]        [email protected]     [email protected]
----XXX-        ----X**-     ----XXX-
(raw version)   (Besenham)   (correct, since tunnel walls are 
                              still visible at distance)

(@ is the player, X is obstacle, * is invisible, - is visible)

I'm sure this can be done - after all, we have NetHack, Zangband, and they all dealt with this problem somehow :)

What algorithm can you recommend for this?

EDIT:

Definition of visible (in my opinion): tile is visible when at least a part (e.g. corner) of the tile can be connected to center of player tile with a straight line which does not intersect any of obstacles.

© Game Development or respective owner

Related posts about 2d

Related posts about engine