C++ 基于BFS算法的走迷宮自動(dòng)尋路的實(shí)現(xiàn)

更新時(shí)間：2021年11月17日 16:02:41 作者：coolight7

這篇文章主要為大家介紹了C++ 基于BFS算法實(shí)現(xiàn)走迷宮自動(dòng)尋路，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

1.效果圖

其中正方形代表障礙物，實(shí)心菱形代表移動(dòng)者（人），空心菱形代表目標(biāo)位置（都是可以在代碼中修改的）

本例使用隊(duì)列(鏈表實(shí)現(xiàn))，以廣度優(yōu)先進(jìn)行自動(dòng)尋路。

2.實(shí)現(xiàn)代碼

1.隊(duì)列方法類(lèi)

coolQueue.h

#pragma once
#include <iostream>
using namespace std;
//隊(duì)列

//坐標(biāo)結(jié)構(gòu)體
struct Point
{
    int x;
    int y;
    Point()
    {
        x = 0;
        y = 0;
    }
    Point(int in_x, int in_y)
    {
        x = in_x;
        y = in_y;
    }

    Point& operator=(const Point& right_p)
    {
        this->x = right_p.x;
        this->y = right_p.y;
        return *this;
    }
};

//隊(duì)列結(jié)構(gòu)體
struct coolQueue
{
    int data;
    Point cool_p;
    coolQueue* next_p;

    coolQueue(int in_data)
    {
        data = in_data;
        next_p = NULL;
    }

    coolQueue(int in_x, int in_y, int in_data = 0)
    {
        cool_p.x = in_x;
        cool_p.y = in_y;
        data     = in_data;
        next_p   = NULL;
    }
};

//隊(duì)列方法類(lèi)，限制訪(fǎng)問(wèn)方式
class queueClass
{
protected:
    coolQueue* Head_p = NULL;
    coolQueue* End_p  = NULL;

public:
    queueClass() {}

    void push(int data);        //入隊(duì)
    void push(int in_x, int in_y, int in_data = 0);
    bool pop(int& re_data);        //出隊(duì)
    bool pop(coolQueue& in_coolQueue);
    void reverse_order();        //翻轉(zhuǎn)

    void clear()
    {
        for (int data; pop(data););
    }

    ~queueClass()
    {
        clear();
    }
};

coolQueue.cpp

#include "coolQueue.h"

/*入隊(duì)函數(shù)
* 傳參：
*    in_data：入隊(duì)的數(shù)據(jù)
*/
void queueClass::push(int in_data)
{
    if (Head_p == NULL)            //隊(duì)列為空
    {
        Head_p = new coolQueue(in_data);
        End_p  = Head_p;
    }
    else if(Head_p == End_p)    //隊(duì)列只有一個(gè)元素
    {
        End_p = new coolQueue(in_data);
        Head_p->next_p = End_p;
    }
    else
    {
        coolQueue* temp_p = new coolQueue(in_data);
        End_p->next_p      = temp_p;
        End_p              = temp_p;
    }
}

/*出隊(duì)
* 傳參：
*    re_data：接收出隊(duì)返回值
* 返回值：
*    成功返回true，隊(duì)列為空返回false
* 
* 把值寫(xiě)入re_data中返回
*/
bool queueClass::pop(int& re_data)
{
    if (Head_p == NULL)        //隊(duì)列為空
        return false;
    re_data = Head_p->data;
    coolQueue* temp_p = Head_p;
    if (Head_p == End_p)    //隊(duì)列只有一個(gè)元素
    {
        Head_p = NULL;
        End_p = NULL;
    }
    else
        Head_p = Head_p->next_p;
    delete temp_p;
    return true;
}

/*同鏈表采用以尾指針為頭的頭插法實(shí)現(xiàn)倒序
*/
void queueClass::reverse_order()
{
    if (Head_p == NULL || Head_p == End_p)
        return;

    coolQueue* p = Head_p, * temp_p;
    do {
        temp_p = p;
        p = p->next_p;
        temp_p->next_p = End_p->next_p;
        End_p->next_p = temp_p;
    } while (p != End_p);
    p = Head_p;
    Head_p = End_p;
    End_p = p;
}

//以下重載用于輔助自動(dòng)尋路實(shí)現(xiàn)
//in_data = 0
void queueClass::push(int in_x, int in_y, int in_data)
{
    if (Head_p == NULL)
    {
        Head_p = new coolQueue(in_x, in_y, in_data);
        End_p = Head_p;
    }
    else if (Head_p == End_p)
    {
        End_p = new coolQueue(in_x, in_y, in_data);
        Head_p->next_p = End_p;
    }
    else
    {
        coolQueue* temp_p = new coolQueue(in_x, in_y, in_data);
        End_p->next_p = temp_p;
        End_p = temp_p;
    }
}

bool queueClass::pop(coolQueue& in_coolQueue)
{
    if (Head_p == NULL)
        return false;
    in_coolQueue.data   = Head_p->data;        //不直接使用復(fù)制是因?yàn)榭赡馨袶ead_p的next_p也復(fù)制出去導(dǎo)致限制訪(fǎng)問(wèn)權(quán)限失效
    in_coolQueue.cool_p = Head_p->cool_p;
    coolQueue* temp_p = Head_p;
    if (Head_p == End_p)
    {
        Head_p = NULL;
        End_p = NULL;
    }
    else
        Head_p = Head_p->next_p;
    delete temp_p;
    return true;
}

2.地圖方法類(lèi)

mapClass.h

#pragma once
#include "coolQueue.h"
#include "windows.h"
#include <cmath>

using namespace std;

#ifndef PI
#define PI 3.14159265358979323846
#endif // !PI

#ifndef Sleep_num
#define Sleep_num 500
#endif // !打印輸出地圖時(shí)的暫停時(shí)間

#ifndef Map_size
#define Map_size 10
#endif // !地圖大小

/*地圖操作類(lèi)
* 保護(hù)繼承隊(duì)列，防止外部調(diào)用隊(duì)列的函數(shù)
*/
class mapClass : protected queueClass
{
protected:
    int map[Map_size][Map_size];    //地圖
    Point persion_p;                //起點(diǎn)位置坐標(biāo)

    void new_map();

    void reflash_map();

    bool auto_find_way(Point& target_p);

    void auto_move(int in_x, int in_y);

public:
    mapClass(const Point& in_p);

    bool auto_main();

    void into_map(int in_data, int num = 1);

    bool into_map(int in_x, int in_y, int in_data);

    void show_map();

    void clear_map(const Point& in_p);
};

mapClass.cpp　　

#include "mapClass.h"

/*初始化地圖
* 
* 把map置零后設(shè)置邊界
*/
void mapClass::new_map()
{
    memset(map, 0, Map_size * Map_size);//清零
    for (int num = Map_size; num--;)    //設(shè)置邊緣障礙物
    {
        map[num][0] = 1;
        map[0][num] = 1;
        map[num][Map_size - 1] = 1;
        map[Map_size - 1][num] = 1;
    }
}

/*刷新地圖
* 
* 由于在auto_find_way()中會(huì)修改地圖中的值作為方向標(biāo)記
* 移動(dòng)后會(huì)殘留一些標(biāo)記，此函數(shù)將會(huì)把這些標(biāo)記清理（即把標(biāo)記置回0）
*/
void mapClass::reflash_map()
{
    for (int x = Map_size - 1; --x;)
        for (int y = Map_size - 1; --y;)
            map[x][y] = map[x][y] % 1000;
    /*方向標(biāo)記為1000，2000，3000 和 4000，故 %1000 即可保留其他東西并清理標(biāo)記*/
}

/*自動(dòng)尋路
* 
* 傳參：
*    &target_p：傳出參數(shù)，找到路徑后寫(xiě)入目標(biāo)的坐標(biāo)
* 返回值：
*    有路徑返回true，沒(méi)有返回false
* 
* 基于隊(duì)列尋找到達(dá)目標(biāo)的最優(yōu)路徑，會(huì)在地圖上留下方向標(biāo)記
* 如果找到，在其他函數(shù)可以 以目標(biāo)位置開(kāi)始，通過(guò)方向標(biāo)記倒推回起點(diǎn)，即為路徑
*/
bool mapClass::auto_find_way(Point& target_p)
{
    coolQueue out_queue(0, 0, 0);    
    for (int push_num = 1; push_num;)
    {
        push_num = 0;        //如果push_num在while循環(huán)后仍然為0，說(shuō)明隊(duì)列空且無(wú)路可走了
        while (this->pop(out_queue))
        {
            for (int i = 1, temp_x, temp_y; i <= 4; ++i)//判斷它的旁邊4個(gè)位置
            {    //此處使用sin()是為了在不同i時(shí)(temp_x, temp_y)指向以out_queue為中心的不同方向
                //效果同auto_move()中的switch()的使用
                temp_x = out_queue.cool_p.x + int(sin(PI / 2 * (i - 2.0)));
                temp_y = out_queue.cool_p.y + int(sin(PI / 2 * (i - 3.0)));
                switch (map[temp_x][temp_y])
                {
                case 0: //可走
                {
                    map[temp_x][temp_y] = i * 1000;        //寫(xiě)入方向標(biāo)記
                    this->push(temp_x, temp_y, 0);        //入隊(duì)
                    ++push_num;
                }break;
                case 10: //抵達(dá)目標(biāo)位置
                {
                    map[temp_x][temp_y] += i * 1000;
                    target_p.x = temp_x;                //寫(xiě)入目標(biāo)位置
                    target_p.y = temp_y;
                    this->clear();                        //清空隊(duì)列
                    return true;
                }break;
                }
            }
            if (out_queue.data == -1)                    //每一輪隊(duì)列的最后一個(gè)的data標(biāo)記為-1
                break;                                    //以起點(diǎn)位置往外一步為一輪
        }
        if (this->End_p != NULL)
            this->End_p->data = -1;
    }
    this->clear();
    return false;
}

/*自動(dòng)移動(dòng)（遞歸函數(shù)）
* 傳參：
*    
* 后序遞歸：先調(diào)用遞歸，再移動(dòng)地點(diǎn)
* 因此此函數(shù)目的是一開(kāi)始傳入目標(biāo)位置，
* 再以地圖上的方向標(biāo)記倒推上一個(gè)位置，
* 直到回到起點(diǎn)位置則開(kāi)始移動(dòng)，每次移動(dòng)調(diào)用show()刷新地圖顯示
* 即可實(shí)現(xiàn)從起點(diǎn)到終點(diǎn)移動(dòng)的效果
*/
void mapClass::auto_move(int in_x, int in_y)
{
    /*switch ()可替換為
    * temp_x = in_x + int(sin(PI / 2 * (map[in_x][in_y] / 1000));
    * temp_y = in_y + int(sin(PI / 2 * (map[in_x][in_y] / 1000 - 1.0));
    */
    int temp_x = in_x, temp_y = in_y;
    switch (map[in_x][in_y] / 1000)    //解析地圖標(biāo)記
    {
    case 0:return;   break;
    case 1:++temp_x; break;
    case 2:++temp_y; break;
    case 3:--temp_x; break;
    case 4:--temp_y; break;
    }
    /*由于函數(shù)是從終點(diǎn)位置遞歸回起點(diǎn)的，所以上一個(gè)調(diào)用此函數(shù)的應(yīng)該是更接近終點(diǎn)的
    * 因此此函數(shù)接受的傳入值（in_x, in_y）是下一個(gè)移動(dòng)點(diǎn)
    * （temp_x,temp_y）為本次的移動(dòng)點(diǎn)
    */
    auto_move(temp_x, temp_y);    //遞歸調(diào)用，讓起點(diǎn)移動(dòng)到本位置（即temp_x, temp_y）

    map[temp_x][temp_y] = 0;    //把現(xiàn)在的位置清零
    map[in_x][in_y] = 100;        //把下一個(gè)移動(dòng)點(diǎn)置100，即可實(shí)現(xiàn)從現(xiàn)在的位置移動(dòng)到下一個(gè)位置的效果
    show_map();                    //顯示打印
    Sleep(Sleep_num);
    return;
}

/*構(gòu)造函數(shù)
* 傳參：
*    in_p：起點(diǎn)位置
*/
mapClass::mapClass(const Point& in_p)
{
    new_map();
    persion_p = in_p;
}

/*自動(dòng)尋路主導(dǎo)函數(shù)
*/
bool mapClass::auto_main()
{
    show_map();                //顯示地圖
    Sleep(Sleep_num);

    this->clear();            //清空隊(duì)列
    this->push(persion_p.x, persion_p.y, -1);//把起點(diǎn)入隊(duì)

    Point target_p;            //目標(biāo)坐標(biāo)
    if (auto_find_way(target_p) == false)    //調(diào)用自動(dòng)尋路
    {
        reflash_map();
        return false;
    }

    auto_move(target_p.x, target_p.y);        //移動(dòng)
    reflash_map();                            //清理地圖殘留標(biāo)記
    persion_p = target_p;                    //重置起點(diǎn)位置，抵達(dá)終點(diǎn)后起點(diǎn)即為終點(diǎn)
    return true;
}

/*對(duì)地圖寫(xiě)入數(shù)據(jù)標(biāo)記
* 
* 傳參：
*    in_data：寫(xiě)入的數(shù)據(jù)值
*    num：     次數(shù)
* 
* 在地圖的隨機(jī)空位置上寫(xiě)入 num 次 in_data 標(biāo)記
* 
* 存在bug：
*    如果地圖坐標(biāo)已滿(mǎn)，寫(xiě)入次數(shù)不夠會(huì)陷入死循環(huán)
*    可考慮加入循環(huán)次數(shù)限制解決
*/
void mapClass::into_map(int in_data, int num)
{
    if (num <= 0)
        return;
    for (int i = 0, j = 0; num--;)
    {
        i = rand() % Map_size;
        j = rand() % Map_size;
        if (map[i][j] == 0)
            map[i][j] = in_data;
        else
            ++num;
    }
}

/*對(duì)地圖寫(xiě)入數(shù)據(jù)標(biāo)記
* 
* 傳參：
*    in_x,in_y：寫(xiě)入的地圖位置
*    in_data：  寫(xiě)入的數(shù)據(jù)值
* 
* 返回值：
*    如果(in_x, in_y)位置為空則寫(xiě)入成功返回true，否則返回false
* 
* 在地圖的(in_x, in_y)位置寫(xiě)入 in_data
*/
bool mapClass::into_map(int in_x, int in_y, int in_data)
{
    if (map[in_x][in_y] == 0)
    {
        map[in_x][in_y] = in_data;
        return true;
    }
    return false;
}

/*打印顯示地圖
*/
void mapClass::show_map()
{
    system("cls");                            //清空控制臺(tái)輸出
    for (int i = 0; i < Map_size; ++i)
    {
        for (int j = 0; j < Map_size; ++j)
            switch (map[i][j] % 1000)
            {
            case 0:        cout << "  "; break;//空白位置
            case 1:        cout << "□"; break;//障礙物
            case 10:    cout << "◇"; break;//目標(biāo)
            case 100:    cout << "◆"; break;//自己
            default:    cout << "  "; break;
            }
        cout << endl;
    }
}

/*重置地圖
* 傳參：
*    in_p：起點(diǎn)位置
* 
* 清空地圖，僅保留 起點(diǎn) 和 邊界 標(biāo)記
* 用于輔助循環(huán)刷新障礙物尋路的實(shí)現(xiàn)
*/
void mapClass::clear_map(const Point& in_p)
{
    for (int x = Map_size - 1; --x;)        //把地圖中的所有位置置零
        for (int y = Map_size - 1; --y;)
            map[x][y] = 0;
    persion_p = in_p;                        //重新設(shè)置起點(diǎn)
    map[in_p.x][in_p.y] = 100;
}

3.main函數(shù)

main.cpp

#include <iostream>
#include <time.h>
#include <cmath>

#include "mapClass.h"
using namespace std;


int main()
{
    srand(int(time(0)));

    Point persion_p(1, 1), target_p(1, 1);
    mapClass test_map(persion_p);

    test_map.into_map(1, 1, 100);    //寫(xiě)入起點(diǎn)
    test_map.into_map(1, 20);        //寫(xiě)入障礙物

    while (1)
    {
        //重置障礙物位置, 取消下面兩句的注釋即可啟用
        //test_map.clear_map(target_p);        //清空地圖
        //test_map.into_map(1, 20);            //生成障礙物

        do {
            target_p.x = rand() % (Map_size - 2) + 1;
            target_p.y = rand() % (Map_size - 2) + 1;
        } while (test_map.into_map(target_p.x, target_p.y, 10) == false);

        if (test_map.auto_main() == false)
        {
            cout << endl << "<< 走不了！" << endl;
            Sleep(1500);
        }
    }

    return 0;
}

3.思路

總體和數(shù)據(jù)結(jié)構(gòu)的教科書(shū)上的大差不差：以起點(diǎn)為中心，每向外一步作為一輪循環(huán)，循環(huán)中把可走的位置入隊(duì)，下一輪循環(huán)把上一輪入隊(duì)的位置出隊(duì)并再以這些位置為中心往外走一步，把可走位置入隊(duì)，一直這樣循環(huán)，直到遇到終點(diǎn)位置或者隊(duì)列中為空（因?yàn)槊恳粋€(gè)方向都走不了則隊(duì)列循環(huán)后為空）。

（想象一下在沒(méi)有障礙物的地圖中，以起點(diǎn)為中心向外擴(kuò)散）

在上述過(guò)程中，把可走位置入隊(duì)的同時(shí)留下方向標(biāo)記（上一個(gè)位置走到此位置的方向），在循環(huán)結(jié)束后從終點(diǎn)位置倒推即可找到一條回到起點(diǎn)的路徑。

此路徑為最優(yōu)解（最優(yōu)解可能不止一條），因?yàn)樗惴ㄖ惺菑钠瘘c(diǎn)往外每一步進(jìn)行一輪判斷，因此如果找到了終點(diǎn)，那么就是在最少的步數(shù)內(nèi)找到了終點(diǎn)，此時(shí)即可結(jié)束循環(huán)，此為最優(yōu)解。如果不結(jié)束，繼續(xù)找下去可能可以找到用更多步數(shù)的路徑。

本例與書(shū)中的不同：

1.在找到路徑后利用system("cls")清屏重新輸出，來(lái)實(shí)現(xiàn)逐步走向終點(diǎn)的效果。

2.在一些細(xì)節(jié)的實(shí)現(xiàn)上使用不同的嘗試(例如 mapClass::auto_find_way()中使用sin()，直接使用地圖做方向標(biāo)記等)

3.支持循環(huán)多次尋路，支持重置障礙物位置

到此這篇關(guān)于C++ 基于BFS算法的走迷宮自動(dòng)尋路的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: