Fringe search plus rapide que A* [pathfinding]

[Fig]

Bonjour,
En faisant du trie (justement arf) j'ai retrouvé cela dans un fond de tiroir.

Le fringe search est une méthode intermédiaire entre IDA* et A*.
Il est très peu documenté (2 papiers à ce propos, le deuxième référençant le premier) et un article copier/coller sur wikipedia. Le reste des interventions sur des forums... Bein c'est moi avec divers pseudo arf.

L'intérêt est qu'il est sensé être plus rapide de 10% minimum à un bonne implémentation de A* (c'est un peu évasif je vous l'accorde) sur des octiles (cases à 8 voisins) et 20% plus rapide sur des Tiles (cases à 4 voisins); respectivement 25 à 40% sur un A* classique [ref: fringe search beating A* on game maps.pdf ou wikipedia]
La particularité du fringe search est qu'elle ne requiert pas de trier une liste. En contrepartie, elle examine plus de point mais passe peu de temps pour chacun d'entre eux. Contrairement à l'IDA* elle mémorise sa bordure et donc ne repart pas à zéro à chaque fois qu'il augmente sa limite.

Le principe parait plus naturel que celui du A*
Imaginez un front de flamme partant d'un point et avançant plus de plus en plus vite vers son objectif. Derrière c'est brulé, noir. Juste une bordure de flamme qui avance.

Bon, ce sera plus clair avec le programme.
Ce qu'il faut savoir c'est qu'il s'agit de mon interprétation du fringe search.
Il existe 3 pseudo-code mais je n'ai pas été capable de les implémenter tels qu'ils sont décrit.(erreur dans le pseudo code... ou je n'ai pas bien compris)
C'est pourquoi il est plus que probable que cette implémentation soit loin d'être optimale. (et possiblement vous pourriez avec un oeil neuf, l'améliorer) Je suis notamment peu satisfait de mon bricolage de fin pour augmenter artificiellement la limite.
A par cela, je n'ai trouvé aucune implémentation dans aucun langage.

Dans un autre programme, j'ai fait les benchmarks avec divers implémentation de A*. Mais permettez moi de garder un peu le suspens concernant les performances.

Dans tout les cas, cela pourrait éventuellement vous intéresser je l'espère.

Code : Tout sélectionner

;*****************************************
;****** Une implémentation du Fringe Search(?)*****
;******** Fig 12/01/2011*********************
;*****************************************
;* *******[clic droit] pour effacer un obstacle ******
;******* [clic gauche] pour placer un obstacle ******
;****** Après avoir placé le point de départ  *******
;****** et d'arrivée, incrémentez le path:[0] *******
;******* [escape] pour sortir******************
;******les noeuds avec un carré bleu sont dans****
;*******la "frange" le carré rouge est le noeud*****
;***************examiné. *******************
;*****************************************

If InitSprite() = 0 Or InitKeyboard()=0 Or InitMouse()=0:MessageRequester("Error","DirectX",0):EndIf
ExamineDesktops()
OpenScreen(DesktopWidth(0),DesktopHeight(0),DesktopDepth(0),"Pathfinding")
Structure ecran
  element.i
  liste.i ;pas necessaire
EndStructure
Dim carte.ecran(20,20)

;{ pathfinding
Structure noeud
  g.i
  *Liste
  cache.i
  parent_x.i
  parent_y.i
EndStructure
Dim noeud.noeud(20,20)
Structure XY
  X.i
  Y.i
EndStructure
NewList open.XY()
CreateSprite(0,50,50):StartDrawing(SpriteOutput(0)):Box(0,0,50,50,RGB(0,255,0)):Box(1,1,48,48,RGB(0,0,0)):StopDrawing()
CreateSprite(1,50,50):StartDrawing(SpriteOutput(1)):Box(0,0,50,50,RGB(0,255,0)):StopDrawing()
CreateSprite(2,50,50):StartDrawing(SpriteOutput(2)):Box(0,0,50,50,RGB(0,255,255)):StopDrawing()
CreateSprite(3,50,50):StartDrawing(SpriteOutput(3)):Box(0,0,50,50,RGB(255,255,0)):StopDrawing()
CreateSprite(4,50,50):StartDrawing(SpriteOutput(4)):Box(0,0,50,50,RGB(255,0,255)):StopDrawing()
CreateSprite(6,10,10):StartDrawing(SpriteOutput(6)):Box(0,0,10,10,RGB(0,0,255)):StopDrawing()
;fleche du curseur
CreateSprite(5,10,10):StartDrawing(SpriteOutput(5)):LineXY(0,0,9,9,RGB(255,255,255)):LineXY(0,0,4,0,RGB(255,255,255)):LineXY(0,0,0,4,RGB(255,255,255)):StopDrawing()
;}


Macro stop ;mets en pause la recherche de frange
  Repeat
    ExamineKeyboard()
    affiche
    If KeyboardPushed(#PB_Key_Escape):End:EndIf
  Until KeyboardPushed(#PB_Key_Pad0)
EndMacro
Macro affiche
  FlipBuffers()
  ClearScreen(RGB(0,0,0))
  ;affiche les cases
  For ix=1 To 14
    For iy=1 To 14
      DisplaySprite(carte(ix,iy)\element,ix*50,iy*50)
      If carte(ix,iy)\liste:DisplaySprite(6,ix*50+30,iy*50+30):EndIf
    Next iy
  Next ix
  ;affiche les informations de débuggage
  StartDrawing(ScreenOutput())
  For ix=1 To 14
    For iy=1 To 14
      If noeud(ix,iy)\cache
        DrawText(ix*50,iy*50+15,Str(noeud(ix,iy)\g)) ;affiche g
        DrawText(ix*50+15,iy*50,Str(noeud(ix,iy)\g+(Abs(x2-ix)+Abs(y2-iy))*100)) ;affiche f
        ;LineXY(ix*50+10,iy*50+10,noeud(ix,iy)\parent_x*50+25,noeud(ix,iy)\parent_y*50+25,RGB(255,0,0));affiche le lien avec les noeuds parents
        ;Box(ix*50+10,iy*50+10,5,5,RGB(255,0,0))
      EndIf
    Next iy
  Next ix
  
  Box(x*50+10,y*50+10,10,10,RGB(255,0,0)) ;noeud examiné
  DrawText(800,235,"nombre de noeuds examinés : "+Str(noeud))
  DrawText(800,250,"limite : "+Str(limite))
  DrawText(800,275,"f_mini : "+Str(f_mini))
  StopDrawing()
EndMacro
Macro souris ;affiche la souris
  ExamineMouse()
  X_souris=MouseX()
  Y_souris=MouseY()
  DisplayTransparentSprite(5,X_souris,Y_souris)
  ;mets un obstacle
  If MouseButton(#PB_MouseButton_Left)
    carte(X_souris/50,Y_souris/50)\element=1
  EndIf
  ;efface un obstacle
  If MouseButton(#PB_MouseButton_Right)
    carte(X_souris/50,Y_souris/50)\element=0
  EndIf
EndMacro

Arrivee_X=0:Arrivee_Y=0
Depart_X=0:Depart_Y=0
Repeat
  ExamineKeyboard()
  affiche
  souris
  XX=Int(X_souris/50)
  YY=Int(Y_souris/50)
  
  If KeyboardReleased(#PB_Key_F1) And carte(XX,YY)\element=0
    carte(Depart_X,Depart_Y)\element=0
    carte(XX,YY)\element=2
    Depart_X=XX
    Depart_Y=YY
  EndIf
  
  If KeyboardReleased(#PB_Key_F2) And carte(XX,YY)\element=0
    carte(Arrivee_X,Arrivee_Y)\element=0
    carte(XX,YY)\element=3
    Arrivee_X=XX
    Arrivee_Y=YY
    
    ;si on a placé un point de départ et d'arrivé, on commence
    If Depart_X And Depart_Y And Arrivee_X And Arrivee_Y
      ;remet à zéro la carte
      ClearList(open())
      For i=1 To 20
        For j=1 To 20
          noeud(i,j)\cache=0
          noeud(i,j)\Liste=0
          noeud(i,j)\parent_x=0
          noeud(i,j)\parent_y=0
          noeud(i,j)\g=0
        Next j
      Next i
      
      ;algo du fringe search adapté
      x1=Depart_X:x2=Arrivee_X:y1=Depart_Y:y2=Arrivee_Y
      ;ajoute le point de départ
      AddElement(open())
      open()\X=x1
      open()\Y=y1
      noeud(x1,y1)\liste=@open()
      noeud(x1,y1)\cache=1
      noeud(x1,y1)\g=0
      noeud(x1,y1)\parent_x=0
      noeud(x1,y1)\parent_y=0
      carte(x1,y1)\liste=1
      limite.i=(Abs(x2-x1)+Abs(y2-y1))*100
      chemin_ok=0:infini=limite:f_mini=limite
      
      While ListSize(open()) And chemin_ok=0
        ForEach open()
          stop
          x=open()\x
          y=open()\y
          g=noeud(x,y)\g
          f=g+(Abs(x2-x)+Abs(y2-y))*100 ;f=g+h
          If x=x2 And y=y2:chemin_ok=1:Break 2:EndIf ;chemin trouvé
          If f>limite:Continue:EndIf ;si le noeud est supérieur à la limite on l'examinera au prochain tour de liste
          If f<f_mini:f_mini=f:EndIf ; on se met de coté la valeur la plus petite pour qu'elle soit la limite du prochain tour de la liste
          
          *current=@open() ;on sauve l'adresse du noeud heureux papa de 8 fistons
          For j=-1 To 1;on expand le noeud examiné en inserant ses 8 fils dans la liste
            For i=-1 To 1
              stop
              xi=x+i
              yj=y+j
              If (i=0 And j=0) Or xi<1 Or yj<1 Or xi>14 Or yj>14 Or carte(xi,yj)\element=1:Continue:EndIf
              cout=100:If x<>xi And y<>yj:cout=114:EndIf
              gs.i=g+cout
              If noeud(xi,yj)\cache And gs>=noeud(xi,yj)\g:Continue:EndIf
              
              ;si le noeud est déja dans la frange, on le vire
              If noeud(xi,yj)\liste
                ChangeCurrentElement(open(),noeud(xi,yj)\Liste)
                DeleteElement(open())
                ChangeCurrentElement(open(),*current)
              EndIf
              AddElement(open()) ; on ajoute le fiston après son pere
              open()\X=xi
              open()\y=yj
              noeud(xi,yj)\liste=@open()
              noeud(xi,yj)\cache=1
              noeud(xi,yj)\g=gs
              noeud(xi,yj)\parent_x=x
              noeud(xi,yj)\parent_y=y
              carte(xi,yj)\liste=1 ;necessaire que pour l'affichage
              PreviousElement(open())
            Next i
          Next j
          ChangeCurrentElement(open(),*current) ;on reviens au pere et on l'efface
          DeleteElement(open())
          noeud(x,y)\liste=0
          carte(x,y)\liste=0
          limite=f_mini ;on update la limite pour le prochain tour de frange
        Next
        If oldlimite=limite ;si on a fait un tour complet dans avoir augmenté la limite
          limite+114         ;c'est que l'on est surement bloqué dans un minima contre un obstacle
        EndIf              ;on augmente nous même la limite
        oldlimite=limite
        f_mini=1000000
      Wend
    EndIf
  EndIf  
  
Until KeyboardPushed(#PB_Key_Escape)

[Fig]

Je vous livre le pseudo code, en espérant que vous en ferez bon usage...

Code : Tout sélectionner

Initialize:
Fringe F ← (s)
Cache C[start] ← (0, null),
C[n] ← null for n <> start
f limit ← h(start)
found ← false
Repeat until found = true or F empty
f min ← ∞
Iterate over nodes n ∈ F from left to right:
(g, parent) ← C[n]
f ← g + h(n)
If f > f limit
f min ← min(f, f min )
continue
If n = goal
found ← true
break
Iterate over s ∈ successors(n) from right to left:
g s ← g + cost(n, s)
If C[s] <> null
(g', parent) ← C[s]
If g s ≥ g'
continue
If F contains s
Remove s from F
Insert s into F after n
C[s] ← (g s , n)
Remove n from F
f limit ← f min
If found = true
Construct path from parent nodes in cache

un des probleme que j'ai rencontré est le suivant :flimit = fmin a la premiere iteration et est egale a infini par conséquent et pour toute les iterations. => gros probleme.
Bon je n'ai peut être pas tout compris j'espere que vous comprendrez mieux parcequ'il est plus sympa ce code... la limite se modifie comme une grande, mais ne semble pas prendre en compte les obstacles...

[dayvid]

Moi sa m'interesse beaucoup, merci je regarde ça

[SPH]

Je me suis penché sur le code et je n'ai pas compris le but de la manoeuvre. Explique clairement ce que ca doit faire entre le depart et l'arrivée (f1 et f2) !

[Fig]

Tu places des obstacles avec les clics de souris gauche et droit pour les effacer, puis tu places ton point de départ avec F1 et ton point d'arrivée avec F2 ensuite tu appuies gentiment sur la touche 0 (zéro) de ton clavier numérique pour que la recherche s'incrémente.

L'algo développe alors ses 8 premières cases voisines. Ensuite il recherche uniquement dans sa bordure les cases qui sont inférieurs à la valeurs f minimum.
Je le rappelle (comme dans A*) f est égal au cout depuis le point de départ jusque cette case, additionnée de la distance de Manhattan depuis cette case jusqu'à l'arrivé (c'est l'euristique ou heurisque ou h)
F=g(cout)+h(euristique)

Contrairement à A* il n'y a pas de liste ouverte et de liste fermé.
Avec A*, La liste ouverte doit être constamment trié ce qui occasionne un cout important de O(nlog(n) au minimum.

Ici il n'y a qu'une seule liste doublement chainée (du nom arbitraire de open() dans mon prog)
Le noeud en cours d'examen est le noeud courant.
Les noeuds placés après sont dans la liste NOW (maintenant)
Les noeuds placés avant sont dans la liste LATER (examinés plus tard)

Pour chaque noeud examiné, Si F de ce noeud est supérieur à la limite, le noeud est mis de coté, cad qu'on l'examinera au prochain tour de la liste. En clair, on se contente de passer au suivant. Du fait que c'est une liste chainée cette action passe le noeud derrière cad en liste LATER.
Si le noeud examiné est plus petit, on développe ses enfants et on les place dans la liste NOW cad qu'il vont être examiné immédiatement.

Quand on a passé en revu tous les noeuds, on recommence en augmentant la limite de f etc...

Voila en gros.

[SPH]

Ok, j'ai testé mais je ne peux pas dire si cette methode est la plus rapide. En gros, la question est : comment aller de A a B au plus court. J'ai tracé un petit graph legerement complexe et il a utilisé toutes les cases pour trouver, ce qui n'est pas 'bien'...

Mais la question est tres interessante et je sais qu'elle a deja ete posé sur le forum.

[Fig]

Il s'agit juste de montrer comment cela fonctionne, avec dans chaque case la visualisation des valeurs de F et G.
Il faut savoir que le fringe search examine autant de case que A*. La différence est qu'il n'examine que les cases en bordure cad celles qui sont marqué par un carré bleu, alors que A* trie TOUTES les cases.
Bref c'est assez nouveau mais bon, je pense que pour apprécier, il faut déjà être familiarisé avec les différents algos de pathfinding...

Je pensais faire aussi un poste concernant les différents moyens de réduire le graph d'exploration en utilisant des abstractions et encore un autre sur le pathfinding dans un univers dynamique (en tenant compte en 3eme dimensions, du temps)

Mais je réalise que probablement ça n'interresse pas grand monde

Je vous montrerai à quoi tout cela sert quand j'aurai fini.


@+

[dayvid]

Si si moi sa m'interesse même si j'y comprend rien , nan serieux

[SPH]

Si si moi sa m'interesse même si j'y comprend rien , nan serieux

Toi, TOUT t'interesse !

[dayvid]

Non SPH pas tous quand même

Mais certaines choses oui