Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (499)
Games in Android Showcase (118)
games submitted by our members
Games in WIP (567)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2 3
  ignore  |  Print  
  Line of sight through 2d polygons (shadows, field of view)  (Read 27554 times)
0 Members and 1 Guest are viewing this topic.
Offline CommanderKeith
« Posted 2009-09-30 09:04:11 »

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!!!!   Cool




Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #1 - Posted 2009-09-30 09:08:27 »

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

Offline CommanderKeith
« Reply #2 - Posted 2009-09-30 09:21:36 »

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!
Legends of Yore - The Casual Retro Roguelike
Offline CommanderKeith
« Reply #3 - Posted 2009-09-30 09:28:16 »

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

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

may the source be with you  Grin

Offline h3ckboy

JGO Coder


Medals: 5



« Reply #4 - Posted 2009-09-30 11:15:48 »

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?
Offline CommanderKeith
« Reply #5 - Posted 2009-09-30 13:06:03 »

Thanks!   Smiley

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.

Offline h3ckboy

JGO Coder


Medals: 5



« Reply #6 - Posted 2009-09-30 16:57:01 »

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

I will try to disect the code. But it would be easier still if I could get it to actually compile Smiley
Offline CommanderKeith
« Reply #7 - Posted 2009-09-30 20:16:48 »

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  Cool

Offline h3ckboy

JGO Coder


Medals: 5



« Reply #8 - Posted 2009-10-01 05:42:04 »

ok, thx for the clarification!!

Il post if I have any other questions Grin.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #9 - Posted 2009-10-01 14:36:34 »

Very cool. Great work.

See my work:
OTC Software
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CommanderKeith
« Reply #10 - Posted 2009-10-01 14:59:02 »

Thanks  Cool

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.


Offline Riven
« League of Dukes »

JGO Overlord


Medals: 801
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2009-10-01 17:47:01 »

Is there any precalculation required?

You might be using the connection-graph?

I'm too lazy to dive in the sourcecode Wink

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline CommanderKeith
« Reply #12 - Posted 2009-10-01 18:19:33 »

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?

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 801
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #13 - Posted 2009-10-01 18:28:45 »

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


Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline CommanderKeith
« Reply #14 - Posted 2009-10-01 18:48:31 »

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  Smiley

Offline ManaSink

Senior Newbie





« Reply #15 - Posted 2009-10-01 19:22:27 »

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  Smiley

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.   Smiley
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #16 - Posted 2009-10-01 19:23:41 »

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.

See my work:
OTC Software
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 801
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #17 - Posted 2009-10-01 19:29:56 »

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline kevglass

JGO Kernel


Medals: 169
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #18 - Posted 2009-10-01 19:34:32 »

Or (b - a) ?

Kev

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 801
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #19 - Posted 2009-10-01 19:36:15 »

Or (b - a) ?

Kev

that can't be put on 1 line:

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #20 - Posted 2009-10-02 03:20:21 »

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

See my work:
OTC Software
Offline CommanderKeith
« Reply #21 - Posted 2009-10-03 11:01:45 »

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

Offline h3ckboy

JGO Coder


Medals: 5



« Reply #22 - Posted 2009-10-09 16:42:04 »

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 Smiley.
Offline InsaneShane63

Junior Newbie





« Reply #23 - Posted 2009-10-09 20:58:45 »

Haha wow!  That's really cool.  Good job.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #24 - Posted 2009-10-10 01:48:47 »

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

See my work:
OTC Software
Offline CommanderKeith
« Reply #25 - Posted 2009-10-10 14:23:59 »

Thanks guys!  Cool 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 Smiley.

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?

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #26 - Posted 2009-10-11 00:17:18 »

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.

See my work:
OTC Software
Offline h3ckboy

JGO Coder


Medals: 5



« Reply #27 - Posted 2009-10-11 12:22: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.
Offline CommanderKeith
« Reply #28 - Posted 2009-10-11 13:28:40 »

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  Cool

Offline h3ckboy

JGO Coder


Medals: 5



« Reply #29 - Posted 2009-10-11 14:28:06 »

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 Tongue
Pages: [1] 2 3
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Pippogeek (38 views)
2014-09-24 16:13:29

Pippogeek (29 views)
2014-09-24 16:12:22

Pippogeek (18 views)
2014-09-24 16:12:06

Grunnt (42 views)
2014-09-23 14:38:19

radar3301 (24 views)
2014-09-21 23:33:17

BurntPizza (61 views)
2014-09-21 02:42:18

BurntPizza (31 views)
2014-09-21 01:30:30

moogie (36 views)
2014-09-21 00:26:15

UprightPath (49 views)
2014-09-20 20:14:06

BurntPizza (53 views)
2014-09-19 03:14:18
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!