Awesome [import]uid: 8271 topic_id: 30317 reply_id: 139588[/import]
Hi all,
I am releasing the version 1.7.0 of Jumper.
Documentation is available online.
In this new version, I have been focusing on ameliorating the internal code: split the search algorithms from the pathfinder class, and then provide a common API for each of these search algorithms.
The new version have some new features, and runs even faster, thanks to a little optimization made in the binary heaps module.
So far, Jumper offers you Finders, which are just different search algorithms. Astar and Jump Point Search are implemented, so far, but this is likely to grow next.
When a pathfinder object is created, it uses by default Jump Point Search algorithm. As of this version, you can switch to pure A-star if desired.
With both finders (JPS and A-star), a search can be made in “ORTHOGONAL” mode (that is, only 4-directions allowed) or in “DIAGONAL” mode (8-directions allowed). You can also use any of the built-in distance heuristics (Manhattan, Euclidian, Diagonal and Card-Intercardinal distance), or even cook your own custom heuristic and pass it to the finder.
New methods have been added to the pathfinder class, mostly for a convenient usage of the new fatures.
Pathfinder:setFinder
Pathfinder:getFinder
Pathfinder:getFinders
Pathfinder:getHeuristics
Pathfinder:getModes The autoFill feature has been removed. So for now on, to interpolate a path returned by Pathfinder:getPath, you will need to call explictely Pathfinder:fill.
Another new feature is the Pathfinder:filter. This utility function does the opposite of Pathfinder:fill. Being given a path, it detects all nodes that can be deducted (interpolated) from a straight move, and prunes them. It leaves a “compressed” or “filtered” path. See handling paths for more details about this feature.
For a detailed list of changes, see the changelog.
Feel free to check this out on Github!
Thanks for reading. [import]uid: 142361 topic_id: 30317 reply_id: 140098[/import]
Hi!
I was last playing with A* a couple years back or so (and remember a few of the snags you mention above…), and I ran across
Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments
while I was at it.* Have you looked into anything like that? I ended up distracted by other shiny things and never implementing it, but it seemed interesting.
* - The author has a few papers; I don’t recall if this was his most recent. [import]uid: 27791 topic_id: 30317 reply_id: 140104[/import]
Hi all,
Jumper reaches version 1.6.3.
Basically, they were not much changes, but just some new features added, as some people have requested.
First, Jumper now supports string maps. The collision map passed upon initialization of the library no longer have to be a 2D table. Instead, you can pass a string, that Jumper will parse in rows (using line-break chars - ‘\n’ and ‘\r’ as delimiters).
Nodes walkability rules were also enhanced, for convenience. You might want to have multiples values for walkable tiles on a collision map, for instance. As of v1.6.3, you can pass a function that Jumper will call to evaluate whether or not a tile is walkable.
[code]
local stringMap = [[
xxxxx#xxxxx
xxxx#*#xxxx
xxx# . #xxx
. .
. . .
#*. .$. .*#
. . .
. .
xxx# . #xxx
xxxx#*#xxxx
xxxxx#xxxxx
]]
– We want chars ‘#’, ‘.’ and ‘*’ to be walkable tiles.
local function isWalkable(value)
return value:match(’[#.*]’)
end
local Jumper = require (“Jumper”)
local pathfinder = Jumper(stringMap, isWalkable)[/code]
A path iterator function have been added, too:
local path, len = pathfinder:getPath(startx, starty, goalx, goaly)
if path then
for x,y in path:iter() do
print('Cell: '..x..' - '..y)
end
end
The Grid object API, adding some functions, mostly iterators too:
Grid:iter()
Grid:each(f,...)
Grid:eachRange(lx,ly,ex,ey,f,...)
Grid:imap(f,...)
Grid:imapRange(lx,ly,ex,ey,f,...)
Some little code improvements were made, too.
There also a complete HTML documentation, available on the git repository. It fully describes the API, and gives a brief description of the purpose of each of Jumper’s modules. This documentation was generated using the excellent LDoc.
See the changelog for more details. The benchmark for Jumper was also updated with the latest version of the library, feel free to try! [import]uid: 142361 topic_id: 30317 reply_id: 139587[/import]
Awesome [import]uid: 8271 topic_id: 30317 reply_id: 139588[/import]
Funny you mention it. I already came across that paper, and I’ll be looking at it, soon, hopefully.
Anyway, thanks. [import]uid: 142361 topic_id: 30317 reply_id: 140215[/import]
I’ve been actively working on this project the past hours, and i came up with a new iteration of Jumper.
Here’s the 1.8.0 release. The detailed changelog can be found here.
Some llittle changes were brought to the interface. Mostly because I wasn’t satisfied with the relationship that was existing between the Grid and the pathfinder object, that is encapsulating the grid within the pathfinder object. That was a bad design choice, just because it was preventing a user from easily having a map with multiple terrain types.
So, as of this new release, Jumper offers to the use two main classes, at the top level : a Grid class, and a Pathfinder class.
local Grid = require('jumper.grid')
local Pathfinder = require('jumper.pathfinder')
To create the grid, it is still fairly simple, just pass a collision map to the Grid class. Then, pass the grid object to the Pathfinder.
The Pathfinder class takes three arg upon instantiation: the finder name, referring to the search algorithm to be used, the grid and the value/function for walkable tiles.
local map = {
{1,1,1,1,1},
{1,0,0,0,1},
{1,0,0,0,1},
{1,1,1,1,1},
}
local grid = Grid(map)
local myFinder = Pathfinder('JPS', grid, 0)
What makes that layout very interesting is that you can keep strick to a unique grid, and then simulate multiple terrain types. In the example above, let’s consider 1 represents a specific terrain type, like ‘land’, and 0 stands for ‘water’. That way, one can design a finder that will look for path on ‘lands’, and another that will search for paths on ‘water’. We can even have a pathfinder for both (land and water, as walkable can also be a function).
local finderLand = Pathfinder('ASTAR', grid, 1)
local finderWater = Pathfinder('ASTAR', grid, 0)
local finderAmphibia = Pathfinder('ASTAR', grid, function(v) return v == 0 or v==1 end)
Added to that, I have included some new search algorithms. Well, they may all not be fast, by essence, by the duty of a library is to offer a choice, not to limit. So far, Jumper implements five well-know search algorithms: A-star, Dijkstra, Breadth first Search, Depth first search and Jump Point Search (the fastest one actually).
The Pathfinder class and the Grid class have also been extended with some new methods, mostly for a convenient use. You can check out the online documentation for more details.
Last point, some methods such as Pathfinder:filter() and Pathfinder:fill() were removed from the Pathfinder class. For now on, using Pathfinder:getPath returns a path, which would be an instance or an internal class named Path. To alter the returned path (interpolate, or compress it), you will just have to call these methods from the returned object:
[code]local path = myFinder:getPath(startX, startY, endX, endY)
if path then
path:fill() – or path:filter()
– iterating along the path
for node, count in path:iter() do
– etc
end
end[/code]
Documentation is available online, and source. Check out the Readme, as it provides all informations you need to easily get started.
Source : Github
Documentation : Jumper
Thanks reading. [import]uid: 142361 topic_id: 30317 reply_id: 140447[/import]
Hi all,
I am releasing the version 1.7.0 of Jumper.
Documentation is available online.
In this new version, I have been focusing on ameliorating the internal code: split the search algorithms from the pathfinder class, and then provide a common API for each of these search algorithms.
The new version have some new features, and runs even faster, thanks to a little optimization made in the binary heaps module.
So far, Jumper offers you Finders, which are just different search algorithms. Astar and Jump Point Search are implemented, so far, but this is likely to grow next.
When a pathfinder object is created, it uses by default Jump Point Search algorithm. As of this version, you can switch to pure A-star if desired.
With both finders (JPS and A-star), a search can be made in “ORTHOGONAL” mode (that is, only 4-directions allowed) or in “DIAGONAL” mode (8-directions allowed). You can also use any of the built-in distance heuristics (Manhattan, Euclidian, Diagonal and Card-Intercardinal distance), or even cook your own custom heuristic and pass it to the finder.
New methods have been added to the pathfinder class, mostly for a convenient usage of the new fatures.
Pathfinder:setFinder
Pathfinder:getFinder
Pathfinder:getFinders
Pathfinder:getHeuristics
Pathfinder:getModes The autoFill feature has been removed. So for now on, to interpolate a path returned by Pathfinder:getPath, you will need to call explictely Pathfinder:fill.
Another new feature is the Pathfinder:filter. This utility function does the opposite of Pathfinder:fill. Being given a path, it detects all nodes that can be deducted (interpolated) from a straight move, and prunes them. It leaves a “compressed” or “filtered” path. See handling paths for more details about this feature.
For a detailed list of changes, see the changelog.
Feel free to check this out on Github!
Thanks for reading. [import]uid: 142361 topic_id: 30317 reply_id: 140098[/import]
Hi!
I was last playing with A* a couple years back or so (and remember a few of the snags you mention above…), and I ran across
Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments
while I was at it.* Have you looked into anything like that? I ended up distracted by other shiny things and never implementing it, but it seemed interesting.
* - The author has a few papers; I don’t recall if this was his most recent. [import]uid: 27791 topic_id: 30317 reply_id: 140104[/import]
Funny you mention it. I already came across that paper, and I’ll be looking at it, soon, hopefully.
Anyway, thanks. [import]uid: 142361 topic_id: 30317 reply_id: 140215[/import]
I’ve been actively working on this project the past hours, and i came up with a new iteration of Jumper.
Here’s the 1.8.0 release. The detailed changelog can be found here.
Some llittle changes were brought to the interface. Mostly because I wasn’t satisfied with the relationship that was existing between the Grid and the pathfinder object, that is encapsulating the grid within the pathfinder object. That was a bad design choice, just because it was preventing a user from easily having a map with multiple terrain types.
So, as of this new release, Jumper offers to the use two main classes, at the top level : a Grid class, and a Pathfinder class.
local Grid = require('jumper.grid')
local Pathfinder = require('jumper.pathfinder')
To create the grid, it is still fairly simple, just pass a collision map to the Grid class. Then, pass the grid object to the Pathfinder.
The Pathfinder class takes three arg upon instantiation: the finder name, referring to the search algorithm to be used, the grid and the value/function for walkable tiles.
local map = {
{1,1,1,1,1},
{1,0,0,0,1},
{1,0,0,0,1},
{1,1,1,1,1},
}
local grid = Grid(map)
local myFinder = Pathfinder('JPS', grid, 0)
What makes that layout very interesting is that you can keep strick to a unique grid, and then simulate multiple terrain types. In the example above, let’s consider 1 represents a specific terrain type, like ‘land’, and 0 stands for ‘water’. That way, one can design a finder that will look for path on ‘lands’, and another that will search for paths on ‘water’. We can even have a pathfinder for both (land and water, as walkable can also be a function).
local finderLand = Pathfinder('ASTAR', grid, 1)
local finderWater = Pathfinder('ASTAR', grid, 0)
local finderAmphibia = Pathfinder('ASTAR', grid, function(v) return v == 0 or v==1 end)
Added to that, I have included some new search algorithms. Well, they may all not be fast, by essence, by the duty of a library is to offer a choice, not to limit. So far, Jumper implements five well-know search algorithms: A-star, Dijkstra, Breadth first Search, Depth first search and Jump Point Search (the fastest one actually).
The Pathfinder class and the Grid class have also been extended with some new methods, mostly for a convenient use. You can check out the online documentation for more details.
Last point, some methods such as Pathfinder:filter() and Pathfinder:fill() were removed from the Pathfinder class. For now on, using Pathfinder:getPath returns a path, which would be an instance or an internal class named Path. To alter the returned path (interpolate, or compress it), you will just have to call these methods from the returned object:
[code]local path = myFinder:getPath(startX, startY, endX, endY)
if path then
path:fill() – or path:filter()
– iterating along the path
for node, count in path:iter() do
– etc
end
end[/code]
Documentation is available online, and source. Check out the Readme, as it provides all informations you need to easily get started.
Source : Github
Documentation : Jumper
Thanks reading. [import]uid: 142361 topic_id: 30317 reply_id: 140447[/import]
Hi all,
Here is a new iteration of Jumper: here.
This new release if totally backwards compatible with the latest one, except for only one minor change (for pure convience issues), related to the way one inits the pathfinder object.
See the related documentation: [
See the ](http://yonaba.github.com/Jumper/modules/jumper.pathfinder.html#pathfinder:new>pathfinder
For%20now%20on,%20to%20init%20a%20new%20Pathfinder%20object,%20the%20%5Bi%5Dgrid%20object%20comes%20first%5B/i%5D.%20Then%20one%20specifies%20the%20finder%20algorithm%20to%20be%20used,%20and%20then%20the%20walkable%20value(s).
As%20a%20straightforward%20example:
%5Bcode%5Dlocal%20Grid%20=%20require(‘jumper.grid’)
local%20Pathfinder%20=%20require(‘jumper.pathfinder’)
local%20map%20=%20%7B
%20%20%7B1,1,1,1,1%7D,
%20%20%7B1,0,0,0,1%7D,
%20%20%7B1,0,0,0,1%7D,
%20%20%7B1,1,1,1,1%7D,
%7D
local%20grid%20=%20Grid(map)
local%20myFinder%20=%20Pathfinder(grid,%20’JPS’,0)%5B/code%5D
Added%20to%20that,%20some%20inner%20changes%20were%20brought%20to%20the%20code%20in%20order%20to%20fix%20some%20little%20odds%20that%20were%20causing%20the%20pathfinder%20to%20fail%20on%20specific%20situations.
Hopefully,%20all%20issues%20detected%20were%20solved,%20as%20of%20now.
A%20new%20feature%20have%20been%20added,%20that%20is%20the%20ability%20for%20the%20pathfinder%20to%20tunnel%20through%20walls.
That%20feature%20overrides%20the%20normal%20behaviour%20of%20the%20pathfinder,%20and%20would%20authorize%20it%20to%20tunnel%20through%20walls,%20heading%20diagonally%20towards%20them.
The%20screeshot%20below%20illustrates%20this%20feature:
<img%20src=)Github
Documentation :
Hi all,
Here is a new iteration of Jumper: here.
This new release if totally backwards compatible with the latest one, except for only one minor change (for pure convience issues), related to the way one inits the pathfinder object.
See the related documentation: [
See the ](http://yonaba.github.com/Jumper/modules/jumper.pathfinder.html#pathfinder:new>pathfinder
For%20now%20on,%20to%20init%20a%20new%20Pathfinder%20object,%20the%20%5Bi%5Dgrid%20object%20comes%20first%5B/i%5D.%20Then%20one%20specifies%20the%20finder%20algorithm%20to%20be%20used,%20and%20then%20the%20walkable%20value(s).
As%20a%20straightforward%20example:
%5Bcode%5Dlocal%20Grid%20=%20require(‘jumper.grid’)
local%20Pathfinder%20=%20require(‘jumper.pathfinder’)
local%20map%20=%20%7B
%20%20%7B1,1,1,1,1%7D,
%20%20%7B1,0,0,0,1%7D,
%20%20%7B1,0,0,0,1%7D,
%20%20%7B1,1,1,1,1%7D,
%7D
local%20grid%20=%20Grid(map)
local%20myFinder%20=%20Pathfinder(grid,%20’JPS’,0)%5B/code%5D
Added%20to%20that,%20some%20inner%20changes%20were%20brought%20to%20the%20code%20in%20order%20to%20fix%20some%20little%20odds%20that%20were%20causing%20the%20pathfinder%20to%20fail%20on%20specific%20situations.
Hopefully,%20all%20issues%20detected%20were%20solved,%20as%20of%20now.
A%20new%20feature%20have%20been%20added,%20that%20is%20the%20ability%20for%20the%20pathfinder%20to%20tunnel%20through%20walls.
That%20feature%20overrides%20the%20normal%20behaviour%20of%20the%20pathfinder,%20and%20would%20authorize%20it%20to%20tunnel%20through%20walls,%20heading%20diagonally%20towards%20them.
The%20screeshot%20below%20illustrates%20this%20feature:
<img%20src=)Github
Documentation :
Hi all,
Here is a new iteration of Jumper: here.
This new release if totally backwards compatible with the latest one, except for only one minor change (for pure convience issues), related to the way one inits the pathfinder object.
See the related documentation: [
See the ](http://yonaba.github.com/Jumper/modules/jumper.pathfinder.html#pathfinder:new>pathfinder
For%20now%20on,%20to%20init%20a%20new%20Pathfinder%20object,%20the%20%5Bi%5Dgrid%20object%20comes%20first%5B/i%5D.%20Then%20one%20specifies%20the%20finder%20algorithm%20to%20be%20used,%20and%20then%20the%20walkable%20value(s).
As%20a%20straightforward%20example:
%5Bcode%5Dlocal%20Grid%20=%20require(‘jumper.grid’)
local%20Pathfinder%20=%20require(‘jumper.pathfinder’)
local%20map%20=%20%7B
%20%20%7B1,1,1,1,1%7D,
%20%20%7B1,0,0,0,1%7D,
%20%20%7B1,0,0,0,1%7D,
%20%20%7B1,1,1,1,1%7D,
%7D
local%20grid%20=%20Grid(map)
local%20myFinder%20=%20Pathfinder(grid,%20’JPS’,0)%5B/code%5D
Added%20to%20that,%20some%20inner%20changes%20were%20brought%20to%20the%20code%20in%20order%20to%20fix%20some%20little%20odds%20that%20were%20causing%20the%20pathfinder%20to%20fail%20on%20specific%20situations.
Hopefully,%20all%20issues%20detected%20were%20solved,%20as%20of%20now.
A%20new%20feature%20have%20been%20added,%20that%20is%20the%20ability%20for%20the%20pathfinder%20to%20tunnel%20through%20walls.
That%20feature%20overrides%20the%20normal%20behaviour%20of%20the%20pathfinder,%20and%20would%20authorize%20it%20to%20tunnel%20through%20walls,%20heading%20diagonally%20towards%20them.
The%20screeshot%20below%20illustrates%20this%20feature:
<img%20src=)Github
Documentation :
Hi all,
Find here an unofficial version of Jumper with minor modifications for multi-agents pathfinding, that I wrote upon the request of a user.
It doesn’t aims to speed, but to return intelligent and realistic looking paths when moving a group of units, avoiding the “stacking” issue when units pathing at the same time have the same destination.
The Readme provides interesting details on how to use it.
Grab it on Github : branch - Node-weight [import]uid: 142361 topic_id: 30317 reply_id: 145396[/import]
Hi, Roland.
Another case of “I’ve seen and read this paper, but never tried to implement it”:
http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Publications_files/coop-path-AIWisdom.pdf
I don’t know how it compares to the node weight approach (needs to do another search first), but maybe it works as a fallback for the non-A* / Dijkstra algorithms? [import]uid: 27791 topic_id: 30317 reply_id: 145453[/import]
Hi StarCrunch,
Cooperative pathfinding is something i’ve already considered, many times. But it doesn’t really suits to me as it end up a bit tricky to implement and to get working right with different search algorithms (in other works, I did not succeeded).
Actually, there is an alternative method, but that goes out of a simple pathfinding library purposes, yet it works really fine. For a group of units, one just runs the pathfinding algorithm (in a clever way so that it won’t drop the framerate), and then use “steering behaviours”. Something I might definitely try someday.
And about ThetaStar, I succeded in implementing it, as it wasn’t that hard, and the papers gave some very clear explanations about that. There are some things left to fix yet, such as finding an efficient line of sight algorithm as the original one described in the article fails miserably in some cases.
Thanks for your feedback and ideas, though. [import]uid: 142361 topic_id: 30317 reply_id: 145479[/import]
Hi all,
Here is a new iteration of Jumper: here.
This new release if totally backwards compatible with the latest one, except for only one minor change (for pure convience issues), related to the way one inits the pathfinder object.
See the related documentation: [
See the ](http://yonaba.github.com/Jumper/modules/jumper.pathfinder.html#pathfinder:new>pathfinder
For%20now%20on,%20to%20init%20a%20new%20Pathfinder%20object,%20the%20%5Bi%5Dgrid%20object%20comes%20first%5B/i%5D.%20Then%20one%20specifies%20the%20finder%20algorithm%20to%20be%20used,%20and%20then%20the%20walkable%20value(s).
As%20a%20straightforward%20example:
%5Bcode%5Dlocal%20Grid%20=%20require(‘jumper.grid’)
local%20Pathfinder%20=%20require(‘jumper.pathfinder’)
local%20map%20=%20%7B
%20%20%7B1,1,1,1,1%7D,
%20%20%7B1,0,0,0,1%7D,
%20%20%7B1,0,0,0,1%7D,
%20%20%7B1,1,1,1,1%7D,
%7D
local%20grid%20=%20Grid(map)
local%20myFinder%20=%20Pathfinder(grid,%20’JPS’,0)%5B/code%5D
Added%20to%20that,%20some%20inner%20changes%20were%20brought%20to%20the%20code%20in%20order%20to%20fix%20some%20little%20odds%20that%20were%20causing%20the%20pathfinder%20to%20fail%20on%20specific%20situations.
Hopefully,%20all%20issues%20detected%20were%20solved,%20as%20of%20now.
A%20new%20feature%20have%20been%20added,%20that%20is%20the%20ability%20for%20the%20pathfinder%20to%20tunnel%20through%20walls.
That%20feature%20overrides%20the%20normal%20behaviour%20of%20the%20pathfinder,%20and%20would%20authorize%20it%20to%20tunnel%20through%20walls,%20heading%20diagonally%20towards%20them.
The%20screeshot%20below%20illustrates%20this%20feature:
<img%20src=)Github
Documentation :
Hi all,
Find here an unofficial version of Jumper with minor modifications for multi-agents pathfinding, that I wrote upon the request of a user.
It doesn’t aims to speed, but to return intelligent and realistic looking paths when moving a group of units, avoiding the “stacking” issue when units pathing at the same time have the same destination.
The Readme provides interesting details on how to use it.
Grab it on Github : branch - Node-weight [import]uid: 142361 topic_id: 30317 reply_id: 145396[/import]
Hi, Roland.
Another case of “I’ve seen and read this paper, but never tried to implement it”:
http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Publications_files/coop-path-AIWisdom.pdf
I don’t know how it compares to the node weight approach (needs to do another search first), but maybe it works as a fallback for the non-A* / Dijkstra algorithms? [import]uid: 27791 topic_id: 30317 reply_id: 145453[/import]