35Fermer
BaruchLe 24/05/2009 à 15:34
Je pense avoir trouvé un algo : un peu comme le A*...

Oué ! Ca marche ! Reste à optimiser quelques trucs.

Zut il ralentit quand même au bout d'un certain temps.

Allez, je le montre quand même : Download

{0,0->L2:Ans->L1 // L1 et L2 contiennent les abscisses et ordonnées des points à partir desquels il faut explorer
2->I // la taille de L1 (et L2), utile pour éviter des dim(L1) répétés

31->B:47->A // ce qui suit est la routine de déplacement du curseur
Repeat K=105
Pxl-Change(B,Ans
Repeat Ans
getKey->K
End
Pxl-Change(B,A
B+(Ans=34)-(Ans=25->B
A+(K=26)-(K=24->A
End

Pxl-On(B,Ans // Ans vaut A
Repeat I=1 // jusqu'à ce qu'il n'y ait plus de branches non explorées (eh oui, les listes vides n'existent pas)
{Ans,Ans+1,Ans,Ans-1->L3 // abscisse des points autour de la branche courante
{B-1,B,B+1,B->L4 // ordonnée
I-1->I // le point courant a été exploré, donc on l'enlève des listes
Ans->dim(L1
Ans->dim(L2
For(Z,1,4
If not(pxl-Test(L4(Z),L3(Z // s'il n'y a rien à côté, on déclare un nouveau point à explorer
Then
Pxl-On(L4(Z),L3(Z
augment(L2,{L4(Z->L2
augment(L1,{L3(Z->L1
I+1->I
End
End
L2(dim(L2->B // on choisit arbitrairement le point suivant à explorer
L1(dim(L1 // comme ça, Ans vaut A
End


Bon d'accord, il y a des défauts :

- on teste le point par lequel on est arrivé, mais bon le tester sans se poser de questions était plus rapide
- vers la fin du coloriage, on explore des points dont les points autour sont déja coloriés

On pourrait éviter les tests inutiles avec un système de balises :

(1) A chaque exploration : pour chaque point autour, s'il est balisé, on ne le teste pas ; pour le reste des points alentours non balisés et non coloriés, on en choisit un qu'on colorie, et on balise les autres.
Et ainsi de suite jusquà être "cerné" par des points balisés ou coloriés.
Là, on choisit un point balisé, on le teste et on recommence (1)
On recommence tout ça jusqu'à ce qu'il n'y ait plus de points balisés.

C'est cool en théorie, mais nul en pratique, puisque qu'il faudrait pouvoir rechercher un élément dans une liste (donc long), et en plus le pxl-Test est assez rapide pour pouvoir en gâcher quelques uns.

Bon, si on cherche à améliorer mon algo (très certainement améliorable) :

Ce qui ralentit le prog, c'est le nombre de points à explorer qu'on retient (càd la taille de L1 et L2), puisque je fais des dim(), des augment() (et ceux-ci sont lents) et des L1(). Donc si on veut minimiser la taille de ces listes, il faudrait "viser les collisions" avec les murs. Par exemple : je sais qu'il y a un mur à ma droite, j'avance, je commence par regarder s'il y a toujours un mur à ma droite, et même, s'il n'y en a pas, j'avance vers la droite pour essayer de le trouver (puisqu'on peut supposer que l'utilisation du prog est plus fréquente pour des dessins avec des lignes continues plutôt que des points épars).

Voilà ! Bon je vais voir si je peux appliquer quelques unes de mes idées.


Bon enfait j'ai trouvé beaucoup mieux ^^.