java図の深さは優先的に巡回してランダムに迷路を生成することを実現します。
最近よく機械室でクラスメートが迷宮を歩くゲームを遊んでいます。自分もjavaでランダムに迷宮を生成するアルゴリズムを書いています。実は図の深さ優先アルゴリズムです。基本的な思想は、迷宮の中の各点に四面壁があります。
1、任意の点からアクセス(私のアルゴリズムでは固定的に(0,0)点から)し、4つの方向のランダムな1つのアクセス(訪問するたびに訪問できるポイントにアクセスすると、その点の方向の壁を取り除く)を行い、訪問先は引き続きこのような認識で次の方向に訪問します。
2、訪問された各点はすでに訪問済みとしてマークされています。ある点に対して、ある方向を訪問する時、まず訪問先が訪問されているかどうか、または境界に触れているかどうかを判断します。この点の四つの方向はすでに訪問されているか、またはすでに訪問できない場合、前の点に戻ります。前の点はこの過程を続けます。
このように遍歴すると、各点が訪問されたことが確認され、また訪問の方向がランダムであるため、多くの異なる遍歴状況が形成されると同時に、2つの点の間の経路は唯一であり、異なる迷路が形成され、起点から終点までの唯一の経路があるということは、図の深さ遍歴アルゴリズムの特徴によって決定される。アルゴリズムの実装では、まず最初の点をスタックに押し込んで、その点をスタックに押し込んで、スタックの一番上の点をランダムに4つの方向に訪問して、新しい点にアクセスして、また新しい点を押し込んで、この点を4つの方向に訪問できなくなったら、その点をスタックから撤退させて、スタックの一番上の点の4つの方向にアクセスして、これを類推します。倉庫の中の点まで全部退出しました。私達の遍歴は成功しました。再帰の過程です。このアルゴリズムは再帰的な方法で実現できます。でもここでは私がこうします。一つ一つの配列をスタックとして手作りして実現します。ほほほ~こんなに多く言っても、自分の表現が表現されているかどうか分かりません。しかし、私は私の具体的なコードの設計はやはりよくないと感じています。完璧さと最適化に欠けるところがたくさんあります。
以下は効果図です
迷宮のクラス:
1、任意の点からアクセス(私のアルゴリズムでは固定的に(0,0)点から)し、4つの方向のランダムな1つのアクセス(訪問するたびに訪問できるポイントにアクセスすると、その点の方向の壁を取り除く)を行い、訪問先は引き続きこのような認識で次の方向に訪問します。
2、訪問された各点はすでに訪問済みとしてマークされています。ある点に対して、ある方向を訪問する時、まず訪問先が訪問されているかどうか、または境界に触れているかどうかを判断します。この点の四つの方向はすでに訪問されているか、またはすでに訪問できない場合、前の点に戻ります。前の点はこの過程を続けます。
このように遍歴すると、各点が訪問されたことが確認され、また訪問の方向がランダムであるため、多くの異なる遍歴状況が形成されると同時に、2つの点の間の経路は唯一であり、異なる迷路が形成され、起点から終点までの唯一の経路があるということは、図の深さ遍歴アルゴリズムの特徴によって決定される。アルゴリズムの実装では、まず最初の点をスタックに押し込んで、その点をスタックに押し込んで、スタックの一番上の点をランダムに4つの方向に訪問して、新しい点にアクセスして、また新しい点を押し込んで、この点を4つの方向に訪問できなくなったら、その点をスタックから撤退させて、スタックの一番上の点の4つの方向にアクセスして、これを類推します。倉庫の中の点まで全部退出しました。私達の遍歴は成功しました。再帰の過程です。このアルゴリズムは再帰的な方法で実現できます。でもここでは私がこうします。一つ一つの配列をスタックとして手作りして実現します。ほほほ~こんなに多く言っても、自分の表現が表現されているかどうか分かりません。しかし、私は私の具体的なコードの設計はやはりよくないと感じています。完璧さと最適化に欠けるところがたくさんあります。
以下は効果図です
迷宮のクラス:
// :zhongZw
// :[email protected]
package cn.zhongZw.model;
import java.util.ArrayList;
import java.util.Random;
public class MazeModel {
private int width = 0;
private int height = 0;
private Random rnd = new Random();
public MazeModel() {
this.width = 50; //
this.height = 50; //
}
public int getWidth() {
return width;
}
public void setWidth(int width) {
this.width = width;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
public MazeModel(int width, int height) {
super();
this.width = width;
this.height = height;
}
public ArrayList < MazePoint > getMaze() {
ArrayList < MazePoint > maze = new ArrayList < MazePoint > ();
for (int h = 0; h < height; h++) {
for (int w = 0; w < width; w++) {
MazePoint point = new MazePoint(w, h);
maze.add(point);
}
}
return CreateMaze(maze);
}
private ArrayList < MazePoint > CreateMaze(ArrayList < MazePoint > maze) {
int top = 0;
int x = 0;
int y = 0;
ArrayList < MazePoint > team = new ArrayList < MazePoint > ();
team.add(maze.get(x + y * width));
while (top >= 0) {
int[] val = new int[] {
-1, -1, -1, -1
};
int times = 0;
boolean flag = false;
MazePoint pt = (MazePoint) team.get(top);
x = pt.getX();
y = pt.getY();
pt.visted = true;
ro1: while (times < 4) {
int dir = rnd.nextInt(4);
if (val[dir] == dir)
continue;
else
val[dir] = dir;
switch (dir) {
case 0: //
if ((x - 1) >= 0 && maze.get(x - 1 + y * width).visted == false) {
maze.get(x + y * width).setLeft();
maze.get(x - 1 + y * width).setRight();
team.add(maze.get(x - 1 + y * width));
top++;
flag = true;
break ro1;
}
break;
case 1: //
if ((x + 1) < width && maze.get(x + 1 + y * width).visted == false) {
maze.get(x + y * width).setRight();
maze.get(x + 1 + y * width).setLeft();
team.add(maze.get(x + 1 + y * width));
top++;
flag = true;
break ro1;
}
break;
case 2: //
if ((y - 1) >= 0 && maze.get(x + (y - 1) * width).visted == false) {
maze.get(x + y * width).setUp();
maze.get(x + (y - 1) * width).setDown();
team.add(maze.get(x + (y - 1) * width));
top++;
flag = true;
break ro1;
}
break;
case 3: //
if ((y + 1) < height && maze.get(x + (y + 1) * width).visted == false) {
maze.get(x + y * width).setDown();
maze.get(x + (y + 1) * width).setUp();
team.add(maze.get(x + (y + 1) * width));
top++;
flag = true;
break ro1;
}
break;
}
times += 1;
}
if (!flag) {
team.remove(top);
top -= 1;
}
}
return maze;
}
}
迷宮
// :zhongZw
// :[email protected]
package cn.zhongZw.model;
import java.util.*;
import java.lang.*;
public class MazePoint {
private int left = 0;
private int right = 0;
private int up = 0;
private int down = 0;
private int x;
private int y;
public boolean visted;
public MazePoint(int x, int y) {
this.x = x;
this.y = y;
}
public int getLeft() {
return left;
}
public void setLeft() {
this.left = 1;
}
public int getRight() {
return right;
}
public void setRight() {
this.right = 1;
}
public int getUp() {
return up;
}
public void setUp() {
this.up = 1;
}
public int getDown() {
return down;
}
public void setDown() {
this.down = 1;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。