基于dfs算法在csgo中用vscript制作一个14*14的必定有解的迷宫

破碎的盾 · 发表于 2022-6-28 11:24:44

不注册个乐园论坛账号能玩??

您需要登录才可以下载或查看，没有账号？注册

×

本帖最后由破碎的盾于 2022-6-28 15:32 编辑

左上角为入口，右下角是出口。
视频里的是10*10，由于vscript的自带脚本防死循环保护，过大的迷宫可能会因为保护运行到一半被报错。
首先，先明晰什么是DFS？

深度优先遍历（Depth First Search, 简称 DFS），深度优先遍历主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
其代码大概思路，我借鉴https://blog.csdn.net/qq_45724216/article/details/115305585中的叙述，应该是这样的。

那么就很简单了，我们主要的目标分为了两大类，第一步是随机生成14*14的迷宫数组，第二步是利用DFS对其进行检验，如果不通过检验，则不批准迷宫生成；如果检验通过，迷宫成功生成。

maze_chunk <- [];
maze_check <- [];
spawner <- Entities.FindByName(null,"chunk_maker");
spawner_origin <- spawner.GetOrigin();
j <- 0; i <- 0;
for(j=0;j<15;j++){
maze_check.push([]);
for(i=0;i<15;i++){
maze_check[j].push(0);
}
}
for(j=0;j<15;j++){
maze_chunk.push([]);
for(i=0;i<15;i++){
maze_chunk[j].push(RandomInt(0,3));
}
}
function generate_maze()
{
if(Entities.FindByNameNearest("chunk1_brush", spawner_origin, 1024)!=null) return;
else{
j <- 0; i <- 0;
for(j=0;j<15;j++){
for(i=0;i<15;i++){
maze_chunk[j][i]=RandomInt(0,3);
}
}
maze_chunk[0][0]=0;
maze_chunk[14][14]=0;
check_maze_start();
if(maze_check[14][14]!=1) generate_maze();
}
}
function check_maze_start()
{
j <- 0; i <- 0;
for(j=0;j<15;j++){
for(i=0;i<15;i++){
maze_check[j][i]=0;
}
}
check_maze(0,0);
}
function check_maze(x,y)
{
maze_check[x][y]=1;
if(x==14&&y==14){
print_maze();
return;
}
else if(x==0){
if(y==0){
check_maze_right(x,y);
check_maze_down(x,y);
}
else if(y==14){
check_maze_up(x,y);
check_maze_right(x,y);
}
else{
check_maze_up(x,y);
check_maze_right(x,y);
check_maze_down(x,y);
}
}
else if(x==14){
if(y==0){
check_maze_left(x,y);
check_maze_down(x,y);
}
else{
check_maze_down(x,y);
check_maze_up(x,y);
check_maze_left(x,y);
}
}
else if(y==0){
if(x==0){
check_maze_right(x,y);
check_maze_down(x,y);
}
else if(x==14){
check_maze_down(x,y);
check_maze_left(x,y);
}
else{
check_maze_right(x,y);
check_maze_left(x,y);
check_maze_down(x,y);
}
}
else if(y==14){
if(x==0){
check_maze_up(x,y);
check_maze_right(x,y);
}
else{
check_maze_left(x,y);
check_maze_up(x,y);
check_maze_right(x,y);
}
}
else{
check_maze_up(x,y);
check_maze_left(x,y);
check_maze_down(x,y);
check_maze_right(x,y);
}
}
function check_maze_left(x,y)
{
if(maze_chunk[x-1][y]!=1 && maze_chunk[x-1][y]!=2 && maze_check[x-1][y]==0) check_maze(x-1,y);
}
function check_maze_right(x,y)
{
if(maze_chunk[x+1][y]!=1 && maze_chunk[x+1][y]!=2 && maze_check[x+1][y]==0) check_maze(x+1,y);
}
function check_maze_up(x,y)
{
if(maze_chunk[x][y-1]!=1 && maze_chunk[x][y-1]!=2 && maze_check[x][y-1]==0) check_maze(x,y-1);
}
function check_maze_down(x,y)
{
if(maze_chunk[x][y+1]!=1 && maze_chunk[x][y+1]!=2 && maze_check[x][y+1]==0) check_maze(x,y+1);
}
function print_maze()
{
local spawner = Entities.CreateByClassname("env_entity_maker");
local j=0;local i=0;
for(j=0;j<15;j++){
for(i=0;i<15;i++){
if(maze_chunk[j][i]==0){
spawner.__KeyValueFromString("EntityTemplate", "chunk0");
spawner.SpawnEntityAtLocation(spawner_origin, Vector(0, 0, 0));
}
if(maze_chunk[j][i]==1){
spawner.__KeyValueFromString("EntityTemplate", "chunk1");
spawner.SpawnEntityAtLocation(spawner_origin, Vector(0, 0, 0));
}
if(maze_chunk[j][i]==2){
spawner.__KeyValueFromString("EntityTemplate", "chunk1");
spawner.SpawnEntityAtLocation(spawner_origin, Vector(0, 0, 0));
}
if(maze_chunk[j][i]==3){
spawner.__KeyValueFromString("EntityTemplate", "chunk0");
spawner.SpawnEntityAtLocation(spawner_origin, Vector(0, 0, 0));
}
spawner_origin.x-=128;
}
spawner_origin.x+=1920;
spawner_origin.y-=128;
}
spawner_origin.y+=1920;
}

复制代码

地图上要先做好命名为chunk0和chunk1的两种template，分别是空气和障碍物就行，还要放一个info_target命名为chunk_maker，用于指引迷宫生成的左上角基准点。然后放个按钮每次拍下就执行generate_maze()就行了。
有什么问题留言细说。不要水贴，移步别处，我担心看不见需要帮助的回复。