精华内容
下载资源
问答
  • Java-复杂迷宫求解

    2018-04-17 02:38:55
    总体的思路不太复杂:首先创建一个栈结构,可以方便的输出最短的路径,然后就是合理的运用递归的思想来进行路径的回溯。先上代码。interface Method{//实现迷宫的栈结构的接口 int MAX = 50;//栈的最大存储量,也...

        最近用C学了数据结构的迷宫求解问题,但是个人感觉用C实现特别麻烦。索性用Java来实现了。总体的思路不太复杂:首先创建一个栈结构,可以方便的输出最短的路径,然后就是合理的运用递归的思想来进行路径的回溯。先上代码。

    interface Method{//实现迷宫的栈结构的接口
        int MAX = 50;//栈的最大存储量,也就是路径的最长量
        void StackInit(StackList stackList);//初始化
        void StackAdd(StackList stackList, place Number);//插入
        void StackDelete(StackList stackList);//删除
        void Display(StackList stackList);//打印(测试用)
    }
    
    
    class StackList{//栈结构
        place[] data;
        int size;
        int capacity;
    }
    
    class My_Method implements Method{//实现栈相关方法的类
        @Override
        public void StackInit(StackList stackList) {
            if(stackList == null){
                return;
            }
            stackList.data = new place[MAX];
            stackList.capacity = MAX;
            stackList.size = 0;
        }
    
        @Override
        public void StackAdd(StackList stackList, place Number) {
            if(stackList == null){
                return;
            }
            if(stackList.size == stackList.capacity){
                return;
            }
            stackList.data[stackList.size] = Number;
            stackList.size++;
        }
    
        @Override
        public void StackDelete(StackList stackList) {
            if(stackList == null){
                return;
            }
            if(stackList.size == 0){
                return;
            }
            stackList.size--;
        }
    
        @Override
        public void Display(StackList stackList) {
            if(stackList == null){
                return;
            }
            for(int i = 0;i<stackList.size;i++){
                System.out.print(" "+stackList.data[i]);
            }
        }
    }
    //-----------------------------------------------------------
    
    interface Maze_Method{//有关迷宫地图的实现方法的接口
        int ROW = 6;//迷宫的行与列
        int COL = 6;
        boolean Exit(Maze maze,place now_place,place start);//检查是不是出口
        void mark(Maze maze, place now_place, place prev_place);//做标记
        boolean CanStay(Maze maze, place now_place, place prev_place);//判断是否可以落到这个位置上
        void Walk(Maze maze, place start, place now_place, place prev_place, StackList cur, StackList _short, Method My_Test);//递归函数
        void Init(Maze maze);//初始化地图
        void Display(Maze maze);//打印地图
    }
    interface Maze_area{
        int ROW = 6;//迷宫的大小
        int COL = 6;
    }
    
    class Maze implements Maze_area{//迷宫地图
        int[][] map = new int[ROW][COL];
    }
    
    class My_Maze_Method implements Maze_Method{//实现迷宫相关的方法
    
        @Override
        public void Init(Maze maze) {//初始化地图
            int[][] New_Map = new int[][]{{0,1,0,0,0,0},
                                          {1,1,0,0,0,0},
                                          {0,1,0,1,1,1},
                                          {1,1,1,1,0,0},
                                          {0,0,0,1,0,0},
                                          {0,0,0,1,0,0,}};
            maze.map = New_Map;
        }
    
        @Override
        public void Display(Maze maze) {//打印地图
            for(int i = 0;i<maze.map.length;i++){
                for(int j = 0;j<maze.map[0].length;j++){
                    System.out.print(" "+ maze.map[i][j]);
                }
                System.out.println();
            }
        }
    
        @Override
        public boolean Exit(Maze maze, place now_place, place start) {//检查是否是出口
            if(now_place == start){
                return false;
            }
            if(now_place.row == 0 || now_place.row == ROW-1 || now_place.col == 0 || now_place.col == COL-1){
                return true;
            }
            return false;
        }
    
        @Override
        public boolean CanStay(Maze maze, place now_place, place prev_place) {//检查某位置是否合法
            if((now_place.row >= ROW) || (now_place.row < 0) || (now_place.col >= COL) || (now_place.col < 0)){
                return false;
            }
            if(maze.map[now_place.row][now_place.col] == 0){
                return false;
            }
            if(maze.map[now_place.row][now_place.col] == 1){
                return true;
            }
            if(maze.map[prev_place.row][prev_place.col] > (maze.map[now_place.row][now_place.col] + 1)){
                return true;
            }
            return false;
        }
    
        @Override
        public void mark(Maze maze, place now_place, place prev_place) {//标记一个位置
            if (prev_place.row == -1 && prev_place.col == -1) {
    
                maze.map[now_place.row][now_place.col] = 2;
            } else {
                maze.map[now_place.row][now_place.col] = maze.map[prev_place.row][prev_place.col] + 1;
            }
        }
    
        @Override
        public void Walk(Maze maze, place start, place now_place, place prev_place, StackList cur, StackList _short, Method My_test) {//递归函数
            if(!CanStay(maze,now_place,prev_place)){//看是否可以在这个位置走
                return;
            }
            mark(maze,now_place,prev_place);//做标记
            My_test.StackAdd(cur,now_place);//将能走的地方入栈
    
            if(Exit(maze,now_place,start)){//如果是出口,那么把cur栈和_short栈的大小做比较,
                if(_short.size == 0) {//把比较小的那个保存在_short栈中
                    _short.data = cur.data;
                    _short.size = cur.size;
                    _short.capacity = cur.capacity;
                }
                if(_short.size > cur.size){
                    _short.data = cur.data;
                    _short.size = cur.size;
                    _short.capacity = cur.capacity;
                }
                My_test.StackDelete(cur);//如果是出口,那么删除栈顶,回溯
                System.out.println("找到一个出口");
                return;
            }
    //顺时针扫描一个位置的上下左右
            place up = new place(now_place.row-1,now_place.col);
            prev_place = now_place;
            Walk(maze,start,up,prev_place,cur,_short,My_test);
    
            place right = new place(now_place.row,now_place.col+1);
            prev_place = now_place;
            Walk(maze,start,right,prev_place,cur,_short,My_test);
    
            place down = new place(now_place.row+1,now_place.col);
            prev_place = now_place;
            Walk(maze,start,down,prev_place,cur,_short,My_test);
    
            place left = new place(now_place.row,now_place.col-1);
            prev_place = now_place;
            Walk(maze,start,left,prev_place,cur,_short,My_test);
            My_test.StackDelete(cur);
        }
    }
    
    
    //-------------------------------------------------------
    
    class place{//描述点的位置
        int row;
        int col;
        place(int row, int col){
            this.row = row;
            this.col = col;
        }
        place(){}
    }
    
    public class Main{
        public static void main(String[] args){
            Maze My_Maze = new Maze();//创建栈对象
            Method Test_stack = new My_Method();//创建栈的实现对象
            StackList stackList_cur = new StackList();//创建每条路径的栈对象
            StackList stackList_short = new StackList();//创建代表最短路径的栈对象
            Test_stack.StackInit(stackList_cur);//初始化栈对象
            Test_stack.StackInit(stackList_short);//初始化栈对象
            Maze_Method New_Test = new My_Maze_Method();//初始化迷宫的实现对象
            place Enter = new place(0,1);//创建入口对象
            place Prev = new place(-1,-1);//创建前一个对象(这里的赋值主要针对入口点,我们可以直接把它赋值成特定的非法值)
            Maze maze = new Maze();//创建地图对象
            New_Test.Init(maze);//初始化地图
            New_Test.Walk(maze,Enter,Enter,Prev,stackList_cur,stackList_short,Test_stack);//实现迷宫求解的主要递归方法
            New_Test.Display(maze);//打印迷宫路径
            System.out.println("迷宫的最短路径是:");
            for(int i = 0; i<stackList_short.size;i++){//打印最短路径
                System.out.println("("+stackList_short.data[i].row+","+stackList_short.data[i].col+")");
            }
        }
    }
        嗯,如果有不合理的地方还请大神指教。
    展开全文
  •  初始化迷宫地图数据 --》2. 检测迷宫的入口是否有效 --》 3. 检测当前位置是否为迷宫的出口 --》4. 保存最短路径 --》5. 检测当前位置的下一步是否能够走通 --》6. 走迷宫 --》7. 具体走迷宫方式 --》8....

           我们通常见的迷宫多种多样,在这里以多通路迷宫为例,对迷宫进行求解,找出最短路径,用C语言对其进行编写,涉及到一些操作包括:

           1. 初始化迷宫地图数据 --》2.检测迷宫的入口是否有效 --》 3. 检测当前位置是否为迷宫的出口 --》4. 保存最短路径 --》5. 检测当前位置的下一步是否能够走通 --》6. 走迷宫 --》7. 具体走迷宫方式 --》8. 打印迷宫地图数据 --》9. 打印路径 

          下面用C实现该操作的一些代码:

        maze.c-->下面是用递归的方式找到迷宫中的最短路径

     

    #define _CRT_SECURE_NO_WARNINGS 0;
    #include "maze.h"
    #include "stack.h"
    #include <stdio.h>
    #include <assert.h>
    //初始化迷宫
    void MazeInit(maze* s, DataTypeMaze arr[MAZE_ROW][MAZE_COL])
    {
    	assert(s);
    	int i = 0, j = 0;
    	for (i = 0; i < MAZE_ROW; i++)
    	{
    		for (j = 0; j < MAZE_COL; j++)
    		{
    			s->maze[i][j] = arr[i][j];
    		}
    	}
    }
    //打印迷宫
    void PrintMaze(maze m)
    {
    	int i = 0, j = 0;
    	for (i = 0; i < MAZE_ROW; i++)
    	{
    		for (j = 0; j < MAZE_COL; j++)
    		{
    			printf("%d ", m.maze[i][j]);
    		}
    		printf("\n");
    	}
    }
    // 检测迷宫的入口是否有效 
    int IsValidEnter(maze *m, PosType enter)
    {
    	 assert(m);
    	 if ((enter._x == 0) || (enter._y == 0) || (enter._x == MAZE_ROW - 1) || (enter._y == MAZE_COL - 1))
    	 {
    		 if (m->maze[enter._x][enter._y] >= 1)
    			 return 1;
    	 }
    
    	       return 0;
    }
    // 检测cur位置是否为迷宫的出口 
    int IsMazeExit(maze* m, PosType cur, PosType enter)
    {
    	assert(m);
    	if (cur._x == enter._x && cur._y == enter._y)
    		return 0;
    
    	if (cur._x == 0 || cur._x == MAZE_COL - 1 || cur._y == 0 || cur._y == MAZE_ROW - 1)
    	{
    		return 1;
    	}
    
    	return 0;
    }
    // 检测当前位置是否为通路 
    int IsPass(maze* m, PosType cur)
    {
    	assert(m);
    	if (m->maze[cur._x][cur._y] == 1)
    		return 1;
    
    	return 0;
    }
    // 打印路径 
    void PrintPath(Stack* s)
    {
    	assert(s);
    	printf("over");
    	while (!IsEmptyStack(s))
    	{
    		printf("<- %d,%d ", StackTop(s));
    		StackPop(s);
    	}
    }
    
    
    // 检测当前位置的下一步是否能够走通 
    int IsNextPass(maze* m,PosType cur, PosType next)
    {
    	assert(m);
    	if ((m->maze[next._x][next._y] == 1) || (m->maze[cur._x][cur._y]< m->maze[next._x][next._y]))  
    		return 1;
    
        	return 0;
    }
    
    void printPath(Stack Path)
    {
    	int i = 0;
    	for (; i < stackSize(&Path); i++)
    	{
    		printf("%d,%d-> ", Path.arr[i]);
    	}
    	printf("over \n");
    }
    // 保存最短路径 
    void SaveShortPath(Stack* path, Stack* shortPath)
    {
    	assert(path);
    	assert(shortPath);
    	int i = 0;
    	shortPath->_top = 0;
    	for (; i < stackSize(path); i++)
    	{
           StackPush(shortPath, path->arr[i]);
    	}
    }
    // 走迷宫 
    void PassMaze(maze* m, PosType  enter, Stack* ShortPath)
    {
    	assert(m);
    	assert(ShortPath);
    	Stack path;
    	if (!IsValidEnter(m, enter))
    	{
    		printf("无效的入口点");
    		return;
    	}
    
    	StackInit(&path);
    	_PassMaze(m, enter, enter,&path,ShortPath);
    }
    // 复杂迷宫--》具体走迷宫方式 
    void _PassMaze(maze *m, PosType enter,PosType cur, Stack *path,Stack* shortPath)
    {
    	assert(path);
    	assert(shortPath);
    	PosType next = cur;
    
    	if (cur._x ==enter._x && cur._y == enter._y)
    		m->maze[cur._x][cur._y] = 2;
    
    		StackPush(path, cur);
    	if (IsMazeExit(m, cur, enter))
    	{
    			if (shortPath->_top == 0 || stackSize(path)<stackSize(shortPath))
    				SaveShortPath(path, shortPath);
    		  
    			StackPop(path);
    			return;
    	}
    
    	//上
    	next = cur;
    	next._x -= 1;
    	if (IsNextPass(m, cur, next))
    	{
    		m->maze[next._x][next._y] = m->maze[cur._x][cur._y] + 1;
    		_PassMaze(m,enter, next, path, shortPath);
    	}
    
    	//右
    	next = cur;
    	next._y += 1;
    	if (IsNextPass(m, cur, next))
    	{
    		m->maze[next._x][next._y] = m->maze[cur._x][cur._y] + 1;
    		_PassMaze(m, enter, next, path, shortPath);
    	}
    
    	//左
    	next = cur;
    	next._y -= 1;
    	if (IsNextPass(m, cur, next))
    	{
    		m->maze[next._x][next._y] = m->maze[cur._x][cur._y] + 1;
    		_PassMaze(m, enter, next, path, shortPath);
    	}
    
    	//下
    	next = cur;
    	next._x += 1;
    	if (IsNextPass(m, cur, next))
    	{
    		m->maze[next._x][next._y] = m->maze[cur._x][cur._y] + 1;
    		_PassMaze(m, enter, next, path, shortPath);
    	}
    
    	StackPop(path);
    }


    下面是用测试代码

    //多通络带环迷宫
    void testMaze()
    {
    	maze m;
    	Stack shortPath;
    	StackInit(&shortPath);
    	DataType x;
    	x._x = 5;
    	x._y = 1;
    	DataTypeMaze arr[MAZE_ROW][MAZE_COL] = { { 0,0 },{ 0, 1,1,1 },{ 0, 1,0,1 },{ 0, 1, 0, 1},{ 0,1,1,1,1,1 },{ 0, 1} };
    	MazeInit(&m, arr);
    	PrintMaze(m);
    	PassMaze(&m, x, &shortPath);
    	printf("迷宫最短路径--:");
    	PrintPath(&shortPath);
    	printf("**********************\n");
    	PrintMaze(m);
    }
    int main()
    {
    	testMaze();
    	system("pause");
    	return 0;
    }


        上面就是实现复杂迷宫求解的C代码,下一篇会写用循环和递归两种方式对简单迷宫进行求解!!!


    展开全文
  • "迷宫地图为\n-------------------\n" ); for (row = 0 ; row ; row++) { for (col = 0 ; col ; col++) { printf ( " %d " , maze-> map [row][col]); } printf ( "\n" ); } } //检测当前节点...

    所需知识

    结构体
    递归

    ❀思路分析
    1.跟上篇比较区别在于,多通路,同出口,同入口,如何在已经找到了一个出口的情况下,如何返回来找另外一条最短路径,还是用赋值法。
    这里写图片描述
    2.探路的顺序是上左右下。
    从入口开始,通路的条件为,下一位置值为1或值大于当前位置的值,
    赋值依次加1
    每次走位置,都调用一次函数,形成递归
    这里写图片描述
    向上走为最高优先级,走不通后向右走,然后向下
    这里写图片描述
    当前位置进入死胡同,走不通,存储路径的栈弹出该错误位置。并递归到上一层,上一个节点,依此类推。退回到有其他通路可走的节点,再进入该下一位置的函数,进行递归。

    这里写图片描述
    到达出口后,将栈s中保存的这条有效路径保存到栈Path。然后再进行。该出口处函数走不通,将会退回到上一个还有其他通路的节点
    这里写图片描述
    只有节点3位置处右侧有第一次未走过的路径(11到左侧12与3到自己的右侧虽然未同一节点,但路线不同),且12>3满足通路条件,开始探路
    这里写图片描述
    走到该位置后发现,下一个位置的7<当前位置的8,死路,回退,同时出栈,这些错误位置,递归退到上一个有其他通路的路口。
    这里写图片描述
    当前位置5还有右出口。
    这里写图片描述
    再一次来到出口,与刚才存进去的栈Path里存的路径相比较,若比之小,则进行替换。
    而后继续程序,出口位置再不可走。递归返回,直到2都没有再有其他未走通路的节点。返回到入口,程序结束。

    具体实现
    //maze.h
    #define __MAZE_H__
    #ifdef __MAZE_H__
    #define ROW 6 //行,纵坐标
    #define COL 6 //列,横坐标
    
    #include <stdio.h>  //打印
    #include <stdlib.h>
    #include <assert.h>
    
    //建立一个地图
    typedef int  DataType;
    //迷宫
    typedef struct Map
    {
        DataType map[ROW][COL];
    }Map;
    //位置
    typedef struct Position
    {
        int x;
        int y;
    }Point;
    //栈
    typedef struct Stack
    {
        Point Sta[40];
        int top;//栈顶,有效数的后一位坐标
    }Stack;
    
    //初始化栈
    void InitStack(Stack * s);
    //入栈
    void PushStack(Stack * s, int x, int y);
    //出栈
    void PopStack(Stack *s);
    //取栈顶位置
    Point StackTop(Stack * s);
    //打印栈
    void PrintStack(Stack * s);
    //把栈s里的内容全部赋值给Path
    void s_Path(Stack * s, Stack * Path);
    //测试栈
    void testStack(Stack *s);
    //清空栈
    void EmptyStack(Stack *s);
    
    
    //初始化迷宫
    void InitMaze(Map * maze);
    //打印迷宫
    void PrintMap(Map * maze);
    //检测当前节点是否有通路,优先次序为上左右下,入栈
    int Pass(Map * maze, Point cur, Point next);
    //通过迷宫和入口寻找出路
    void FindExit(Map * maze, Point entry);
    //显示路线
    void PrintPath(Map * maze,Stack * Path);
    
    #endif //__MAZE_H__
    
    //maze.c
    #include "Maze.h"
    //初始化栈
    void InitStack(Stack * s)
    {
        assert(s);
        s->top = 0;
    }
    //入栈
    void PushStack(Stack * s, int x, int y)
    {
        assert(s);
        if (40 == s->top)
        {
            perror("PushStack error\n");
            return;
        }
        s->Sta[s->top].x = x;
        s->Sta[s->top].y = y;
        s->top++;
    }
    //出栈
    void PopStack(Stack *s)
    {
        if (s->top == 0)
        {
            perror("PopStack error\n");
            return;
        }
        assert(s);
        s->top--;
    }
    //取栈顶元素
    Point StackTop(Stack * s)
    {
        if (s->top == 0)
        {
            perror("StackTop error \n");
            return ;
        }
        return (s->Sta[s->top - 1]);
    }
    //打印栈
    void PrintStack(Stack * s)
    {
        for (int i = 0; i < s->top; i++)
        {
            printf(" x=%d ,y = %d \n", s->Sta[i].x, s->Sta[i].y);
        }
        printf("\n");
    }
    //清空栈 
    void EmptyStack(Stack * s)
    {
        s->top = 0;
    }
    //把栈s里的内容全部赋值给Path
    void s_Path(Stack * s, Stack * Path)
    {
        int tmp = s->top;
        while (tmp)
        {
            tmp--;
            Path->Sta[tmp] = s->Sta[tmp];
    
        }
    
        Path->top = s->top;
    }
    //测试栈
    void testStack(Stack * s)
    {
        printf("测试栈\n");
        InitStack(s);
        printf("入栈1,1、2,1、,3,3、4,3、5,7\n");
        PushStack(s, 1, 1);
        PushStack(s, 2, 1);
        PushStack(s, 3, 3);
        PushStack(s, 4, 3);
        PushStack(s, 5, 7);
        PrintStack(s);
        PopStack(s);
        printf("出栈一次\n");
        PrintStack(s);
        EmptyStack(s);
        printf("清空栈\n");
        PrintStack(s);
    }
    void InitMaze(Map * maze)
    {
        int col = 0, row = 0;
        if (maze == NULL)//非法传参,按理这里为Map类型的指针
        {
            return;
        }
        //0 0 0 0 0 0
        //1 1 1 1 0 0
        //0 0 0 1 0 0
        //0 1 1 1 1 1
        //0 0 1 0 0 0
        //0 0 0 0 0 0
        //初始化一个数组
        DataType arr[ROW][COL] = {
            { 0, 0, 0, 0, 0, 0 },
            { 0, 1, 1, 1, 0, 0 },
            { 0, 1, 0, 1, 0, 0 },
            { 0, 1, 0, 1, 0, 0 },
            { 0, 1, 1, 1, 1, 1 },
            { 0, 1, 0, 0, 0, 0 }
        };
        //把该数组的值传递给迷宫
        for (row = 0; row < ROW; row++)
        {
            for (col = 0; col < COL; col++)
            {
                maze->map[row][col] = arr[row][col];
            }
        }
    }
    void PrintMap(Map *maze)
    {
        int col = 0, row = 0;
        printf("迷宫地图为\n-------------------\n");
        for (row = 0; row < ROW; row++)
        {
            for (col = 0; col < COL; col++)
            {
                printf(" %d ", maze->map[row][col]);
            }
            printf("\n");
        }
    }
    
    //检测当前节点是否有通路,优先次序为上左右下,入栈
    int Pass(Map * maze,Point cur,Point next)
    {
        if ((cur.x>ROW-1)||(cur.y>COL-1)||(next.x>ROW-1)||(next.y>COL-1))
        {
            return 0;
        }
        if ((maze->map[next.x][next.y] == 1)||(maze ->map [next.x][next.y]>maze->map [cur.x][cur.y]))
            return 1;
        return 0;
    }
    //检测是否走出迷宫
    int YesPass(Map * maze, Point pos)
    {
        if (pos.x == 0 || pos.y == 0 || pos.x == ROW - 1 || pos.y == COL - 1)
            return 1;
        return 0;
    }
    //通过迷宫地图和入口找出口
    void FindExit(Map * maze, Point cur,Point entry, Stack * s,Stack * Path)
    {
        Point next = cur;
        //探路走起来,先赋值,再走路
        //若为入口,先赋值2
        if ((0 == s->top) && (entry.x == cur.x) && (entry.y == cur.y))
        {
            maze->map[cur.x][cur.y] = 2;
            PushStack(s, cur.x, cur.y);
        }
        //若找到了出口进行标记
        if (YesPass(maze, cur)&&((entry.x != cur.x)||(entry.y != cur.y)))
        {
            if (Path->top == 0)
            {
                s_Path(s,Path);
            }
            if (s->top < Path->top)
            {
                s_Path(s, Path);
            }
        }
        //上通路
        next.x = cur.x-1;
        next.y = next.y;
        if (Pass(maze,cur, next))
        {
            maze->map[next.x][next.y] = maze->map[cur.x][cur.y] + 1;
            PushStack(s, next.x, next.y);
            FindExit(maze, next, entry, s, Path);
        }
        //左通路
        next.x = cur.x;
        next.y = cur.y-1;
        if (Pass(maze,cur, next))
        {
            maze->map[next.x][next.y] = maze->map[cur.x][cur.y] + 1;
            PushStack(s, next.x, next.y);
            FindExit(maze, next, entry, s, Path);
        }
        //右通路
        next.x = cur.x;
        next.y = cur.y+1;
        if (Pass(maze, cur,next))
        {
            maze->map[next.x][next.y] = maze->map[cur.x][cur.y] + 1;
            PushStack(s, next.x, next.y);
            FindExit(maze, next, entry, s, Path);
        }
        //下通路
        next.x = cur.x + 1;
        next.y = cur.y;
        if (Pass(maze,cur, next))
        {
            maze->map[next.x][next.y] = maze->map[cur.x][cur.y] + 1;
            PushStack(s, next.x, next.y);
            FindExit(maze, next, entry, s, Path);
        }
        PopStack(s);
    }
    //显示路线
    void PrintPath(Map * maze,Stack * Path)
    {
        char arr[ROW][COL];
        while (Path->top)
        {
            maze->map[StackTop(Path).x][StackTop(Path).y] = 20;
            arr[StackTop(Path).x][StackTop(Path).y] = '*';
            PopStack(Path);
        }
        printf("---------------------\n");
        for (int row = 0; row < ROW; row++)
        {
            for (int col = 0; col < COL; col++)
            {
                if (maze->map[row][col] != 20)
                {
                    maze->map[row][col] = 0;
                    arr[row][col] = 1;
                }
                printf(" %c ", arr[row][col]);
            }
            printf("\n");
        }
    }
    //源.c
    #include "Maze.h"
    int main()
    {
        //给定入口
        Point e;
        e.x = 5;
        e.y = 1;
        //定义迷宫
        Map  maze;
        //定义栈存放路径
        Stack s;
        //定义栈存放最短路径
        Stack Path;
        //初始化两个栈
        InitStack(&Path);
        testStack(&s);
        //初始化迷宫
        InitMaze(&maze);
        //打印迷宫
        PrintMap(&maze);
        //通过迷宫和入口找出口
        FindExit(&maze,e, e, &s,&Path);
        //打印当前栈中保存的路径
        //PrintStack(&Path);
        //打印因为探路而改变的迷宫
        PrintMap(&maze);
        //显示路线
        PrintPath(&maze,&Path);
        printf("-----------------\n");
        system("pause");
        return 0;
    }
    
    结果

    这里写图片描述

    展开全文
  • 地图基础 地图的形式很多,这里我使用的地图是以tile块为单位分割的地图地图上的tile块形式很多,但主要分成三种: A:陆地,可以在上面分布一些角色啦物件啦; B:过渡,根据物理框可以在上面移动,不过...

    地图基础

     

    地图的形式很多,这里我使用的地图是以tile块为单位分割的地图,地图上的tile块形式很多,但主要分成三种:

     

    A:陆地,可以在上面分布一些角色啦物件啦;

    B:过渡,根据物理框可以在上面移动,不过一般不会分布物件;

    C:水域,不可移动的区域,可以理解成为迷宫的“墙”;

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    在后文的迷宫生成方案里,会以水域作为分割,主要围绕陆地的分布来设计迷宫,过渡的地块根据游戏实际需要再去生成。如果你不希望地图用水域来分割,那只需要把水域改成传统的墙壁即可。

     

    本文用来展示的地图,面积都比较小,方便表达迷宫的生成规则。在实际游戏制作时,按需求去铺量就行。

     

    方案一:主路扭曲型

     

    1、首先,按照下图的间隔规则来生成基础的大地图,1为陆地,0为水域。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    2、然后,选择一个靠近边缘的1作为起点,在它的周围随机找另一个黄色的1(这里的“周围”指的是上下左右4个方向,斜边不算)。找到就把他们联通,即把两个1之间的0变成陆地,这里用红色来表示。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    3、把上一步“终”的格子作为新的一个“起”格子,不停循环第二步的过程,直到找不到周围有黄色的1。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    4、这时候,原路往回走(即不停去找前一个格子),直到找到一个格子,这个格子周围有黄色的1,那么从这个格子开始重复前两个步骤。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    5、接下来就是不停重复上面的步骤,找到就联通,找不到就往回走。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    6、填充完整个地图之后,迷宫就算是制作完成了,根据需求加上终点即可。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    总结一下,这种方案生成的迷宫会有一条明显的主路,即一条特别长、贯穿大部分区域的路线,同时,迷宫的路线一般比较扭曲。

     

    方案二:自然分岔型

     

    这个方案的雏形来自于随机prim算法,具体步骤如下:

     

    1、跟方案一一样,生成一个基础地图。格子先用黄色1和灰色0来表示,暂时不区分水陆。

     

    2、随机取一个地图边缘的黄色1,把它标记为红色1,即变成陆地。然后把它旁边的灰色0标记成蓝色0,表示“待定”。(注意的是,大地图四周的灰色0固定不变,作为地图边缘而存在)

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    3、敲黑板了!!这里是重点!!!

     

    随机选一个蓝色的0(这一步很重要,会使这个方案明显区别于上一个方案),然后看红色1隔着这个蓝色0对面的格子,是否是黄色的1:

     

    • 如果是,则把对面的黄色1标记成红色1,即变成陆地,然后把蓝色0变成红色的0,即也变成陆地;

    • 如果不是,就把这个蓝色的0变成灰色的0。

     

    最后,把新创建的红色1周围的灰色0,标记成蓝色0。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    4、继续重复上面的步骤

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    5、对比上图和下图,这里取一个蓝色0生成一个红色1之后,新生成的红色1旁边,有两个蓝色0的两边都是红色1了,那么就根据第三步的规则,在稍后取到这些蓝色0时,就会把他们变成灰色0。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    6、继续重复上述步骤,直到整个地图没有蓝色0了,地图就生成完毕。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    总结一下,对比方案一,这套方案不会出现明显的主路,迷宫相对比较自然,但迷宫的分岔路会比较多,所以迷宫可能会更复杂,即玩家需要做选择的次数可能比较多。

     

    方案三:块状分割型

     

    上述两个方案有个共同的特点,就是道路永远都是1个格子宽,如果游戏需要给地图创造一些小型地块或者更宽的道路,需要在迷宫生成之后再用各种分布的规则来丰富迷宫。

     

    而第三个方案则以小型地块作为出发点来设计迷宫,这套方案的雏形来自于国外大神Bob Nystrom,有兴趣的可以去查看他个人主页。

     

    1、首先,在大地图(还是之前那个大地图)上生成若干小型地形,保证边长是奇数且不重合就好(示意图全部使用了正方形,实际上可以做成长方形让地图更加自然)。注意顶点要在黄色1格子上即可,这里我用橙色1来表示这些小型地块。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    2、然后,根据之前方案一的迷宫生成方案,在非小型地块的区域里,用迷宫来填充。这一步完成之后,迷宫和小型地形是分隔开来的。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    3、在橙色1的小型地形周围,随机取点以连接黄色1,连接点的数量可以根据需要来确定,建议是不要吝啬连接点的个数,因为这种地图之下,分岔路远比前两种方案要少。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    4、接下来是简化地图,目的是去掉一些死胡同,因为这种方案的核心在于小型地块,没有必要让玩家在迷宫的路上绕。方法是把一些3边都是灰色0的黄色1去掉即可,具体数量也根据游戏需求来制定,我这里只去掉了一部分。

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    5、最后,给地图加上出口和入口,地图就做完啦!

     

    经验分享:三套简单的迷宫地图生成方案 ...

     

     

    总结一下,这种方案比前两种多了小型地块,这一点比较适合设计玩家的阶段性反馈。同时地图的分岔路明显减少,玩家在这种方案下的选择次数会明显降低。另外,由于这个方案的步骤相对多且独立,所以对于设计者来讲会比较容易控制地图的结构。

    迷宫生成网页:http://www.mazegenerator.net/

    转载于:https://www.cnblogs.com/damowang/p/7047357.html

    展开全文
  • #复杂迷宫求解(2)

    2018-08-30 20:48:22
    // pos 必须在地图中 pos位置如果是1 int IsPass ( Maze * m , Position pos ) { assert ( m ) ; if ( pos . _x >= ROW || pos . _x < 0 || pos . _y >= COL || pos . _y >= COL )...
  • 概述:文章基于一种基础的地图,来...其中不少方法来自于游戏界前辈,我根据自己的基础地图做了不少修正(毕竟迷宫地图的形式多种多样,适合自己游戏的才是最好的)。 根据方案生成地图之后,还可以加上一些静...
  • 上一篇博客我们提到了多出口迷宫的情况,但是在此基础上迷宫路径如果带环呢,如何解决? 情况如下图: 可以看出,红色圈出来的部分形成了一个环。那如果我们还是采用上次的办法,看看能不能找出最短路径。 ...
  • 为了更方便的设计关卡,配套开发了可视化的迷宫地图编辑器,并实现了复杂迷宫地图的深度优先生成; 迷宫游戏实现了文件的读写,实现了导出和读取玩家自制地图,并加入了通过DFS绘制迷宫出路的功能;
  • ~小游戏开发——迷宫复杂版)~
  • 迷宫

    2021-03-02 15:43:21
    第十届蓝桥杯。迷宫问题之BFS,DFS两种解题。
  • 控制两只具有独特能力和能力的狗来征服复杂迷宫 K9 Krew是一款使用Javascript构建的2D游戏。 游戏具有两个完全完成的级别。 使用平铺地图编辑器可以轻松添加更多级别。 资料下载 最新版本可以在找到。 屏幕截图
  • 迷宫问题

    2015-01-31 17:10:00
    2.复杂迷宫问题 3.最优路线迷宫问题 1.经典迷宫 先看地图从图上标出的起点到终点找出线路的算法 先看地图地图无非就是一个二维的数组,用某个标记标记为墙壁(这里用数字9)某个标记标记成线路(这里用数字1...
  • 迷宫生成器

    2012-05-09 11:03:16
    生成各种大小、不同复杂程度的迷宫迷宫的宽高路径的多少 墙的多少都可以随意调整
  • 迷宫小游戏

    2013-04-03 15:45:48
    学习编程半年,自己写的一个可以随机生成迷宫图的迷宫游戏,每关迷宫地图都会扩大,而且迷宫只生成唯一一条可通往出口的道路。为了解决C#闪烁的问题,选择了控件加GDI+混合使用,未使用双缓冲。代码有多余的方法,也...
  • 蓝桥杯迷宫

    2021-03-30 17:59:47
    下图给出了一个迷宫的平面图,其中标记为1 的为障碍,标记为0 的为可 以通行的地方。 010000 000100 001001 110000 ...对于下面这个更复杂迷宫(30 行50 列) 010101010010110010010101100101101001000
  • 迷宫生成算法

    2019-09-20 19:24:29
    最近做课设时,有一个部分...迷宫其实就是一个复杂的地形图,在这个地形中有基本的障碍和通道,当然也可以有其他元素。 我们这里用最简单的方式描述迷宫——矩阵。迷宫中的地形也只有障碍和通道两种元素。可以用0和1...
  • C实现迷宫问题

    2018-05-04 13:09:33
    用二维码创建一个m*n的迷宫地图,1表示通路,0表示障碍,从迷宫中寻找出路。 迷宫问题大致有三种情况实现: 使用递归和非递归方法实现简单的迷宫问题 如果迷宫有多条出路,求最短出路 针对复杂迷宫问题寻找最短...
  • 迷宫游戏开发

    2020-12-03 16:32:45
    迷宫生成算法:地图难度:kruskai算法>随机深度优先算法>prim算法>递归分割算法 功能 增加状态栏显示状态信息 作弊(查看提示)增加惩罚分数(当前作弊一次惩罚20分) 保存读取地图 菜单栏,可用于...
  • 走出迷宫

    2020-12-30 12:42:24
    当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。 假设你已经得到了一个 n × m 的迷宫的图纸,请你找出从起点到出口的最短路。 输入格式 第一行是...
  • 基础迷宫问题

    2018-05-17 02:16:15
    D: 走出迷宫时间限制: 1 Sec 内存限制: 128 MB提交: 14 解决: 12[提交][状态][讨论版][命题人:quanxing]题目描述当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,856
精华内容 742
关键字:

复杂迷宫地图