• file： Graph.h

• brief：这个Graph类是用来画格子地图的，这个类可以生成地图起点终点和障碍物坐标

• author：AIplusX

• version：beta_v0.0

• date：2021_11_17

• update：2021_11_17

• warning：记得在类的析构函数里面delete掉堆内申请的内存

• remarks：用户参数结构体里的map地图数组直接存储的是颜色数值，这样利于实现绘图，障碍物的数量是与格子数量成正比例关系的

• todo：无

#pragma once

#include <vector>
#include <iostream>
#include <conio.h>
#include <graphics.h>
#include "Point.h"

#define RANDOM(a) (rand()%(a)) 
#define RANDOM_RANGE(a,b) (rand()%((b)-(a)+1)+(a))  //[i, j]

//#define    BLACK            0
//#define    BLUE            0xAA0000
//#define    GREEN            0x00AA00
//#define    CYAN            0xAAAA00
//#define    RED                0x0000AA
//#define    MAGENTA            0xAA00AA
//#define    BROWN            0x0055AA
//#define    LIGHTGRAY        0xAAAAAA
//#define    DARKGRAY        0x555555
//#define    LIGHTBLUE        0xFF5555
//#define    LIGHTGREEN        0x55FF55
//#define    LIGHTCYAN        0xFFFF55
//#define    LIGHTRED        0x5555FF
//#define    LIGHTMAGENTA    0xFF55FF
//#define    YELLOW            0x55FFFF
//#define    WHITE            0xFFFFFF

#define PATH            0xFFFF55//LIGHTCYAN
#define OBSTACLE        0x000000//BLACK
#define START            0x0000AA//RED
#define END                0x00AA00//GREEN
#define GENERATE        0x55FFFF//YELLOW
#define SEARCH            0x55FF55//LIGHTGREEN
#define PASS_SEARCH        0xAAAAAA//LIGHTGRAY

const int map_line = 60;
const int map_col  = 30;
const int block = 16;
const int block_division = 3;

typedef struct _UserPara
{

public:
    int block_size = block;
    int win_width = map_line * block_size;
    int win_height = map_col * block_size;
    int win_real_height = win_height + block_size * 3;
    int map_x = win_width / block_size - 1;
    int map_y = win_height / block_size - 1;
    int obstacle_num = map_line * map_col / block_division;
    int map[map_line][map_col] = { 0 };

}UserPara;

class A_star;

class Graph
{
    public:
        Graph(UserPara user_para);
        ~Graph();
        friend class A_star;
        static void show_map(const UserPara&);
        void set_obstacles_start_end();
        Point get_start();
        Point get_end();
        UserPara get_userPara();
        std::vector<Point*> get_obstacle();


    private:
        UserPara graph_user_para;
        Point start;
        Point end;
        std::vector<Point*> obstacle_vector;
        std::vector<Point*> obstacle;

};

• file：Graph.cpp

• brief：构造函数

• author：AIplusX

• param：用户参数结构体

• return：无

• exception：无

• note：函数内部生成起点终点和障碍物的坐标点，其中起点终点存在栈里，障碍物坐标点存在堆里，同时做easyX画图所需要的初始化操作

• remarks：无

#include <time.h>
#include <random>
#include "Graph.h"

Graph::Graph(UserPara user_para)
{
    graph_user_para = user_para;
    start = Point(1, 1);
    end = Point(graph_user_para.map_x-1, graph_user_para.map_y-1);
    set_obstacles_start_end();
    srand((unsigned)time(NULL));
    initgraph(graph_user_para.win_width, graph_user_para.win_real_height);
    settextstyle(16, 8, _T("Courier"));
    setbkcolor(WHITE);
    settextcolor(BLACK);
    cleardevice();
}

• file：Graph.cpp

• brief：获取私有变量

• author：AIplusX

• param：无

• return：相应参数

• exception：无

• note：无

• remarks：无

std::vector<Point*> Graph::get_obstacle()
{
    return obstacle;
}

UserPara Graph::get_userPara()
{
    return graph_user_para;
}

Point Graph::get_end()
{
    return end;
}

Point Graph::get_start()
{
    return start;
}

• file：Graph.cpp

• brief：生成随机障碍坐标点

• author：AIplusX

• param：无

• return：无

• exception：无

• note：随机障碍物坐标的生成方法是将所有坐标点存进vector里面，然后将vector打乱，之后从头开始取相应数量的坐标点做为障碍物。注意取出障碍物的坐标点之后将其从乱序vector中删除

• remarks：注意打乱vector的方法

void Graph::set_obstacles_start_end()
{

    for (int i = 0; i <= graph_user_para.map_x; i++) {
        for (int j = 0; j <= graph_user_para.map_y; j++) {
            Point* obstacle = new Point(i, j);
            if (*obstacle != start && *obstacle != end) {
                obstacle_vector.push_back(obstacle);
            }
            else { delete obstacle; }
        }
    }

    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(obstacle_vector.begin(), obstacle_vector.end(), rd);

    for (int i = 0; i < graph_user_para.obstacle_num; i++) {
        obstacle.push_back(obstacle_vector[0]);
        obstacle_vector.erase(obstacle_vector.begin());
    }

}

• file：Graph.cpp

• brief：可视化地图

• author：AIplusX

• param：用户数据结构体

• return：无

• exception：无

• note：无

• remarks：无

void Graph::show_map(const UserPara& para)
{
    for (int i = 0; i <= para.map_x; i++) {
        for (int j = 0; j <= para.map_y; j++) {
            setfillcolor(para.map[i][j]);
            fillrectangle(i * para.block_size, j * para.block_size, \
                (i + 1) * para.block_size, (j + 1) * para.block_size);
        }
    }
}

• file：Graph.cpp

• brief：析构函数

• author：AIplusX

• param：用户数据结构体

• return：无

• exception：无

• note：删除掉堆里的内存，obstacle_vector和obstacle里的坐标点加起来就是整个地图上的坐标（起点终点除外）

• remarks：无

Graph::~Graph()
{
    for (int i = 0; i < obstacle_vector.size(); i++) {
        delete obstacle_vector[i];
        obstacle_vector.erase(obstacle_vector.begin());
    }


    for (int i = 0; i < obstacle.size(); i++) {
        delete obstacle[i];
        obstacle.erase(obstacle.begin());
    }
}