StraightEdge - 2D path finding and lighting

Shared Code
#1

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

#2

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

#3

Cool! Is there code available?

#4

Looks very nice.

Samples: https://code.google.com/p/straightedge/w/list
Source: https://code.google.com/p/straightedge/source/checkout

#5

Wow, thanks. ::slight_smile: Is there code available?

#6

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

#7

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 :stuck_out_tongue: so the downloads is the only place to get it.

#8

Hey is the source code available?

:stuck_out_tongue:

#9

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!

#10

Hahaha I was joking. I found it.

#11

thats really cool :).

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

#12

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

Lol, I should be less gullible at this age :slight_smile:

#13

one of the “bad guys”, like hte people who shoot you :stuck_out_tongue:

#14

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

#15

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

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

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

#16

I dunno why but i keep thinking of ‘Paradroid’ while playing around with your demo.
:wink:

#17

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

#18

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

#19

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

Thanks for the feedback guys :slight_smile:

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.