Fast, 2d, line of sight?

Posts: 43
Joined: 2009.02
Post: #1
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.
Quote this message in a reply
Posts: 1,487
Joined: 2002.09
Post: #2
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.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Read a text file line by line? jdunehew 6 16,187 Dec 29, 2011 11:54 AM
Last Post: Blacktiger
  Line Of Sight in Tile Game whogben 9 11,797 Mar 18, 2005 06:58 AM
Last Post: radiance