Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.
La shoutbox n'est pas chargée par défaut pour des raisons de performances. Cliquez pour charger.

Forum Casio - Projets de programmation


Index du Forum » Projets de programmation » Algo BMP->Multi Drawstat
Zezombye Hors ligne Rédacteur Points: 1756 Défis: 13 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


Précédente 1, 2, 3, 4, 5
Zezombye Hors ligne Rédacteur Points: 1756 Défis: 13 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
Lephenixnoir En ligne Administrateur Points: 24563 Défis: 170 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 !
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Zezombye Hors ligne Rédacteur Points: 1756 Défis: 13 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
Lephenixnoir En ligne Administrateur Points: 24563 Défis: 170 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.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Dark storm En ligne Labélisateur Points: 11641 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
Dark storm En ligne Labélisateur Points: 11641 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
Breizh_craft En ligne Modérateur Points: 1171 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.
Breizh.pm – Un adminsys qui aime les galettes.
Breizh_craft En ligne Modérateur Points: 1171 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 :


Breizh.pm – Un adminsys qui aime les galettes.
Drak Hors ligne Rédacteur Points: 1925 Défis: 40 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 storm En ligne Labélisateur Points: 11641 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
Drak Hors ligne Rédacteur Points: 1925 Défis: 40 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 !
Lephenixnoir En ligne Administrateur Points: 24563 Défis: 170 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.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Drak Hors ligne Rédacteur Points: 1925 Défis: 40 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 !
Lephenixnoir En ligne Administrateur Points: 24563 Défis: 170 Message

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


Avec plaisir, mais tu sembles avoir trouvé mieux toi-même.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Drak Hors ligne Rédacteur Points: 1925 Défis: 40 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 !
Précédente 1, 2, 3, 4, 5

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 122 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