I am trying to implement Field of View algorithm in my game and I followed the great tutorial here : sight-and-light and here is what I got so far :

enter image description here

As you can see it works fine for me :)

And then I try to use this algorithm in a tiled map. It also works fine but just a little bit slow so I am now trying to find a way to optimize the algorithm.

Some information might help to optimize :

  • The tiled map is Orthogonal
  • All the tiles have the same size 32 * 32 and are square
  • Tiles marked 0 means empty marked as 1 means a obstacle
  • I have used Connected Component Labelling algorithm for a preprocess :
    • All the obstacles have been merged into several regions
    • I know all the vertices position in each regions

Something like this :

enter image description here

Say I have 9 connected regions ( 9 polygons ) and 40 vertices in total.

Based on the algorithm in the above link, there will be :

  • ray-cast : 40 * 3 ( 3 ray-cast per vertices in angle +- 0.00001)
  • edges : 40
  • edge * ray-cast intersection test : 40 * 40 * 3 == 4800

I think there should be a way to reduce the ray cast count and the edges count that I need to do the intersection calculation in a above situation but just could not figure out a good solution.

Any suggestion will be appreciated, thanks :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.