iDevGames Forums

Full Version: Fast, 2d, line of sight?
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
What sort of algorithm do you suggest for quickly calculating a rough line of sight? It would be circular, top-down objects that would need to be detected, with varying sized objects inbetween.

I'm for as quick as possible, because I hope on implementing it in Ruby.
Ray sphere/circle intersections are pretty trivial. Just need a little quadratic formula.

As for collections of varying sized objects, you might try going with some variation on quad trees, sphere trees, or some other sort of binary spatial tree. Ray to splitting plane collisions are also very easy if you do a quad or binary spatial tree.

Spatial trees are a pretty varied group of data structures with ton of variations with different focuses on fast updates or fast queries or specific expectations on data layout.
Reference URL's