I have a large grid with hundreds of individual agents, each of which is moving around based on its own visual inputs and a fast control algorithm.

My question is: How can I efficiently provide each agent with a set of other agents (or walls) that they can see?

Ray casting from each individual works, but is slow. It seems like I should be able to preprocess the world at each step to speed up this process since I'll be doing it MANY times, but I haven't been able to come up with an appropriate algorithm. Is there some known trick that I've missed?

  • 1
    \$\begingroup\$ There is something called the "visibility complex" which I haven't yet figured out but here's a paper you might look at — scholar.google.com/… \$\endgroup\$ – amitp Oct 30 '16 at 19:06

If you haven't already, look into using optimisation algorithms and data structures such as quadtrees, spatial hashing, binary space partitioning, and so on.

A quadtree in particular would do just fine in this case, and is fairly simple to implement. It subdivides a rectangular area of the game world into four equally sized rectangles, and continues to do so for each of the resulting rectangles for a specified number of levels. If an object overlaps one of these rectangles, its reference is stored in that rectangle's 'bucket' (array of object references).

When you look for a particular object inside the quadtree, you check each rectangle's bucket for the object, and continue down to the last rectangle (the leaf of the quadtree) that contains the object in its bucket. Then you just perform a check on each of the object in that bucket to find the one you're looking for.

In your case, you would look for the rectangles the ray intersects, and then sort through the objects to see which is the closest one. That part could be a little tricky, but it shouldn't be impossible to do.

If you have rooms or walls / barriers, you could look into partitioning the map according to how the walls intersect when extended infinitely. Objects in the same room or region would be visible to each other, which limits the pool of objects you have to check the ray against.

| improve this answer | |

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.