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, 5
ZezombyeHors ligneRédacteurPoints: 1625 Défis: 12 Message

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
Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
LephenixnoirEn ligneAdministrateurPoints: 15781 Défis: 136 Message

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 !
ZezombyeHors ligneRédacteurPoints: 1625 Défis: 12 Message

Citer : Posté le 19/08/2018 16:33 | #


Si tu fais ça, tu peux prendre ces arguments dans le main :
int main(int width, int height, char[] pixels)


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.
Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
LephenixnoirEn ligneAdministrateurPoints: 15781 Défis: 136 Message

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

Citer : Posté le 19/08/2018 17:06 | #


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

Citer : Posté le 19/08/2018 18:05 | # | Fichier joint


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



test2.png processed in 56 lines (9.03s)

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})

Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
Breizh_craftHors ligneModérateurPoints: 981 Défis: 7 Message

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.
Informagicien professionnel, prestidigitateur système. Tout est possible.
Breizh_craftHors ligneModérateurPoints: 981 Défis: 7 Message

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 :


Informagicien professionnel, prestidigitateur système. Tout est possible.
DrakHors ligneRédacteurPoints: 1925 Défis: 38 Message

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 !
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 stormHors ligneMembre d'honneurPoints: 10828 Défis: 176 Message

Citer : Posté le 19/08/2018 21:23 | #


C'est déjà le cas sur le topic officiel
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 12/09/2018 00:04 | #


Je up ce topic pour demander : Est-ce envisageable d'avoir un algo BMP -> SuperDrawstat ?
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 !
LephenixnoirEn ligneAdministrateurPoints: 15781 Défis: 136 Message

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.
DrakHors ligneRédacteurPoints: 1925 Défis: 38 Message

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 ?
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 !
LephenixnoirEn ligneAdministrateurPoints: 15781 Défis: 136 Message

Citer : Posté le 12/09/2018 18:28 | #


Avec plaisir, mais tu sembles avoir trouvé mieux toi-même.
DrakHors ligneRédacteurPoints: 1925 Défis: 38 Message

Citer : Posté le 12/09/2018 18:29 | #


J'ouvre un topic.
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 !
Pages : Précédente1, 2, 3, 4, 5

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2019 | Il y a 81 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