Algo Cercle Andres/Bresenham

[Fig]

Bon, j'ai fait une petite recherche sur le fofo et je constate que cela à déjà été discuté ici (en tout cas en ce qui concerne Bresenham)

Voila l'utilisation que j'en fais:

Pour un jeu (rts par exmple) nécessitant une recherche autour d'un personnage ou d'un bâtiment. (et si l'élément recherché ne peut pas l'être en itérant une liste contenant cet élément ou si cette liste est plus longue que le nombre de case à explorer par exemple)
Ou encore pour révéler la carte autour d'un personnage, d'un nombre de x cases (en fonction de la limite de vue du personnage)

Le problème du tracé de cercle de Bresenham est qu'il n'est pas couvrant (il "rate" des cases). L'algo d'Andres au contraire n'en rate aucune et ne repasse pas deux fois au même endroit. C'est lui qu'il faut utiliser

En ce qui concerne l'algo de traçage de ligne de Bresenham, il est très utile pour ce qui est de la réduction de nombre de noeud d'un pathfinding.

Code : Tout sélectionner

Structure XY
  X.i
  Y.i  
  coul.i
EndStructure
Global NewList Cercle_Bresenham.XY()
Global NewList Cercle_Andres.XY()

;algorithme de tracé de cercle de Bresenham
Procedure TracerCercleBresenham(rayon,x_centre,y_centre,coul)
   y=rayon ;    // on se place en haut du cercle 
   m=5-4*rayon ;      // initialisation
   While x <= y;    // tant qu'on est dans le second octant
     AddElement(cercle_bresenham())
     cercle_bresenham()\x=x+x_centre:cercle_bresenham()\y=y+y_centre:Cercle_Bresenham()\coul=coul
     AddElement(cercle_bresenham())
     cercle_bresenham()\x=y+x_centre:cercle_bresenham()\y=x+y_centre:Cercle_Bresenham()\coul=coul
     AddElement(cercle_bresenham())
     cercle_bresenham()\x=-x+x_centre:cercle_bresenham()\y=y+y_centre:Cercle_Bresenham()\coul=coul
     AddElement(cercle_bresenham())
      cercle_bresenham()\x=-y+x_centre:cercle_bresenham()\y=x+y_centre:Cercle_Bresenham()\coul=coul
      AddElement(cercle_bresenham())
      cercle_bresenham()\x=x+x_centre:cercle_bresenham()\y=-y+y_centre:Cercle_Bresenham()\coul=coul
      AddElement(cercle_bresenham())
      cercle_bresenham()\x=y+x_centre:cercle_bresenham()\y=-x+y_centre:Cercle_Bresenham()\coul=coul
      AddElement(cercle_bresenham())
      cercle_bresenham()\x=-x+x_centre:cercle_bresenham()\y=-y+y_centre:Cercle_Bresenham()\coul=coul
      AddElement(cercle_bresenham())
      cercle_bresenham()\x=-y+x_centre:cercle_bresenham()\y=-x+y_centre:Cercle_Bresenham()\coul=coul
      If m > 0 ;choix du point F
      y - 1
     m=m-8*y
      EndIf
      x+1 ;
      m=m + 8*x+4 ;
   Wend
EndProcedure

;algorithme de tracé de cercle d'Andres
Procedure TracerCercleAndres(rayon,x_centre,y_centre,coul)
y=rayon
d=rayon - 1
While y>=x 
     AddElement(cercle_Andres())
     Cercle_Andres()\x=x+x_centre:Cercle_Andres()\y=y+y_centre:Cercle_Andres()\coul=coul
     AddElement(Cercle_Andres())
     Cercle_Andres()\x=y+x_centre:Cercle_Andres()\y=x+y_centre:Cercle_Andres()\coul=coul
     AddElement(Cercle_Andres())
     Cercle_Andres()\x=-x+x_centre:Cercle_Andres()\y=y+y_centre:Cercle_Andres()\coul=coul
     AddElement(Cercle_Andres())
      Cercle_Andres()\x=-y+x_centre:Cercle_Andres()\y=x+y_centre:Cercle_Andres()\coul=coul
      AddElement(Cercle_Andres())
      Cercle_Andres()\x=x+x_centre:Cercle_Andres()\y=-y+y_centre:Cercle_Andres()\coul=coul
      AddElement(Cercle_Andres())
      Cercle_Andres()\x=y+x_centre:Cercle_Andres()\y=-x+y_centre:Cercle_Andres()\coul=coul
      AddElement(Cercle_Andres())
      Cercle_Andres()\x=-x+x_centre:Cercle_Andres()\y=-y+y_centre:Cercle_Andres()\coul=coul
      AddElement(Cercle_Andres())
      Cercle_Andres()\x=-y+x_centre:Cercle_Andres()\y=-x+y_centre:Cercle_Andres()\coul=coul
   If d >= 2*x
      d=d-2*x-1
      x+1
   ElseIf d <= 2*(rayon-y)
      d=d+2*y-1
      y-1   
   Else 
      d=d+2*(y-x-1)
      y-1
      x+1
  EndIf
Wend
EndProcedure

If InitSprite() = 0 Or InitKeyboard() = 0
  MessageRequester("Error", "Sprite system can't be initialized", 0)
  End
EndIf
OpenScreen(640,480,32,"test")
ClearScreen(RGB(0,0,0))

;calcul 50 cercles concentriques avec les 2 méthodes, en incrémentant le rayon
For i=1 To 100
   coul=RGB(Random(255,40),Random(255,40),Random(255,40))
TracerCercleAndres(i,100,160,coul)
TracerCercleBresenham(i,360,160,coul)
Next i

Repeat
   FlipBuffers()
StartDrawing(ScreenOutput())
;trace les cercles calculés avec Bresenham (en vert)
ForEach  cercle_bresenham()
Plot(cercle_bresenham()\x,cercle_bresenham()\y,Cercle_Bresenham()\coul) 
Next
;trace les cercles calculés avec Andres (en jaune)
ForEach  cercle_Andres()
Plot(cercle_Andres()\x,cercle_Andres()\y,Cercle_Andres()\coul) 
Next
StopDrawing()
  ExamineKeyboard()
Until KeyboardPushed(#PB_Key_Escape)

[djes]

Plantouille grave ici

[SPH]

Ca clignote grave

[Fig]

Lol coool Faut changer la résolution, désolé....

Ou mettre en fenêtré...
OU tracer dans un sprite et l'afficher..; bref ce n'était pas vraiment mon inquiétude l'affichage désolé

[djes]

C'est bon, ça fonctionne en 800x600. L'algo de bresenham modifié permet de n'avoir que deux points par ligne, et donc facilite le remplissage entre ces deux points. Chacun ses avantages... My two cents

[Fig]

Arf, évidement, dis comme cela... Il ne s'agit pas de révolutionner le tracé de cercle sur un écran.

Seulement pour déterminer dans une grille de jeu la proximité d'un autre objet, c'est idéal je trouve

[djes]

Sans doute!

[Backup]

Arf, évidement, dis comme cela... Il ne s'agit pas de révolutionner le tracé de cercle sur un écran.

Seulement pour déterminer dans une grille de jeu la proximité d'un autre objet, c'est idéal je trouve

dans cette utilisation precise, je ne suis pas sur de l'utilité

en effet, dans un jeu , en principe on sait toujours ou ce trouve les "objets"
puisque par principe s'il sont a l'ecran, c'est qu'on les y a mis

donc on a leur coordonnées ... non ?

ou j'ai loupé un épisode

[Fig]

Pour un jeu (rts par exmple) nécessitant une recherche autour d'un personnage ou d'un bâtiment. (et si l'élément recherché ne peut pas l'être en itérant une liste contenant cet élément ou si cette liste est plus longue que le nombre de case à explorer par exemple)
Ou encore pour révéler la carte autour d'un personnage, d'un nombre de x cases (en fonction de la limite de vue du personnage)

Je me quote moi-même (le comble du narcissisme )

Un exemple concret: Un de tes bucheron a épuisé la ressource de bois qu'il exploitait.
Dans le cas où tu as bien fait les choses, tu as une grille (ou une table de hachage, n'est ce pas) qui contient chacun de tes arbres (de tous les éléments du jeu d'ailleurs, c'est la carte quoi) , et une liste qui contient chacun de tes arbres et leurs coordonnées sur la grille.
Dans ce cas, soit tu prend la coordonnée de ton bucheron puis tu fais une recherche dans la liste des arbres en mesurant la distance séparant le bucheron et chacun des arbres. Soit tu prend les coordonnées du bucheron et tu testes les cases environnantes en fonction de sa limite de vue.
Si le personnage a une ligne de vue de rayon 5 ( c'est une nombre de cases) par exemple, il est plus rapide de tester ces dizaines cases que de passer en revue la liste des arbres de la carte (car dans mon cas par exemple il y a des milliers d'arbres sur la carte)

[G-Rom]

+1 fig !
j'ai hâte de voir ce que tu vas non pondre !

[Fig]

non pondre !

Lapsus (?) révélateur j'en ai peur On verra quand se sera assez propre pour le montrer.