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 18/08/2018 18:11 | #
Le cardinal de l'ensemble, soit le nombre de lignes dans la solution.
Citer : Posté le 18/08/2018 18:12 | #
ou alors la valeurs absolue de S
Citer : Posté le 18/08/2018 18:24 | #
Ok, convaincu alors
ou alors la valeurs absolue de S
Citer : Posté le 18/08/2018 19:21 | # |
Fichier joint
C'est peut-être pas optimal, mais précisément 19 secondes sur ma machine, j'obtiens ce qui suit. Je pense que les logs sont suffisamment clairs.
Concernant les couleurs, elles sont générées aléatoirement, désolé, si c'est pas hyper beau.
Get lines: complete
4589 lines found
Remove double lines: complete
2945 lines kept
Remove useless lines: complete
771 lines kept
Draw: complete
Solution found in 75 lines
=================================================
(30, 25) (16, 26)
(7, 21) (7, 10)
(11, 21) (11, 11)
(5, 20) (5, 11)
(23, 16) (17, 24)
(22, 3) (14, 2)
(1, 19) (0, 11)
(31, 18) (31, 11)
(22, 27) (11, 25)
(20, 15) (14, 22)
(10, 21) (8, 14)
(27, 27) (17, 25)
(26, 11) (24, 5)
(17, 11) (11, 5)
(12, 23) (6, 23)
(10, 17) (9, 11)
(7, 6) (0, 11)
(31, 17) (28, 25)
(12, 19) (4, 22)
(4, 20) (4, 15)
(30, 10) (26, 7)
(29, 21) (24, 21)
(22, 23) (16, 28)
(19, 17) (17, 11)
(2, 24) (0, 28)
(23, 14) (20, 17)
(16, 15) (13, 13)
(15, 24) (10, 26)
(12, 6) (7, 6)
(11, 8) (8, 8)
(10, 10) (6, 10)
(29, 22) (25, 26)
(29, 18) (26, 21)
(26, 14) (26, 10)
(25, 15) (21, 17)
(24, 19) (22, 20)
(23, 26) (19, 22)
(22, 11) (22, 9)
(21, 22) (26, 28)
(18, 7) (16, 5)
(15, 12) (13, 14)
(14, 22) (14, 19)
(13, 28) (12, 30)
(12, 20) (11, 12)
(11, 14) (3, 21)
(6, 26) (5, 28)
(2, 28) (0, 26)
(2, 13) (1, 10)
(26, 19) (25, 21)
(20, 15) (17, 17)
(19, 27) (19, 24)
(16, 15) (14, 16)
(16, 5) (14, 5)
(15, 12) (13, 12)
(14, 2) (10, 6)
(13, 10) (11, 8)
(12, 18) (4, 15)
(2, 15) (0, 15)
(1, 13) (1, 10)
(31, 18) (28, 21)
(30, 26) (30, 25)
(26, 28) (25, 24)
(25, 26) (13, 26)
(24, 29) (24, 29)
(24, 15) (18, 22)
(23, 4) (25, 8)
(21, 29) (21, 29)
(19, 7) (19, 7)
(17, 29) (16, 28)
(17, 19) (12, 23)
(14, 28) (14, 28)
(12, 20) (8, 21)
(12, 17) (4, 17)
(4, 22) (1, 19)
(2, 28) (1, 29)
=================================================
Done!
Citer : Posté le 18/08/2018 19:25 | #
Citer : Posté le 18/08/2018 19:25 | #
Wow, bien joué ! Je pense que l'une des parties les plus complexes correspond aux zones de noir : les yeux, le sol et surtout la bouche. Je suis impressionné par ce que ton algorithme a produit !
Citer : Posté le 18/08/2018 19:39 | #
T'as vérifié sur la machine que le code produit bien le même dessin ?
Citer : Posté le 18/08/2018 19:40 | #
Zou, enjoy ! https://git.planet-casio.com/Dark-Storm/sprite-optimizer
Le code est sûrement largement optimisable, je ne pense pas revenir dessus à part pour faire un readme, donc servez-vous.
On va dire que c'est sous CeCILL 1.2
Ajouté le 18/08/2018 à 19:41 :
T'as vérifié sur la machine que le code produit bien le même dessin ?
Non, pas encore, mais j'ai vérifié que l'algo de Bresenham utilisé produisait bien les mêmes résultats.
Je vais tester on-calc
Ajouté le 18/08/2018 à 20:39 :
Bon, il se trouve que c'est long de recopier à la main, y'a quelqu'un qui peut me dire ('avec BIDE tiens par exemple) ce que ce code donne ?
G-Connect
Graph(X,Y)=({30-14T, 7+0, 11+0, 5+0, 23-6T, 22-8T, 1-1T, 31+0, 20-6T, 10-2T, 21-10T, 26-2T, 17-6T, 12-6T, 10-1T, 7-7T, 27-9T, 29-5T, 4+0, 12-8T, 30-4T, 2-2T, 21-5T, 19-2T, 31-3T, 23-3T, 16-3T, 11-3T, 10-4T, 15-5T, 12-5T, 25+1T, 24-2T, 22+0, 18-2T, 15-2T, 13-1T, 13+1T, 6-1T, 2-2T, 2-1T, 29-3T, 29-4T, 23-4T, 8-5T, 21+5T, 12-1T, 26-1T, 23+1T, 16-2T, 16-2T, 15-2T, 13-2T, 2-2T, 2-2T, 25-3T, 20-3T, 14-4T, 9-4T, 20-7T, 30+0, 29+0, 26+0, 24+0, 23+0, 21+0, 21+0, 19+0, 17+0, 14+0, 14+0, 9+0, 6+0, 2+0, 1+0}+10, {25+1T, 21-11T, 21-10T, 20-9T, 16+8T, 3-1T, 19-8T, 18-7T, 15+7T, 21-7T, 27-2T, 11-6T, 11-6T, 23+0, 17-6T, 6+5T, 27-2T, 21+0, 20-5T, 19+3T, 10-3T, 24+4T, 22+6T, 17-6T, 17+8T, 14+3T, 15-2T, 8+0, 10+0, 24+2T, 6+0, 15-2T, 19+1T, 11-2T, 7-2T, 12+2T, 28+2T, 22-2T, 26+2T, 28-2T, 13-2T, 18+3T, 22+4T, 26-4T, 16+5T, 22+6T, 20-8T, 19+2T, 14+2T, 15+1T, 5+0, 12+0, 10-2T, 15+0, 12+2T, 24+3T, 15+2T, 2+4T, 18-3T, 25+1T, 26+0, 20+0, 12+0, 29+0, 4+0, 29+0, 17+0, 7+0, 29+0, 28+0, 19+0, 21+0, 17+0, 20+0, 29+0}+10)
Citer : Posté le 18/08/2018 21:10 | # |
Fichier joint
Fais attention à ton ViewWindow, ton Tθmin doit être à 0. Enfin, j'ai dû rajouter le Tθmin et max pour que ça marche.
Voici le résultat de ton algo, DS. Tu n'es pas loin, mais... Ce ver-la semble un peu plus triste que l'original
Citer : Posté le 18/08/2018 21:13 | #
Un rapide coup d'oeil à ses tests précédents me laisse entendre que son programme trace exactement ce qu'il faut, mais qu'il a utilisé en fichier d'entrée un sprite différente du tien. (Ou alors sa fonction pour lire l'image ne renvoie pas tout à fait ce qu'il faut.)
Citer : Posté le 18/08/2018 21:24 | #
Ah, peut-être le sens du Bresenham. J'avais pas vérifié le sens.
Quid de ce code ?
Citer : Posté le 18/08/2018 21:57 | # |
Fichier joint
Toujours pas.
Citer : Posté le 18/08/2018 22:53 | #
Ah putain, fait iech. Ok j'ai compris. Je m'explique :
Casio utilise l'algorithme de Bresenham pour tracer ses traits. Sauf que… le dessin est inversé par rapport à toutes les libs que j'ai testées. C'est à dire que [python] line(x1, y1, x2, y2) et [python] bresenham(x1, y1, x2, y2) vont renvoyer le même résultat, mais qui correspondra à [casio] F-Line x2, y2, x1, y1. Une histoire de pixel près. C'est pareil pour toutes les fonctions Casio (dont GraphXY).
Tout ça pour dire que dans mon code, je fais gaffe à bien inverser le bresenham quand je génère les traits, sauf que je garde que celui qui est "à l'endroit", à savoir celui qui n'est pas tel que Casio le dessine. Donc ça veut dire qu'il faut que j'inverse le sens au moment non pas de garder les traits, mais au moment de générer le code pour Casio.
Si ma théorie est ok, ce code devrait produire un truc correct
Citer : Posté le 18/08/2018 23:32 | # |
Fichier joint
Oui mais non. Le dessin est parfait, vraiment ! Seulement... Il a la tête à l'envers.
Citer : Posté le 18/08/2018 23:37 | #
Bah t'inversera le VW
Il est à combien sur ce test ?
Citer : Posté le 18/08/2018 23:39 | #
Oh hell no.
Bah comme d'hab', quoi. Les paramètres normaux. J'ai juste décalé vers la gauche m'enfin bon.
Citer : Posté le 18/08/2018 23:40 | #
Haha
nickelCiter : Posté le 18/08/2018 23:41 | #
Nan mais comme d'hab ça veut dire 1, 127, 0, 1, 63, 0 ou 1, 127, 0, 63, 1, 0 ? Je te rappelle que moi le (0, 0) il est en haut à gauche.
Citer : Posté le 18/08/2018 23:53 | #
Ah.
Citer : Posté le 19/08/2018 00:01 | #
Si c'est juste une question de flip, ça se règle facilement, mais faut qu'on se mette d'accord sur les origines
Citer : Posté le 19/08/2018 00:57 | # |
Fichier joint
Parce que je le vaut bien. Le gif est un peu long, y'a 56 sprites de différents types