Algo BMP->Multi Drawstat
Posté le 15/08/2018 23:40
Le sujet est apparu dans la shout, et je me suis dit qu'il y avait peut être possibilité de faire un algo potable. L'algorithme vise à obtenir la solution optimale (pas juste une solution potable).
On va prendre comme l'exemple le sprite de drak, avec uniquement la plus grosse partie :
(du coup il lui manque un oeil et une partie de sa carapace, mais shh.)
Il fait 32x32 px, et on vise un ordre de magnitude de quelques minutes.
On ne prend que le multi drawstat, car dans le super drawstat on doit aussi prendre en compte l'ordre de dessin.
L'algo fera :
0) Division du sprite en plusieurs parties qui ne se touchent pas, et calcul séparé de chacune de ces parties
1) Recensement de chaque point noir du sprite (à la louche, on va dire qu'il y en a 256, soit 1/4 des pixels)
2) Traçage de chaque ligne existante entre chaque point (soit 256*255 = ~65000 ce qui est faisable)
3) Parmi les lignes tracées, ne retenir que celles qui ne traversent que des pixels noirs
On devrait obtenir environ 1000 lignes (au pif total).
4) Parmi les lignes tracées, enlever celles qui sont totalement incluses dans une et une seule ligne, et qui ne voisinent pas d'autres lignes :
On enlève donc la ligne verte (car totalement incluse dans la ligne rouge) :
Par contre, on n'enlève pas la ligne verte ici, parce qu'elle pourrait faire partie de la solution optimale (elle est voisine à une autre ligne) :
5) Parmi les lignes qui restent, enlever celles qui sont superposées (comme on trace les lignes dans les 2 sens, ce qui est obligé car avec l'algo de brezenham ça ne donne pas les mêmes résultats, on peut avoir des lignes verticales ou horizontales superposées)
6) La partie la plus consommatrice : calculer (avec un algo magique) le nombre de lignes minimum pour couvrir tout le sprite.
On a ensuite uniquement besoin de trouver un groupement de lignes qui est égal au nombre de lignes minimum et qui couvre tout le sprite (ça doit se faire assez simplement).
Pour optimiser cette partie, on ne peut pas enlever les lignes qui se superposent. Par exemple, dans ce sprite, la solution optimale contient deux lignes qui se superposent :
La seule optimisation qui me vient à l'esprit est de ne prendre que les groupements qui couvrent tout le sprite. Par contre pour faire ça sans itérer sur chaque groupement (qui, pour 500 lignes, est de l'ordre de 2^500 = 10^150 = quand même beaucoup) aucune idée.
Du coup faudrait implémenter cet algo afin de voir les lignes qui restent à l'étape 6, voir si c'est faisable
Citer : Posté le 19/08/2018 16:25 | #
Par contre il faudrait si possible mettre ça dans un exécutable (que ce soit en exe ou en elf) : je vais pas demander aux utilisateurs d'installer python ainsi que les modules complémentaires
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 19/08/2018 16:31 | #
Ne te dégonfle pas Darks, un port en C++ ira statistiquement 40 ou 60 fois plus vite, c'est une occasion en or !
Citer : Posté le 19/08/2018 16:33 | #
Si tu fais ça, tu peux prendre ces arguments dans le main :
Comme ça c'est BIDE (ou pour tes tests, un script python) qui s'occupe de traiter l'image et de la convertir en liste de pixels.
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 19/08/2018 16:39 | #
Si tu arrives à faire un programme C/C++ qui prend ça comme arguments, Zezombye, je te tire mon chapeau.
Citer : Posté le 19/08/2018 17:06 | #
Ne te dégonfle pas Darks, un port en C++ ira statistiquement 40 ou 60 fois plus vite, c'est une occasion en or !
Je répète, le code est sous licence CeCILL, donc n'importe qui peut faire un port en C/C++. Perso ça me gonfle de le faire, donc je reste sur la version Python
Citer : Posté le 19/08/2018 18:05 | # | Fichier joint
J'ai fini de tracer au dessus du sprite, j'ai fait 70 lignes. Je pense que j'aurais pu optimiser à un endroit ou 2, donc je dirais que la solution optimale est dans les 68-69 lignes.
Je n'accepterai qu'un algo qui me donne un nombre de lignes inférieur ou égal au mien
Mouahaha
Pour info @Zezombye, ton sprite simplifié, voilà le résultat. Convaincu ?
Graph(X,Y)=({16-2T, 7-7T, 11-11T, 5-5T, 17-11T, 14-6T, T, 31-31T, 20-26T, 9-10T, 21-31T, 26-27T, 17-23T, 9-8T, 12-18T, 7-14T, 27-36T, 29-34T, 4-4T, 4+4T, 26-22T, 16-11T, 18-19T, 28-25T, 23-26T, 15-20T, 12-17T, 9-15T, 22-20T, 14-15T, 1, 29-32T, 25-24T, 21-17T, 25-27T, 23-27T, 12-14T, 10-14T, 27-26T, 25-24T, 9-8T, 2T, 2-4T, 26-30T, 14-18T, 26-31T, 22-27T, 19-21T, 30-30T, 29-29T, 17-17T, 14-14T, 13-13T, 12-12T, 6-6T, 2-2T}, {24-25T, 19-30T, 19-29T, 18-27T, 22-30T, T, 9-T, 16-23T, 13-6T, 8-T, 25-27T, 11-17T, 9-15T, 19-25T, 21-21T, 4+T, 25-27T, 19-19T, 18-23T, 20-23T, 5-2T, 26-32T, 11-5T, 23-31T, 12-9T, 22-20T, 4-4T, 12-5T, 18-19T, 18-16T, 9-7T, 16-13T, 22-18T, 15-17T, 6-10T, 24-28T, 15-11T, 8-8T, 23-25T, 19-21T, 15-17T, 11-12T, 13-13T, 12-9T, 4T, 25-30T, 25-27T, 15-21T, 24-24T, 18-18T, 27-27T, 17-17T, 24-24T, 18-18T, 14-14T, 18-18T})
Citer : Posté le 19/08/2018 18:09 | #
Je trouve impressionnant que ça trouve des diagonales comme les deux rougeâtres au milieu du sprite. Je pense que sur une plus longue distance, elle serait évidente pour un humain, mais pas sur un truc aussi court, ça paraît trop irrégulier pour être une droite, à priori, pour un œil humain.
Citer : Posté le 19/08/2018 18:49 | # | Fichier joint
Dark Storm a fait un GIF, il a supprimé son post, le GIF étant un peu lent
Et en plus rapide :
Citer : Posté le 19/08/2018 21:16 | #
Super, ce gif ! Il pourrait très bien servir de démonstration pour montrer la puissance et l'efficacité de cet algorithme !
Citer : Posté le 19/08/2018 21:23 | #
C'est déjà le cas sur le topic officiel
Citer : Posté le 12/09/2018 00:04 | #
Je up ce topic pour demander : Est-ce envisageable d'avoir un algo BMP -> SuperDrawstat ?
Citer : Posté le 12/09/2018 06:17 | #
Ça je me suis penché sur la question plus personnellement, et c'est sans doute possible, mais plus difficile... à causer du coût de lever le crayon on doit parfois privilégier des lignes plus surprenantes, j'envisage un critère de sélection hybride longueur/tracé, mais je n'ai pas encore essayé de mettre la méthode au test.
Citer : Posté le 12/09/2018 13:45 | #
Je suis très intéressé par tes avancées à ce sujet. Si tu en trouves l'occasion, peut-être pourrais-tu ouvrir un topic à ce sujet ?
Citer : Posté le 12/09/2018 18:28 | #
Avec plaisir, mais tu sembles avoir trouvé mieux toi-même.
Citer : Posté le 12/09/2018 18:29 | #
J'ouvre un topic.