Most efficient way of finding entities in a grid?

Question

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?

• Ali1S232: if I'm not mistaken, this question and answer might help you. gamedev.stackexchange.com/questions/12826/….
• Ali1S232: gamedev.stackexchange.com is a better place to ask a question like this.
• Alex Hope O'Connor: 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?
• ahodder: @Alex Hope O'Connor - that is a possibility. I will look into it thank you.
• John Lyon: @Gajet that question is about pathfinding, this one is more about geometry.

Answer 1

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)

• ahodder: 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?
• Neal Tibrewala: The K-D tree naively only partitions the space, so no two towers would cover the same pixel (no overlapping areas)