Jump to content

[TOPIC: topicViewTemplate]
[GLOBAL: userSmallPhoto]
Photo

Jumper - ( An Extremely Fast) 2D Pathfinder For grid-based games
Started by roland.yonaba Aug 27 2012 08:02 PM

* * * * * 1 votes
38 replies to this topic
[TOPIC CONTROLS]
Page 2 of 2 1 2
This topic has been archived. This means that you cannot reply to this topic.
[/TOPIC CONTROLS]
[modOptionsDropdown]
[/modOptionsDropdown]
[reputationFilter]
[TOPIC: post.html]
#26

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

I've been actively working on this project the past hours, and i came up with a new iteration of Jumper.
Here's the 1.8.0 release. The detailed changelog can be found here.

Some llittle changes were brought to the interface. Mostly because I wasn't satisfied with the relationship that was existing between the Grid and the pathfinder object, that is encapsulating the grid within the pathfinder object. That was a bad design choice, just because it was preventing a user from easily having a map with multiple terrain types.
So, as of this new release, Jumper offers to the use two main classes, at the top level : a Grid class, and a Pathfinder class.

local Grid = require('jumper.grid')
local Pathfinder = require('jumper.pathfinder')

To create the grid, it is still fairly simple, just pass a collision map to the Grid class. Then, pass the grid object to the Pathfinder.
The Pathfinder class takes three arg upon instantiation: the finder name, referring to the search algorithm to be used, the grid and the value/function for walkable tiles.

local map = {
  {1,1,1,1,1},
  {1,0,0,0,1},
  {1,0,0,0,1},
  {1,1,1,1,1},
}
local grid = Grid(map)
local myFinder = Pathfinder('JPS', grid, 0)

What makes that layout very interesting is that you can keep strick to a unique grid, and then simulate multiple terrain types. In the example above, let's consider 1 represents a specific terrain type, like 'land', and 0 stands for 'water'. That way, one can design a finder that will look for path on 'lands', and another that will search for paths on 'water'. We can even have a pathfinder for both (land and water, as walkable can also be a function).

local finderLand = Pathfinder('ASTAR', grid, 1)
local finderWater = Pathfinder('ASTAR', grid, 0)
local finderAmphibia = Pathfinder('ASTAR', grid, function(v) return v == 0 or v==1 end)

Added to that, I have included some new search algorithms. Well, they may all not be fast, by essence, by the duty of a library is to offer a choice, not to limit. So far, Jumper implements five well-know search algorithms: A-star, Dijkstra, Breadth first Search, Depth first search and Jump Point Search (the fastest one actually).

The Pathfinder class and the Grid class have also been extended with some new methods, mostly for a convenient use. You can check out the online documentation for more details.

Last point, some methods such as Pathfinder:filter() and Pathfinder:fill() were removed from the Pathfinder class. For now on, using Pathfinder:getPath returns a path, which would be an instance or an internal class named Path. To alter the returned path (interpolate, or compress it), you will just have to call these methods from the returned object:

local path = myFinder:getPath(startX, startY, endX, endY)
if path then
  path:fill() -- or path:filter()
  
  -- iterating along the path
  for node, count in path:iter() do
    -- etc
  end
end

Documentation is available online, and source. Check out the Readme, as it provides all informations you need to easily get started.
Source: Github
Documentation: Jumper

Thanks reading.
uid: 142361 topic_id: 30317 reply_id: 140447


[TOPIC: post.html]

[TOPIC: post.html]

[TOPIC: post.html]
#29

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

Hi all,

Find here an unofficial version of Jumper with minor modifications for multi-agents pathfinding, that I wrote upon the request of a user.
It doesn't aims to speed, but to return intelligent and realistic looking paths when moving a group of units, avoiding the "stacking" issue when units pathing at the same time have the same destination.
The Readme provides interesting details on how to use it.
Grab it on Github: branch - Node-weight
uid: 142361 topic_id: 30317 reply_id: 145396


[TOPIC: post.html]
#30

StarCrunch

[GLOBAL: userInfoPane.html]
StarCrunch
  • Contributor

  • 824 posts
  • Corona SDK

Hi, Roland.

Another case of "I've seen and read this paper, but never tried to implement it":

http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Publications_files/coop-path-AIWisdom.pdf

I don't know how it compares to the node weight approach (needs to do another search first), but maybe it works as a fallback for the non-A* / Dijkstra algorithms?
uid: 27791 topic_id: 30317 reply_id: 145453


[TOPIC: post.html]
#31

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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.
uid: 142361 topic_id: 30317 reply_id: 145479


[TOPIC: post.html]
#32

lukestirk

[GLOBAL: userInfoPane.html]
lukestirk
  • Enthusiast

  • 37 posts
  • Corona SDK

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?

[TOPIC: post.html]
#33

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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.

 



[TOPIC: post.html]
#34

lukestirk

[GLOBAL: userInfoPane.html]
lukestirk
  • Enthusiast

  • 37 posts
  • Corona SDK

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?



[TOPIC: post.html]
#35

Richards App Store

[GLOBAL: userInfoPane.html]
Richards App Store
  • Observer

  • 26 posts
  • Corona SDK

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?



[TOPIC: post.html]
#36

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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?

 

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. 



[TOPIC: post.html]
#37

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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?

 

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.



[TOPIC: post.html]
#38

loughrank

[GLOBAL: userInfoPane.html]
loughrank
  • Enthusiast

  • 41 posts
  • Corona SDK

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!  



[TOPIC: post.html]
#39

adipalgunaa

[GLOBAL: userInfoPane.html]
adipalgunaa
  • Observer

  • 1 posts
  • Corona SDK

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.




[topic_controls]
Page 2 of 2 1 2
 
[/topic_controls]