Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

Showcase your libraries, tools and other projects that help your fellow love users.
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

Post by Roland_Yonaba »

rokit boy wrote:hey i have a problem
in game.lua

Code: Select all

gr = grid(map)
finder = pathfinder('JPS', gr, 0) 
i get an error saying it needs a grid object when initializing finder. so "gr" isn't a grid object for some reason.
help?
Hi,

You might be using the latest 1.8.1 version. As I said in the relevant post, and also in the Readme, the grid object must come first.
This is due to a little change I pushed since the previous version, as it was making more sense.
So the correct syntax would be :

Code: Select all

gr = grid(map)
finder = pathfinder(gr, 'JPS', 0) 
Hope this helps.
User avatar
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

Re: Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

Post by Ragzouken »

Hey, thanks again for this; it's really nice to have a simple and fast pathing thing to drop in.

I'm wondering if you can provide any input to a problem I'm trying to solve - I want to try and smooth the path afterwards. One way of looking at it is that I want to allow any kind of movement between nodes that isn't blocked by a wall, rather than only allowing the eight compass directions. Not sure the best way to achieve this, if there even is a good way to solve it.

My current thought is look at sets of three consecutive points and see if the ends have line of sight to each other, but I'm not sure this would give great results every time and I probably need a strategy to subdivide straight paths (e.g in the image below you can see it wouldn't work for the top three points because they don't have line of sight). I thought you might have useful input since you seem to know a bit about pathfinding problems!

Here's what I'm currently looking at - ideally I'd want to turn that path into an approximation of the actual shortest path if there were no grid.
sound.png
sound.png (15.11 KiB) Viewed 4594 times
edit: I guess I should make it clear that my geometry doesn't lend itself well to anything but ray/line/point checks for collision
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

Post by Roland_Yonaba »

Let us try something.
Download the latest development version of Jumper (direct link to .zip), try ThetAStar and let me know how it works for you :)

Code: Select all

local finder = Pathfinder(grid, 'THETASTAR',walkable)
User avatar
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

Re: Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

Post by Ragzouken »

This works great :D Thanks!
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

Post by Roland_Yonaba »

Awesome. Really glad it worked.
Actually it has some minor flaws, when used with grids with tile based movements (yours is vertex-based), but i recently pinpointed the problem, i just need to replace the lineOfSight algorithm with a supercover bresenham based line marching algorithm.
Also, i might replace ThetAstar with a cheaper any-angle pathfinding algorithm, named Lazy ThetAstar, which seems better (I still have to make some tests before).
All those features will be merged in the next release! :)
User avatar
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

Re: Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

Post by Ragzouken »

002.png
002.png (16.6 KiB) Viewed 4526 times
all in all pretty good :) you can see the top path sadly has a kink in it, but it's quite a lot better than what I was doing before.
User avatar
micha
Inner party member
Posts: 1083
Joined: Wed Sep 26, 2012 5:13 pm

Re: Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

Post by micha »

Ragzouken wrote:you can see the top path sadly has a kink in it, but it's quite a lot better than what I was doing before.
The kink is there, because at the corner, there is not grid points. The kink-path seems to be the shortest possible one on the grid.

There are algorithms for finding the true shortest path in a 2d area of polygons:
First remove the underlying grid. For the shortest path, all the "internal" grid nodes are not needed. Instead you only need all nodes at wall corners (assuming the player has a radius of zero). For round obstacles you would have to discretize them using polygons.
The start and end point of the path are not in this set of nodes, so add these two, too.

Next construct a graph out of these points by adding edges: For each pair of nodes, check if the two points can be connects by a straight line without hitting an obstacle (ray casting), if so, add an edge between the two nodes. This graph is called "visibility graph", I believe.

Then do path finding on this graph.
User avatar
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

Re: Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

Post by Ragzouken »

oh yeah, you are right about the corner thing

the reason I'm using jumper rather than polygon pathfinding is that I haven't really been able to work out how to derive the underlying polygons from the map data - the collision is done by ray intersection checks on 2d constructed solid geometry i.e union/difference/intersection of shapes, which as I understand it is a pain in the ass to make polygons from
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

Post by Roland_Yonaba »

The Great Micha is definitely right. Although as of now, Jumper just features grid based maps.
But I am working on it. Slowly, but I am definitely having some progress. :)

Ragzouken, great work so far. If you do not want the path to squeeze around the circle shape, you can tag its surrounding nodes as unwalkable in the collision map... :)
User avatar
Rishavs
Party member
Posts: 103
Joined: Sat Oct 17, 2009 5:29 am
Contact:

Re: Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

Post by Rishavs »

Hi

does anyone have a simple example of Jumper working with STI?
Post Reply

Who is online

Users browsing this forum: No registered users and 55 guests