It is currently Sat Mar 25, 2017 6:45 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: Jump Point Search (Pathfinding)
PostPosted: Fri Mar 17, 2017 3:09 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Thu Apr 30, 2009 5:23 pm
Posts: 106
Location: Côtes d'Azur, France
I made an implement of JPS search with optimisations "B+P" in assembly.
This algorithm won last pathfinding competitions on grids (it's only for grid graphs)
If you want detail, an explanation here:
http://zerowidth.com/2013/05/05/jump-po ... ained.html
The optimisations in this paper.
http://users.cecs.anu.edu.au/~dharabor/ ... caps14.pdf

Everything is in this zip (exe, library JPS, Binaries Heaps, special Hashtable and pb sources inside)
http://dl.free.fr/hvJCwuObW

Image
Open/close list nodes are really few.
The path is the shortest and is really smooth (45° or straight lines only).
The algo is "online" ie it's dynamic, nothing is process before.

To switch between A* and JPS press [Space]. In this exemple, 7 sec for A* and 10ms for JPS. (this map contains 1024x1024 cells)

Please if you see a bug thank you to report. :wink:

_________________
There are 2 methods to program bugless.
But only the third works fine.


Last edited by Fig on Fri Mar 24, 2017 11:07 am, edited 2 times in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: Jump Point Search (Pathfinding)
PostPosted: Thu Mar 23, 2017 3:17 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Thu Apr 30, 2009 5:23 pm
Posts: 106
Location: Côtes d'Azur, France
MAJ labyrinthe for tests and add Classical A* algo to compare speed.

_________________
There are 2 methods to program bugless.
But only the third works fine.


Top
 Profile  
Reply with quote  
 Post subject: Re: Jump Point Search (Pathfinding)
PostPosted: Thu Mar 23, 2017 3:49 pm 
Offline
Addict
Addict
User avatar

Joined: Sat Feb 19, 2005 2:46 pm
Posts: 1589
Location: Pas-de-Calais, France
Thank you for this great piece of code :D

_________________
Prehistoric games - Bobble Puzzle, Purebreaker 3 ~> http://djes.free.fr


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye