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

Karai17
Party member
Posts: 906
Joined: Sun Sep 02, 2012 10:46 pm

### Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search

Hey,

I was wondering how easy it would be to create a table of "walkable tiles" instead of just a single value. I am looking for a path finding library that works well with Tiled and I believe that Jumper would probably do the trick, but it only accepts a single tile to be "walkable" whereas I would need to be able to set multiple tile values. Tiled assigns a unique number to each tile in its tile sets so having grass + dirt + ... all able to be walked on would be terrific.

Thoughts?
STI - An awesome Tiled library
LÖVE3D - A 3D library for LÖVE 0.10+

Dev Blog | GitHub | excessive ❤ moé

Zeliarden
Party member
Posts: 139
Joined: Tue Feb 28, 2012 4:40 pm

### Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search

Check my earlier post, posted a test with Advanced Tiled Loader (JumperATL.love)
It generats a walkmap from a collision layer.
You can always use Tile Propeties to set grass and dirt to solid and genrate a map walk map from that

Karai17
Party member
Posts: 906
Joined: Sun Sep 02, 2012 10:46 pm

### Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search

Aah! How did I miss that post!? Thanks for the reply, mate, I'll give this a shot.
STI - An awesome Tiled library
LÖVE3D - A 3D library for LÖVE 0.10+

Dev Blog | GitHub | excessive ❤ moé

Karai17
Party member
Posts: 906
Joined: Sun Sep 02, 2012 10:46 pm

### Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search

Double post, etc.

So I managed to get Jumper to work with ATL but I am having issues with the collision map. it seems that when my Player is standing at (0,0), (0,n), or (n,0), when the enemy attempts to draw a path to me, the game crashes citing invalid values.

Does Jumper have trouble with the index value of 0? ATL seems to want to use 0,0 as the beginning point, even though lua's "best practice" is to index from 1. Would this be my issue, or is something else the problem?
STI - An awesome Tiled library
LÖVE3D - A 3D library for LÖVE 0.10+

Dev Blog | GitHub | excessive ❤ moé

Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Contact:

### Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search

Hi Karai,

Lua tables starts indexing at 1, and Jumper uses the same rule. If you're working on a map like this:
map = {
{0,0,0},
{0,0,0},
{0,0,0},
}
Only locations [i,j] for i,j between 1,3 (included) are valid locations with Jumper.
I don't know how tiles are indexed with ATL.If they starts at (0,0) you may have to shift every coordinates with ATL from 1 to the right and 1 down. So that Tile (0,0) with ATL will correspond to Tile(1,1) with Jumper.

I think that this is what Zeliarden did in his demo (JumperATL):
He used this function (pathfinder.lua) to set a collision map:

Code: Select all

function walkmap(w, h, l)
local walk = {}
for wy=0, h do
walk[wy] = {}
for wx=0, w do
walk[wy][wx] = 0
end
end
for x, y, tile in map.tileLayers[l].tileData:iterate() do
x=x+1 -- shifting index from 1 to the right
y=y+1 -- shifting index from 1 down
walk[y][x] = 1
end
return walk
end

And then used the returned collision map to init Jumper (main.lua)

Code: Select all

	wmap = walkmap(map.width, map.height, "Collision")
walkable = 0
allowDiagonal = true
smoothpath = false
drawpath = true
pather = Jumper(wmap,walkable,allowDiagonal)

Hope this helps.

EDIT: Thanks using this, by the way. I'm still improving this, as I'm not sure I understood fully how JPS works on some specific cases.
I'll be happy to have feedbacks, and if you happened to have a workable and clean demo, I can share it as an example of use on Github.

SudoCode
Citizen
Posts: 61
Joined: Fri May 04, 2012 7:05 pm

### Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search

Is there an easy way to implement more than one node cost? I'm attempting to write my own pathfinding code at the moment with 4 directional movement, and it's giving me a bit of a headache. I'd love to use this, but only if I could implement different node costs.

Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Contact:

### Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search

SudoCode wrote:Is there an easy way to implement more than one node cost? I'm attempting to write my own pathfinding code at the moment with 4 directional movement, and it's giving me a bit of a headache. I'd love to use this, but only if I could implement different node costs.
Can you explain a bit more what you want to do exactly ?

For Jumper, all heuristics to evaluate node costs when expanding the search are defined inside heuristics.lua
The way they are used for each jump points is specified in jumper.lua (look inside identifySuccessors function)
But if you're looking for ways to implement your own A-star, I won't recommend looking at Jumper's source, as it features A-star + Jump point search on the top, which results in a little different ways of expanding the search process that may look confusing if you never experienced implementing A-star.

You can take a look at this very good tutorial (abstract, though) from Patrick Lester, and also look at how nodes codes are handled in all these Lua A* implementations:

Karai17
Party member
Posts: 906
Joined: Sun Sep 02, 2012 10:46 pm

### Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search

I've been poking at this for hours and I just can't seem to get the collision map and the tiled map to line up! Could you take a look at this and perhaps give me some pointers? The most relevant files are screens/gameplay.lua and entity.lua

https://dl.dropbox.com/u/12958391/KLD-jumper.love
STI - An awesome Tiled library
LÖVE3D - A 3D library for LÖVE 0.10+

Dev Blog | GitHub | excessive ❤ moé

Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Contact:

### Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search

I actually don't have enough time to go through the entire code, but I can give some tips.
It seems you're using Jumper to move the mobs. Right ?

So first of all, forget all about Jumper, and set everything right. Make sure to have the base map loaded and displayed correctly.
Same thing for the player.
Now, you can init the collisionMap, as you already does. To make sure this collision map was built properly, you can attach a console and print the collision map:

Code: Select all

-- gameplay.lua
-- Create Collision Map
self.collisionMap = createCollisionMap(self.map, "Collision")
table.foreach(self.collisionMap,function(_,row) print(table.concat(row,'')) end) --prints the collision map
Thus, init Jumper with the collision map.
Now for Mobs, each new mob should have some base coordinates related to ATL:

Code: Select all

Mob = {  x, y = ...} -- coordinates of the mob with ATL 
Now, when you want a mob to attack the player, first, find the player coordinates : player.x,player.y
These are the player coordinates with ATL and these coordinates should correspond to location (player.x+1, player.y+1) on the collision map.
So, the mob should look for a path from (self.x+1, self.y+1) to (player.x+1,player.y+1).

When Jumper returns a path, keep in mind that this path is made of locations on the collision map.
So, to route the mob, you will have to go through the returned path, and substract 1 from each x,y coordinates.

Code: Select all

 -- Gets the path from a mob to the player
local path = pather:getPath(mob.x+1,mob.y+1,player.x+1,player.y+1)

-- Makes the returned path compatible with ATL
if path then
mob.path = {}
for _,node in (path) do
mob.path[#mob.path+1] = {x = node.x-1, y = node.y-1}
end
end

Now you can move the mob along mob.path.
Guess that should work.