首页 > 代码库 > 走迷宫——C++ 算法实现

走迷宫——C++ 算法实现

  这两个看了几个不错的走迷宫算法,然后按照自己的方式写了一个实现,代码如下:

MyMazeMap.cpp

 

 1 #include <iostream>
 2 #include <Windows.h>
 3 #include "MazeMap.h"
 4 #include "Mazer.h"
 5 using namespace std;
 6 
 7 const int SUCCESS = 0;
 8 
 9 int main()
10 {
11     int map[8][12] = {
12         { WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL },
13         { ROAD, ROAD, ROAD, ROAD, ROAD, WALL, WALL, ROAD, WALL, WALL, ROAD, WALL },
14         { WALL, WALL, WALL, WALL, ROAD, WALL, WALL, ROAD, WALL, WALL, ROAD, WALL },
15         { WALL, WALL, WALL, WALL, ROAD, WALL, WALL, ROAD, WALL, WALL, ROAD, WALL },
16         { WALL, WALL, ROAD, ROAD, ROAD, ROAD, ROAD, ROAD, ROAD, WALL, ROAD, WALL },
17         { WALL, WALL, ROAD, WALL, WALL, ROAD, WALL, WALL, ROAD, ROAD, ROAD, WALL },
18         { WALL, ROAD, ROAD, WALL, WALL, ROAD, WALL, WALL, WALL, WALL, WALL, WALL },
19         { WALL, ROAD, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL }
20     };
21 
22     MyMazeMap maze;
23 
24     maze.setMazeMap(*map, 8, 12);//创建map的一个迷宫
25 
26     maze.setMazeWall(*);//墙的表示字符
27     maze.drawMap();//控制台显示迷宫
28 
29     Faceto faceto;//人进入迷宫的朝向
30     faceto = _up;
31 
32     MyMazer mazer(maze);//走迷宫的人的对象
33     
34     mazer.setPersonPosition(7, 1);//迷宫入口位置
35     mazer.setPersonSpeed(FAST);//走迷宫的速度设置
36     mazer.setPersonChar(T);//人的字符表示
37     mazer.start(faceto);//开始走迷宫
38     
39     system("pause");
40     return 0;
41 }

 

MazeMap.h

 1 #ifndef MAZEMAP_H
 2 #define MAZEMAP_H
 3 
 4 #include <Windows.h>
 5 
 6 #define WALL 1
 7 #define ROAD 0
 8 
 9 class MyMazeMap
10 {
11 public:
12     MyMazeMap();
13     MyMazeMap(const MyMazeMap &_mazeMap);
14     ~MyMazeMap();
15     void setMazeMap(int *map,int row, int col);//设置指向地图二维数组的指针
16     void setMazeWall(char _wall);//设置墙壁字符表示
17     void drawMap();//打印地图
18     int **getMap();//获取地图二维数组的指针
19     int getCol();//获得二维数组的列数
20     int getRow();//获得二维数组的行数
21     void setExitPosition(COORD coo);//设置出口位置
22     COORD getExitPosition();//获得出口位置
23 
24 private:
25     char m_cWall;//代表墙的字符
26     char m_cRoad;//代表路的字符
27     int m_iMapRow;//二维数组的行数
28     int m_iMapCol;//二维数组的列数
29     int **m_pMap;//指向地图二维数组的指针
30     COORD m_ExitPosition;//迷宫出口坐标
31 };
32 
33 #endif

 

MazeMap.cpp

#include <iostream>
#include "MazeMap.h"

using namespace std;


MyMazeMap::MyMazeMap()
{
    m_cRoad =  ;
    m_cWall =  ;
    m_iMapCol = 0;
    m_iMapRow = 0;
    m_ExitPosition.X = 0;
    m_ExitPosition.Y = 0;
    m_pMap = NULL;
}

MyMazeMap::MyMazeMap(const MyMazeMap &_mazeMap)
{
    m_cRoad = _mazeMap.m_cRoad;
    m_cWall = _mazeMap.m_cWall;
    m_iMapCol = _mazeMap.m_iMapCol;
    m_iMapRow = _mazeMap.m_iMapRow;
    m_ExitPosition = _mazeMap.m_ExitPosition;
    m_pMap = _mazeMap.m_pMap;
}

MyMazeMap::~MyMazeMap()
{
    //for (int i = 0; i < m_iMapRow; i++)
    //{
    //    delete[]m_pMap[i];
    //    m_pMap[i] = NULL;
    //}
}

void MyMazeMap::setMazeMap(int *map, int row, int col)//设置指向地图二维数组的指针
{
//    m_pMap = map;
    m_iMapCol = col;
    m_iMapRow = row;

    m_pMap = new int*[m_iMapRow];
    for (int i = 0; i < m_iMapRow; i++)
        m_pMap[i] = new int[m_iMapCol];
    
    int *p = map;
    for (int i = 0; i < m_iMapRow; i++)
    {
        for (int j = 0; j < m_iMapCol; j++)
        {
            m_pMap[i][j] = *p;
            p++;
        }
    }
}

void MyMazeMap::setMazeWall(char _wall)//设置墙壁字符表示
{
    m_cWall = _wall;
}

void MyMazeMap::drawMap()//打印地图
{
    for (int i = 0; i < m_iMapRow; i++)
    {
        for (int j = 0; j < m_iMapCol; j++)
        {
            if (m_pMap[i][j] == WALL)
                cout << m_cWall;
            else
                cout << m_cRoad;
        }
        cout << endl;
    }

}

int **MyMazeMap::getMap()
{
    return m_pMap;
}

int MyMazeMap::getCol()
{
    return m_iMapCol;
}

int MyMazeMap::getRow()
{
    return m_iMapRow;
}

void MyMazeMap::setExitPosition(COORD coo)
{
    m_ExitPosition = coo;
}

COORD MyMazeMap::getExitPosition()//获得出口位置
{
    return m_ExitPosition;
}

 

Mazer.h

#ifndef MAZER_H
#define MAZER_H

#include <string>
#include <Windows.h>
#include <iostream>
#include "MazeMap.h"

enum Faceto{_up,_down,_left,_right};
enum Speed{LOW,MID,FAST};

class MyMazer
{
public:
    MyMazer();
    MyMazer(MyMazeMap _mazeMap);
    ~MyMazer();
    void setPersonPosition(int x, int y);//人当前位置
    void setPersonSpeed(Speed _speed);//人移动的速度
    void setPersonChar(char person);//表示人的字符
    void start(Faceto _faceto);//游戏开始函数
    void gotoxy(int x, int y);//动画控制
    Faceto turn(Faceto _faceto);//人转向之后的朝向
    int getSteps();//获取步数
    MyMazeMap m_mazeMap;

private:
    char m_cPerson;//表示人的字符
    Faceto m_cFaceto;//表示人的朝向
    COORD m_iNowLocal;//人当前位置
    COORD m_iPreviousLocal;//人的前一个位置
    //int destination[2] = { 0, 0 };
    //int orignPoint[2] = { 0, 0 };
    Speed m_speed;//人的速度
    int m_iSteps;//记录人走了多少步
};

#endif

 

Mazer.cpp

#include <Windows.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include "Mazer.h"

using namespace std;

MyMazer::MyMazer()
{
    m_cPerson = Y;
    m_cFaceto = _up;
    m_speed = LOW;
    m_iNowLocal.X = 0;//
    m_iNowLocal.Y = 1;//
    m_iPreviousLocal.X = 0;
    m_iPreviousLocal.Y = 0;
    m_iSteps = 0;
    MyMazeMap m_mazeMap;
    m_mazeMap.getMap();
}

MyMazer::MyMazer(MyMazeMap _mazeMap)
{
    m_cPerson = Y;
    m_cFaceto = _up;
    m_speed = LOW;
    m_iNowLocal.X = 0;//
    m_iNowLocal.Y = 1;//
    m_iPreviousLocal.X = 0;
    m_iPreviousLocal.Y = 0;
    m_mazeMap = _mazeMap;

    m_mazeMap.getMap();
//    m_mazeMap.getExitPosition();
    //m_mazeMap.detTerpoint(originPoint, destination);
}

MyMazer::~MyMazer()
{
    
}

void MyMazer::setPersonPosition(int x, int y)//人当前位置
{
    m_iNowLocal.X = x;
    m_iNowLocal.Y = y;
}

int MyMazer::getSteps()//获取步数
{
    return m_iSteps;
}

void MyMazer::setPersonSpeed(Speed _speed)//人移动的速度
{
    m_speed = _speed;
}

void MyMazer::setPersonChar(char person)//表示人的字符
{
    m_cPerson = person;
}

Faceto MyMazer::turn(Faceto _faceto)//人转向之后的朝向   基于右手算法,定义下一步往哪走
{
    m_cFaceto = _faceto;
    if (m_cFaceto == _up)
    {
        if (m_mazeMap.getMap()[m_iNowLocal.X][m_iNowLocal.Y + 1] != WALL)//右边界不是墙
        {
            m_cFaceto = _right;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X - 1][m_iNowLocal.Y] != WALL)//上边界不是墙
        {
            m_cFaceto = _up;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X][m_iNowLocal.Y - 1] != WALL)//左边界不是墙
        {
            m_cFaceto = _left;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X + 1][m_iNowLocal.Y] != WALL)//下边界不是墙
        {
            m_cFaceto = _down;
        }
    }
    else if (m_cFaceto == _right)
    {
        if (m_mazeMap.getMap()[m_iNowLocal.X + 1][m_iNowLocal.Y] != WALL)//下边界不是墙
        {
            m_cFaceto = _down;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X][m_iNowLocal.Y + 1] != WALL)//右边界不是墙
        {
            m_cFaceto = _right;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X - 1][m_iNowLocal.Y] != WALL)//上边界不是墙
        {
            m_cFaceto = _up;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X][m_iNowLocal.Y - 1] != WALL)//左边界不是墙
        {
            m_cFaceto = _left;
        }
    }
    else if (m_cFaceto == _down)
    {
        if (m_mazeMap.getMap()[m_iNowLocal.X][m_iNowLocal.Y - 1] != WALL)//左边界不是墙
        {
            m_cFaceto = _left;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X + 1][m_iNowLocal.Y] != WALL)//下边界不是墙
        {
            m_cFaceto = _down;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X][m_iNowLocal.Y + 1] != WALL)//右边界不是墙
        {
            m_cFaceto = _right;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X - 1][m_iNowLocal.Y] != WALL)//上边界不是墙
        {
            m_cFaceto = _up;
        }
    }
    else if (m_cFaceto == _left)
    {
        if (m_mazeMap.getMap()[m_iNowLocal.X - 1][m_iNowLocal.Y] != WALL)//上边界不是墙
        {
            m_cFaceto = _up;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X][m_iNowLocal.Y - 1] != WALL)//左边界不是墙
        {
            m_cFaceto = _left;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X + 1][m_iNowLocal.Y] != WALL)//下边界不是墙
        {
            m_cFaceto = _down;
        }
        else if (m_mazeMap.getMap()[m_iNowLocal.X][m_iNowLocal.Y + 1] != WALL)//右边界不是墙
        {
            m_cFaceto = _right;
        }
    }

    return m_cFaceto;
}

void MyMazer::start(Faceto _faceto)//游戏开始函数
{
    char tempcPer = Y;
    tempcPer = m_cPerson;
    m_iSteps = 1;

    double speed_num = 0;
    if (m_speed == LOW)
        speed_num = 2;
    else if (m_speed == MID)
        speed_num = 1;
    else if (m_speed == FAST)
        speed_num = 0.5;

    m_cFaceto = _faceto;

    //画第一个点的位置
    setPersonChar(tempcPer);
    gotoxy(m_iNowLocal.Y, m_iNowLocal.X);
    cout << m_cPerson;
    
    //从二维数组下面的二行输出当前走的步数
    gotoxy(0, m_mazeMap.getRow() + 2);
    cout << "步数统计:" << m_iSteps << endl;
    Sleep(speed_num * 1000);

    while (1)
    {
        m_iPreviousLocal = m_iNowLocal;
        switch (m_cFaceto)
        {
            case 0://_up
            {
                   m_iNowLocal.X = m_iNowLocal.X - 1;
                   break;
            }
            case 1://_down
            {
                       m_iNowLocal.X += 1;
                       break;
            }
            case 2://_left
            {
                       m_iNowLocal.Y = m_iNowLocal.Y - 1;
                       break;
            }
            case 3://_right
            {
                       m_iNowLocal.Y += 1; 
                       break;
            }
        }

        m_iSteps++;//记录步长

        //从二维数组下面的二行输出当前走的步数
        gotoxy(0, m_mazeMap.getRow() + 2);
        cout << "步数统计:" << m_iSteps << endl;

        //边界测试,四个边任何一个等于边界值都会退出
        if ((m_iNowLocal.X == 0 || m_iNowLocal.X ==m_mazeMap.getRow()-1 ) || (m_iNowLocal.Y == m_mazeMap.getCol()-1 || (m_iNowLocal.Y == 0)))
        {//判断有没有走到出口的位置,到了,结束循环
            setPersonChar( );
            gotoxy(m_iPreviousLocal.Y, m_iPreviousLocal.X);
            cout << m_cPerson;
            Sleep(0.05 * 1000);
            setPersonChar(tempcPer);
            gotoxy(m_iNowLocal.Y, m_iNowLocal.X);
            cout << m_cPerson;
            Sleep(speed_num * 1000);
            break;
        }
        
        //当前要走的位置不是出口位置,移动位置,
        m_cFaceto = turn(m_cFaceto);//判断当前位置的下一个位置的方向
        
        setPersonChar( );
        gotoxy(m_iPreviousLocal.Y, m_iPreviousLocal.X);
        cout << m_cPerson;

        Sleep(0.05 * 1000);

        setPersonChar(tempcPer);
        gotoxy(m_iNowLocal.Y, m_iNowLocal.X);
        cout << m_cPerson;

        //从控制台的第二十行输出当前走的步数
        /*gotoxy(0, m_mazeMap.getRow()+2);
        cout << "步数统计:" << m_iSteps << endl;*/
        
        Sleep(speed_num * 1000);
        
    }
    setPersonChar( );
    gotoxy(0, m_mazeMap.getCol());

    cout << endl << endl << endl << endl;
    cout << "走的步数:" << m_iSteps << endl;
    cout << "出口坐标:" << "(" << m_iNowLocal.X << ", " << m_iNowLocal.Y << ")" << endl;
    cout << "Finally the maze!" << endl;

}

void MyMazer::gotoxy(int x, int y)//动画控制
{
    COORD cd;
    cd.X = x;
    cd.Y = y;
    HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleCursorPosition(handle, cd);
    
}

运行画面:

 

技术分享

 

 技术分享

 

走迷宫——C++ 算法实现