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

Showcase your libraries, tools and other projects that help your fellow love users.
User avatar
Karai17
Party member
Posts: 906
Joined: Sun Sep 02, 2012 10:46 pm

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

Post by Karai17 » Mon Sep 24, 2012 8:26 pm

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

Post by Zeliarden » Mon Sep 24, 2012 9:35 pm

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

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

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

Post by Karai17 » Mon Sep 24, 2012 9:40 pm

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é

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

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

Post by Karai17 » Wed Oct 03, 2012 2:44 am

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é

User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

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

Post by Roland_Yonaba » Wed Oct 03, 2012 9:09 am

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

Post by SudoCode » Wed Oct 03, 2012 3:59 pm

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.

User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

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

Post by Roland_Yonaba » Wed Oct 03, 2012 4:44 pm

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:

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

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

Post by Karai17 » Wed Oct 03, 2012 5:15 pm

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
STI - An awesome Tiled library
LÖVE3D - A 3D library for LÖVE 0.10+

Dev Blog | GitHub | excessive ❤ moé

User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

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

Post by Roland_Yonaba » Wed Oct 03, 2012 7:17 pm

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.

User avatar
Kadoba
Party member
Posts: 399
Joined: Mon Jan 10, 2011 8:25 am
Location: Oklahoma

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

Post by Kadoba » Thu Oct 04, 2012 4:58 pm

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.

Post Reply

Who is online

Users browsing this forum: Google [Bot] and 26 guests