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?

  • 1
    if I'm not mistaken, this question and answer might help you. gamedev.stackexchange.com/questions/12826/…. – Ali1S232 Jul 11 '11 at 22:44
  • gamedev.stackexchange.com is a better place to ask a question like this. – Ali1S232 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. – ahodder Jul 11 '11 at 22:51
  • @Gajet that question is about pathfinding, this one is more about geometry. – John Lyon Aug 1 '11 at 6:26

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)

  • 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? – ahodder 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

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.