Jumper - ( An Extremely Fast) 2D Pathfinder For grid-based games

Solar2D Lua Language
#61

Hi StarCrunch,

Cooperative pathfinding is something i’ve already considered, many times. But it doesn’t really suits to me as it end up a bit tricky to implement and to get working right with different search algorithms (in other works, I did not succeeded).
Actually, there is an alternative method, but that goes out of a simple pathfinding library purposes, yet it works really fine. For a group of units, one just runs the pathfinding algorithm (in a clever way so that it won’t drop the framerate), and then use “steering behaviours”. Something I might definitely try someday.

And about ThetaStar, I succeded in implementing it, as it wasn’t that hard, and the papers gave some very clear explanations about that. There are some things left to fix yet, such as finding an efficient line of sight algorithm as the original one described in the article fails miserably in some cases.

Thanks for your feedback and ideas, though. [import]uid: 142361 topic_id: 30317 reply_id: 145479[/import]

#62

Hi, first thanks for the library it’s very helpful for my project. Just 1 question, how can you convert the x y position of the tile to use screen x y coords instead?

#63

Thanks for the kind words.

Actually, converting tile coordinates to world coordinates roughly depends on your game. You might have defined a tile size (if your tiles are square, for instance) or a couple of sizes (on x and y) for tiles:

In the following setup, i’ll assume that your upper left coordinate is 0,0 for world coordinates, or tile(1,1) for tiles coordinates.

local tileWidth = 32 local tileHeight = 32

Let’s say you have a world of 100 tiles width and 100 tiles height. What makes :

local nTilesX = 100 local nTilesY = 100 local worldWidth = nTilesX \* tileWidth local worldHeight = nTilesY \* tileHeight -- Creates the collision map to be passed to the Grid object. local map = {} for y = 1, nTilesHeight do map[y] = {}   for x = 1, nTilesWidth do map[y][x] = 0 end end  

Now you can use those functions to convert tiles coordinates to world coordinates, or vice versa. I am assuming that to find a tile coordinates in thje world, you only need the coordinates of its upper-left corner.

local function tileToWorld(tileX, tileY)   local worldX = (tileX - 1) \* tileWidth   local worldY = (tileY - 1) \* tileHeight   return worldX, worldY end local function worldToTile(worldX, worldY)   local tileX = math.ceil(worldX/tileWidth)   local tileY = math.ceil(worldY/tileHeight)   return tileX, tileY end

Well, note that they work right here because the upper-left tile is mapped at 1,1 in tiles coordinates. In case the upper left tile is mapped at 0,0, you might use these instead:

local function tileToWorld(tileX, tileY)   local worldX = (tileX) \* tileWidth   local worldY = (tileY) \* tileHeight   return worldX, worldY end local function worldToTile(worldX, worldY)   local tileX = math.floor(worldX/tileWidth)   local tileY = math.floor(worldY/tileHeight)   return tileX, tileY end  

Hope this helps.

#64

Thanks Roland that did what I needed.

Now my next problem is I need multiple paths so I can have rows of enemies and I need the paths so be smooth. A sample map I am working on is attached, I basically lay a grid over the top and blocked out where the paths are, any advice on how I could get the paths smooth around the bends?

#65

First I just wanted to say thanks for making this library! Seems like it’s going to help me a lot. I am working on a new project, and this is my first time ever making a grid based game, so I have no experience with creating tiled worlds, path finding, etc. My basic understanding of how this library would fit in, is you would make the map graphics, which includes walkable areas and some unwalkable areas, and you run the jumper class and when creating your map you use e.g. 0,0,0,1,1,0,0,1,0 etc. to show which parts of the map are walkable and which parts aren’t. My question is, where do I need to specify map/tile size so that when I make that map array, each number for a tile represents the actual size of the tiles in my graphics?

#66

Hi Richards,

Actually Jumper doesn’t need to be aware of the tile size of the graphics in your game. It just need the 2D matrix that represents the collision map of your game. Later, you are the one using the tile graphics to match the tile coordinates that Jumper returns to the world’s coordinates to displace correctly your objects on the screen.

TO put it in a nutshell, you can start figuring out what are your world’s size. It might be the exact size of the device screen, or larger (and in that case, you might have to deal with a view camera and scrolling). Then, considering the tile dimensions you are working with, you can calculate how much cells you have along the world’s width and height. You basically create a 2D matrix of values accordingly, and then fill it according to the obstacles position.

I would suggest to take a look at my previous post, it pretty much covers the same topic. 

#67

Hi Luke,

Sorry for the short delay.Better late than never, though.

Path smoothing is a huge theory, and Jumper was not made to solve this issue. At least, not straight.

Maybe you should explain more what you want to accomplish. Can you picture the grid you have, outline an example of path and how you want it to be smoothed ? Thanks.

#68

Hi, first thanks for the library it’s very helpful for my project. Just 1 question, how can you convert the x y position of the tile to use screen x y coords instead?

#69

Thanks for the kind words.

Actually, converting tile coordinates to world coordinates roughly depends on your game. You might have defined a tile size (if your tiles are square, for instance) or a couple of sizes (on x and y) for tiles:

In the following setup, i’ll assume that your upper left coordinate is 0,0 for world coordinates, or tile(1,1) for tiles coordinates.

local tileWidth = 32 local tileHeight = 32

Let’s say you have a world of 100 tiles width and 100 tiles height. What makes :

local nTilesX = 100 local nTilesY = 100 local worldWidth = nTilesX \* tileWidth local worldHeight = nTilesY \* tileHeight -- Creates the collision map to be passed to the Grid object. local map = {} for y = 1, nTilesHeight do map[y] = {}   for x = 1, nTilesWidth do map[y][x] = 0 end end  

Now you can use those functions to convert tiles coordinates to world coordinates, or vice versa. I am assuming that to find a tile coordinates in thje world, you only need the coordinates of its upper-left corner.

local function tileToWorld(tileX, tileY)   local worldX = (tileX - 1) \* tileWidth   local worldY = (tileY - 1) \* tileHeight   return worldX, worldY end local function worldToTile(worldX, worldY)   local tileX = math.ceil(worldX/tileWidth)   local tileY = math.ceil(worldY/tileHeight)   return tileX, tileY end

Well, note that they work right here because the upper-left tile is mapped at 1,1 in tiles coordinates. In case the upper left tile is mapped at 0,0, you might use these instead:

local function tileToWorld(tileX, tileY)   local worldX = (tileX) \* tileWidth   local worldY = (tileY) \* tileHeight   return worldX, worldY end local function worldToTile(worldX, worldY)   local tileX = math.floor(worldX/tileWidth)   local tileY = math.floor(worldY/tileHeight)   return tileX, tileY end  

Hope this helps.

#70

Thanks Roland that did what I needed.

Now my next problem is I need multiple paths so I can have rows of enemies and I need the paths so be smooth. A sample map I am working on is attached, I basically lay a grid over the top and blocked out where the paths are, any advice on how I could get the paths smooth around the bends?

#71

First I just wanted to say thanks for making this library! Seems like it’s going to help me a lot. I am working on a new project, and this is my first time ever making a grid based game, so I have no experience with creating tiled worlds, path finding, etc. My basic understanding of how this library would fit in, is you would make the map graphics, which includes walkable areas and some unwalkable areas, and you run the jumper class and when creating your map you use e.g. 0,0,0,1,1,0,0,1,0 etc. to show which parts of the map are walkable and which parts aren’t. My question is, where do I need to specify map/tile size so that when I make that map array, each number for a tile represents the actual size of the tiles in my graphics?

#72

Hi Richards,

Actually Jumper doesn’t need to be aware of the tile size of the graphics in your game. It just need the 2D matrix that represents the collision map of your game. Later, you are the one using the tile graphics to match the tile coordinates that Jumper returns to the world’s coordinates to displace correctly your objects on the screen.

TO put it in a nutshell, you can start figuring out what are your world’s size. It might be the exact size of the device screen, or larger (and in that case, you might have to deal with a view camera and scrolling). Then, considering the tile dimensions you are working with, you can calculate how much cells you have along the world’s width and height. You basically create a 2D matrix of values accordingly, and then fill it according to the obstacles position.

I would suggest to take a look at my previous post, it pretty much covers the same topic. 

#73

Hi Luke,

Sorry for the short delay.Better late than never, though.

Path smoothing is a huge theory, and Jumper was not made to solve this issue. At least, not straight.

Maybe you should explain more what you want to accomplish. Can you picture the grid you have, outline an example of path and how you want it to be smoothed ? Thanks.

#74

Thank you thank you for building this library - I was able to implement it with great ease!

I wanted to ask - is there a quick/easy way to remove diagonal paths?  The particular game I’m working on is best executed without diagonal movement through the grid.  

**** DERP *****

I found it - changed: pathfinder.lua, line 163

newPathfinder:setMode(‘DIAGONAL’)

to 

newPathfinder:setMode(‘ORTHOGONAL’)

Sorry I didn’t just figure this out on my own first!  

#75

Hi!

i have some question.

can we regenerate path to end point so we can get new path after adding listener? in example, i have a listener so i change the value from walkable into not walkable. So the object must change the route to end point?

thanks.

#76

Thank you thank you for building this library - I was able to implement it with great ease!

I wanted to ask - is there a quick/easy way to remove diagonal paths?  The particular game I’m working on is best executed without diagonal movement through the grid.  

**** DERP *****

I found it - changed: pathfinder.lua, line 163

newPathfinder:setMode(‘DIAGONAL’)

to 

newPathfinder:setMode(‘ORTHOGONAL’)

Sorry I didn’t just figure this out on my own first!  

#77

Hi!

i have some question.

can we regenerate path to end point so we can get new path after adding listener? in example, i have a listener so i change the value from walkable into not walkable. So the object must change the route to end point?

thanks.