开发工具：Android Studio 3.1
开发语言：java
闲来无事，自己做了一个迷宫自动寻路游戏
算法简介：
2D迷宫地图自动生成算法：首先随机生成一个迷宫，但是有可能没有路，所以先进行一次搜索，如果搜索不通，就随机选择一个访问过的点，然后设置这个点四周都可以走，这样可以保证一定有一条路可以走出迷宫。
迷宫自动寻路算法：主要采用深度优先搜索算法，同时对每个方向加入权重，对于四个搜索方向，首先搜索那个离终点最近的那个方向，然后搜索权重次大的那个方向，如果可以继续往下搜索就继续往下，重新计算下一个点的权重。如果走不通就回退到上一个点，搜索除目前走的的其他权重最大的方向。
下面是部分代码：
void FindWay()
{
int i,j;
int tx,ty;
//acc为已访问，noacc为未访问,针对的是maze
Vector<Node> acc=new Vector<Node>();
Vector<Node> noacc=new Vector<Node>();
//开始小maze所有元素加入未访问列表noacc
for( i=0;i<10;i++)
for(j=0;j<10;j++)
noacc.addElement(new Node(i,j));
//从noacc中随机选取一个元素
Node temp=RandNode(noacc,noacc.size());
noacc.removeElement(temp);
acc.addElement(temp);
maze2[temp.x][temp.y]=1;
while(acc.size()<100)
{
//reverse表示访问过 verse表示没有访问过
Vector<Integer> reverse=new Vector<Integer>();
Vector<Integer> verse =new Vector<Integer>();
for(i=0;i<4;i++)
{
tx=temp.x+walk_dir[i].x;
ty=temp.y+walk_dir[i].y;
//保证移动后的点在小maze中
if(tx>=0&&tx<10&&ty>=0&&ty<10)
{
//找未访问过的点
if(maze2[tx][ty]==0) //没有被访问过
{
verse.addElement(new Integer(i));
}
else //被访问过
{
reverse.addElement(new Integer(i));
}
}
}
//如果四周都被访问过,则可能为死点，将四周打通且打通一个2*2的空间
if(verse.size()==0)
{
temp=RandNode(acc,acc.size());
}
//存在没有被访问的点
else
{
Random r=new Random();
int t=r.nextInt(verse.size());
int m=verse.elementAt(t);
maze1[temp.x*2+1+walk_dir[m].x][temp.y*2+1+walk_dir[m].y]=1;
temp=new Node(temp.x+walk_dir[m].x,temp.y+walk_dir[m].y);
noacc.removeElement(temp);
acc.addElement(temp);
maze2[temp.x][temp.y]=1;
}
}
}
下面是截图：
全部代码在本人的github里，下面是相关链接，有兴趣的读者自行下载：
https://github.com/jiang-congcong/Maze
转载自原文链接, 如需删除请联系管理员。
原文链接：安卓迷宫自动寻路，转载请注明来源！