Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (481)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (548)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  StraightEdge - 2D path finding and lighting  (Read 17502 times)
0 Members and 1 Guest are viewing this topic.
Offline CommanderKeith
« Posted 2010-12-03 01:57:19 »

Hi,

I made a google code project for 2D path-finding and lighting, StraightEdge.

Here's the web start demo (left click or WASD/arrow keys to move, right click to shoot, N to change map, V to change view)

I tried to make the code and project more user-friendly. Thanks to Riven for his tips on that.


Note that the demos all render using Java2D which is the bottleneck in terms of performance.
Also, Java2D has no way of doing 'soft-clipping', that's why you see jaggies in the above image. When rendered using LWJGL the demos run faster and look smoother since they have full anti-aliasing.

Comments and criticisms welcome Smiley

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #1 - Posted 2010-12-03 22:46:03 »

Woooooooooo!

I'm totally gonna use this in something. I've been meaning to use your pathfinding code for a long time and now I have an excuse. i'm sure I'll have criticism/comments when I actually try it out. Smiley

See my work:
OTC Software
Offline Nate

JGO Kernel


Medals: 145
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #2 - Posted 2010-12-04 09:51:46 »

Cool! Is there code available?

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline zammbi

JGO Coder


Medals: 4



« Reply #3 - Posted 2010-12-04 10:01:11 »

Looks very nice.

Cool! Is there code available?
Samples: https://code.google.com/p/straightedge/w/list
Source: https://code.google.com/p/straightedge/source/checkout

Current project - Rename and Sort
Offline Nate

JGO Kernel


Medals: 145
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #4 - Posted 2010-12-04 21:19:42 »

Wow, thanks. Roll Eyes Is there code available?

Online Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #5 - Posted 2010-12-04 22:28:21 »

Oh come on, go to the [downloads] tab and grab the jar prepended with "src_"

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline CommanderKeith
« Reply #6 - Posted 2010-12-04 23:02:40 »

Woooooooooo!

I'm totally gonna use this in something. I've been meaning to use your pathfinding code for a long time and now I have an excuse. i'm sure I'll have criticism/comments when I actually try it out. Smiley

Cool, yeah the path finding is probably more useful. Something that's interesting is that it can be used to do key push left right up down movement and mouse click movement which suits an rpg.

Sorry for the confusion with the source code... I can't upload the source thru subversion because my work blocks that for some reason  Tongue so the downloads is the only place to get it.

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #7 - Posted 2010-12-06 16:06:46 »

Hey is the source code available?

Tongue

See my work:
OTC Software
Offline CommanderKeith
« Reply #8 - Posted 2010-12-06 21:12:25 »

See downloads... Looks like i'll have to find a way to upload it thru subversion, everyone is so used to getting it that way!

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #9 - Posted 2010-12-06 21:55:03 »

See downloads... Looks like i'll have to find a way to upload it thru subversion, everyone is so used to getting it that way!
Hahaha I was joking. I found it.

See my work:
OTC Software
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline h3ckboy

JGO Coder


Medals: 5



« Reply #10 - Posted 2010-12-07 06:29:02 »

thats really cool Smiley.

but forgive me if Im wrong, didnt u already make one of these int he shared cod?

oh, and btw, for some reason a guy dissapeared after a while, and never came back Tongue
Offline CommanderKeith
« Reply #11 - Posted 2010-12-07 09:50:43 »

thats really cool Smiley.

but forgive me if Im wrong, didnt u already make one of these int he share cod?

oh, and btw, for some reason a guy dissapeared after a while, and never came back Tongue

Thanks heckboy, yes its the same thing, but with a few improvements to the code, and in project form with wiki pages and little easy demo examples. Hopefully it's more accessible and easy to use now. Who is the guy you are talking about?!

Hahaha I was joking. I found it.

Lol, I should be less gullible at this age Smiley

Offline h3ckboy

JGO Coder


Medals: 5



« Reply #12 - Posted 2010-12-14 20:31:40 »

Thanks heckboy, yes its the same thing, but with a few improvements to the code, and in project form with wiki pages and little easy demo examples. Hopefully it's more accessible and easy to use now. Who is the guy you are talking about?!

one of the "bad guys", like hte people who shoot you Tongue
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #13 - Posted 2011-01-13 14:29:18 »

This is awesome! Cheesy Looking forward to working with it, once I get an idea where this can be used  Tongue

Offline CommanderKeith
« Reply #14 - Posted 2011-01-14 04:00:22 »

Cool, I'm glad you like it. I've had very little feedback from non-JGO people, yet seems like there's about 2 downloads of the source per day. Maybe the downloads are all just google's indexing bot lol. I linked to the project on wikipedia's path finding and A* pages and I'm getting a lot of traffic from there according to google analytics.

I uploaded a new version which has an improved A* pathfinding algorithm thanks to Nate's suggestion of storing the open/closed/unprocessed state of the nodes in the nodes themselves instead of keeping an open and closed list/set and doing contains(obj) all the time. I don't know why I didn't think of that! I must have got carried away with the idea of open and closed lists like they had in the A* tutorials I read Smiley

Also the linking of nodes is much quicker. I thought of a smarter way of doing it. When connecting nodes I used to just connect all nodes that were reachable. By reachable, I mean that a line from one node to another is not intersected by any obstacles.

This led to lots and lots of connections. The thing is that not all of these connections are actually useful for finding a path between obstacles.

I found an efficient way to determine if a connection is useful or not. By ignoring useless connections, the nav-mesh is a lot smaller and faster to calculate, and the path finding algorithm works more quickly because there are less connections to process. On the demo maps, there was a decrease of between 80 to 95% in the number of connections  Cool

To see the impact, look at these before and after screenshots:

Before, with 26,444 node connections



After, with only 1,735 node connections



BTW to see the demos run with the new innovations, just click the web start or applet demo and press 'C' to toggle wire frame view and connection-rendering.

Cheers,
Keith

Offline SwampChicken
« Reply #15 - Posted 2011-01-18 01:35:19 »

I dunno why but i keep thinking of 'Paradroid' while playing around with your demo.
 Wink
Offline CommanderKeith
« Reply #16 - Posted 2011-01-18 02:14:02 »

Ah yeah you're right!

Btw I just figured out how to use batik and xml (Argh! I hate xml) to make polygons out of svg documents created in inkscape, yay! Should be easier to make maps now.

It's funny how much progress I made when JGO was offline lol

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #17 - Posted 2011-01-18 18:32:24 »

This remains awesome. Kudos to getting such a big speed improvement out of it.

See my work:
OTC Software
Offline jfrazierjr

Junior Newbie





« Reply #18 - Posted 2011-01-28 17:10:57 »

Hey Keith, great stuff.   We have talked a bit before in the past, not sure if you remember or not.  We are thinking about possibly using your lib for MapTool version 1.4 which we hope to start coding fairly soon.   I have a few questions for you that might make our lives simpler:

  • Have you tried making the path finding algorithm to utilize a grid(ie, the movement conforms to the grid center) to see how hard/easy it would be the implement.  This is quite a standard feature in many RPG's.  One thing to consider is that some creatures need to fill 2x2, 3x3, etc grid squares
  • Along with the above, do you think it might be possible to have the LOS to be calculated from each of the 4 corners and merged
  • Have you by any chance tried to pull any of the code into an OSGi bundle?   We have someone looking into that at the moment as a proof of concept, but was wondering if you might have also checked into this at some point.
Offline CommanderKeith
« Reply #19 - Posted 2011-01-29 12:59:43 »

Thanks for the feedback guys  Smiley

Hi jfrazierjr, yes I remember your project, it's well advanced. That's great how you are thinking of building some of this code into it.

About the grid path finding, that's actually what I am trying to avoid with this project. The idea is to use polygons only, not tiles. There are plenty of other path finding projects using grids/tiles/cells such as the one posted by appel in this forum section.

Doing line of sight out of each corner of the tile should be ok, just a matter of making it look good. do you want the line of sight for the unit to do ai or is it for the graphical effect?

I don't know what an osgi bundle is, I'll look it up and get back to you.

Offline jfrazierjr

Junior Newbie





« Reply #20 - Posted 2011-02-01 14:06:06 »

About the grid path finding, that's actually what I am trying to avoid with this project. The idea is to use polygons only, not tiles. There are plenty of other path finding projects using grids/tiles/cells such as the one posted by appel in this forum section.
  Well, we already have implementations of path finding for gridless(as yours would be), square, and hex(both directions, vertical/horizontal), but would have to make some changes to the rendering and path finding code to accommodate.   It does not help that we allow variable unit sizes, eg: one person may use 50px squares, another may use 100px squares, and another may use 25px hexes.   We also have to keep track of "units" so that each cell has a specific unit value.  That way, if one game system counts things in squares, the units would be one such that Range: 5  means 5 squares.   Likewise, a game system where each cell is 5 feet, the same 5 squares turns into 25 feet as a whole for measurements.

Doing line of sight out of each corner of the tile should be ok, just a matter of making it look good. do you want the line of sight for the unit to do ai or is it for the graphical effect?
Not 100% sure I understand the full meaning, but it would likely be used for both ai and UI.   One of the things we currently do is have a Fog or War effect and "remember" where the "character"(ie, the source of the Line of Sight) has previously been before.  This means that if you put up walls the "character" cannot see the entire board until his vision/light sources(depending on day/night mode) have revealed an area similar to most war games such as C&C, Warcraft, Starcraft, etc.    Also, we currently have a feature which prevents movement through (well, actually into would be more precise terminology) hard Fog of War which would of course require an ai component in addition to the UI.  Our hopes in our next version would be to add a movement blocking (which could be independent of the LOS blocking in some cases) feature, so we will likely duplicate the lines created for sight blocking and then perhaps add additional lines for movement blocking.  Think of things such as small windows, or elevation(cliffs, at the top of) that might not block line of sight, but will block movement.




I don't know what an osgi bundle is, I'll look it up and get back to you.
  it's a standardized way to organize code into functional units to create a "plug-in" style architecture.  Most likely your lib probably would be compatible as a whole as long as it returns some interface defined objects where the implementation could be swapped out.   The Eclipse platform runs on top of OSGi which is why plug-ins are possible.


Offline CommanderKeith
« Reply #21 - Posted 2011-02-02 08:02:23 »

Well, we already have implementations of path finding for gridless(as yours would be), square, and hex(both directions, vertical/horizontal), but would have to make some changes to the rendering and path finding code to accommodate.   It does not help that we allow variable unit sizes, eg: one person may use 50px squares, another may use 100px squares, and another may use 25px hexes.   We also have to keep track of "units" so that each cell has a specific unit value.  That way, if one game system counts things in squares, the units would be one such that Range: 5  means 5 squares.   Likewise, a game system where each cell is 5 feet, the same 5 squares turns into 25 feet as a whole for measurements.
Gee sounds like a lot of messing around for you trying to support all of those grids..

Quote
Not 100% sure I understand the full meaning, but it would likely be used for both ai and UI.   One of the things we currently do is have a Fog or War effect and "remember" where the "character"(ie, the source of the Line of Sight) has previously been before.  This means that if you put up walls the "character" cannot see the entire board until his vision/light sources(depending on day/night mode) have revealed an area similar to most war games such as C&C, Warcraft, Starcraft, etc.    Also, we currently have a feature which prevents movement through (well, actually into would be more precise terminology) hard Fog of War which would of course require an ai component in addition to the UI.  Our hopes in our next version would be to add a movement blocking (which could be independent of the LOS blocking in some cases) feature, so we will likely duplicate the lines created for sight blocking and then perhaps add additional lines for movement blocking.  Think of things such as small windows, or elevation(cliffs, at the top of) that might not block line of sight, but will block movement.
Cool, yeah fog of war is something that I messed around with a bit but couldn't find an elegant polygon-only solution. The problem is the explosion in the number of points when I tried to break off little pieces from the fog polygon. I think tile-based fog of war is the way to go. You can see my different (failed) attempts in the packages straightedge.test.experimental and straightedge.test.experimental.map  Undecided I'll eventually make a tile-based solution that fits with the rest of the API but it's not a big concern for me now and you probably have your own implementation of fog in your existing code i guess?

Quote
it's a standardized way to organize code into functional units to create a "plug-in" style architecture.  Most likely your lib probably would be compatible as a whole as long as it returns some interface defined objects where the implementation could be swapped out.   The Eclipse platform runs on top of OSGi which is why plug-ins are possible.
Hmm well there are some interfaces but for the low-level stuff (which is most of the API) i deliberately tried to avoid interfaces since they make the code harder to follow and look bloated for the larger number of files. I mean what's the point of having a Point interface and then a sub-class PointImpl as well. Easier just to have a Point class. And they slow performance (last time I checked, but according to [http://stackoverflow.com/questions/973504/does-java-optimize-method-calls-via-an-interface-which-has-a-single-implementor-m this link] maybe that's no true anymore). Would you prefer more interfaces so that you can swap bits of my code for your existing code? I would just replace the code manually to keep it simple rather than have loads of interfaces flying around. But that's just my personal preference and I'm open to being convinced otherwise!  Smiley

Offline jfrazierjr

Junior Newbie





« Reply #22 - Posted 2011-02-02 15:01:45 »

Well, we already have implementations of path finding for gridless(as yours would be), square, and hex(both directions, vertical/horizontal), but would have to make some changes to the rendering and path finding code to accommodate.   It does not help that we allow variable unit sizes, eg: one person may use 50px squares, another may use 100px squares, and another may use 25px hexes.   We also have to keep track of "units" so that each cell has a specific unit value.  That way, if one game system counts things in squares, the units would be one such that Range: 5  means 5 squares.   Likewise, a game system where each cell is 5 feet, the same 5 squares turns into 25 feet as a whole for measurements.
Gee sounds like a lot of messing around for you trying to support all of those grids..

Yes, it is.  But it's the price we pay to support a free program for a hobby that has many different styles of Role Playing Games in a "generic" manner.    The rendering code is fairly convoluted(lot's of if(){} statements to accommodate the various play styles we currently support.    


Cool, yeah fog of war is something that I messed around with a bit but couldn't find an elegant polygon-only solution. The problem is the explosion in the number of points when I tried to break off little pieces from the fog polygon. I think tile-based fog of war is the way to go. You can see my different (failed) attempts in the packages straightedge.test.experimental and straightedge.test.experimental.map  Undecided I'll eventually make a tile-based solution that fits with the rest of the API but it's not a big concern for me now and you probably have your own implementation of fog in your existing code i guess?
 Yes.  The process goes something like this in the rendering pipeline:

Put down base layer
Put down an "object" layer(these are things such as tables, chairs, trees,etc that the player may not interact with directly.  
Put down drawings(simple shapes using graphics.drawX)
Put down labels (simple text using graphics.drawString)
Put down player character (and NPC's) tokens
Get the character tokens vision limit
Get the light sources on the map and do an intersect with the vision area
Determine Vision blocking shape (area Object)
Draw FOW(ie, cover with black)
Cut out cached previously revealed area(Area object) and cover with partial transparency to simulate "soft FOW"
Cut out current visible area (ie, line of sight, Area Object).

Also of note, many of the previous layers also do some clipping so that we don't try to draw strings, objects, etc in places where hard FOW won't be seen.  For example, depending on the server startup options, we optionally render the NPC's tokens in Soft FOW, it just depends on the host's start up preferences.   Yea, it's a ton of work and lot's of stuff to keep up with.  I "think" I got that ordering right above as I am doing it off the top of my head.  

Quote
it's a standardized way to organize code into functional units to create a "plug-in" style architecture.  Most likely your lib probably would be compatible as a whole as long as it returns some interface defined objects where the implementation could be swapped out.   The Eclipse platform runs on top of OSGi which is why plug-ins are possible.
Hmm well there are some interfaces but for the low-level stuff (which is most of the API) i deliberately tried to avoid interfaces since they make the code harder to follow and look bloated for the larger number of files. I mean what's the point of having a Point interface and then a sub-class PointImpl as well. Easier just to have a Point class. And they slow performance (last time I checked, but according to [http://stackoverflow.com/questions/973504/does-java-optimize-method-calls-via-an-interface-which-has-a-single-implementor-m this link] maybe that's no true anymore). Would you prefer more interfaces so that you can swap bits of my code for your existing code? I would just replace the code manually to keep it simple rather than have loads of interfaces flying around. But that's just my personal preference and I'm open to being convinced otherwise!  Smiley
 

Well, we may (or may not) end up having to make changes before for we implement the SE code.  The goal of using OSGi, is to allow end users (who know java) to follow the API's we create and write up their own additions(similar to an eclipse plugin).    For example, there is a concept currently in our software for macros and macro groups which individual users can edit to place their one custom "script" code.  These are used to do such things as "click this button to roll 2 10 sided dice and print the results to the chat window".   However, currently, the macro and macro group code directly generates buttons and option groups which ties the implementation directly to Swing JButton and JOptionGroup objects(ie, this is what the current macro building code does).  However, what if a user wished to implement this in the UI as a JTree instead.  Currently, they would have to change the macro and macrogroup classes.  However, using an OSGi model, we uncouple the "model" (macro and macro group) from the "view"(some type of UI) and the UI implementation can be much easily switched out and the UI coder does not have to know anything about how the macro's are built or work.  

I seem to recall that your top level classes implements Shape?  If that's the case, that may very well be just fine for what we need it for without any changes, again, I have no idea since I have not really looked into it(someone else is on that part of the code.)  








Offline CommanderKeith
« Reply #23 - Posted 2011-02-03 01:14:45 »

Very nice way of doing it, thanks for the explanation.

I will look into OSGI some more, sounds useful. I guess that the straightedge code will be the model only so there shouldn't be any issues.

I seem to recall that your top level classes implements Shape?  If that's the case, that may very well be just fine for what we need it for without any changes, again, I have no idea since I have not really looked into it(someone else is on that part of the code.)   

Cool, yeah KPolygon implements Shape and that's the output of the vision code. Phew!

Btw I haven't used the java.awt.geom.Area much at all, but you may find that [http://tsusiatsoftware.net/jts/main.html JTS] does a better job of calculating intersections, unions etc. I've found it to be very fast and reliable and with great support.

Let me know if there's any edits you or the other devs would like me to make to the SE code.

Offline dime26

Senior Member


Medals: 2
Projects: 3
Exp: 5 years


Should traffic wardens be armed?


« Reply #24 - Posted 2013-04-10 10:50:41 »

Can I use this with LibGDX?
Offline dermetfan

Senior Member


Medals: 11



« Reply #25 - Posted 2013-07-19 17:51:47 »

Really nice! Just started to learn how to use this and it seems simple enough to learn. I bet it will be worth it, first test runs perfectly.

Offline lcass
« Reply #26 - Posted 2013-08-20 11:51:37 »

Is there a tutorial anywhere on how to use the lighting it would be extremely useful.
Offline CommanderKeith
« Reply #27 - Posted 2013-08-24 00:41:31 »

Hi Icass,
The demo code which is included in the zipped source file shows some different methods of drawing the lights, my preferred method is to make an image with a nice alpha gradient that is fully opaque at the light source and fully alpha at the border of an ellipse which is encompassed by the image. You can see the code for that in straightedge.test.demo.View and Player.
Cheers,
Keith

Offline lcass
« Reply #28 - Posted 2013-09-19 22:16:50 »

So how does the light work is it raycasting or do you overlay then figure out what the shape will be for each object?
Pages: [1]
  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.

atombrot (27 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (22 views)
2014-08-16 06:12:11

Rayexar (61 views)
2014-08-11 02:49:23

BurntPizza (39 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (37 views)
2014-08-06 19:49:38

BurntPizza (67 views)
2014-08-03 02:57:17
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!