It is currently Sun Oct 22, 2017 6:11 pm

All times are UTC + 1 hour




Post new topic Reply to topic  [ 9 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: 187
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: 187
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: 1682
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: 187
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  
 Post subject: Re: Jump Point Search (Pathfinding)
PostPosted: Wed Aug 23, 2017 11:19 am 
Offline
New User
New User

Joined: Wed Aug 23, 2017 11:16 am
Posts: 4
Thanks JPS is really fast
Is it stable to be used for our games? Can you give a quick hint on how to avoid it from clinging/hugging wall to make it more natural?


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

Joined: Thu Apr 30, 2009 5:23 pm
Posts: 187
Location: Côtes d'Azur, France
As far as i know, it's stable on my computer, but i actually didn't test it on several configurations.
The asm parts are kind of tricky... Who knows ?

JPS doesn't use elaborate attractive/repulsive map.
In that case, you'll need to use a standard A* implementation which is slower but more flexible for different purposes. (not only pathfinding)
Notice, the path follows walls only if it turns later in that direction. if area are wide opens, it goes straight through.

_________________
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: Wed Aug 23, 2017 8:18 pm 
Offline
New User
New User

Joined: Wed Aug 23, 2017 11:16 am
Posts: 4
By the way I used directly the code and not the compiled dll.
I'm trying to update the wall data on real-time and check if route is possible but encounter same error.
It works if I don't update the wall data.

Here's how i did.
Quote:
CreateArea(512) ; init area

;update/change all wall data in real-time captured from camera
while quit = #false
for y = 0 to 399
for x = 0 to 399
if screenblock(x,y) = #black
addwall(x,y)
else
deletewall(x,y)
endif

; check if path is possible on given point
if JPS_Fast(50,50,60,60,@s.spt)
debug "found path"
quit = #true
endif
next
next
wend



I always get this error from this part.
Quote:
Procedure.l gauche_Fast(x.l,y.l,*area_1,Gx.l,Gy.l)
EnableASM
MOV ebx,dword [p.v_x]
MOV eax,dword [p.v_y]
DEC eax ;passe à la ligne Above
MOV edi,dword [v_largeur] ;nb d'octets par ligne
MOV esi,dword [p.p_area_1]
MUL edi
PUSH eax ;eax=y*nbligne
XOR edx,edx
MOV eax,ebx
MOV ebp,8
DIV ebp ;divise par x/8 eax result, edx reste cad le nombre de bit à décaler
POP ebx ;ebx=y*nbligne
ADD eax,ebx ;eax=x/8+y*nbligne
ADD esi,eax ;esi=eax+adress de base
SUB esi,3 ;recule de 3 octets
MOV ecx,7 ;reste ecx et edx complément à 7
SUB ecx,edx
XOR ebp,ebp ;met à zero le total de déplacement
!_bouclette2:
;Above EAX
PUSH ebp ;sauvegarde le déplacement total
PUSH esi ;sauvegarde esi pour boucler sur l'adresse de l'emplacement... Vérifier si nécessaire !!!!!
MOV eax,dword [esi] ;charge les 32 bits Above
BSWAP eax ;remets les octets dans l'ordre
SHR eax,CL ;décale jusqu'a ce qu'on soit aligné pour la ligne du dessus
MOV ebx,eax
NOT ebx ; !B
SHL eax,1 ;<<1
AND eax,ebx ;B<<1 & !B
SHL eax,cl


Top
 Profile  
Reply with quote  
 Post subject: Re: Jump Point Search (Pathfinding)
PostPosted: Thu Aug 24, 2017 10:13 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Thu Apr 30, 2009 5:23 pm
Posts: 187
Location: Côtes d'Azur, France
You can't/shouldn't delete a wall on the 0 and 511 row/column.
The area has to be surrounded by a wall all the time.(it saves boundaries tests) So you can only use 1->510 cells.

Maybe it's the problem here as you update the x=0 and y=0 (?)

Also,for performance purpose, i suggest you record walls that change and update that specifics cells, not all of them.
But It shouldn't be an issue.

Thank you for testing. :D

_________________
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  [ 9 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