tile based line of sight algorithim

[Seiko]

Guys,

I posted this on another web site forum but always like a cross section of views. I appreciate some of you may groan when I raise this old chestnut but hopefully someone has the time to post a few ideas.

I have a visual basic 2D tile based engine (using Dx8.1 D3D) and have recently added a line of sight algorithim so that some of the tiles are not shown if the view is blocked.

I currently use a simple 360 degree ray trace algorithim where by I step out from the center at a specified angle plotting tiles until the ray hits a tile that is a wall. Having hit a wall tile I increase the angle and start again.

Unfortunately even with a single degree increment I still occasionally fail to scan all tiles. I.e. a few are missed out as the ray trace simply doesn't quite hit them all.

So as opposed to reduce the angle increment to .5 and then require 720 angle iterations I wanted to explore some other techniques. I've scanned the web but alas cant really find any working examples of other techniques.

If some one could please offer some advice or point me to the other techniques I'd be greatful. Of course I need it to be as fast as possible but more importantly it mustn't miss any tiles?

Thanks in advance, look forward to the ideas

: )

edit=typos

 

[bloodbob]

how many tiles? you may wish to try the inverse approach do LOS check from each tile to view point and if collision discard tile that way you shouldn't miss any tile. Also if combinded with a far cliping pane you can limit the number of tiles.

 

[Seiko]

how many tiles? you may wish to try the inverse approach do LOS check from each tile to view point and if collision discard tile that way you shouldn't miss any tile. Also if combinded with a far cliping pane you can limit the number of tiles.

32*24. BTW, I only scan the visible tiles. i.e. those that are in the curent viewport.

I've tried checking each tile seperately, i.e. choose destination tile, determine angle from origin, step along from origin determining when wall struck. Although this means I actually check each tile it also means I end up scanning each tile irrespective of walls. I tried to optimise this so I only choose the outer edge tiles but that then results in some of the inner tiles being missed. I suspect scanning every tile will actually be a lot more expensive than a ray trace even if I increase the precision by reducing the angle increment?

Any further ideas would be great.