最近發現很多人都在寫演算法類的博客，今天就獻丑了使用HTML,CSS和JavaScript制作一個簡單的迷宮生成小代碼，證明了自己對一些簡單的小演算法還是可以駕馭的，基本功沒有荒廢，
迷宮生成有很多種演算法，今天給大家展示的是鉆孔法（道路延伸），
- 1 首先將陣列所有屬性都設定成為墻，
- 2 進行道路挖掘，在陣列中進行道路屬性值設定，每次隨機選擇點打樁，在打樁資料旁邊進行延伸路徑，向上、向下、向左或向右看前方兩個方格，如果那不是通道，則延長道路，如果無法延長道路，此時從現有道路中隨機選擇點（但 X 和 Y 坐標偶數的點）并延長道路，
- 3 重復步驟2的操作并用道路填滿整個螢屏，完成迷宮，
鉆孔法的特點
演算法的特點是遇到墻壁才會生成道路，如果存在道路無法通過的墻壁死胡同，就會在墻壁周圍生產道路，由此可以看出，這種迷宮生成方法傾向于圍繞起點生成通道，換句話說迷宮以起點，到終點目標的正確路徑是最短路徑，這樣的生產方式小型迷宮沒有問題，但是當你創建一個大迷宮時，答案就變得很單調了，另外，通道是隨機彎曲的，直線很少，所以如果你創建一個大迷宮，它會看起來很亂很復雜，
html構成
<div style="margin-bottom:10px;">
迷宮格子數
<input id="sumSize" type="text" value="20" style="width:30px;">
<button id="創建迷宮">創建迷宮</button>
</div>
<div id="zhtbs"></div>
墻壁生成Js演算法
for (var i = 0; i < this.size; i++) {
var row = [];
this.box.push(row);
for (var j = 0; j < this.size; j++) {
// 第一行和最后一行是墻
if (i === 0 || (i + 1) === this.size) {
row.push(0);
// 第一列和最后一列也是墻壁
} else if (j === 0 || (j + 1) === this.size) {
row.push(0);
// 奇數行都是過路
} else if (i % 2 === 1) {
row.push(1);
// 偶數行墻壁和路交替排列
} else {
// 墻壁和路
row.push(j % 2);
}
}
}
-
第一行與最后一行全是墻壁
-
第一列與最后一列全是墻壁
-
奇數行都是路
-
偶數行墻壁和路交替出現
道路生成演算法（鉆孔法）
- 第一行與最后一行 不生成路
- 不是偶數墻的不生成路
- 設定所有需要鉆孔方位置的鉆孔方向都是在上方開始
- 隨機排列墻的方向，在墻的周圍隨機向一個方向進行鉆孔打路
for (var r = 0; r < this.box.length; r++) {
// 第一行與最后一行 生成
if (r === 0 || (r + 1) === this.box.length) {
continue;
}
// 生成有墻的行
if (r % 2 === 1) {
continue;
}
// 獲得行
var row = this.box[r];
// 初始化行，上下左右 引數
var direction = ['top', 'bottom', 'left', 'right'];
if (r >= 4) {
// 出了第一行，默認都是上
direction = direction.slice(1);
}
for (var i = 0; i < row.length; i++) {
//邊緣不生成路
if (i === 0 || (i + 1) === row.length) {
continue;
}
// 獲得處理墻
if (i % 2 === 0) {
// 隨機排列墻的方向
direction = this.shuffle(direction);
// 隨機向一個方向，生成路
// 在隨機方向上去掉墻壁生成路
for (var j = 0; j < direction.length; j++) {
if (direction[j] === "top") {
if (this.box[r-1][i] === 1) {
this.box[r-1][i] = 0;
break;
}
}
if (direction[j] === "left") {
if (this.box[r][i-1] === 1) {
this.box[r][i-1] = 0;
break;
}
}
if (direction[j] === "right") {
if (this.box[r][i+1] === 1) {
this.box[r][i+1] = 0;
break;
}
}
if (direction[j] === "bottom") {
if (this.box[r+1][i] === 1) {
this.box[r+1][i] = 0;
break;
}
}
}
}
}
}
迷宮演算法完整代碼
<html>
<head>
<meta charset="UTF-8">
<title>Maze</title>
<style>
.maze {
}
.maze:after {
width: 0;
height: 0;
content: "";
clear: both;
}
.w {
background-color: blue;
width: 10px;
height: 10px;
padding: 0;
margin: 0;
float: left;
}
.p {
background-color: white;
width: 10px;
height: 10px;
padding: 0;
margin: 0;
float: left;
}
.s, .e {
background-color: yellow;
width: 10px;
height: 10px;
padding: 0;
margin: 0;
float: left;
}
</style>
<script>
</script>
<body>
<div style="margin-bottom:10px;">
迷宮格子數
<input id="sumSize" type="text" value="20" style="width:30px;">
<button id="創建迷宮" onclick="onRun()">創建迷宮</button>
</div>
<div id="zhtbs"></div>
<script>
function zht(size){
this.pagesum=size;
this.size = (size % 2 === 0 ? size + 1 : size);
this.box = [];
this.$maze = document.querySelector("#zhtbs");
this.ALGO = {STICK: 1};
this.shuffle =function (o) {
for(var j, x, i = o.length; i; j = Math.floor(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
return o;
}
this.show = function () {
var snipet = '';
for (var i = 0; i < this.size; i++) {
for (var j = 0; j < this.size; j++) {
if (i == 0 && j == 1) {
//入口
snipet += '<div class="p"></div>';
}
else if (i==(this.pagesum%2==0?this.pagesum:this.pagesum-1) && j == (this.pagesum%2==0?this.pagesum-1:this.pagesum-2)) {
// 出口
snipet += '<div class="p"></div>';
}
else if (this.box[j][i] === 0) {
// 墻
snipet += '<div class="w"></div>';
}
else {
// 路
snipet += '<div class="p"></div>';
}
}
}
this.$maze.innerHTML = snipet;
this.$maze.style.height = (this.size * 10) + 'px';
this.$maze.style.width = (this.size * 10) + 'px';
}
this.create = function (options) {
options = options || {};
if (options.algorithm === this.ALGO.STICK) {
this._createByStick();
}
this.show();
}
this._createByStick = function () {
//初始化 墻與路生成
this.box = [];
for (var i = 0; i < this.size; i++) {
var row = [];
this.box.push(row);
for (var j = 0; j < this.size; j++) {
// 第一行和最后一行是墻
if (i === 0 || (i + 1) === this.size) {
row.push(0);
// 第一列和最后一列也是墻壁
} else if (j === 0 || (j + 1) === this.size) {
row.push(0);
// 奇數行都是過道
} else if (i % 2 === 1) {
row.push(1);
// 偶數行墻壁和通道交替排列
} else {
// 墻壁和通道
row.push(j % 2);
}
}
}
for (var r = 0; r < this.box.length; r++) {
// 第一行與最后一行 生成
if (r === 0 || (r + 1) === this.box.length) {
continue;
}
// 生成有墻的行
if (r % 2 === 1) {
continue;
}
// 獲得行
var row = this.box[r];
// 初始化行，上下左右 引數
var direction = ['top', 'bottom', 'left', 'right'];
if (r >= 4) {
// 出了第一行，默認都是上
direction = direction.slice(1);
}
for (var i = 0; i < row.length; i++) {
//邊緣不生成路
if (i === 0 || (i + 1) === row.length) {
continue;
}
// 獲得處理墻
if (i % 2 === 0) {
// 隨機排列墻的方向
direction = this.shuffle(direction);
// 隨機向一個方向，生成路
// 在隨機方向上去掉墻壁生成路
for (var j = 0; j < direction.length; j++) {
if (direction[j] === "top") {
if (this.box[r-1][i] === 1) {
this.box[r-1][i] = 0;
break;
}
}
if (direction[j] === "left") {
if (this.box[r][i-1] === 1) {
this.box[r][i-1] = 0;
break;
}
}
if (direction[j] === "right") {
if (this.box[r][i+1] === 1) {
this.box[r][i+1] = 0;
break;
}
}
if (direction[j] === "bottom") {
if (this.box[r+1][i] === 1) {
this.box[r+1][i] = 0;
break;
}
}
}
}
}
}
}
}
function onRun(){
var size = parseInt(document.querySelector("#sumSize").value);
if (isNaN(size)) size = 20;
var z=new zht(size);
z.create({algorithm: 1});
}
onRun();
</script>
</body>
</html>
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/294739.html
標籤：其他