0
我想用javascript（深度優先搜索算法）生成迷宮。我已經閱讀了很多DFS算法。但是我正面臨着迷宮生成的困難。生成的迷宮根本不像迷宮。我試圖按照最基本的一個使用堆棧來保持路徑記錄以創建一個迷宮。我有兩個文件一個maze.js和另一個index.html來顯示迷宮的輸出。在javascript中使用DFS算法的奇怪輸出代的生成
下面是maze.js
function Cell(center) {
this.center_cell = center;
this.neighbours = null;
this.visited = false;
// top, right, bottom, left neighbours, 1
// means the wall in between has been
// removed
this.walls = [ 0, 0, 0, 0 ];
this.last_selected_neigh = null;
this.calc_neighbours = function() {
var n_top = [ this.center_cell[0], this.center_cell[1] - 1 ];
var n_right = [ this.center_cell[0] + 1, this.center_cell[1] ];
var n_bottom = [ this.center_cell[0], this.center_cell[1] + 1 ];
var n_left = [ this.center_cell[0] - 1, this.center_cell[1] ];
this.neighbours = new Array(n_top, n_right, n_bottom, n_left);
// console.log(this.neighbours);
return this.neighbours;
};
this.set_visited = function() {
this.visited = true;
};
this.get_visited = function() {
return this.visited;
};
this.get_neighbours = function() {
return this.calc_neighbours();
};
this.get_random_neighbour = function() {
this.calc_neighbours();
var rand_neigh = Math.floor(Math.random() * 4);
this.last_selected_neigh = rand_neigh;
// break the walls that is in-between this cell and other neighbour
// this.walls[rand_neigh] = 1;
return this.neighbours[rand_neigh];
};
this.get_walls = function() {
return this.walls;
};
this.remove_wall = function() {
this.walls[this.last_selected_neigh] = 1;
};
};
var maze = {
width : null,
height : null,
cells : [],
build : function(width, height) {
this.width = width;
this.height = height;
return this;
},
get_width : function() {
return this.width;
},
get_height : function() {
return this.height;
},
put_cell : function(x, y, item) {
this.cells[x][y] = item;
},
pop_cell : function() {
this.cells.pop();
},
init : function() {
for (var y = 0; y < this.get_height(); y++) {
// cell_pos = new Array();
for (var x = 0; x < this.get_width(); x++) {
this.cells[x] = new Array();
this.cells[x][y] = new Array();
}
}
return this;
},
begin : function() {
// initialize the empty cells
this.init();
var randomCell = [ Math.floor(Math.random() * this.get_height()),
Math.floor(Math.random() * this.get_width()) ];
var cell = new Cell(randomCell);
var total_cells = this.width * this.height;
var total_visits = 1;
var stack = [];
cell.set_visited();
stack.push(cell);
while (total_visits <= total_cells) {
var random_pos = cell.get_random_neighbour();
var r_x = random_pos[0];
var r_y = random_pos[1];
var random_neighbour = new Cell(random_pos);
// get all neighbours
random_neighbour.calc_neighbours();
if (random_neighbour.get_visited() == false) {
// this.cells.push(cell);
if (r_x > -1 && r_x < this.get_width() && r_y > -1
&& r_y < this.get_height()) {
stack.push(random_neighbour);
random_neighbour.set_visited();
cell.remove_wall();
this.put_cell(r_x, r_y, cell);
cell = random_neighbour;
}
// Set the currently selected random neighbour as current cell
} else {
cell = stack.pop();
}
// Update the visit counter
total_visits++;
}
// console.log(this.get_all_cells());
},
get_cell : function(x, y) {
return this.cells[x][y];
},
get_all_cells : function() {
return this.cells;
},
draw : function() {
$table = $('<tbody></tbody>');
for (var y = 0; y < this.height; y++) {
$tr = $('<tr></tr>');
$table.append($tr);
for (var x = 0; x < this.width; x++) {
$td = $('<td> </td>');
$tr.append($td);
if (this.get_cell(x, y) != undefined) {
var cur_cell = this.get_cell(x, y);
// console.log(cur_cell.center_cell);
if (typeof cur_cell == "object") {
if (cur_cell.visited
&& cur_cell.center_cell[0] < this.get_width()
&& cur_cell.center_cell[0] > -1
&& cur_cell.center_cell[1] > -1
&& cur_cell.center_cell[1] < this.get_height()) {
var walls = cur_cell.get_walls();
// console.log(cur_cell);
///console.log(walls);
if (walls[0] == 0) {
$td.css({
'border-top' : '2px solid #000'
});
}
if (walls[1] == 0) {
$td.css('border-right', '2px solid #000');
}
if (walls[2] == 0) {
$td.css('border-bottom', '2px solid #000');
}
if (walls[3] == 0) {
$td.css('border-left', '2px solid #000');
}
// console.log(walls_bound);
}
}
}
}
}
$("#maze").html($table);
}
}
的代碼下面是index.html代碼：
<html>
<head>
<title>Maze</title>
<script src="lib/jquery.js"></script>
<script src="src/maze.js"></script>
<style type="text/css">
#maze {
border:2px solid #000;
border-spacing:0;
border-collapse:collapse;
}
#maze td {
/* border:2px solid #000; */
width: 20px;
height: 20px;
}
#maze tr {
height:20px;
}
</style>
</head>
<body>
<table id="maze" cellspacing="1" cellpadding="1">
</table>
<script>
var m = maze.build(4,4);
m.begin();
m.draw();
</script>
</body>
</html>
，我得到的輸出是非常不同的，甚至沒有像迷宮的。這應該是非常基本的算法。
我的問題：
- 我的代碼不會從棧中彈出的元素，我不知道爲什麼。我試圖保持
cell=stack.pop斷點，它似乎永遠不會到達那裏。 - 我還不清楚迷宮的死角。任何人都可以請我指出正確的方向？
在此先感謝您。
