Jumper : (Very) Fast Pathfinder for 2D Grid-Based games

Roland_Y · January 2013

Hi Bowerandy,

Thanks for your insterest in this.
Well, that's an interesting point. Let's consider the brute force approach, with a huge grid. That means that you will have to set a huge 2D array (collision map), like 1024*768, and pass it to Jumper.

Well, since the start, Jumper was designed for grid-based games. Just because it was easier to deal with rectangular graphs, for me at first, and then focus on implementing efficient pathfinding algorithms. So, if we consider that memory is not a limiting factor here, the only concern would be speed, here. The interesting point here is that Jumper implements Jump Point Search, which is a very recent algorithm, that processes way more faster than regular A-star, with a quite lightning speed. You can witness it all by yourself running the benchmark program (not updated with the latest version of Jumper, though, but I'm on it). That benchmark let run a set of pathfinding problems (called a scenario) on simple to very complex maps, and monitors the time of search, using Jump Point Search. So em>fast enough ? I'll rather say "yes", IMHO. Well, you can try it all by yourself, designing huge maps and generate some problems, and then monitor the results, the time it takes. I can provide some help with that if needed.

But, you might also want to consider that maybe using a brute force approach is not what's the best. As I don't know how your maps might look like, I can't be 100% sure, but maybe you can design a non rectangular graph of nodes, but just a navigation mesh. Well, actually Jumper do not support navMeshes (sorry), but I'm planning looking into it soon. This topic can give you a pretty clear of what i have in mind. And pathfinding on NavMeshes is not that complicated to implement, hopefully.

I'll put a dot here. Hope this helps.
Sorry for the delay, by the way.

Best regards,
Roland.

bowerandy · January 2013

Hi @Roland_Y, thanks for the reply.

Do you know what, I think I've gone completely mad. You'll think I'm bonkers but my game actually *is* grid based but I'd just "forgotten". I use a grid size of 16 pixels so in fact I have a map of only 64x48 tiles. That should be easily workable shouldn't it?

The reason I got confused 8-} is because the AI for the game is currently in ObjectiveC and I've been down in there debugging. At that level I don't use the grid slots but instead a number of splined curves. That's what made me forget about the tiled nature of the problem.

The reason I'm interested in Jumper is because I'd eventually like to get rid of this ObjectiveC code and do everything in Lua. That way I can support Android as well as IOS. Since the current version of the AI is working, I probably won't try changing to Jumper right now but will take a look at some point in the near future.

I do have one question though. One issue I'm struggling with in my current implementation is how to make AI bots that aren't perfect. Is there any way with Jumper to assign some sort of "efficiency" rating to the search so that one can make "stupid" bots that take a longer path than the "smarter" ones?

BTW, if you put the poster's name preceded by an @ sign (@bowerandy in my case) in your replies to this forum then we receive an e-mail when they come through.

best regards

paul_k_clark · January 2013

@bowerandy, I'm looking at something similar (path navigation) and I had a few thoughts on the matter that might help for the stupid bots
1. a random selection from the top 2-3 paths
2. a weighted selection (best path 10 % of the time)
3. Always take the best path but the bots move slower

The last option is possible without any changes to @Roland_Y's path finder. Option 2 and 3 would allow for gradual increase in ability of the bots.

Roland_Y · January 2013

@bowerandy
Well, in that case, Jumper might be a good candidate for you. A map of 64x48 should be processed lightningly fast, hopefully. See this gist for more details

Concerning your second question, @paul_k_clark already provided an interesting answer. Well, the purpose of Jumper is to return a path, and Jumper would return an approximation of the optimal path. If you need to simulate wandering, a common artifact is selecting a random node that lies between the start and the goal node, pathfind from the start to that random node and then pathfind from that random node to the original target. Or, keep the original path, but apply a impulse function that would occasionaly slower agents. Steering behaviors seems to be a good option, too.

vitalitymobile · February 2013

@Roland_Y

Can you take a look at this problem? Is this a bug or I am missing something? thanks!

https://github.com/Yonaba/Jumper/issues/2

Roland_Y · March 2013

@vitalitymobile

The was solved, hopefully. See the latest commit pushed.

Roland_Y · March 2013

Hi all,
Here is a new iteration of Jumper: 1.8.1 release.
The detailed changelog can be found here.

This new release if totally backwards compatible with the latest one, except for only one minor change (for pure convience issues), related to the way one inits the pathfinder object.
See the related documentation: pathfinder
For now on, to init a new Pathfinder object, the [i]grid object comes first[/i]. Then one specifies the finder algorithm to be used, and then the walkable value(s).

As a straightforward example:

local Grid = require('jumper.grid')
local Pathfinder = require('jumper.pathfinder')
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(grid, 'JPS',0)

Added to that, some inner changes were brought to the code in order to fix some little odds that were causing the pathfinder to fail on specific situations.
Hopefully, all issues detected were solved, as of now.

A new feature have been added, that is the ability for the pathfinder to tunnel through walls.
That feature overrides the normal behaviour of the pathfinder, and would authorize it to tunnel through walls, heading diagonally towards them.
The screeshot below illustrates this feature:

See the dedicated section in the Readme, for more details.

Documentation and full source is freely available.
To easily get started with this library, please take a look at the readme.

Source: Github
Documentation: Jumper

Thanks reading.

vitalitymobile · March 2013

@Roland_Y it works perfectly !
When my game release, i will notice you :P

Roland_Y · March 2013

@vitalitymobile
Awesome,I can't wait for that.
Good luck with the code.

Best regards,
Roland.

Roland_Y · March 2013

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

mach · May 2013

Hi Roland,

Thank you for your work in implementing pathfinding in LUA.

I recently found the site http://trainsportedgame.no-ip.org/index.php - a game about transporting passengers via train on a track layout. In this game, one can implement different pathfinding algorithms and strategies for deciding which passenger should best be picked up and transported. After uploading your LUA-scripts, you can compete against other participants.

The trains in this game can only move forward. Turning is only allowed on dead ends, where the tracks make an U-turn. So the concept of direction of movement is essential under these circumstances.

Any idea to implemet pathfinding without moving backwards, using your code?

Regards,
Michael

Roland_Y · September 2013

@mach: Hi,
I am responding with a huge delay, sorry for that, there's been a long time I dropped around. Maybe you shou have opened a ticket on Github.
This issue have been discussed already, on Github. There is a very workable version of the library in a separated branch.
Thanks for your contribution.

zell2002 · November 2013

Hi ! Love this lib.
Was wondering if it was possible to not have to use a grid ? So i could create custom path nodes and still use your framework? Ive begun looking through the core files but its looking slightly more complex than i was expecting.anywhere to recommend i beglin looking from?

Roland_Y · November 2013

Hi @Zell2002,

Thanks for your interest in this.
Well, the same question have been asked to me not so long ago on here, then I'll just restate my anwser, if you do not mind.

In its current state, Jumper operates on grids. Not that it has to, but it was just a design choice of mine when I started working on this library some time ago.
But, on the other hand, all the search algorithms that Jumper implements (all but JPS) are generic graphs search algorithms, and they are not tight to grids. They can easily work on a waypoint graph. This is something I am considering to implement in the next iteration of Jumper. While the logic is straightforward, I will necessarily have to reconsider the general layout of the library, in terms of class, to come up with something clean to offer. I'll be working on it when I can find some spare time for that, though.

Besides this, do not hesistate if you have any other question. Thanks!

Yan · November 2018

What about nativeness ?

MoKaLux · December 2023

https://wiki.gideros.rocks/index.php/Pathfinding
- added the pull requests that haven't been merged on Roland Yonaba GH
- added --!NOEXEC so you don't have to manually exclude the files from execution
- changed to some Gideros Luau Enhancements: <> instead of abs, ...
- tested for quite a bit and seems to work good, no memory leaks?

Thank you sir Roland_Y

Howdy, Stranger!

Categories

In this Discussion

Top Posters

Jumper : (Very) Fast Pathfinder for 2D Grid-Based games

Comments

Howdy, Stranger!

Quick Links

Categories

In this Discussion

Top Posters

Jumper : (Very) Fast Pathfinder for 2D Grid-Based games

Comments