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
ZezombyeEn 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 : 1, 2, 3, 4, 5Suivante
LephenixnoirEn ligneAdministrateurPoints: 15736 Défis: 136 Message

Citer : Posté le 16/08/2018 10:13 | #


6) La partie la plus consommatrice : parmi les lignes qui restent, calculer chaque groupement de lignes possible, puis prendre celui qui contient le moins de lignes tout en couvrant l'intégralité du sprite.

Pour information, il y a 2^n groupements de lignes possibles pour n lignes, donc si tu n'arrives pas à descendre de 1000 lignes à 30 grand maximum, tu as perdu.

Tes optimisations sont intéressantes... on voit bien le point (4) qui tient compte du levé de crayon, par exemple. Tu attises ma curiosité, maintenant j'ai bien envie de voir ce que ton algo donne.
Ne0tuxHors ligneMembre d'honneurPoints: 3272 Défis: 261 Message

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


Je vais suivre tout ça avec grand intérêt, j'essaie dès que possible de lancer ce sujet alors je suis vraiment content qu'il devienne plus qu'une idée pour certains.

Je me demandais : est-ce que ce genre de problème ne serait pas intéressant à traiter par un réseau de neurones à 32*32=1024 entrées ? Le soucis c'est que le nombre de sorties (coordonnées des points) n'est pas connu à l'avance...

Pour le point 2), si je ne me trompe pas, le nombre de lignes reliant n points n'est que de n(n-1)/2. C'est la somme arithmétique des premiers entiers de 0 à n-1. Donc pour 256 points nous avons maximum 32640 segments.
Mes principaux jeux : Ice Slider - CloneLab - Arkenstone

La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
ZezombyeEn ligneRédacteurPoints: 1625 Défis: 12 Message

Citer : Posté le 16/08/2018 11:32 | #


Pour le point 2), si je ne me trompe pas, le nombre de lignes reliant n points n'est que de n(n-1)/2. C'est la somme arithmétique des premiers entiers de 0 à n-1. Donc pour 256 points nous avons maximum 32640 segments


Cette formule ne compte pas les deux sens (le segment de A à B est considéré le même que de B à A) or ce n'est pas le cas dans les lignes diagonales avec l'algorithme de Brezenham, il ne faut donc pas diviser par 2.

Tes optimisations sont intéressantes... on voit bien le point (4) qui tient compte du levé de crayon, par exemple.


Y'a pas de prise en compte du levé de crayon, c'est le multi drawstat (sinon il faut en plus prendre en compte l'ordre de dessin des lignes, et dans ce cas je crois bien que c'est n^n au lieu de 2^n)

Le point 4 c'est juste pour enlever les lignes dont on est 100% sûr qu'elles ne font pas partie de la solution optimale.

Pour information, il y a 2^n groupements de lignes possibles pour n lignes


Corrigé

Pour les groupements, même si on en a 2^100 possibles, on peut affiner notre itération : par exemple, ignorer les groupements de moins de 10 lignes, parce que c'est impossible de tracer le sprite en moins de 10 lignes. (par contre, aucune idée de comment calculer un nombre minimum de lignes)
Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
NinestarsHors ligneMembrePoints: 2253 Défis: 22 Message

Citer : Posté le 16/08/2018 11:42 | #


Intéressant cette méthode, disons que c'est la méthode intuitive. Je pense qu'il doit exister des méthodes plus mathématiques pour résoudre ce genre de problème. J'avais fait une détection de ligne avec l'algorithme de Hough, c'est efficace mais pas déterministe du coup ce sont des probabilités de ligne. Dans notre cas c'est pas possible puisqu'on cherche à être "parfait" ... :/
La partie 6 va être plutôt chaude à réaliser

Sinon j'imagine la chose comme cela :
Prendre un segment au hasard A
Chercher tout les segments B qui partagent un point en commun avec A et enregistrer tout les cas.
Boucler pour tous les segments AB

Ça va te donner un arbre de solutions et il faudra prendre là branche la moins profonde qui utilise tout les segments...
Nan en fait je suis même pas sûr que ça marche...
Surtout si le sprite est en plusieurs partie distinctes !

J'ai une idée qui me vient, peut être que l'algo de digstra pourrait aider dans ce cas.

En tout cas si t'y arrives ça sera d'une grande utilité !
LephenixnoirEn ligneAdministrateurPoints: 15736 Défis: 136 Message

Citer : Posté le 16/08/2018 11:56 | #


Pour les groupements, même si on en a 2^100 possibles, on peut affiner notre itération : par exemple, ignorer les groupements de moins de 10 lignes, parce que c'est impossible de tracer le sprite en moins de 10 lignes. (par contre, aucune idée de comment calculer un nombre minimum de lignes)

« Mauvaise réponse » j'ai envie de dire : il n'y a que "10 parmi 100" groupements de 10 lignes (1.71 × 10¹³) sur les 2^100 groupements (1.27 × 10³⁰) donc tu gagnes strictement rien.

Au contraire, tu as plutôt envie de tester tous les petits groupements, car ça va vite. Par exemple ton algorithme pourrait commencer par couvrir le dessin d'une façon bourrine. Si tu obtiens un résultat de 50 lignes, tu sais déjà que c'est inutile de chercher les groupements qui en ont plus, ce qui te simplifie beaucoup les choses.

Je serais plutôt tenté d'essayer tous les groupements de i lignes pour i petit, et de m'arrêter dès que je trouve un groupement valide.

Même si je ne suis pas encore convaincu que le bruteforce soit réalisable en pratique.
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

Citer : Posté le 16/08/2018 12:04 | #


Je me demandais : est-ce que ce genre de problème ne serait pas intéressant à traiter par un réseau de neurones à 32*32=1024 entrées ?

C'est une idée, mais qui se charge de générer un dataset suffisant pour entrainer le réseau ?

Sinon en y réfléchissant, ça doit pouvoir se générer automatiquement. Pour la fonction d'évaluation, il suffit de regarder sir la solution est valide et garder le nombre de traits trouvés comme score.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
ZezombyeEn ligneRédacteurPoints: 1625 Défis: 12 Message

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


10^18 calculs à faire en moins c'est déjà pas mal (même s'il faudrait affiner beaucoup plus...)

L'idée ce serait de définir une lower bound et de commencer à partir de ça, et comme tu le dis de ne pas chercher les groupements supérieurs si on a une solution en x lignes.
Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
LephenixnoirEn ligneAdministrateurPoints: 15736 Défis: 136 Message

Citer : Posté le 16/08/2018 12:23 | #


10^18 calculs à faire en moins c'est déjà pas mal (même s'il faudrait affiner beaucoup plus...)

Certes c'est un énorme gain ! Mais s'il t'en reste 10³⁰ ça ne t'avance pas tant que ça...

L'idée ce serait de définir une lower bound et de commencer à partir de ça, et comme tu le dis de ne pas chercher les groupements supérieurs si on a une solution en x lignes.

Oui, ça me semble beaucoup plus judicieux.

Tu avances vers la méthode raffinée du bruteforce : le backtracking, aka branch-and-bound. Là tu peux espérer avoir des temsp décents, peut-être. Je te laisse regarder si ça t'intéresse.
Ne0tuxHors ligneMembre d'honneurPoints: 3272 Défis: 261 Message

Citer : Posté le 16/08/2018 13:12 | #


Zezombye a écrit :
Cette formule ne compte pas les deux sens (le segment de A à B est considéré le même que de B à A) or ce n'est pas le cas dans les lignes diagonales avec l'algorithme de Brezenham, il ne faut donc pas diviser par 2.


Tu veux dire que sur Casio, tracer une ligne de A vers B ou de B vers A n'affiche pas la même chose ? Maintenant que tu le dis je crois que c'est tout à fait vrai (exemple : une diagonale de cinq de large et deux de haut donne deux résultats différents suivant le sens). Dans ce cas en effet le sens importe, et il ne faut pas diviser par 2 (à préciser dans ton énoncé initial tout de même "segment orienté"). Ce n'est pas vraiment un détail qui nous aide à simplifier le problème, malheureusement...

Est-ce que ça force pour autant à implémenter l'algo de Bresenham (pas de "z") quelquepart dans l'algorithme ?
Mes principaux jeux : Ice Slider - CloneLab - Arkenstone

La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
DrakHors ligneRédacteurPoints: 1925 Défis: 38 Message

Citer : Posté le 16/08/2018 13:52 | #


Lephenixnoir a écrit :
Pour les groupements, même si on en a 2^100 possibles, on peut affiner notre itération : par exemple, ignorer les groupements de moins de 10 lignes, parce que c'est impossible de tracer le sprite en moins de 10 lignes. (par contre, aucune idée de comment calculer un nombre minimum de lignes)

« Mauvaise réponse » j'ai envie de dire : il n'y a que "10 parmi 100" groupements de 10 lignes (1.71 × 10¹³) sur les 2^100 groupements (1.27 × 10³⁰) donc tu gagnes strictement rien.

Au contraire, tu as plutôt envie de tester tous les petits groupements, car ça va vite. Par exemple ton algorithme pourrait commencer par couvrir le dessin d'une façon bourrine. Si tu obtiens un résultat de 50 lignes, tu sais déjà que c'est inutile de chercher les groupements qui en ont plus, ce qui te simplifie beaucoup les choses.

Je serais plutôt tenté d'essayer tous les groupements de i lignes pour i petit, et de m'arrêter dès que je trouve un groupement valide.

Même si je ne suis pas encore convaincu que le bruteforce soit réalisable en pratique.


N'est-il pas possible de commencer à partir du groupement le plus petit, pour ensuite, dans un ordre croissant, aller chercher les groupements qui contiennent plus de lignes, jusqu'à tomber sur un groupement correct ? Ainsi, on pourrait espérer trouver une solution optimale, à condition bien sûr d'avoir balayé l'ensemble des possibilités au nombre de lignes inférieur.
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 !
ZezombyeEn ligneRédacteurPoints: 1625 Défis: 12 Message

Citer : Posté le 16/08/2018 13:58 | #


C'est ce que je pensais faire, mais tester même des groupements de 10 lignes (parmi 100) ça doit faire dans les 10^10 ce qui fait beaucoup
Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

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


10 parmi 100 ~= 1.73e13

Ajouté le 17/08/2018 à 13:07 :
Concernant le réseau de neurones, j'ai regardé du coté de TensorFlow, ça a vachement progressé depuis le temps. A priori ça ne sera pas compliqué de créer le réseau.

Je suis en train de réfléchir sur le format du réseau, mais pour l'instant je pars sur :
- input : sprite de 32x32 = 1024
- couches : deux ou trois couches denses (fully-connected) de 256 neurones
- output : un tableau de 128 = 64x2, qui correspondrait à la liste drawstat directement, remplie de 0 une fois le dessin fini.

Concernant le dataset, comme je l'avais prévu ça va être chiant de le faire, mais je verrai si y'a pas moyen de le créer automatiquement. Faut juste que je regarde comment sont gérés les traits par la Casio (c'est pas du Bresenham, malheureusement...) histoire de pas faire un truc qui soit pas reproductible on-calc.

La plus grande inconnue, ça va être la précision du réseau : par définition, il est pas capable de sortir des résultats exacts, juste des "probabilités". Peut-être qu'en l'entrainant sur un gros dataset (entre 10^6 et 10^7 images) assez longtemps, on aura des résultats corrects. C'est à voir.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
ZezombyeEn ligneRédacteurPoints: 1625 Défis: 12 Message

Citer : Posté le 17/08/2018 13:20 | #


c'est pas du Bresenham, malheureusement...


Heu si, j'avais justement vérifié avec BIDE, les sprites que je trace avec Bresenham sont identiques à ceux tracés sur la calto.

output : un tableau de 128 = 64x2


Tu le sors d'où le 64 ? Qui te dit que la solution optimale ne fait pas 70 lignes
Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

Citer : Posté le 17/08/2018 13:24 | #


Je fais la supposition qu'un sprite de plus de 64 points, c'est en pratique jamais atteint. Au pire je monte à 128, mais bon...

Mais oui, c'est arbitraire et on pourra toujours trouver un cas où c'est trop peu. Tiens, question simple mais dont la réponse est pas évidente : sur un sprite de 32*32, quel est le nombre maximal de points/lignes ? A quoi correspond-t-il ?
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
LephenixnoirEn ligneAdministrateurPoints: 15736 Défis: 136 Message

Citer : Posté le 17/08/2018 14:33 | # | Fichier joint


Le sprite de Drak est plus gros que 64 points en tous cas.

Sur un sprite de 32×32, une majoration triviale du nombre de lignes à tracer est 1024 ; une ligne par point.

Le maximum semble difficile à calculer, je peux affirmer que c'est au moins 256 en utilisant le sprite de 32×32 suivant :

Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

Citer : Posté le 17/08/2018 18:16 | #


Heu si, j'avais justement vérifié avec BIDE, les sprites que je trace avec Bresenham sont identiques à ceux tracés sur la calto.

T'es sûr que Bresenham donne des résultats différents suivant le sens du segment ?
M'enfin si c'est le cas, ça m'arrange.
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 17/08/2018 18:17 | #


En voyant ton image je me suis dit que le plus simple serait peut être d'avoir l'image en fond clair, puis redessiner par dessus l'image avec des traits. Laisser l'utilisateur trouver la meilleure façon...

Ajouté le 17/08/2018 à 18:18 :
Il me semble que Bresenham est symétrique, peu importe le sens du segment
Dark stormEn ligneMembre d'honneurPoints: 10825 Défis: 176 Message

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


Le sprite de Drak est plus gros que 64 points en tous cas.

C'est pas faux. Peut-être que 32*32 c'est un peu gourmand comme début. Je commencerai par 8*8, éventuellement 16*16. Faudrait déjà que les résultats soient probant sur de petits sprites avant de lancer le calcul sur des images plus grandes
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
ZezombyeEn ligneRédacteurPoints: 1625 Défis: 12 Message

Citer : Posté le 17/08/2018 18:20 | #


C'est ce que je fais, je redessine dessus en ce moment je n'accepterai qu'un algo qui me donne un nombre de lignes inférieur ou égal au mien

Il me semble que Bresenham est symétrique, peu importe le sens du segment


Nope :


Ajouté le 17/08/2018 à 18:30 :
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. (enfin bon ça fait quand même beaucoup...)

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


Il faudrait, comme lephé le dit, couper en petits morceaux, mais lorsqu'on est sûr qu'on ne coupe pas une ligne en 2. Par exemple, on peut couper une partie rouge ici :


Par contre aucune idée de comment trouver les endroits de coupage.
Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
NinestarsHors ligneMembrePoints: 2253 Défis: 22 Message

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


D'accord, merci pour l'exemple !

Il y a pas un prblème de continuité entre les traits dans ton exemple ?
Parce que le dernier point d'un segment doit être exactement le même que le premier du second. Là tu as trouvé les traits qui ne chevauchent pas.
Pages : 1, 2, 3, 4, 5Suivante

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