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.

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 Bresenham's line 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?

For my needs, I'll define visible like this: 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.

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?

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.