Comment construire un niveau résoluble de Same Game (aka Chain-Shot, aka Clickomania)

Question

Je construis un jeu tel que Same Game, quand je dois créer un nouveau niveau, je viens de lancer un algorithme à remplir le tableau avec N couleurs, cet algorithme remplit le tableau au hasard, mais évidemment les niveaux générés de cette façon ne sont pas tous une solution.

Je dois faire une fonction pour résoudre ce problème, afin que le jeu puisse être joué par un joueur parfait pour toujours.

J'ai un maximum de 6 couleurs et un minimum de 2 et la planche a une taille raisonnable (14x12) mais peut être modifiée.

La langue n'est pas pertinente.

EDIT: Je n'ai pas besoin de résoudre le puzzle, j'ai besoin de créer des niveaux qui ont au moins une solution.

Answer 1

Je viens de vérifier environ cinq versions différentes du jeu sur Ubuntu et j'ai trouvé une réponse que vous pouvez piller!

Simon Tatham's Portable Puzzle Collection

Je joue sur les cinq de ses jeux préférés, mais incessamment GNOME même. Je viens de charger son même jeu et il a la possibilité d'assurer la solubilité lors de la création de jeux personnalisés. Même a un système de notation personnalisable. Tout est terriblement avancé.

Un exe et un code source sont disponibles à partir du lien ci-dessus.

Et la licence est MIT (ce qui signifie que vous pouvez l'utiliser librement dans les jeux commerciaux - mais s'il vous plaît lui donner quelque chose à si vous pouvez vous le permettre)

Answer 2

Une méthode, qui, j'ajouterai, est rarement la plus efficace, consiste à construire le niveau en sens inverse.

C'est assez simple à faire dans ce cas. Vous commencez simplement avec rien et ajoutez des groupes cliquables avec certains aléatoire ... Je dis un peu de hasard, car vous devrez peut-être ajouter des blocs supplémentaires pour vous assurer que toutes les colonnes sont remplies.

Mais en y pensant, même alors il y a une possibilité que deux groupes cliquables que vous ajoutez se touchent et provoquent un effondrement imprévu, résultant en un jeu inachevable. Donc, cette méthode ne garantirait pas un jeu solvable.

Vous pouvez jeter un oeil à la source pour une version open source comme Same GNOME et de voir comment ils le font (s'ils le font tout!)

Answer 3

créer un « élucidé » carte, puis changer à l'aide N mouvements arrières valides mais aléatoires. Après avoir ajouté chaque mouvement en arrière, vous pouvez exécuter les mouvements en avant (sur un tableau temporaire) pour vérifier un puzzle résoluble.

Answer 4

Si vous ne pouvez pas exécuter un algorithme de vérification, en raison des contraintes de temps, vous devrez peut-être utiliser une bibliothèque d'énigmes. Vous pouvez avoir un thread d'arrière-plan générant de nouveaux puzzles aléatoires tout le temps, et en exécutant un algorithme de vérification sur eux pour vérifier s'ils sont valides. Quand un puzzle valide est trouvé, il est ajouté à votre bibliothèque de puzzles (en supposant que le même puzzle n'existe pas déjà). Ensuite, votre jeu se charge aléatoirement dans la bibliothèque. Cela vous permet de vous assurer que vous avez toujours des puzzles valides, mais vous permet quand même de les générer aléatoirement et de les vérifier sans ralentir le chargement du puzzle.

Answer 5

Je pense que la meilleure façon est, si vous générez un niveau au hasard, Je veux dire ajouter 1 ou plusieurs blocs en même temps à la même colonne, donc vous allez avoir quelques blocs de connexion. Ensuite, vous écrivez un algorithme de résolution simple, qui résout juste le conseil jusqu'à ce qu'il n'y ait plus de mouvements possibles. Ensuite, vous essayez simplement de compléter la partie restante, en poussant juste quelques blocs du haut de sorte que vous avez plus de blocs à disparaître. Vous continuez jusqu'à ce que vous finissiez le tableau. Vous stockez les pièces que vous avez ajoutées dans une autre matrice. Ensuite, il suffit d'ajouter la 2ème matrice à la première à partir du haut. Si le tableau n'est pas plein, il vous suffit de compléter le tableau avec des blocs pour commencer (blocs de connexion).