Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
1  
if I'm not mistaken, this question and answer might help you. gamedev.stackexchange.com/questions/12826/…. – Gajoo Jul 11 '11 at 22:44
gamedev.stackexchange.com is a better place to ask a question like this. – Gajoo Jul 11 '11 at 22:44
1  
I remember in an old game engine the base map object had a method which would return all objects currently on that tile, so when doing an LOS check I would simply loop over a grid of tiles and check each object upon those tiles. The way this worked I believe in each tile had a collection of objects which would change as other objects entered an left them. Maybe you could structure your game objects to support something similar? – Alex Hope O'Connor Jul 11 '11 at 22:47
@Alex Hope O'Connor - that is a possibility. I will look into it thank you. – AedonEtLIRA Jul 11 '11 at 22:51
@Gajet that question is about pathfinding, this one is more about geometry. – jozzas Aug 1 '11 at 6:26
show 2 more comments

1 Answer

up vote 2 down vote accepted

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)

share|improve this answer
Thanks, Interval tree looks like it may work. Your suggestion thought pointed me to a K-D Tree; do you think that could work as well? – AedonEtLIRA Aug 4 '11 at 14:51
1  
The K-D tree naively only partitions the space, so no two towers would cover the same pixel (no overlapping areas) – Neal Tibrewala Aug 5 '11 at 2:30
Ah, thanks for the clarification. – AedonEtLIRA Aug 5 '11 at 20:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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