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

[Karai17]

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?

[Zeliarden]

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]

Aah! How did I miss that post!? Thanks for the reply, mate, I'll give this a shot.

[Karai17]

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?

[Roland_Yonaba]

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]

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]

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:

• LuAstar, by me.
• MarekkPie's loveAstar, with binary heaps
• Kikito's Pulsar

[Karai17]

Thanks for the reply!

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

[Roland_Yonaba]

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.
Remember that Tile(0,0) in AdvTiledLoader corresponds to Node(1,1) on your 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.

[Kadoba]

Have you considered making the grid dimensions boundless instead of static? I think it would make your library a lot more flexible and could probably be done in a few tweaks.