Difference between revisions of "Jumper"

(Jumper)
 
(Order of arguments not up-to-date with latest version)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
{{#set:Name=Jumper}}
 
−
{{#set:LOVE Version=Any}}
 
−
{{#set:Description= Fast pathfinding library for 2D grid-based maps}}
 
−
 
−
 
−
== What's this ? ==
 
−
 
 
'''Jumper''' is a pathfinding library designed for uniform-cost 2D grid-based games. It aims to be lightning '''fast''' and '''lightweight'''. It also features a '''clean public interface''' with chaining features which makes it very friendly and easy to use.
 
'''Jumper''' is a pathfinding library designed for uniform-cost 2D grid-based games. It aims to be lightning '''fast''' and '''lightweight'''. It also features a '''clean public interface''' with chaining features which makes it very friendly and easy to use.
−
 
  
 
== Technical notes ==
 
== Technical notes ==
 +
Jumper implements a lots if search algorithms: A-star, Dijkstra, Breadth-First search, Depth First search and Jump Point search (the fastest amongst all).
  
−
Jumper implements the [http://harablog.wordpress.com/2011/09/07/jump-point-search/ Jump Point Search] algorithm (tight along with [http://www.aiwisdom.com/ai_astar.html A-star] running on the background). It also implements a lighter implementation binary heaps module to maintain its open list of nodes while performing a search.
+
A benchmark program running in console is available on [https://github.com/Yonaba/Jumper-Benchmark Github]. It features a set of 132 maps from the [http://movingai.com/GPPC/ 2012 Grid-based Path Planning Competition].  
−
 
 
−
A benchmark program running in console is available on [https://github.com/Yonaba/Jumper-Benchmark Github]. It features a set of 132 maps from the [http://movingai.com/GPPC/ 2012 Grid-based Path Planning Competition]. You might want to try this program to witness the performance of ''Jump Point Search algorithm''.
 
−
 
 
  
 
== Usage ==
 
== Usage ==
−
 
 
Jumper is '''easy''' to use. Here is a basic example using the latest version available.
 
Jumper is '''easy''' to use. Here is a basic example using the latest version available.
  
 
<source lang="lua">
 
<source lang="lua">
−
-- A collision map.
+
-- Usage Example
−
-- We assume here that 0 represents walkable tiles
+
-- First, set a collision map
 
local map = {
 
local map = {
−
  {0,0,0,0,0},
+
    {0,1,0,1,0 },
−
  {0,0,1,0,0},
+
    {0,1,0,1,0 },
−
  {0,0,1,0,0},
+
    {0,1,1,1,0 },
−
  {0,0,1,0,0},
+
    {0,0,0,0,0 },
−
  {0,0,0,0,0},
 
 
}
 
}
 +
-- Value for walkable tiles
 +
local walkable = 0
  
−
local walkable = 0
+
-- Library setup
−
local Jumper = require ('Jumper') -- Calls the library
+
local Grid = require ("jumper.grid") -- The grid class
 +
local Pathfinder = require ("jumper.pathfinder") -- The pathfinder lass
 +
 
 +
-- Creates a grid object
 +
local grid = Grid(map)
 +
-- Creates a pathfinder object using Jump Point Search
 +
local myFinder = Pathfinder(grid, 'JPS', walkable)  
 +
 
 +
-- Define start and goal locations coordinates
 +
local startx, starty = 1,1
 +
local endx, endy = 5,1
  
−
-- We init our pathfinder instance, passing it the map,  
+
-- Calculates the path, and its length
−
-- and defining what are the walkable tiles
+
local path, length = myFinder:getPath(startx, starty, endx, endy)
−
local pathfinder = Jumper(map,walkable)
+
if path then
 +
  print(('Path found! Length: %.2f'):format(length))
 +
    for node, count in path:iter() do
 +
      print(('Step: %d - x: %d - y: %d'):format(count, node.x, node.y))
 +
    end
 +
end
  
−
-- Gets the path from location (1,1) to location (5,5)
+
--> Output:
−
local path, length = pathfinder:getPath(1,1,5,5)
+
--> Path found! Length: 8.83
 +
--> Step: 1 - x: 1 - y: 1
 +
--> Step: 2 - x: 1 - y: 3
 +
--> Step: 3 - x: 2 - y: 4
 +
--> Step: 4 - x: 4 - y: 4
 +
--> Step: 5 - x: 5 - y: 3
 +
--> Step: 6 - x: 5 - y: 1
 
</source>
 
</source>
  
 
Jumper offers '''a lot more options''' to customize the pathfinding behavior. Please, kindly check out the [https://github.com/Yonaba/Jumper/blob/master/README.md Readme] to figure them out.
 
Jumper offers '''a lot more options''' to customize the pathfinding behavior. Please, kindly check out the [https://github.com/Yonaba/Jumper/blob/master/README.md Readme] to figure them out.
−
 
  
 
== Feedback ==
 
== Feedback ==
−
 
 
If you have any question, proposal, idea to improve, or if you are just using Jumper in a project, I would love to hear your feedback. Issues/suggestions can be posted on the project [https://github.com/Yonaba/Jumper/issues issue tracker] on Github, or by [http://www.google.com/recaptcha/mailhide/d?k=01HyTvozzFr6QcQ0z5kWMOcg==&c=JKAjCplG02SOWgniiVzypsN1mkpjYjRXjt4Kfdf6g0Q= e-mail].
 
If you have any question, proposal, idea to improve, or if you are just using Jumper in a project, I would love to hear your feedback. Issues/suggestions can be posted on the project [https://github.com/Yonaba/Jumper/issues issue tracker] on Github, or by [http://www.google.com/recaptcha/mailhide/d?k=01HyTvozzFr6QcQ0z5kWMOcg==&c=JKAjCplG02SOWgniiVzypsN1mkpjYjRXjt4Kfdf6g0Q= e-mail].
−
 
  
 
== Links ==
 
== Links ==
−
 
+
* [https://github.com/Yonaba/Jumper Source]
−
<ul>
+
* [https://love2d.org/forums/viewtopic.php?f=5&t=9322 Forum thread]
−
<li>[https://github.com/Yonaba/Jumper Source]</li>
+
* [https://github.com/Yonaba/Jumper/blob/master/README.md README.md]
−
<li>[https://love2d.org/forums/viewtopic.php?f=5&t=9322 Forum thread]</li>
+
* [https://github.com/Yonaba/Jumper-Examples Demos]
−
<li>[https://github.com/Yonaba/Jumper/blob/master/README.md README.md]</li>
 
−
<li>[https://github.com/Yonaba/Jumper-Examples Demos]</li>
 
−
</ul>
 
  
 
[[Category:Libraries]]
 
[[Category:Libraries]]
 +
{{#set:Name=Jumper}}
 +
{{#set:LOVE Version=Any}}
 +
{{#set:Description= Fast pathfinding library for 2D grid-based maps}}
 +
{{#set:Keyword=AI}}

Latest revision as of 05:58, 25 July 2020

Jumper is a pathfinding library designed for uniform-cost 2D grid-based games. It aims to be lightning fast and lightweight. It also features a clean public interface with chaining features which makes it very friendly and easy to use.

Technical notes

Jumper implements a lots if search algorithms: A-star, Dijkstra, Breadth-First search, Depth First search and Jump Point search (the fastest amongst all).

A benchmark program running in console is available on Github. It features a set of 132 maps from the 2012 Grid-based Path Planning Competition.

Usage

Jumper is easy to use. Here is a basic example using the latest version available. 

-- Usage Example
-- First, set a collision map
local map = {
    {0,1,0,1,0 },
    {0,1,0,1,0 },
    {0,1,1,1,0 },
    {0,0,0,0,0 },
}
-- Value for walkable tiles
local walkable = 0

-- Library setup
local Grid = require ("jumper.grid") -- The grid class
local Pathfinder = require ("jumper.pathfinder") -- The pathfinder lass

-- Creates a grid object
local grid = Grid(map) 
-- Creates a pathfinder object using Jump Point Search
local myFinder = Pathfinder(grid, 'JPS', walkable) 

-- Define start and goal locations coordinates
local startx, starty = 1,1
local endx, endy = 5,1

-- Calculates the path, and its length
local path, length = myFinder:getPath(startx, starty, endx, endy)
if path then
  print(('Path found! Length: %.2f'):format(length))
    for node, count in path:iter() do
      print(('Step: %d - x: %d - y: %d'):format(count, node.x, node.y))
    end
end

--> Output:
--> Path found! Length: 8.83
--> Step: 1 - x: 1 - y: 1
--> Step: 2 - x: 1 - y: 3
--> Step: 3 - x: 2 - y: 4
--> Step: 4 - x: 4 - y: 4
--> Step: 5 - x: 5 - y: 3
--> Step: 6 - x: 5 - y: 1

Jumper offers a lot more options to customize the pathfinding behavior. Please, kindly check out the Readme to figure them out.

Feedback

If you have any question, proposal, idea to improve, or if you are just using Jumper in a project, I would love to hear your feedback. Issues/suggestions can be posted on the project issue tracker on Github, or by e-mail.

Links



Retrieved from "https://love2d.org./w/index.php?title=Jumper&oldid=25475"