Efficient 2d Java Line of Sight for a lot of entities?

Question

My problem today is this:

I have many civilians going around, they are classes stored by an arraylist.

The idea is when they see another civilian panic, they'll start to panic and it will spread.

First I call each classes Step() function by looping through an iterator. Then in the Step() function it goes through another civillian iterator As it goes through, it tries to detect whether it can see the other civillian in the iterator, this is where performance time goes from 0 to 50 Milliseconds for having 100 Civillians.

This is the problem I need to fix, I tried to make an easy way to detect whether any objects are in the way of point a to point b.

Here's the code for the line of sight:

public static Object LOS(int x, int y, int x2, int y2, String Scan, Object Me, Object You) {
   DirectionX = (x-x2)/Quality;
   DirectionY = (y-y2)/Quality;
   CurrentX = x;
   CurrentY = y;
   String[] ScanArray = Scan.split(":");
   for(int I=0;I<=Quality;I++) {
      for(String Type: ScanArray) {
         if(Type.equals("Boxs")) {
            Iterator it=Level.Boxs.iterator();
            while(it.hasNext()) {
               Box Box = (Box)it.next();
               if(Me!=Box&&You!=Box) {
                  //Collision = Tools.Collision((int)(CurrentX-(Width/2)), (int)(CurrentY-(Width/2)), Width, Width, Box.GetX(), Box.GetY(), Box.GetWidth(), Box.GetHeight(), 1);
                  boolean Col = Tools.BasicCollision((int)(CurrentX-(Width/2)), (int)(CurrentY-(Width/2)), Width, Width, Box.GetX(), Box.GetY(), Box.GetWidth(), Box.GetHeight());
               }
            }
         }
      }

      CurrentX-=DirectionX;
      CurrentY-=DirectionY;
   }
   return null;
}

If you have a headache the fundamentals are:

It figures out 10 points in between and detects whether it is inside, using BasicCollision:

public static boolean BasicCollision(int x, int y, int width, int height, int x2, int y2, int width2, int height2) {
   if(x<x2+width&&x+width>x2&&y<y2+height&&y+height>y2) {
      return true;
   } else {
      return false;
   }
}

My question is: Is there an easier way to detect this Line of Sight that doesn't severely impact my performance in large numbers? Any feedback?

Answer 1

One thought would be to maintain non-panicky and panicky people in separate lists N and P, and then limit your LOS checks to <n, p> ∈ N × P. That way you never check same-state people, which will speed things up.

Another thing (which you may already be doing--not sure) would be to make sure that once you determine that a nonpanicker has become a panicker, immediately halt remaining checks for that former nonpanicker. This will help your algorithm scale with increasing population size for a fixed map. When the population gets very large then you should converge toward 100% panicking pretty quickly, which means no more checks are needed as noted in the comments below.

Answer 2

From your description it seems like your code is iterating over every possible pairing of two civilians. The drawing suggests that this is unnecessary. You can use some sort of geometric indexing to keep track of nearby civilians. Then test them first. If they are in the LOS, then panic. Otherwise test farther away civilians.

Answer 3

You have several options:

A) Assume that people can panic also hearing other people screaming, so the line of sight code is not that important XD.

B) In case A is not an option, you have to do this for each civilian:

1. Calculate if the segment between two civilians has a length less or equal some constant value.
2. Compute if this segment intersects with a poligon (rectangle, in your case).

You have to perform 1 before 2 because it greatly reduces the ammount of work, given that 2 is the most expensive computation. Also you have to consider some kind of "memory" about the calculations you have already made, e.g.: If you just processed the C1-C2 segment, don't do again C2-C1.

In addition to that, you have to optimize 2. Testing if a segment intersects with a rectangle is equivalent to test if a given segment intersects with 4 segments. When you have intersected with one of them, we're sure the civilians don't see each other, so it makes no sense to process the remaining segments in the rectangle.

Since this is a typical geometrical problem, known as the line segment intersection problem, you can find plenty of open source code on the internet. Most people use a sweep line algorithm along with some data structure.

Answer 4

If you treat rooms as zones, joined by portals, you only only have to do visibility scans within each room and those parts of adjoining rooms that are visible through the pre-determined portals.

Your line-of-sight is likely not accounting for the direction the civilian is facing? In such a case, if you divide rooms that contain obstacles like pillars or goes around corners into separate convex zones and assuming that all civilians in the same zone are all visible to each other. You may take that further by having overlapping concave zones and allowing civilians to be in more than one zone at once as as to find as many as possible in the same zone as the other civilian so as to avoid all other visibility checks.

If your terrain is uneven and you have a large number of agents then you may be interested in this O(n) sweep (where N is the granularity of a grid you've divided terrain into):