It is currently Tue Aug 22, 2017 6:28 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 5 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: 169
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: 169
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: 1637
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  
 Post subject: Re: Jump Point Search (Pathfinding)
PostPosted: Tue Aug 01, 2017 9:01 pm 
Offline
User
User
User avatar

Joined: Fri Mar 04, 2005 7:46 pm
Posts: 48
Location: argentina
ohh :D :D That's good, I'll take a look. I made one of my own, with the classic theory, but I use it in a city simulator, and end up doing strange things the cars and the people...
:? :oops:

_________________
Amd Vishera fx8350 ,16Gbram, Gtx650 ti, 2gb,Win 10pro. 13tbs. 8)


Top
 Profile  
Reply with quote  
 Post subject: Re: Jump Point Search (Pathfinding)
PostPosted: Wed Aug 02, 2017 6:23 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Thu Apr 30, 2009 5:23 pm
Posts: 169
Location: Côtes d'Azur, France
Pretty easy to test in your game:
Code:
Structure pt
  x.l
  y.l
EndStructure
Structure spt
  List spot.pt()
EndStructure
Define p.spt
Import "librairie jps.lib"
CreateArea(size.l) ;=>create a square area size (power of 2, ie 64, 128, 256, 512 etc...) large (For safety, a fence of walls around this area is create also. Be aware of that)
;If your map is 100x80, CreateArea(128) will be use and just add walls at lines 100 and 80 to make the area smaller.
AddWall(x.l,y.l) ;=>add a non traversable node
DeleteWall(x.l,y.l) ;=>make a node traversable
IsWall(x.l,y.l) ;=> Test obstacle presence (return 0/1)
JPS_Fast(sx.l,sy.l,gx.l,gy.l,*p.spt) ;=> process pathfinding from Point(sx,sy) to point(gx,gy). list of points in p\spot()\x,y (return 0 if no path exists)
EndImport

the Dlls x86: http://dl.free.fr/v7rgmbaeo

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


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 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