6
\$\begingroup\$

I've been searching for information on implementing line-of-sight in my game. I've found some great resources for 2D implementations that produce pixel-perfect results, but there's very little info on 3D implementations.

So far, I've found these methods that could be used to achieve line-of-sight:

  • Shadow maps

  • Shadow volumes

  • 3D grids / octrees

However, each of these seems to have limitations. Shadow maps are quite expensive to calculate, especially for omni-directional line-of-sight (just like omni-directional shadows). Shadow volumes have special requirements for geometry and are rather difficult to produce. 3D grids and octrees are not pixel-perfect and require an additional renderer on top of the grid implementation.

Have I missed something here? Which method would be the most suitable for a top-down 3D game?

\$\endgroup\$
  • \$\begingroup\$ The right implementation depends on your requirements. I'm afraid this might actually be an X/Y problem. Why do you need line-of-sight? Is it merely to get monsters to see the player? Is it to calculate when a monster is in view of the player? Further, why do you need it to be in 3D? Can entities be at various heights? Can they be occluded by 3D geometry? Is the scene static, or dynamic? In the worst case (dynamic, 3D, "pixel perfect", omni-directional) there is little you can do besides rendering many occlusion maps of the scene. In the best case, you can get away with simple raycasting. \$\endgroup\$ – mklingen Dec 30 '14 at 14:46
  • \$\begingroup\$ Can you describe your use case? What kind of accuracy do you need? \$\endgroup\$ – Steven Dec 30 '14 at 17:13
6
\$\begingroup\$

The first thing I would suggest is to use a 2d implementation like the one in Teleglitch, like you said yourself, you found solutions, this is a lot simpler.

Line of sight is a gameplay mechanic. If the game is top-down, the gameplay is essentially 2d and there is likely a limited benefit to using actual 3d line of sight.

No, you are absolutely right. This is not a simple problem. Imagine that without knowing anything about the content (without making assumptions about the visual space / the geometry of the environment), you actually "need" to send a ray for each tiny spot you wish to decide on. It is like checking collisions for a bunch of infinitely small balls moving towards all directions that are within the viewing angle of the source. It is not simple in 2d either if the data is complex enough, the advantage is that in 2d, you only need to sample a 1d space. In 3d you need to sample a 2d matrix so the amount of work needed especially for real time applications is very daunting.

Using shadow volumes is probably your best bet. Octrees could help to reduce the amount of work too but those are both suggestion you alread made.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.