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

Shared Code
#1

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!!! 8)

http://www.fileden.com/files/2008/9/22/2110084/LineOfSightMaze.png

http://www.fileden.com/files/2008/9/22/2110084/LineOfSightPillars.png

#2

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. :wink:

#3

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

#4

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

may the source be with you ;D

#5

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?

#6

Thanks! :slight_smile:

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 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.

#7

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 :P.

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

#8

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 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 8)

#9

ok, thx for the clarification!!

Il post if I have any other questions ;D.

#10

Very cool. Great work.

#11

Thanks 8)

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.

#12

Is there any precalculation required?

You might be using the connection-graph?

I’m too lazy to dive in the sourcecode :wink:

#13

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?

#14

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;
}
}
`

#15

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 :slight_smile:

#16

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

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. :slight_smile:

#17

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.

#18

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.

Excuse my French: Nope. :wink:

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

#19

Or (b - a) ?

Kev

#20

that can’t be put on 1 line:

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