Line of Sight algorithm: Bresenham

While I was working at my roguelike I faced the issue of what player can see.

This issue is known as Field of View. In a roguelike, player lives in a grid-world. His field of view are the tile he can see all around, given a certain range (influenced tipically by lighting). One of the possible methods to resolve this is using a line of sight algorithm, usefull also in other circumstances.

The plot is simple. Can player see from his position A to position B? If a rect line can be traced from A to B without passing through an obstruction (wall or whatever) he can.

Calling this for every end point of the area around the player results in the field of view. Sound simple, but it’s a bit tricky to implement.

I started with a couple of implementation of mine, based on the rect-between-two-points equation, that sounds like this:

(y – y0)(x1 – x0) = (x – x0)(y1 – y0)

and I reached a quite good result. In my game, player has a sight of 6, which means he can see at 6 cells, or tiles, around him. With this, almost the full area was correctly filled but some cells did not obey rightly.

After a bit of headache I opted for google and found this nice article on Bresenham line drawing alg.

Copy/paste on my routine, made some little edit and the result is pretty good. If you are looking for a line of sight algorithm I suggest it. It worked for me.

Bye.

Advertisement