|
|
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!
|
|
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.  Lol, ok yeah you're not meant to draw an obstacle on top of the triangle player may the source be with you 
|
|
|
|
h3ckboy
|
 |
«
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?
|
|
|
|
CommanderKeith
|
 |
«
Reply #5 - Posted
2009-09-30 13:06:03 » |
|
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
|
 |
«
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  . I will try to disect the code. But it would be easier still if I could get it to actually compile 
|
|
|
|
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 
|
|
|
|
h3ckboy
|
 |
«
Reply #8 - Posted
2009-10-01 05:42:04 » |
|
ok, thx for the clarification!! Il post if I have any other questions  .
|
|
|
|
Eli Delventhal
|
 |
«
Reply #9 - Posted
2009-10-01 14:36:34 » |
|
Very cool. Great work.
|
|
|
|
Games published by our own members! Check 'em out!
|
|
CommanderKeith
|
 |
«
Reply #10 - Posted
2009-10-01 14:59:02 » |
|
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
|
 |
«
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 
|
Hi, appreciate more people! Σ ♥ = ¾ Learn how to award medals... and work your way up the social rankings!
|
|
|
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?
|
|
|
|
Riven
|
 |
«
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!
|
|
|
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 
|
|
|
|
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  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
|
 |
«
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.
|
|
|
|
Riven
|
 |
«
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.  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!
|
|
|
kevglass
|
 |
«
Reply #18 - Posted
2009-10-01 19:34:32 » |
|
Or (b - a) ?
Kev
|
|
|
|
Riven
|
 |
«
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!
|
|
|
Eli Delventhal
|
 |
«
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.
|
|
|
|
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!  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
|
 |
«
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  .
|
|
|
|
InsaneShane63
Junior Newbie
|
 |
«
Reply #23 - Posted
2009-10-09 20:58:45 » |
|
Haha wow! That's really cool. Good job.
|
|
|
|
Eli Delventhal
|
 |
«
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. 
|
|
|
|
CommanderKeith
|
 |
«
Reply #25 - Posted
2009-10-10 14:23:59 » |
|
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
|
 |
«
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.
|
|
|
|
h3ckboy
|
 |
«
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.
|
|
|
|
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 
|
|
|
|
h3ckboy
|
 |
«
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 
|
|
|
|
|