Saturday, February 18, 2006

Calculating Line of Sight - Help Needed!

At the moment, Emergent Mercenary uses the following algorythm to work out of one unit can see another (i.e. are there any walls in the way):-

(Note - the map of the game is a simple 40x40 array, and each cell can be a wall or floor. Unit positions are stored as floating point numbers, so they can be anywhere, not just in the centre of a map square)

1) Work out a line from one unit to another
2) Move along the line, and at every interval, check whether the point is part of a wall or a map. If its a wall, the unit cannot see the target.

This does work well in general, but if two units are close together but round the corner from each other, it can sometimes return true when in fact there is a corner in the way. I could try increasing the interval, but this obviously increases the time it takes the algorythm to run. Does anyone know a better method?

Any help much appreciated.

No comments: