opencv实现DFS迷宫寻路

z13228604287

[C++] 纯文本查看 复制代码

#pragma once
#ifndef MAZE_H
#define MAZE_H
#include<string>
#include<iostream>
#include<vector>
#include"SeqStack.h"
#include"CirSequence.h"
#include<opencv2\core\core.hpp>
#include<opencv2\highgui.hpp>
using namespace std; 
class Maze {        
public :
        //构造函数
        Maze();
        //搜索最短路径
        void Slove();
        //打印路径
        void PrintPath();
        //打印迷宫
        void PrintMap(SeqStack&sorce);
private:
        //将寻路方向复制到一个二维数组
        void CopyDir(int des[][4]);
        //搜索方向优先级
        CirSequence dir;
        //迷宫图形化,显示
        Mat image;
        //迷宫图
        vector<string>cells; 
    //网格划分后的行列数
        int height, width;
        //迷宫行数、列数
        int rows, columns;
        //dfs搜索路径起点，终点
        NODE start, end;
    //搜索路径
        SeqStack Path;
        //复制迷宫
        void CellsCopy(vector<string>& des, vector<string>& source);
        //寻路
        bool ExitMaze(int row, int column);
        //判断结点是否可通过
        bool Vaild(int row, int column);
        void DrawBlock(int row, int col, int height, int width, Scalar color);
        void DrawMaze();
        
};
#endif

[C++] 纯文本查看 复制代码

#pragma once
#ifndef NODE_H
#define NODE_H
#include<math.h>
#include<opencv2/core/core.hpp>
#include<opencv2/highgui/highgui.hpp>
#include<opencv2/imgproc/imgproc.hpp>
#include<opencv2/objdetect/objdetect.hpp>
#include<opencv2/imgproc/types_c.h>
using namespace cv;
typedef struct NODE
{
        int i=0, j=0;
}*pNODE;
const Scalar wall_color(100, 200, 200);
const Scalar way_color(30, 70, 20);
const Scalar pass_color(300, 150, 100);
const Scalar start_end_color(120, 100, 100);
const int SIZE = 10000;
#endif // !NODE_H

[C++] 纯文本查看 复制代码

#pragma once
#ifndef SEQSTACK_H
#define SEQSTACK_K
#include<iostream>
#include"NODE.h"
using namespace std;
class SeqStack 
{
private:
        NODE *arr;//数组动态创建
        int top;//栈顶位置
        int size;//最多可储存的元素数目
public:
        //构造函数 初始化动态创建一个顺序栈
        SeqStack(int size);
        //获取压入栈中元素的个数
        int GetNum();
        //判断栈是否为空
        bool SeqStack_isempty();
        //将元素入栈
        void SeqStack_Push(pNODE p);
        //将元素出栈
        void SeqStack_Pop();
        //打印结点
        void print();
        //获取顶部结点
        pNODE GetTop();
        //赋值函数重载
        SeqStack& operator=(const SeqStack&c);
        //清空栈
        void Clear();
        pNODE GetValus();
};
#endif

[C++] 纯文本查看 复制代码

#include"CirSequence.h"
CirSequence::CirSequence(const NODE &staloc, const NODE &endloc)
{
        this->Seq = new NODE[4];
        Seq[0] = { 0,1 }; Seq[1] = { 1,0 }; Seq[2] = { 0,-1 }; Seq[3] = { -1,0 };
        this->AdjustSeq(staloc, endloc);
}
pNODE CirSequence::GetSeq() { return Seq; }
CirSequence::CirSequence()
{
        this->Seq = new NODE[4];
        Seq[0] = { 0,1 }; Seq[1] = { 1,0 }; Seq[2] = { 0,-1 }; Seq[3] = { -1,0 };
        this->spin = this->start = 0;
}
void  CirSequence::AdjustSeq(const NODE &staloc, const NODE &endloc)
{
        NODE vec = { endloc.i - staloc.i,endloc.j - staloc.j };
        spin = 1;
        if (vec.j > 0)//终点在起点右方
        {
                start = 0;
                if (vec.i < 0)//终点在起点右上方
                        spin = -1;
        }
        if (vec.i == 0) //终点与起点横坐标相同
                if(vec.j>0)//终点在起点右方
                        start = 0;
                else start = 2;//终点在起点左方
        if (vec.j == 0)//终点与起点纵坐标相同
                if (vec.i > 0)//终点在起点下方
                        start = 1;
                else start = 3;// 终点在起点上方
        if (vec.j < 0)//终点在起点左方
        {
                start = 2;
                if (vec.i > 0)//终点在起点左下方
                        spin = -1; 
        }
}
int CirSequence::GetSpin() { return spin; }
int CirSequence::GetStart() { return this->start; }

[C++] 纯文本查看 复制代码

#include"maze.h"
#include<iostream>
#include <stdlib.h> 
#include"CirSequence.h"
#include<string>
using namespace cv;
using namespace std;
int main() {
        namedWindow("小白鼠",0);
        waitKey(0);
        Maze a;
        a.Slove();

        cout << "是否需要重新设置起始点？若需要请输入yes，否则请输入no:" << endl;
        string instruction;
        cin >> instruction;
        if (instruction == "yes")
                while (1) {
                        a.Slove();
                        instruction.clear();
                        cout << "是否需要重新设置起始点？若需要请输入yes，否则请输入no:" << endl;
                        cin >> instruction;
                        if (instruction == "yes")
                                continue;
                        else
                                break;
                }
        destroyWindow("小白鼠");
        system("pause");
        return 0;
}

[JavaScript] 纯文本查看 复制代码

#include"maze.h"
#include"SeqStack.h"
#include <stdlib.h> 
#include <time.h>
#include<iostream>
#include"CirSequence.h"
#include<vector>
#include<string>
using namespace cv;
using namespace std; 
extern int gap = 2;
//创建全局二维数组存储每次寻路方向优先级
extern int arr[2][4] = { 0 };
//创建全局变量保存初始化迷宫
extern vector<string> initcells(100);
//创建全局变量跟踪dfs寻路的迷宫动态变化
extern vector<string> tempcells(100);
//将寻路顺序存入二维数组
void Maze::CopyDir(int des[][4]) 
{
        int flag = this->dir.GetStart();
        int count = this->dir.GetSpin();
        for (int j = 0; j < 4; flag = (4+flag + count) % 4,j++)
        {
                des[0][j] =this->dir.GetSeq()[flag].i;
                des[1][j] = this->dir.GetSeq()[flag].j;
        };
}
//将迷宫中坐标为（i，j）的结点描绘为指定颜色
void Maze::DrawBlock(int row, int col, int height, int width,Scalar color) 
{
        Point p1 = Point(col*width + gap, row*height + gap);
        Point p2 = Point((col+1)*width - gap, (row+1)*height - gap);
        rectangle(this->image, p1, p2, color, -1);
};
//在初始化时展示迷宫图
void Maze::DrawMaze()
{
        this->height = this->image.rows / this->rows;
        this->width = this->image.cols / this->columns;
        for (int i = 0; i < rows; i++)
        {
                for (int j = 0; j < columns; j++)
                {
                        if (this->cells[j] == ' ')
                                this->DrawBlock(i, j, height, width, way_color);
                        else
                                if (this->cells[j] == '0')
                                this->DrawBlock(i, j, height, width, wall_color);
                }
                imshow("小白鼠", this->image);
                waitKey(1);
        }
}
//cells类拷贝
void Maze::CellsCopy(vector<string>& des, vector<string>& source)
{
        des.clear();
        for (int i = 0; i <this->rows; i++)
                des.push_back(source);
}
//打印路径
void Maze::PrintPath()
{
        Path.print();
}
//打印迷宫图
void Maze::PrintMap(SeqStack&sorce)
{
        pNODE p=sorce.GetValus();
        for (int k = 0; k <sorce.GetNum(); k++)
        {
                        this->DrawBlock(p[k].i, p[k].j, height, width, pass_color);
                        imshow("小白鼠", this->image);
                        waitKey(1);
        }
} 
//判断点（row，column）是否可行
bool Maze::Vaild(int row, int column)
{
        bool path = false;
        if (row >= 0 && row < rows&&column >= 0 && column < columns&&cells[row][column] == ' ')
                path = true;
        return path;
};
//搜索一条起点为（row，column）的通路
bool Maze::ExitMaze(int row, int column)
{
        bool done = false;
        if (Vaild(row, column))
        {
                        cells[row][column] = 'B';
                        this->DrawBlock(row,column, height, width, pass_color);
                        imshow("小白鼠", this->image);
                        waitKey(100);
                        pNODE p = new NODE;
                        p->i = row;
                        p->j = column;
                        this->Path.SeqStack_Push(p);
                        delete[]p;
                if ((row == this->end.i) && (column == this->end.j))
                        done = true;
                else
                {
                        done = ExitMaze(row+arr[0][0], column + arr[1][0]);
                        if (!done)
                                done=ExitMaze(row + arr[0][1], column+arr[1][1]);
                        if (!done)
                                done=ExitMaze(row+arr[0][2], column +arr[1][2]);
                        if (!done)
                                done=ExitMaze(row +arr[0][3], column+arr[1][3]);
                }
                if (done)
                {
                        cells[row][column] = '*'; 
                }
                else
                {
                        this->DrawBlock(row, column, height, width, way_color);
                        imshow("小白鼠", this->image);
                        waitKey(100);
                        this->Path.SeqStack_Pop();
                }
        }
        return done;
};
//寻找最短路径
void Maze::Slove()
{
        cout << "请输入迷宫起点的横坐标[0," << this->rows - 1 << "]、纵坐标：[0," << this->columns - 1 << "]";
        cin >> start.i >> start.j;
        cout << "请输入迷宫终点的横坐标[0," << this->rows - 1 << "]、纵坐标：[0," << this->columns - 1 << "]";
        cin >> end.i >> end.j;
        if (  start.i<0|| start.i>this->rows - 1 ||start.j>this->columns - 1 || start.j < 0)
        
        {
                cout << "输入非法，请重新输入" << endl;
                return;
        }
        //清空前一次寻路的栈中路径
        this->Path.Clear();
        //调整寻路顺序
        this->dir.AdjustSeq(this->start, this->end);
        //存储寻路顺序到数组arr中
        this->CopyDir(arr);
        //将初始化的迷宫存储在cells中
        CellsCopy(cells,initcells);
        //对起点和终点描色
        if (this->cells[this->start.i][this->start.j] == ' ' && this->cells[this->end.i][this->end.j] == ' ')
        {
                this->DrawBlock(this->start.i, this->start.j, height, width, start_end_color);
                this->DrawBlock(this->end.i, this->end.j, height, width, start_end_color);
                imshow("小白鼠", this->image);
                waitKey(1000);
        }
        //初次寻路
        bool done = ExitMaze(start.i, start.j);
        CellsCopy(tempcells, cells);
        SeqStack temppath = this->Path; 
        SeqStack shortestpath= this->Path;
        static int count = 0;
        if (!done)
        {
                cout << "失败" << endl;
                this->DrawBlock(this->start.i, this->start.j, height, width, way_color);
                this->DrawBlock(this->end.i, this->end.j, height, width, way_color);
                imshow("小白鼠", this->image);
                waitKey(10);
                return;
        } 
        else
        {
                for (int i = 0; i < 2; i++)
                {
                        cells[Path.GetTop()->i][Path.GetTop()->j] = ' ';
                        this->DrawBlock(Path.GetTop()->i, Path.GetTop()->j, height, width, way_color);
                        imshow("小白鼠", this->image);
                        waitKey(100);
                        Path.SeqStack_Pop();
                }
                int tempi, tempj, prei = 0, prej=0;
                while (!Path.SeqStack_isempty())
                {
                        tempi = Path.GetTop()->i;
                        tempj = Path.GetTop()->j;
                        CellsCopy(tempcells, cells);
                
                        temppath = this->Path; 
                        for(int j=0;j<4;j++)
                        {                
                                if(tempi + arr[0][j]== prei && tempj + arr[1][j]== prej)
                                        continue; 
                                if (ExitMaze(tempi + arr[0][j], tempj + arr[1][j]))
                                {
                                        count++;
                                        Path.GetTop()->i, Path.GetTop()->j;
                                        cout << "-----------------------------成功路径"<<count<<"--------------------------：" << endl;
                                        this->PrintMap(Path);
                                        this->Path.print();
                                        if (this->Path.GetNum() < shortestpath.GetNum())
                                                shortestpath.operator=(this->Path);
                                        int n = this->Path.GetNum() -temppath.GetNum();
                                        for (int m = 0; m < n; m++)
                                        {
                                                this->DrawBlock(Path.GetTop()->i, Path.GetTop()->j, height, width, way_color);
                                                imshow("小白鼠", this->image);
                                                waitKey(1);
                                                Path.SeqStack_Pop();
                                        }
                                }CellsCopy(cells, tempcells);
                        }
                        prei = tempi; prej = tempj;
                        cells[Path.GetTop()->i][Path.GetTop()->j] = ' ';
                        this->DrawBlock(Path.GetTop()->i, Path.GetTop()->j, height, width, way_color);
                        imshow("小白鼠", this->image);
                        waitKey(1);
                        Path.SeqStack_Pop();
                }
                this->Path = shortestpath;
                cout << "最短路径的长度为：" <<shortestpath.GetNum()<< endl;
                this->PrintPath();
        }
}
Maze::Maze() :Path(SIZE)
{
                cout << "迷宫行数和列数";
                cin >> rows;
                cin >> columns;
                char *str = new char[columns];
                srand((unsigned)time(0));
                string cellstr;
                this->image = Mat::zeros(40 * this->rows, 40 * this->columns, CV_8UC3);
                for (int i = 0; i < rows; i++)
                {
                        for (int j = 0; j < columns; j++)
                        {
                                if ((rand() % 10) > 5)
                                {
                                        str[j] = '0';
                                }
                                else
                                        str[j] = ' ';
                        }
                        cellstr = str;
                        cells.push_back(cellstr);
                }
        this->CellsCopy(initcells, this->cells);
        this->DrawMaze();
};

[C++] 纯文本查看 复制代码

#include"SeqStack.h"
#include<iostream>
using namespace std;
void SeqStack::SeqStack_Push(pNODE p) {
        if (this->top == size - 1)
        {
                cout << "栈已满";
                cout << endl;
                return;
        };
        this->top++;
        this->arr[top] = *p;
        arr[top].i = p->i;
        arr[top].j = p->j;
};
bool SeqStack::SeqStack_isempty() {
        if (this->top == -1)
        {
                 return true;
        };
        if (this->top > -1)
        {
                return false;
        }
};
int SeqStack::GetNum() 
{
        return this->top + 1; 
}
void SeqStack::print()
{
        int m = 0;
        if (!this->SeqStack_isempty())
                while (1) {

                        cout << "<" << arr[m].i << "," << arr[m].j << ">";
                        m++;
                        if (m > top) {
                                cout << endl; return;
                        }
                }; 
}
void SeqStack::SeqStack_Pop() 
{
        if (this->top == -1)
        {
                cout << "栈已空";

                cout << endl;

                return;
        };
        this->top--;
};
void SeqStack::Clear() {
        while (!this->SeqStack_isempty())
                this->SeqStack_Pop();

};
pNODE SeqStack::GetValus() 
{
        pNODE p = new NODE[this->GetNum()];
        int m = 0;
        if (!this->SeqStack_isempty())
                while (1)
                {
                        p[m].i = arr[m].i;
                        p[m].j = arr[m].j;
                        m++;
                        if (m > top)
                         break ;
                };
        return p;
}
SeqStack& SeqStack::operator=(const SeqStack&c)
{
        this->size = c.size;
        this->top = c.top;
        this->arr = new NODE[c.size];
        for (int i = 0; i < size; i++)
        {
                this->arr.i = c.arr.i;
                this->arr.j = c.arr.j;
        }
        return *this;
}
pNODE SeqStack::GetTop()
{
        if (top >= 0)
                return &arr[top];
}
SeqStack::SeqStack(int size = SIZE) :size(SIZE)
{
        this->top = -1;
        this->arr = new NODE[SIZE];
};

夜狂

搞进支持库里啊

新手玩家

厉害了

jia201314973