LÖVE

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 :
Hope this helps.

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

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

This works great Thanks!

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!

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.

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.

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

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

Hi

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