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

Shared Code
#21

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

#22

I made some optimisations and now the code is 3 to 10 times faster, woo hoo! :smiley: 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:

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

Cheers 8)
keith

#23

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

#24

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

#25

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

#26

Thanks guys! 8) 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.

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?

#27

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.

#28

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.

#29

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:


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

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

#30

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

what is this?


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

#31

That’s fine.

nextM would be 2 if m == 1.

If m == 3, nextM would be 0.

#32

I think that I had figured it out. So m is supposed to be the point after j, and nextM is the point after that?

I have spent about an hour, and I think that I have a pretty solid grasp of about the first half of it.

it is actually pretty genious :slight_smile:

#33

same as:

int nextM = (m+1) % points.size();

#34

not that i understood all that high level stuff you are talking about

here is my problem

downloaded the *.jar (which i assume is the compiled code)
and the dependency jar

so i double click the LineOfSight.jar and i am expecting it to work
(it works fine when using the jnlp)

it opens the “Progess : Just a few Moments: Quit (Button)” frame and never executes

what can i do to run it as a desktop ? (and not compiling the source i was given generously)

#35

Hi skinny boy,

Look up how to include jars on the classpath so you can include JTS, and use the source code I provided rather than the jar. What IDE are you using? In netbeans it’s easy to include jars.

That’s cool, never seen that. Is there a similar thing for prevM which is like this with the conditional operator?


int prevM = (m-1 < 0 ? points.size()-1 : m-1);

Cheers,
Keith

#36 

int range = points.size();
int nextM = (m+1) % range;
int prevM = (m-1+range) % range;
#37

Nice 8)

#38

i use JCreator and i am seriously thinking about changing it
i will give it a shot when i have time

#39

Pretty neat. So what’s the actual algorithm going on here? Are you creating shadow polys from each object and then subtracting them from a big light poly to get the final light shape?

#40

Thanks a lot, this is pretty much the algorithm:

Make an empty list of points
Add all polygon points that have an unobstructed line to the eye (or light source)
Add all polygon intersection points that have an unobstructed line to the eye
Add all points on the sight polygon (or field of view) that have an unobstructed line to the eye
Sort the list by the angle of each point relative to the eye, from the x-axis
Search through the points and find any polygon points that are ‘end points’ which would cast a shadow.
Cast a ray from these points away from the eye, and find the intersection of this ray with the nearest polygon or the nearest edge of the sight polygon.
Add the intersection to the list, before or after the ‘end point’ depending on which side the end point is on.

It took a lot of trial and error to arrive at this method. I tried lots of other ways but they weren’t stable. This one works fine so long as the eye is never collinear with any edges of the polygons, which i enforce by making the player unable to penetrate a slightly larger polygon, which i create using JTS. You pointed me to that so cheers :slight_smile: