Line of sight through 2d polygons (shadows, field of view)

[CommanderKeith]

Hi,

I've made an algorithm that constructs a field of view polygon.

Most up to date version is the StraightEdge project at http://code.google.com/p/straightedge/

Here's the demo:
http://keithphw.freehostia.com/LineOfSight/LineOfSight.jnlp

source (note that clicking this link may not work, you may have to paste the link text into your browser window to actually download the zip file):
http://keithphw.freehostia.com/LineOfSight/src.zip
dependency jar (Java Topology Suite):
http://keithphw.freehostia.com/LineOfSight/jts-1.8.jar

Comments appreciated!!!!  

[Nate]

Sweet! Someday I want to make a game with something similar. Have you thought about implementing various field of view algorithms?
http://roguebasin.roguelikedevelopment.org/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds

Your program doesn't like it when I embed the triangle in carbonite, Han Solo style.

[CommanderKeith]

Thanks nate!

Yes I did see that article, i think OrangyTang linked to it a while back. All of the strategies there are pixel-based line of sight, where as this one uses polygons.

Hopefully this method scales better for bigger screen resolutions since you don't have to test every single pixel.

But it needs optimising, it's too slow right now. I'd like to be able to have an RTS game with all of the units having their own field of view

Games published by our own members! Check 'em out!

[CommanderKeith]

Your program doesn't like it when I embed the triangle in carbonite, Han Solo style.

Lol, ok yeah you're not meant to draw an obstacle on top of the triangle player   

may the source be with you 

[h3ckboy]

A. THANK YOU SO MUCH!!! This is the first demo I have ever found in java for shadowcasting!!!

B. is this based off of the pathfinding demo?

[CommanderKeith]

Thanks!   

Yes the demo is based on the path finding code, but it's a separate class that does the line of sight.

astarpathfinder.los.SightField.intersectSightPolygon(ArrayList<KPolygon> polygons) is where the line of sight polygon is calculated. That's all you need, besides some of the geometry classes like KPolygon and KPoint.

[h3ckboy]

what is this??

import com.vividsolutions.jts.geom.*;

Is the class Polygon converter required for shadow casting??

EDIT:

further looking into it showed that it was that polygon converter required them not the other way around .

I will try to disect the code. But it would be easier still if I could get it to actually compile

[CommanderKeith]

Hi heckboy,

The PolygonConverter class and the JTS package are used to make shrunk versions of polygons. These are needed in the demo because there has to be a guarantee that the 'eye' or light source can never be on the edge of a polygon - it always has to be at least a very small distance away. So obstacles have two polygons an outerPolygon which can't be penetrated by the player, and an innerPolygon which is a shrunk version of the outerPolygon and is used to cast shadows.

You don't need to use this method to gaurantee that the 'eye' isn't on the edge of a polygon - if your physics engine can do that then that's fine. So the shadow casting code is not bound to the rest of the code. Notice that the method
astarpathfinder.los.SightField.intersectSightPolygon(ArrayList<KPolygon> polygons) takes polygons as an argument, rather than PathBlockingObstacles which have the innerPolygon and outerPolygons.

I hope that answers your question! To get the demo to compile, just include the jts package on the classpath and it should be fine. Let me know if it works out 

[h3ckboy]

ok, thx for the clarification!!

Il post if I have any other questions .

[Eli Delventhal]

Very cool. Great work.

Games published by our own members! Check 'em out!

[CommanderKeith]

Thanks 

I thought such a thing must already exist but after googling for ages i couldn't find anything except pixel-based strategies.

So I tried to make my own but it was never stable due to floating point rounding problems. I think I've fixed that by making it so that the player can't be too close to an obstacle so that he's collinear with the edges.

Interestingly, the polygon-based non-pixel approach seems to work well with java2d because it means that you don't need to access an image's pixel buffer which normally destroys hardware acceleration.

[Riven]

Is there any precalculation required?

You might be using the connection-graph?

I'm too lazy to dive in the sourcecode

[CommanderKeith]

Thanks for having a look Riven - there isn't any pre-calculation in the line of sight code at the moment. The big delay you see is due to the a-star path finding code which has nothing to do with the line of sight calculations.

But soon I'll add some pre-calculation of obstacle intersection points. Currently all obstacles are intersected with each other every frame which is obviously a massive waste when they're not moving so I'll cache those intersection points which will speed things up slightly.

Apart from that I'm not sure what further optimisations I can make... since there's only one method that does the calcs the profiler option '-Xprof' only tells me how much time is spent in that method, not in which part of the method so maybe I'll have to break up the methods into smaller ones to be able to tell what's taking the most time... is that what you would do?

[Riven]

No. Xprof is high unreliable. It lies! Damn lies!

1. Use VisualVM (shipped with every JDK since u10)
  -> keep in mind that the overhead is rather big and can skew results

2. Scatter System.nanoTime() in your method.
  -> keep in mind that querying the time also takes time. measure that time, and substract that from each timing:


for(int i=0; i<1024; i++)
   System.nanoTime(); // warm the JIT
long selfTime = -(System.nanoTime() - System.nanoTime());

...

long aTook = 0;
long bTook = 0;
for(....)
{
   long t0 = System.nanoTime();
   // ...
   long t1 = System.nanoTime();
   aTook += (t1-t0)-selfTime;
   
   for(...)
   {
      long t0 = System.nanoTime();
      // ...
      long t1 = System.nanoTime();
      bTook += (t1-t0)-selfTime;
   }
}

[CommanderKeith]

Apparently Xprof has been fixed since java 6 u10 or so. Ken Russell fixed it a few months before he left Sun. Such a pity he left.

Similarly to your experiences with visualVM I've had the same problems of skewed results when using netbean's profiler - it seems to over-estimate the time taken to do small methods for some reason whereas Xprof appears more accurate.

I like the System.nanoTime approach, very clever. I'll try that, thanks 

[ManaSink]

Similarly to your experiences with visualVM I've had the same problems of skewed results when using netbean's profiler

I think these might be the same beast under the covers, just a re-package by Sun.

I like the System.nanoTime approach, very clever. I'll try that, thanks 

nanoTime() is pretty awesome, but it uses a CPU specific ticker, so it may act weird on multi-CPU boxes (Usually AMD + Windows).  If the nanoTime() calls run on different CPUs, they can return wildly different timestamps which can make your code go crazy.  I think you can get a patch from AMD that will keep them in sync.  Great for development, but can produce weird bugs if you use it on customer boxes.


Anyway, nice stuff man, thanks for sharing.   

[Eli Delventhal]

No. Xprof is high unreliable. It lies! Damn lies!

1. Use VisualVM (shipped with every JDK since u10)
  -> keep in mind that the overhead is rather big and can skew results

2. Scatter System.nanoTime() in your method.
  -> keep in mind that querying the time also takes time. measure that time, and substract that from each timing:


for(int i=0; i<1024; i++)
   System.nanoTime(); // warm the JIT
long selfTime = -(System.nanoTime() - System.nanoTime());

...

long aTook = 0;
long bTook = 0;
for(....)
{
   long t0 = System.nanoTime();
   // ...
   long t1 = System.nanoTime();
   aTook += (t1-t0)-selfTime;
   
   for(...)
   {
      long t0 = System.nanoTime();
      // ...
      long t1 = System.nanoTime();
      bTook += (t1-t0)-selfTime;
   }
}

There isn't really a reason to find out how long nanoTime takes, is there, because all you're trying to do is find what takes the longest, right?

If A > B > C > D, then A+X > B+X > C+X > D+X. So it's no big deal to worry about that for profiling, as long as X remains consistent.

Also, Riven, I think you've got a typo with your negative signs for selfTime.
Don't you mean either long selfTime = (System.nanoTime() - System.nanoTime()) or += (t1-t0)+selfTime ? Right now in your code above it looks to me like you're doubling how long nanoTime takes, rather than subtracting it out. Unless I missed something.

[Riven]

There isn't really a reason to find out how long nanoTime takes, is there, because all you're trying to do is find what takes the longest, right?

Nope, selfTime is pretty important (that's why i added the inner-loop).
It will make the inner-loop much slower than the outer loop, so you have to compensate by removing the selfTime. Without it, the results will be skewed towards the highest-density of nanoTime calls. That is not related to performance, that is realated to where you decided to put the timing-code. Therefore it must be taken out of the equation, thus selfTime *must* be subtracted.

Also, Riven, I think you've got a typo with your negative signs for selfTime.
Don't you mean either long selfTime = (System.nanoTime() - System.nanoTime()) or += (t1-t0)+selfTime ? Right now in your code above it looks to me like you're doubling how long nanoTime takes, rather than subtracting it out. Unless I missed something.

Excuse my French: Nope.

One line: (incorrect)
long t = System.nanoTime() - System.nanoTime();

Three lines:  (incorrect)
long a = System.nanoTime(); // first! lower value
long b = System.nanoTime(); // higher value
long t = a - b; // (lower - higher) = negative, that's incorrect, because selfTime is always positive !!


Correct:
long t = -(a - b); // -(lower - higher) = positive

[kevglass]

Or (b - a) ?

Kev

[Riven]

Or (b - a) ?

Kev

that can't be put on 1 line:

System.nanoTime() - System.nanoTime() // try to swap that!

[Eli Delventhal]

Ah yes, I didn't think about the order with which times would come in when you do nanoTime - nanoTime. Cool.

[CommanderKeith]

I made some optimisations and now the code is 3 to 10 times faster, woo hoo!  Even the 'medium maze' map runs at a reasonable 40 fps on my machine compared to 5fps before. These were the big optimisations:
- caching the obstacle intersections
- minimising calls to polygon.contains(point) by using distance calculations

If you press 'K' then a rotating polygon will be inserted into the map wherever the mouse pointer was. These rotating polygons will only be included in the line-of-sight calculations, not the path-finding calculations.

The webstart and source are updated. Here's a new screenshot with lots of rotating polygons:


Cheers 
keith

[h3ckboy]

I noticed that the new version had a lot more classes in the LOS section if I am not mistaken.

Are these required now? cause it would be nice to do it the faster way .

[InsaneShane63]

Haha wow!  That's really cool.  Good job.

[Eli Delventhal]

This thing is totally badass. I really want to make a game just on top of your code, it's so fun having that little triangle run around.

[CommanderKeith]

Thanks guys!  You're totally welcome to use the code. I've got some ideas to use this thing for some fancy 2d graphics - like making a few stationary lights that cast shadows against unit outlines. Totally pointless but i think it'd look cool.

I'm experimenting with different shading on the light source too - like using java2D's RadialGradientPaints.

I noticed that the new version had a lot more classes in the LOS section if I am not mistaken.

Are these required now? cause it would be nice to do it the faster way .

The new classes was just a refactoring of the internal classes into proper classes. You need them to use the new faster version.

Also, I've worked out a solution for stopping the bugs when shapes have collinear sides that overlap. I test for collinear overlaps and then randomly jiggle the offending polygon points around which fixes the problem. I'll post up the new code tomorrow.

One thing I'd like to figure out is a good way to implement discovered and undiscovered parts of the map. Right now the light source code is good for 'fog of war' but not for blacking out/revealing undiscovered terrain... any ideas?

[Eli Delventhal]

I haven't looked through your code, but could you perhaps just store a single java.awt.geom.Area that is where you have visited? Then just subtract your line of site from it each step. Could be very slow, I dunno, but it's certainly easy.

[h3ckboy]

you could just check if you current reducedSightField has more than another polygon say ExploredTerrain. and if so add on to it. not sure if this would work though.

[CommanderKeith]

I haven't looked through your code, but could you perhaps just store a single java.awt.geom.Area that is where you have visited? Then just subtract your line of site from it each step. Could be very slow, I dunno, but it's certainly easy.

you could just check if you current reducedSightField has more than another polygon say ExploredTerrain. and if so add on to it. not sure if this would work though.

Good ideas, thanks. The hard bit is making a union of the polygons in a fast enough way. java.awt.geom.Area is too slow and I think JTS's version of polygon unions might be very slow as well. I'll try it out and let you know. Checking for the possibility of an intersection is a great idea to speed it up.

By the way, I updated the webstart and source code to reflect the new more stable version. Now you can automatically check and fix problematic arrangements of polygons by doing this:

1   2

CollinearOverlapChecker c = new CollinearOverlapChecker(); c.fixCollinearOverlaps(polygonList);

Since the fix I haven't seen any bugs where obstacle intersections are missing which is cool 

[h3ckboy]

I have a question. This is a regular java question but since it is in your program Il just ask here:

what is this?

1	int nextM = (m+1 >= points.size() ? 0 : m+1);

if say:
m=1
points.size() = 4

how would this work out?

sry for noobish question