4Fermer6
gon33Le 25/05/2009 à 11:15
Baruch (./4) :
Je pense avoir trouvé un algo : un peu comme le A*...

C'est quoi le A*???

Bon, va falloir que je regarde ce que donne ton programme sur calto... Dans la théorie, ça marche assez bien! Mais dans la pratique, normalement c'est moins bien.
En fait, t'as implémenté une Pile; c'est à dire un conteneur de type LIFO (Last In, First Out). C'est une structure valable pour ce programme, mais il y en a une qui permet d'éviter plus les collisions (je te laisse encore chercher un peu^^). D'ailleur, je pense que ça va planter pour des zones très grandes (sur le mien, ça utilisait à peu près trois fois moins de mémoire que le nombre de points à colorier, mais ça plantait quand même).

Baruch (./4) :
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).



En fait le système d'ajout à la liste ralentit ton programme:

Quand tu fais augment(...), tu copies la première liste en mémoire; puis la deuxième; et ensuite le token s'exécute, donc le temps d'exécution est à peu près proportionnel à la somme des tailles de listes. Enfin bref, plus ta liste grossit et plus l'exécution est lente.

En fait, ce que tu veux faire, c'est mettre une seule valeur au bout de ta liste; donc tu peux faire : L4(Z) -> L2(Dim(L2)+1
Ou beaucoup mieux, tu stockes la taille des listes dans une variable que tu incrémente de temps en temps... (comme pour I)
Je pense pas que ce soit utile de réduire la taille de ta liste quand tu as examiné un point; en fait, si tu ne fais que décrémenter l'indice, ça suffit (sinon, quand tu la réincrémente, le programme doit de nouveau chercher et allouer des zones mémoires à utiliser, et ça peut être lent).
Baruch (./4) :
(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.


En théorie ça marche bien en fait! Il suffit de faire ça dans une matrice; et de stocker en plus la liste des points balisés dans une autre structure de données (une pile par exemple). Donc tu dois gérer deux structures de données, mais tu as un accès rapide aux infos... Sauf que tu peux pas faire ça sur Ti, parce que ça te prend trop de place une matrice...