Seuls les membres ayant 30 points peuvent parler sur le chat.

Forum Casio - Projets de programmation


Index du Forum » Projets de programmation » Algo BMP->Multi Drawstat
ZezombyeHors ligneRédacteurPoints: 1625 Défis: 12 Message

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


Pages : Précédente1, 2, 3, 4, 5Suivante
LephenixnoirHors ligneAdministrateurPoints: 15740 Défis: 136 Message

Citer : Posté le 18/08/2018 18:11 | #


Le cardinal de l'ensemble, soit le nombre de lignes dans la solution.
Shadow15510Hors ligneAdministrateurPoints: 3782 Défis: 15 Message

Citer : Posté le 18/08/2018 18:12 | #


ou alors la valeurs absolue de S
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Moral
   95%
NinestarsHors ligneMembrePoints: 2253 Défis: 22 Message

Citer : Posté le 18/08/2018 18:24 | #


Ok, convaincu alors
Shadow a écrit :
ou alors la valeurs absolue de S
La valeur absolue à un sens pour les nombres, là S n'est pas un nombre
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

Citer : Posté le 18/08/2018 19:21 | # | 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


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.



305 black pixels over 1024 (29.8%)
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!

Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
NinestarsHors ligneMembrePoints: 2253 Défis: 22 Message

Citer : Posté le 18/08/2018 19:25 | #


DrakHors ligneRédacteurPoints: 1925 Défis: 38 Message

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 !
Eon the Dragon : version 1.2
Let's have a look!
Marre de ces RPGs qui t'imposent des classes, des compétences et des sorts ? Crée tes propres capacités sur Eon the Dragon ! Des monstres, des dragons et des combats aussi épiques que difficiles t'attendent !
Un RPG unique et immense t'attend ! Joue dès maintenant à Aventura, le Royaume Poudingue !
Vous aussi, soyez swag et rejoignez Planète Casio !
LephenixnoirHors ligneAdministrateurPoints: 15740 Défis: 136 Message

Citer : Posté le 18/08/2018 19:39 | #


T'as vérifié sur la machine que le code produit bien le même dessin ?
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

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 :
Lephenixnoir a écrit :
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 ?

ViewWindow 1,127,0,63,1,0,1,1
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)

Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
DrakHors ligneRédacteurPoints: 1925 Défis: 38 Message

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

Eon the Dragon : version 1.2
Let's have a look!
Marre de ces RPGs qui t'imposent des classes, des compétences et des sorts ? Crée tes propres capacités sur Eon the Dragon ! Des monstres, des dragons et des combats aussi épiques que difficiles t'attendent !
Un RPG unique et immense t'attend ! Joue dès maintenant à Aventura, le Royaume Poudingue !
Vous aussi, soyez swag et rejoignez Planète Casio !
LephenixnoirHors ligneAdministrateurPoints: 15740 Défis: 136 Message

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.)
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

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 ?

Graph(X,Y)=({30-14T, 7+0, 11+0, 5+0, 23-6T, 22-8T, 1-1T, 31+0, 14+6T, 8+1T, 11+10T, 25+1T, 11+6T, 10-1T, 6+6T, 0+7T, 18+9T, 24+5T, 4+0, 12-8T, 30-4T, 2-2T, 21-5T, 17+1T, 31-3T, 20+3T, 13+3T, 8+3T, 10+5T, 7+5T, 3+6T, 24-2T, 22+0, 17+2T, 14+2T, 13-1T, 13+1T, 13+2T, 6-1T, 2-1T, 0+2T, 26+3T, 26-1T, 25-4T, 23+2T, 19+4T, 10+2T, 6+4T, 28-1T, 26-1T, 16-2T, 13+2T, 11+2T, 10-1T, 2-2T, 0+2T, 22+4T, 10+4T, 21+5T, 17+5T, 17+2T, 30+0, 29+0, 24+0, 21+0, 17+0, 14+0, 14+0, 13+0, 12+0, 6+0, 2+0, 1+0}, {25+1T, 10+11T, 11+10T, 11+9T, 16+8T, 3-1T, 19-8T, 11+7T, 22-7T, 17-7T, 25+2T, 7+6T, 5+6T, 15+6T, 23+0, 11-5T, 25+2T, 21+0, 15+5T, 19+3T, 10-3T, 24+4T, 22+6T, 19-6T, 17+8T, 17-3T, 13+2T, 8+0, 26-2T, 6+0, 21-7T, 19+1T, 9+2T, 6+1T, 5+0, 28+2T, 22-2T, 14-2T, 26+2T, 13-2T, 26+2T, 21-3T, 28-4T, 15+2T, 4+4T, 22+4T, 21-4T, 10+0, 23+2T, 19+2T, 15+1T, 12+0, 8+2T, 15+2T, 12+1T, 15+0, 17-3T, 6-4T, 22+5T, 25+2T, 11+6T, 26+0, 20+0, 29+0, 29+0, 29+0, 28+0, 19+0, 26+0, 20+0, 16+0, 20+0, 29+0})


Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
DrakHors ligneRédacteurPoints: 1925 Défis: 38 Message

Citer : Posté le 18/08/2018 21:57 | # | Fichier joint


Toujours pas.


Eon the Dragon : version 1.2
Let's have a look!
Marre de ces RPGs qui t'imposent des classes, des compétences et des sorts ? Crée tes propres capacités sur Eon the Dragon ! Des monstres, des dragons et des combats aussi épiques que difficiles t'attendent !
Un RPG unique et immense t'attend ! Joue dès maintenant à Aventura, le Royaume Poudingue !
Vous aussi, soyez swag et rejoignez Planète Casio !
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

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

Graph(X,Y)=({16+14T, 7+0, 11+0, 5+0, 17+6T, 14+8T, 0+1T, 31+0, 20-6T, 9-1T, 21-10T, 26-1T, 17-6T, 9+1T, 12-6T, 7-7T, 27-9T, 29-5T, 4+0, 4+8T, 26+4T, 0+2T, 16+5T, 18-1T, 28+3T, 23-3T, 16-3T, 11-3T, 15-5T, 12-5T, 9-6T, 22+2T, 22+0, 19-2T, 16-2T, 12+1T, 14-1T, 15-2T, 5+1T, 1+1T, 2-2T, 29-3T, 25+1T, 21+4T, 25-2T, 23-4T, 12-2T, 10-4T, 27+1T, 25+1T, 14+2T, 15-2T, 13-2T, 9+1T, 0+2T, 2-2T, 26-4T, 14-4T, 26-5T, 22-5T, 19-2T, 30+0, 29+0, 24+0, 21+0, 17+0, 14+0, 14+0, 13+0, 12+0, 6+0, 2+0, 1+0}, {26-1T, 21-11T, 21-10T, 20-9T, 24-8T, 2+1T, 11+8T, 18-7T, 15+7T, 10+7T, 27-2T, 13-6T, 11-6T, 21-6T, 23+0, 6+5T, 27-2T, 21+0, 20-5T, 22-3T, 7+3T, 28-4T, 28-6T, 13+6T, 25-8T, 14+3T, 15-2T, 8+0, 24+2T, 6+0, 14+7T, 20-1T, 11-2T, 7-1T, 5+0, 30-2T, 20+2T, 12+2T, 28-2T, 11+2T, 28-2T, 18+3T, 24+4T, 17-2T, 8-4T, 26-4T, 17+4T, 10+0, 25-2T, 21-2T, 16-1T, 12+0, 10-2T, 17-2T, 13-1T, 15+0, 14+3T, 2+4T, 27-5T, 27-2T, 17-6T, 26+0, 20+0, 29+0, 29+0, 29+0, 28+0, 19+0, 26+0, 20+0, 16+0, 20+0, 29+0})

Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
DrakHors ligneRédacteurPoints: 1925 Défis: 38 Message

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.


Eon the Dragon : version 1.2
Let's have a look!
Marre de ces RPGs qui t'imposent des classes, des compétences et des sorts ? Crée tes propres capacités sur Eon the Dragon ! Des monstres, des dragons et des combats aussi épiques que difficiles t'attendent !
Un RPG unique et immense t'attend ! Joue dès maintenant à Aventura, le Royaume Poudingue !
Vous aussi, soyez swag et rejoignez Planète Casio !
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

Citer : Posté le 18/08/2018 23:37 | #


Bah t'inversera le VW
Il est à combien sur ce test ?
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
DrakHors ligneRédacteurPoints: 1925 Défis: 38 Message

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.
Eon the Dragon : version 1.2
Let's have a look!
Marre de ces RPGs qui t'imposent des classes, des compétences et des sorts ? Crée tes propres capacités sur Eon the Dragon ! Des monstres, des dragons et des combats aussi épiques que difficiles t'attendent !
Un RPG unique et immense t'attend ! Joue dès maintenant à Aventura, le Royaume Poudingue !
Vous aussi, soyez swag et rejoignez Planète Casio !
NinestarsHors ligneMembrePoints: 2253 Défis: 22 Message

Citer : Posté le 18/08/2018 23:40 | #


Haha T'es allé vite pour faire ton algo Dark, impressionant en plus ça marche nickel
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

Citer : 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.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
DrakHors ligneRédacteurPoints: 1925 Défis: 38 Message

Citer : Posté le 18/08/2018 23:53 | #


Ah.
Eon the Dragon : version 1.2
Let's have a look!
Marre de ces RPGs qui t'imposent des classes, des compétences et des sorts ? Crée tes propres capacités sur Eon the Dragon ! Des monstres, des dragons et des combats aussi épiques que difficiles t'attendent !
Un RPG unique et immense t'attend ! Joue dès maintenant à Aventura, le Royaume Poudingue !
Vous aussi, soyez swag et rejoignez Planète Casio !
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

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
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

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


Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
Pages : Précédente1, 2, 3, 4, 5Suivante

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2019 | Il y a 139 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd