Quick 2D sight area calculation algorithm?
- by Rogach
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-
-@------ -@------ -@------
----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.