It is currently Fri Jul 28, 2017 7:57 pm

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: 159
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/kEjXIisxg

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 Sun Mar 26, 2017 5:54 pm, edited 3 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: 159
Location: Côtes d'Azur, France
23/03/17 MAJ labyrinthe for tests and add Classical A* algo to compare speed.
26/03/17 JPS improved: no need to test the parent's node direction.(1/8th faster now)

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


Last edited by Fig on Sun Mar 26, 2017 6:28 pm, edited 3 times in total.

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: 1633
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 2 guests


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