I'm working on my first game; a tower defense. So far It's coming along nicely. The only issue I am having (so far) is I can't figure out a way to effciently discover if an entity has entered a towers line of sight. So far I have considered just having every entity run though each known entity and calculate LOS, but that would bog down extremely quick. Then I thought of just having a bounding box for each tower and one each game step see if anything is in the bounding box. I have the same performance issue with that. Can anyone put forth some advice to put me on the correct track?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Try using an interval tree: http://en.wikipedia.org/wiki/Interval_tree
It allows you to store multiple intervals (the ranges of the towers) and make overlapping "stabbing queries" against those intervals with the query interval (the bounding box of your entity).
The tree does generalize to higher dimensions (e.g. 2D)