Une brève explication d'un jeu de labyrinthe fait à Java pour les cousins du primaire
en premier
L'autre jour, mes cousins de 4e et 1re année sont venus nous rendre visite. Comme jouer avec le corps est difficile, j'ai pensé que si je le faisais dans le jeu, ce serait calme, alors j'ai créé un jeu de labyrinthe qui fonctionne avec CUI. En conséquence, leur mère était plus dépendante que leurs cousins, et à la fin ils ne pouvaient pas arrêter l'agitation de Dottanbattan.
environnement
Linux Mint 18 'Sarah' MATE 64-bit Java 1.8.0_131 Google Chrome 61.0.3163.79 (version officielle) (64 bits)
Algorithme de génération de labyrinthe
Il semble y avoir divers algorithmes pour créer un labyrinthe, mais cette fois nous utiliserons un algorithme appelé ** méthode de creusement (méthode d'extension de route) **. Divers algorithmes sont écrits de manière facile à comprendre sur ce site, nous vous recommandons donc de vous y référer.
supposition
Supposons que le labyrinthe soit sur un plan bidimensionnel et soit une collection de "masse" comme un papier quadrillé. A ce moment, la masse doit jouer le rôle de «mur» ou de «route». Supposons également que l'extérieur du labyrinthe est complètement rempli de routes. Et il n'y a qu'une seule route du début au but.
Méthode de forage (méthode d'extension de route)
Cet algorithme est similaire à la façon dont les humains créent des labyrinthes à la main. Par conséquent, le degré d'aléa de la route est élevé. De plus, les lignes droites ont tendance à être moins, donc si vous créez un grand labyrinthe, il aura l'air désordonné. Le contenu de l'algorithme est présenté ci-dessous.
- Faites du labyrinthe entier un mur.
- Utilisez une case choisie au hasard comme route, à l'exception des cases qui touchent l'extérieur du labyrinthe.
- Prolongez la route au hasard à partir de là (à moins que la case au-dessus, en dessous, à gauche et à droite dans la direction dans laquelle vous allez soit la route).
- Répétez l'étape 3 autant que possible.
- Sélectionnez au hasard une case parmi les cases qui se trouvent déjà sur la route, sauf à l'extérieur du labyrinthe.
- Répétez les étapes 3 à 5 autant que possible.
Je n'expliquerai qu'un peu l'étape 3.
■: Mur □: Route ○: Le carré sur le point d'avancer -: Peu importe que ce soit un mur ou une route
Supposons que vous essayez de partir d'une route à gauche. À ce stade, si les cases sur le côté gauche de la route sont les suivantes, vous pouvez prolonger la route vers la gauche.
- ■ - ■ ○ □ ← Essayer de prolonger la route à partir d'ici
- ■ -
Cependant, si même l'un des carrés qui était un mur dans la figure précédente (par exemple, le carré au-dessus de ○) devient une route, vous ne pourrez pas prolonger la route vers la gauche. La raison en est que la «route en cours de prolongement» et la «route adjacente à ○» sont liées. Si vous permettez aux deux routes de se connecter, vous vous retrouverez avec une route en boucle et il y aura plus d'une route du début à l'objectif.
- □ - ■ ○ □ ← Essayer de prolonger la route à partir d'ici
- ■ -
Après avoir terminé l'étape 6, tout ce que vous avez à faire est de sélectionner les carrés qui seront le départ et le but parmi les carrés qui touchent l'extérieur du labyrinthe.
la mise en oeuvre
Tous sont implémentés en utilisant Java. Voici la partie de l'algorithme de génération labyrinthe que je viens de décrire (pour ceux qui veulent voir le code complet ici). De plus, la partie correspondant à chaque étape montrée dans l'explication précédente est montrée dans le commentaire.
Maze.java
//Méthode pour créer un nouveau labyrinthe
static void createMaze() {
// [étape 1]Initialisation
for (int i = 0; i < mazeSize; i++) {
for (int j = 0; j < mazeSize; j++) {
wall[i][j] = true;
}
}
// [Étape 2]Sélectionnez au hasard la position de départ (1 pour mazeSize)- 2）
Random rnd = new Random();
row = rnd.nextInt(mazeSize - 2) + 1;
col = rnd.nextInt(mazeSize - 2) + 1;
wall[row][col] = false;
rowStack.push(row);
colStack.push(col);
boolean continueFlag = true;
// [Étape 6]Ci-dessous, mur[][]Répétez jusqu'à ce que le tout soit rempli
while (continueFlag) {
// [Étape 3,4]Prolongez la route jusqu'à la limite en haut, en bas, à gauche ou à droite
extendPath();
// [Étape 5]Sélectionnez la prochaine position de départ de la route existante (0 à mazeSize)- 1）
continueFlag = false;
while (!rowStack.empty() && !colStack.empty()) {
row = rowStack.pop();
col = colStack.pop();
if (canExtendPath()) {
continueFlag = true;
break;
}
}
}
}
L'explication des principales variables est la suivante.
--int mazeSize: La longueur d'un côté du labyrinthe généré (carré). --Boolean [] [] wall: l'état du labyrinthe entier. True représente le mur et false représente la route. --int row: La ligne du "carré que vous essayez de tracer". --int col: Une colonne de "masses essayant de faire place". --Stack rowStack: Une pile avec des lignes de "masses déjà sur la route". --Stack colStack: Une pile avec des colonnes de "masses déjà sur la route".
Les principales méthodes sont expliquées ci-dessous.
--extendPath (): Effectuez les étapes 3 et 4 de l'explication précédente. --canExtendPath (): détermine si la "masse que vous essayez de tracer un chemin" peut vraiment tracer un chemin.
En empilant les «masses déjà transformées en route» sur la pile, vous pouvez vérifier toutes les routes auxquelles l'étape 3 peut être appliquée.
Résultat d'exécution
Le résultat de l'exécution ressemble à ceci (mazeSize = 30).
Le «**» en bas à gauche représente le joueur et le «GO» en haut à droite représente le but. Vous pouvez déplacer le lecteur vers le haut, le bas, la gauche et la droite avec la touche wsad. Lorsque vous atteignez l'objectif, le temps clair sera affiché avec l'éloge. Lorsque vous l'essayez, c'est assez difficile car il se ramifie de manière compliquée.
Implémentation en JavaScript et HTML
Je l'ai également implémenté en JavaScript et HTML afin qu'il puisse être lu dans le navigateur. C'est fondamentalement la même chose que l'implémentation Java. Pour savoir comment dessiner le labyrinthe, j'ai utilisé ce site comme référence.
Résultat d'exécution de la version du navigateur
Le résultat de l'exécution ressemble à ceci (mazeSize = 50).
Le bloc bleu en bas à gauche représente le joueur et le bloc rouge en haut à droite représente le but. Vous pouvez déplacer le lecteur vers le haut, le bas, la gauche et la droite avec les touches fléchées. Lorsque vous atteignez l'objectif, le temps clair sera affiché dans la boîte de dialogue avec l'éloge. Vous pouvez modifier librement la taille du labyrinthe à partir du champ de saisie en haut. Je ne pense pas à la façon dont cela fonctionne sur un smartphone. ~~ Au fait, vous pouvez jouer depuis ici. ~~
Tâches futures
―― ~~ Je veux en faire une interface graphique afin de pouvoir la lire facilement sous Windows et la mettre dans un fichier exe. ~~ L'époque semble être le Web, j'ai donc rendu possible de jouer avec un navigateur. ―― ~~ L'apparence est désordonnée, je veux donc augmenter le nombre de routes droites. ~~ Je pense que c'est plus intéressant comme labyrinthe s'il est en désordre, alors laissez-le tel quel. ―― ~~ Actuellement, vous devez appuyer sur la touche Entrée après avoir appuyé sur la touche wsad, donc je veux le déplacer avec juste la touche wsad. ~~ La version du navigateur peut être jouée avec les touches fléchées. «Je veux afficher des scores élevés.
URL de référence, etc.
Labyrinthe généré automatiquement http://www5d.biglobe.ne.jp/stssk/maze/make.html GitHub https://github.com/hey-cube/maze [JavaScript] Créez un mystérieux labyrinthe de donjons avec HTML + JavaScript http://www.yoheim.net/blog.php?q=20151202 ~~ HeyCube Labyrinth http://www.coins.tsukuba.ac.jp/~s1411396/index.html~~
finalement
Quand j'ai rompu avec mes cousins, on m'a demandé: "Puis-je jouer à ce jeu plus?" J'ai donc promis de le rendre disponible pour téléchargement et jouer sur le Web. Donc, éventuellement, je vais rendre ce labyrinthe téléchargeable et jouable.
Je suis content s'il y a des gens qui s'intéressent à ce que j'ai fait.
(Ajouté le 08/09/2017) Je n'ai pas utilisé la méthode de téléchargement et de lecture, mais j'ai créé une version de navigateur pour que mes cousins puissent jouer à la maison.
(Ajouté le 24/03/2018) A cette époque, je ne comprenais pas JavaScript, mais avec le recul, c'est terrible ... Quel que soit l'algorithme, veuillez ne pas vous référer au code JavaScript.
Recommended Posts