yonaba / jumper Goto Github PK

In case the destination is not reachable, getPath() fails and returns nil. It would be interesting to get an incomplete path passing an extra-arg. Actually, such a path can be retrieved from the closed list right after failing to reach the destination in the search expansion loop, but the expected result would probably differ depending on the search algorithm used.

Pathfinder:getPath(...) triggers the selected finder, and returns nil if a path was not found. That is easy to circumvent, using an efficient floodfill algorithm applied on the entire grid, we specify what nodes are related using integer values, and if a path can be found of not between two nodes. The finder will then lookup these values and early exit in case they do not match (i.e, there's no path between the given locations).

The floodfill should be run once, upon initialization. It should obviously be called again in case the collision map is updated.

The trade-off would be the amount of space needed to store the floodfill values, so let's make of it an optional feature.

As the issue title implies, having the possibility to return a path having a given maximum length. That would be useful for units having a maximum stepping ability, or units that can move on a limited distance when attempting to reach a goal.

Will check if a given node is visible from another given node.

-- Returns true if nodeB is visible from nodeA or vice versa
-- allowDiagonal will depend on the number of allowed directions when moving.
function Grid:lineOfSight(nodeA, nodeB)

Instead of passing deltas to Heuristics, they should handle nodes as arguments.
That will facilitate writing more effective custom heuristics functions on the basis on the passed-in nodes themselves.

Hi, I was wondering if it's possible to do 3D pathfinding with Jumper?

Thanks!

Hi,

I'm trying to get the latest version of Jumper to work but I always get this error:

jumper.lua:379: attempt to index field 'startNode' (a nil value)

Here's my code:

    elseif button == "r" then
        messages.showMessage("Right clickin'")

        table.foreach(employee_instances, function(i)
            employee = employee_instances[i]

            if employee.selected then
                local map_tile_x, map_tile_y = math.floor(math.floor(x)/32), math.floor(math.floor(y)/32)

                see(x)
                see(y)

                if pather.grid:isWalkableAt(map_tile_x, map_tile_y) then
                    messages.showMessage("Checking for a path...")

                    local start_tick = love.timer.getMicroTime()*1000
                    local path, length = pather:getPath(employee.x, employee.y, map_tile_x, map_tile_y)
                    local time = (love.timer.getMicroTime()*1000 - start_tick)

                    if path then
                        messages.showMessage("Go!!!")
                        employee:orderMove(path)
                    end
                end
            end
        end)
    end

I based this code on the Examples you provided for Löve.

Am I doing something wrong or is it a bug? Please tell me if you need any more infos.

Thanks and keep up the good work!

/tommy

https://github.com/Yonaba/Jumper/blob/master/jumper/core/lookuptable.lua#L1

local addNode(self, node, nextNode, ed)

did you mean

local function addNode(self, node, nextNode, ed)

Merge node weight based pathfinding to master. It has proven to be a handy way to handle simultaneous pathfinding for multiple agents, for most use cases.

We can have, for grid maps, tiles than can only be crossed in specific directions. For instance, it can only be entered north, south, etc.

• The first approach is to define, for specific nodes, the edges that cannot be taken to enter/leave the node itself. Internally, while expanding the search, the pathfinder will consider this information to properly retrieve the nodes to be examined next.
• The second approach, bitmasks. I already investigated it, but not in-depth. The results were not satisfactory at all, but I would probably reconsider it if the previous does not work.

Something minor, and I don't have time to fork and fix it myself at the moment:

https://github.com/Yonaba/Jumper/blob/master/jumper/core/floodfill.lua#L75
You open a '(' for the while statement but forget to close it before 'do'

Also, thanks a lot for this massively useful library ;)

I use Jumper, astar, for river generation and it uses way too much memory. I was wondering if its possible if you could do some internal optimization for memory. Some suggestions are allowing the user to use an ffi struct for the map data or if you didn't use a class for the nodes internally. Tables take up a large amount of memory so using a class for nodes makes it take up more memory than needed.

Description for Lazy ThetAstar here, with pseudocode given. It is another any-angle path planning algorithm which reduces the number of length-of sight (LOS) checks per step, thus optimizing performance of ThetAstar.

In its actual state, clearance value calculation for an entire map works quite well, but very is slow, especially on
huge maps. I should probabaly try an alternate implementation, compare it to the actual one and then keep what seems to be the fastest.
There is an available source, based on a recursive approach that can be taken as a reference for that alternate implementation.
See AnnotatedMapAbstraction.cpp

Provide a clever path caching system, so that requesting a path previously calculted and cached triggers a simple database lookup. This alternative might be implemented as a complementary feature for the pathfinder, as discussed here.

When diagonal moves are allowed, an agent when turning around a corner (wall edge) can cross the corner. This behaviour might not be suitable for some games, as it results in unaesthetic paths, especially for agents having a certain size. Although it can be solved with clearance, we shoud be able to allow/disallow the ability to cross a corner when making a diagonal move.

This can be easily implemented by skipping an adjacent neighbor when getting the list of a node neighbors. Assuming dx and dy are the normalized vectors of movement, we check if the node at (currentNode.x+dx, currentNode.y) is walkable. In case it is, we only add it to the list of neighbors if cornerCrossing is allowed.

The ability to (dis)allowCornerCrossing will be added as a new method to the pathfinder interface.

Thanks Yonaba for your work,
Jumper has been a huge help to me!

It would be great to have a way to identify a node on a grid as one that can be traversed but not "landed" on. The issue I am having is units in a game should be able to pass through a node occupied by an "ally" but shouldn't be able to "land" on it.

Hi,
Thank for awesome Jumper! I think we have a bug with JPS and ORTHOGONAL combo? If i change JPS to ASTAR, the path is found.

Thanks!

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

-- Library setup
local Grid = require ("zgame.jumper.grid") -- The grid class
local Pathfinder = require ("zgame.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) 
myFinder:setMode ('ORTHOGONAL')

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

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

Hi Yonaba,
I am using Jumper in my project and setup the map like bellow.
But when i try to move gem from 5,3 to 4,3 (that i think it nearby and possible to move) it show can not move. Can you check it?

Thanks!

local Jumper = require 'Jumper.init'
local map = {
    {0,1,1,1,0,1,1},
    {1,1,1,1,1,1,1},
    {0,0,1,0,1,1,1},
    {1,1,1,1,1,1,1},
}

local walkable = 0
local postProcess = false
local pather = Jumper(map,walkable,postProcess)
local sx,sy = 5,3
local ex,ey = 4,3
print('Hello Jumper! from Gideros')
local path = pather:getPath(sx,sy,ex,ey)
if path then
  print(('Path from [%d,%d] to [%d,%d] was : found!'):format(sx,sy,ex,ey))
  for i,node in ipairs(path) do
    print(('Step %d. Node [%d,%d]'):format(i,node.x,node.y))
  end
else
    print(('Path from [%d,%d] to [%d,%d] was : not found!'):format(sx,sy,ex,ey))
end  

I think it would be useful to implement a method that returns the first node of a path and deletes it at the same time.

One would expect to have x followed by y (.e.g my grid is grid[x][y]). This engine unfortunately uses non-standard y first and then x second [y][x]. Took me few days to identify the culprit. Maybe this report will help somebody.

Some time ago I wanted to use Jumper on a heightmap. What I was aiming for was a simple check for climb/fall distance.
If the walkable callback included the current and checked positions, would that break the A* or Dijkstra implementations?

Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman–Ford algorithm which computes single-source shortest paths in a weighted directed graph. The algorithm is believed to work well on random sparse graphs and is particularly suitable for graphs that contain negative-weight edges.

Pseudo-code for procedure Shortest-Path-Faster-Algorithm(G, s):

for each vertex v ≠ s in V(G)
  d(v) := ∞
  d(s) := 0
  offer s into Q
  while Q is not empty
    poll Q
    for each edge (u, v) in E(G)
      if d(u) + w(u, v) < d(v) then
        d(v) := d(u) + w(u, v)
          if v is not in Q then
            offer v into Q

jumper-1.8.1-1.tar.gz seems to work with the demo provided in the readme. current head (df4eb22) does not. node.x and node.y are nil. node seems to be a table.

Provide methods to the Grid interface to define custom iteration order/schema.
Customizable aspects expected:

• Order on Y axis (north to south, or south to north)
• Order on X axis (left to right, or right to left)
• X-axis before Y-axis, or Y-axis before X-axis

Yonaba,

I currently have a grid displaying, and a player can touch a square and it would calculate a path from the center square in the map to the square that the player touched. The funny thing is, sometimes I have troubles with the assert on line ~340? (I changed mine for debugging). I get the "Invalid or unreachable at [endx][endy]" error, but it is not displaying the correct endy value.

For example, if I click on grid[3][10], it might be valid and everything works great. If I then click on grid [3][11], it says unreachable at 3,10. The weird part is that depending on what device I am emulating the rows and columns are different, i.e. iphone 4 doesn't work for row 7 and sg3 doesn't work on col 7,10 or 14.

It is really strange. I have a video here:
http://screencast.com/t/IRZZqfvl5a

and here are some screenshots:
http://screencast.com/t/79v3PLgih6HF
http://screencast.com/t/E4CZN5na9

I don't know if you have any insights: I have been struggling on this issue and can't seem to find any answers online.

Thank you, you have always been so helpful

Custom search algorithm, cooked by @rafaelcastrocouto.
See here

• It performs better than Astar on some cases
• Already uses binary heaps (two heap internally)
• When expanding from a node, it gives priority to node have a few neighbors.
• Produces more natural paths.

Might require more tests, but would be a nice addendum to Jumper.

I am probably not the right person to ask this, as I am still new to Lua (more fluent in other dynamic language like javascript), but it seems like this project may need some help pushing out a new release?

A few improvement could be:

• Some of pending PRs are trivial and merge-able, eg. #46 #48;
• Many commits happened after the March 3rd 2013 release, 1.8.1, changelog can includes changes in master that haven't been released;

This feature is not likely to be useful (included in 1.8.1). It sounded like something good,at first, but it should be removed in the next release. Plus, it does not well acommodates with most of search algorithms, such as Jump Point Search, ThetAstar and Lazy ThetAstar.
The feature will be removed, in favor of allowCornerCrossing (see #30)

Hi, sorry if this is the wrong place to ask for help; I couldn't find a forum to post to. Thanks for the amazing library you built together! I'm working on implementing it in Dota 2 modding. I have a couple questions.

1: The program is finding a path, but when it tries to execute this line:

         print(('Step: %d - x: %d - y: %d'):format(count, node:getX(), node:getY())) 

it gives me an error: "attempt to call method 'getX' (a nil value)".

When I comment out that line and let the for loop run, here is each node's table printed out: http://pastebin.com/wUTbn3NN

2: What are you required to do when you need to change nodes from walkable to unwalkable and vice versa? At the moment I'm changing values in the collision map to 1 (without searching), and then running this code:

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

However this seems quite expensive, and I even get small lag spikes everytime this executes.

Thanks!

Jump Point Search was not actually devised for orthogonal search on uniform cost grids. It actually takes advantage of heading diagonally (over straight directions) to reach a goal.

In the actual implementation of JPS, the problem was partially solved, but not in a very elegant manner, as it floods the search with forced neighbors, jump points and discards evrey single diagonal expansion. It works fine, but the search time is a bit long (higher than standard A-star) and the return path is a step-by-step path.

The point here is to look into ways to develop a new set of pruning rules for 4-directions grids. Some starting points that might be worth investigating further or detailed articles that can be used for reference:

• Online graph pruning for pathfinding on grid maps (original paper, pdf, direct link)
• Jump Point Search (Daniel Harabor's blog)
• Jump Point Search explained (Nathan Witmer's article)
• How to speed up pathfinding with the JPS algorithm (GameDev tuts+)
• Is JPS appliable to non-diagonal grids (Ilmari Karonen's response on Gamedev StackExchange).
• Hybrid limited range JPA* in a 3D world

As the extra features is about to grow, and cannot be applied straight to all search algorithms, it might be interesting to separate pathfinders.

Basically, there can be a top level pathfinder class, from which the user cannot instantiate.
This super class will implement the common features shared accross all finders.

And ideally, from this class we will have methods to derive all specialized finders, with their specific methods.

local Pathfinder = require '.?/pathfinder.lua'
local astarFinder = Pathfinder.newAstarFinder(grid, walkable)

If possible, make it backwards compatible.

Could be an interesting feature to be added to the pathfinder class. Sometimes, we do want to avoid some specific nodes without marking them as unwalkable. I am thinking of adding those methods to the API:

pathfinder:setAvoidance(f)
pathfinder:unsetAvoidance()

Typically, a function will be passed to the former method. That function will be called on each node to check whether or not the node should be ignored from the search.
The given function should be prototyped as specified below, and will return a boolean.

function f(node, ...) ... end

That's in jumper/core/assert.lua

Fix:

--- a/jumper/core/assert.lua
+++ b/jumper/core/assert.lua
@@ -96,7 +96,6 @@ if (...) then
                isBool = isBoolean,
                isMap = isMap,
                isStrMap = isStringMap,
-               isOutOfRange = isOutOfRange,
                isNil = isNil,
                type = type,
                matchType = matchType

Edit: Similarly for jumper/core/utils.lua:

--- a/jumper/core/utils.lua
+++ b/jumper/core/utils.lua
@@ -146,7 +146,6 @@ if (...) then
                arrayToNodes = arrayToNodes,
                strToMap = stringMapToArray,
                around = around,
-               drAround = drAround,
                traceBackPath = traceBackPath
        }

Following Depth First search and Besr First Search, include Breadth First search, for uniform-cost grids and point graphs.

Pseudo-code:

procedure BFS(G,v) is
  create a queue Q
  create a vector set V
  enqueue v onto Q
  add v to V
  while Q is not empty loop
    t ← Q.dequeue()
    if t is what we are looking for then
      return t
    end if
    for all edges e in G.adjacentEdges(t) loop
      u ← G.adjacentVertex(t,e)
      if u is not in V then
        add u to V
        enqueue u onto Q
      end if
    end loop
  end loop
  return none
end BFS

Yonaba,

First off you have been awesome. I have been using this pathfinder for a small game I am making for personal use (mostly to prove I can do it).

I am trying to build my .apk and it is giving me an error in the lookuptable.lua file, saying I need a ')' before the ','
http://screencast.com/t/mY9EN6yXIF

I can build the file if I comment out the whole file, since I am currently not actually using any part of the Jumper package. I plan to implement it soon. Do you have any suggestions?

Brian H.

I should consider including weighting for A-star based search algorithms when summing G-cost and H-cost to compose F-cost.

local function weightedF(G, H, alpha)
  alpha = alpha or 0.5
  return alpha * G + (1 - alpha) * H
end

The purpose of this is to give full control to balance between Dijkstra search (alpha = 1), Classical A-Star (alpha = 0,5) and Best-First-Search (alpha = 0).

hi yonaba,
thanks for the library you created. but i have a question about my TD project.
can we just regenerate new path after we change the value of grid map? in example, i have a listener so i can change the value of grid map from walkable into not walkable. so when the program start and it had a endPoint. player can adding some block so we need a new path to go through the end point.

thanks

As of now, Jumper only features grid type as an input data structure for pathfinding.
PointGraph maps can also be featured, as all the search algorithms implemented (but Jump Point Search) operates on graphs, and are not bound to explicit grid maps.
That would certain extend the possibilities of usage of Jumper.

Hi there I'm trying to connect the Jumper library with the programming game trAInsported but I'm unable to get the require 'foo.bar' thing working .. is this a known issue or am I just to stupid ?