js实现扫雷-算法分析
扫雷实现及其算法分析
本⽂主要是通过使⽤Javascript，通过对扫雷游戏中⽤到的算法分析，⼀步步实现⽤到的算法，进⽽实现扫雷过程，本⽂没有对实际游戏进⾏完善，主要是针对于算法分析，帮助⼩伙伴应对免试或者求职时遇到的算法；
1. 随机⽣成雷区
这⾥我们使⽤经典的洗牌算法来实现雷区的随机化，尽量保证每个格⼦⽣成雷的概率相等；每次从当前坐标点之后的⼆维数组中随机选择⼀个坐标，并将⽣成的随机坐标（randx,randy）与当前选择的坐标互换，实现⼀次随机选择；
function shuffle(arr){
for(var i=0;i<n*m;i++){
// 从[i,n)区间随机选择元素
var number=Math.floor(Math.random()*(n*m-i))+i;
var x=parseInt(i/m);
var y=parseInt(i%m)
var randx=parseInt(number/m);
var randy=parseInt(number%m);
swap(arr,x,y,randx,randy);
}
}
2.计算每个格⼦周围的雷的数量
以当前坐标点为中⼼，对周围⼋个点进⾏遍历，每个雷的位置table[x][y]值为1，isArea()函数⽤于判断当前遍历的坐标点是否在⼆维数组范围内，函数实现会在下⾯给出，将每个点周围的雷的数量存储在⼀个新的⼆维数组numbers中；
// 计算每个格⼦周围的雷的数量
function cauletenum(){
for(var i=0;i<n;i++)
for(var j=0;j<m;j++){
// 如果检测到雷，将这个点的数值记为-1；表⽰游戏结束
if(table[i][j]==1)
numbers[i][j]=-1;
else
{
//遍历⼋个点，并将雷的数量累加计算出来
for(var ii=i-1;ii<=i+1;ii++)
for(var jj=j-1;jj<=j+1;jj++)
{
if(isArea(ii,jj)&&table[ii][jj]==1)
numbers[i][j]++;
}
}
}
}
3.点击空⽩打开⼀⽚雷区的算法（floodfill）
对当前是空⽩的坐标点，对其周围上下左右四个⽅向进⾏深度优先遍历，碰到数字或者雷时停⽌向下的遍历；
// 当点击的位置是空的，则进⾏深度优先遍历，进⽽打开⼀⽚区域，
//碰到数字停⽌；
function open(x,y){
if(!isArea(x,y))
js 二维数组
{
//如果当前位置不在数组范围，则返回
return;
}
if(table[i][j]==1)
{
//点到雷，游戏结束
return;
}
open[x][y]=true;
// 如果点到的是带有数字的格，表⽰周围有雷，直接返回
if(numbers[x][y]>0)
return;
for(var i=x-1;i<=x+1;i++)
for(var j=y-1;j<=y+1;j++)
// 在有效区域，并且没有打开过，并且不是雷，则打开该区域
if(isArea(i,j)&&!open[i][j]&&table[i][j]!=1)
open(i,j);//进⾏深度优先遍历
}
以下为案例源码：
每个函数都有详细注释，不明⽩的地⽅欢迎留⾔，有更好的意见也欢迎指导；GitHub-
Blog-
var n=10,m=10,war=20;//n⾏  m列  war雷
//⽣成⼆维数组，初始没有雷，所有都为0
var table=new Array();//游戏区域
var numbers=new Array();//每个格⼦周围雷的数量
var open=new Array();//是否被打开过
// 数组的初始化
for(var i=0;i<n;i++)
{
numbers[i]=new Array(m);
table[i]=new Array(m);
open[i]=new Array(m);
for(var j=0;j<m;j++)
{
numbers[i][j]=0;
table[i][j]=0;
open[i][j]=false;
}
}
// 雷区初始化完成渲染到窗⼝
function render(){
for(var i=0;i<n;i++){
for(var j=0;j<m;j++)
{
document.write(table[i][j]+"  ")
}
document.write("<br>")
}
}
//初始化雷区
function init(arr){
reset(arr);
shuffle(arr);
// render();
}
// 将雷顺序排在⼆唯数组中
function reset(arr)
{
for(var i=0;i<war;i++)
{
var x=parseInt(i/m);
var y=parseInt(i%m)
arr[x][y]=1;
}
}
// 随机排列
function shuffle(arr){
for(var i=0;i<n*m;i++){
// 从[i,n)区间随机选择元素
var number=Math.floor(Math.random()*(n*m-i))+i;
var x=parseInt(i/m);
var y=parseInt(i%m)
var randx=parseInt(number/m);
var randy=parseInt(number%m);
swap(arr,x,y,randx,randy);
}
}
// 将随机产⽣的位置与顺序位置交换
function swap(arr,x,y,randx,randy){
var t=arr[x][y];
arr[x][y]=arr[randx][randy];
arr[randx][randy]=t;
}
// 判断坐标是否在数组中
function isArea(x,y)
{
if(x>=0&&x<n&&y>=0&&y<m)
return true;
else
return false;
}
// 计算每个格⼦周围的雷的数量
function cauletenum(){
for(var i=0;i<n;i++)
for(var j=0;j<m;j++){
// 如果检测到雷，将这个点的数值记为-1；表⽰游戏结束
if(table[i][j]==1)
numbers[i][j]=-1;
else
{
//遍历⼋个点，并将雷的数量累加计算出来
for(var ii=i-1;ii<=i+1;ii++)
for(var jj=j-1;jj<=j+1;jj++)
{
if(isArea(ii,jj)&&table[ii][jj]==1)
numbers[i][j]++;
}
}
}
}
// 当点击的位置是空的，则进⾏深度优先遍历，进⽽打开⼀⽚区域，碰到数字停⽌；
function open(x,y){
if(!isArea(x,y))
{
//如果当前位置不在数组范围，则返回
return;
}
}
if(table[i][j]==1)
{
//点到雷，游戏结束
return;
}
open[x][y]=true;
// 如果点到的是带有数字的格，表⽰周围有雷，直接返回
if(numbers[x][y]>0)
return;
for(var i=x-1;i<=x+1;i++)
for(var j=y-1;j<=y+1;j++)
/
/ 在有效区域，并且没有打开过，并且不是雷，则打开该区域                if(isArea(i,j)&&!open[i][j]&&table[i][j]!=1)
open(i,j);//进⾏深度优先遍历
}
// document.write("<br>")
// 将⽣成的雷区⽤表格的形式渲染出来
function rendertable(){
var tmp="<table>"
// console.log(numbers
for(var i=0;i<n;i++){
tmp+="<tr>";
for(var j=0;j<m;j++)
{
if(numbers[i][j]==-1)
tmp+="<td>"+"❤"+"</td>"
else
tmp+="<td>"+numbers[i][j]+"</td>"
// document.write(numbers[i][j]+"  ")
}
tmp+="</tr>";
document.write("<br>")
}
tmp+="</table>";
document.write(tmp);
}
init(table);
cauletenum();
rendertable();

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。