Algo Picross ?

Dev
#1

Bonjour à tous,

Voila, j’ai commencé à coder un jeu de Picross sur Nintendo DS et ça avance pas mal.
Par contre, j’hésite sur la façon de stocker les puzzles.

En effet une grille de Picross, une fois finie ressemble à ça :

1 1 1 5 1 1 1 5 5 |X|X|X|X|X| 1 1 |X| | | |X| 1 1 |X| | | |X| 1 1 |X| | | |X| 5 |X|X|X|X|X|
Et pour le moment je stocke le puzzle case par case :

char * puzzle[] = { "1,1,1,1,1\n" "1,0,0,0,1\n" "1,0,0,0,1\n" "1,0,0,0,1\n" "1,1,1,1,1"}
Ce qui est la solution la plus simple vu qu’il suffit juste de comparer si la case sur laquelle on clique est bien une case à cocher.

Par contre j’aimerais bien voir s’il est possible de stocker uniquement les aides sur le côté et non la grille complète afin de « gagner » un peu de place (et surtout que ça fasse un peu plus pro), comme ceci :

char * puzzle[] = { "col:5|1,1|1,1|1,1|5\n" "lig:5|1,1|1,1|1,1|5\n"}
Et évidemment, ça c’est chaud à coder…

Est-ce que quelqu’un aurait une piste (ou un site bien documenté) sur comment réussir à coder un algo qui générerait le puzzle final uniquement avec les indications ? Car ça fait appel à de l’IA, et l’IA c’est pas mon fort… ou bien alors une autre solution de stockage moins lourde que la mienne, je suis pas sectaire B)

Merci :smiley:

#2

Ah, j’adorais Mario’s Picross sur GB.
Maintenant, ton truc est théoriquement possible (vu qu’une seule possiblité existe pour une combinaison lignes-colonnes), mais il faudrait créer un résolveur de picross infaillible qui peut te sortir la bonne réponse, la stocker dans la RAM de la façon matrice, et la filer au joueur.

Je réfléchis si j’ai un algo, et je te redis.

edit: je pense que t’as regardé l’article Wikipédia, mais ça fait un remainder sur les techniques. Et les liens en bas doivent donner des algos (ils font comme tu le voudrais en tous cas).

#3

[quote=“Neomattrix, post:2, topic: 30387”](vu qu’une seule possiblité existe pour une combinaison lignes-colonnes)[/quote]Tu entends quoi par ca ?

En tout cas bon jeu le picross. Je l’avais refait en java, mais avec ta première technique de stockage des tableau.

#4

Tu l’aurai encore quelquepart B) ?

#5

Par pitié, sépare les données de ta structure et les données de l’“interface utilisateur”.

Exemple simple: on te file une API 2D toute bete, et tu veux adapter ton code. Tu vas donc devoir enlever ce que tu t’escrimes à ajouter B)

Mais comme je n’ai pas bien compris, je ne sais pas si c’est ton but ou si c’est justement ce que tu veux éviter…

#6

heu oui mais me faut chercher. Je regarde et je mets le lien.

Bon c’est une version archi béta de l’apha et n’ai pas completement fini, ni commenté, ni optimisé, ni …, ni …, et ce n’est pas une série d’excuses pour dire que je code comme un porc sous ecstasy.

ZePicross

#7

j’y pipe que dalle en programmation mais ce serait vraiment de la balle si t’arrivais à m’accrocher autant que mario’s picross sur SNIN.

que la force soit avec toi !

#8

Hello !

Si cela peut t’aider, j’ai sous la main le code d’un Picross.
C’était pour un cours de programmation en assembleur sur Palm il y a quelques années. Un ami a fait un Picross et on avait mis les sources de nos projets à disposition des autres.

Donc si tu le veux, c’est par là : Picross en assembleur

Ce sont uniquement des grilles de 10x10 et les niveaux sont générés aléatoirement. Par contre aucune idée de la méthode utilisée ici. J’avais pas trop regardé le code… j’ai surtout usé mon écran à force d’y jouer B)

#9

Merci mais l’assembleur c’est un langage d’une autre planète pour moi…

#10

[quote=« Neomattrix, post:2, topic: 30387 »]Ah, j’adorais Mario’s Picross sur GB.
Maintenant, ton truc est théoriquement possible (vu qu’une seule possiblité existe pour une combinaison lignes-colonnes), mais il faudrait créer un résolveur de picross infaillible qui peut te sortir la bonne réponse, la stocker dans la RAM de la façon matrice, et la filer au joueur.

Je réfléchis si j’ai un algo, et je te redis.

edit: je pense que t’as regardé l’article Wikipédia, mais ça fait un remainder sur les techniques. Et les liens en bas doivent donner des algos (ils font comme tu le voudrais en tous cas).[/quote]

Pfff ouais c’est théoriquement possible et puis la question m’ayant intéressé (j’adore le picross) j’ai cherché à droite et à gauche. Et pioufff si tu veux faire un solveur uniquement pour économiser de la mémoire sur le stockage des grilles… Tu vas y passer du temps, beaucoup, et si tu veux faire des grilles un peu balèzes ca va prendre du temps de les résoudre…
Mais si jamais ça marche moi je suis preneur :smiley: Et j’accepterai même que tu m’offres j’envisagerai de m’acheter je me ferai offrir une DS pour y jouer B)

Sinon a mon avis pour un solveur le meilleur moyen est d’implémenter les techniques simples que tu trouves sur wikipédia et ensuite c’est du backtracking de malade… Je ne vois pas mieux… Ah si et tu peux optimiser le backtracking en commençant par les lignes/colonnes qui offrent le moins de combinaisons possibles ça te met direct sur les bonnes branches de l’arbre ('fin je pense)

#11

Oué, dans les liens de Wikipedia ça redirigeait vers un solveur en Java pas trop mal foutu, qui résolvait le puzzle en temps réel en testant les combinaisons.
J’ai décompilé les .class pour voir à quoi ça ressemblait et j’ai pleuré, des algos de fous furieux…

Donc je pense que pour le moment je vais m’en tenir à la grille stockée en dur en rajoutant les indications de colonnes (pour éviter d’avoir à les retrouver par algo)