• file： A_star.h

• brief：A_star类用法的注意事项

• author：AIplusX

• version：beta_v0.0

• date：2021_11_15

• update：2021_11_15

• warning：offset_x和offset_y数组的大小有2种形式，大小分别是4和8，分别对应宏定义的曼哈顿距离和欧几里得距离，因为曼哈顿距离只走4个格子，而欧几里得距离要走8个格子，所以在显示算法的时候env_nums要进行更改（曼哈顿距离是4，欧几里得距离是8）。在记录探索和轨迹路径的时候，作者是在堆里面申请的内存，所以vector里面存的都是指针，指向堆里的内存

• todo：无

#pragma once
#include "Graph.h"
#include <vector>

//#define Manhattan_Distance  0
#define Euclidean_Distance  1

#define MIN(x,y) ((x) >= (y) ? (y) : (x))

class Graph;

class A_star
{
    public:
        A_star() {};
        ~A_star();
        void Astar_algorithm();
        bool judge_env_legal(const Point&);
        int calcu_Hn(const Point&);
        int calcu_Gn(const Point&);
        int calcu_cost(const Point&, const Point&);
        void set_start_end_obs_map(Graph&);
        void add_openset(Point* p) { openset.push_back(p); };
        void add_fatherset(Point* p) { fatherset.push_back(p); };
        void delete_openset(const int& idx) {openset.erase(openset.begin() + idx);};
        void search_env_block(Point*);
        void calcu_type_selection(int&, const int&, const int&);
        void show_para_below(Point*);
        bool is_alread_set(std::vector<Point*>&, Point*);
        void get_trajectory(const Point*);
        UserPara get_astar_userpara();
        Point* find_min_Fn(int& idx);

    private:
        int cross_cost = 14;
        int plane_cost = 10;
        std::vector<Point*> openset;
        std::vector<Point*> fatherset;
        //std::vector<Point*> trajectory;
        std::vector<Point*> obstacleset;        
        Point start;
        Point end;
        UserPara user_trajectory;
        const int env_nums = 8;
        //int offset_x[4] = {0, 1, 0, -1};
        //int offset_y[4] = {-1, 0, 1, 0};
        int offset_x[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
        int offset_y[8] = { -1, -1, -1, 0, 1, 1, 1, 0};

};

• file：A_star.cpp

• brief：以下函数顺序就是文件内函数的存储顺序。

• author：AIplusX

• param[in|out] 输入：vector和待查找元素 | 输出：布尔值（true或者false）

• return 找到了返回true，没找到返回false

• exception 无

• note：

• 这是个基于模板实现的函数，功能是在vector里面找寻是否有相同的元素

• remarks：可以进行改进，注意在查找的时候是比对vector元素和被查找元素的是否一样，如果改成指针向量的话，注意要对比指针所指内存的元素和被查找元素是否相同，不要进行指针的对比

#include "A_star.h"
#include <math.h>
#include <limits>

template <typename T>
const bool vector_contain(std::vector<T>& Vec, const T& Element)
{
    if (std::find(Vec.begin(), Vec.end(), Element) != Vec.end())
        return true;

    return false;
}

• file：A_star.cpp

• brief：析构函数

• author：AIplusX

• param[in|out] 输入：无 | 输出：无

• return：无

• exception：无

• note：

• 析构函数里面释放掉堆里的内存，这里释放了openset和fatherset向量里指针所指的内存，障碍物的内存在Graph类的析构函数里进行了回收

• remarks：无

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

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

}

• file：A_star.cpp

• brief：从Graph类的对象获取起点，终点坐标，障碍物坐标点向量，用户参数的结构体

• author：AIplusX

• param[in|out]：输入：Graph类对象 | 输出：无

• return：无

• exception：无

• note：

• 从Graph类的对象获取起点，终点坐标，障碍物坐标点向量，用户参数的结构体，然后修改用户参数结构体里的二维数组相应内容，修改成可走路径，障碍物，起点终点

• remarks：注意要在这里面初始化起点的G和F

void A_star::set_start_end_obs_map(Graph& user_graph)
{
    start = user_graph.get_start();
    end = user_graph.get_end();
    obstacleset = user_graph.get_obstacle();
    user_trajectory = user_graph.get_userPara();

    for (int i = 0; i <= user_trajectory.map_x; i++) {
        for (int j = 0; j <= user_trajectory.map_y; j++) {
            user_trajectory.map[i][j] = PATH;
        }
    }

    user_trajectory.map[start.x][start.y] = START;
    user_trajectory.map[end.x][end.y] = END;

    start.Gn = 0;
    start.Fn = start.Gn + calcu_Hn(start);

    for (int i = 0; i < obstacleset.size(); i++) {
        user_trajectory.map[obstacleset[i]->x][obstacleset[i]->y] = OBSTACLE;
    }

}

• file：A_star.cpp

• brief：A*算法的主体

• author：AIplusX

• param[in|out]：输入：无 | 输出：无

• return：无

• exception：无

• note：

• 利用openset和fatherset进行更新待搜索向量和父节点向量，算法运行可视化是通过Graph的静态函数实现的，算法运行的基本循环逻辑是：找到最小F节点->在该节点附近开始探索->找到局部最优点->存到父节点向量->从openset中删除->更改map内容

• remarks：注意节点信息都是存在堆里的，栈里只存了指向堆的指针向量

void A_star::Astar_algorithm()
{
    int min_Fn_idx(0);
    Point* min_Fn_p = new Point(start.x, start.y);

    memcpy(min_Fn_p, &start, sizeof(start));
    add_openset(min_Fn_p);

    while (!openset.empty()) {
        Graph::show_map(user_trajectory);
        min_Fn_p = find_min_Fn(min_Fn_idx);
        show_para_below(min_Fn_p);
        if (*min_Fn_p == end) { break; }
        search_env_block(min_Fn_p);

        add_fatherset(min_Fn_p);
        delete_openset(min_Fn_idx);

        user_trajectory.map[min_Fn_p->x][min_Fn_p->y] = PASS_SEARCH;
    }

    get_trajectory(min_Fn_p);
}

• file：A_star.cpp

• brief：获取最终轨迹（黄色方块）

• author：AIplusX

• param[in|out]：输入：终点内存的指针 | 输出：无

• return：无

• exception：无

• note：

• 获取最终的路径

• remarks：注意要返回堆中终点内存的地址，因为之前在set_start_end_obs_map也获取了起点和终点信息，但是那是存在栈里的，没有指向前一个方块的指针信息，所以不能用，一定是要返回堆中终点内存的地址

void A_star::get_trajectory(const Point* p)
{
    p = p->pre_point;
    while (p != nullptr) {
        user_trajectory.map[p->x][p->y] = GENERATE;
        p = p->pre_point;
    }
    user_trajectory.map[start.x][start.y] = START;
    user_trajectory.map[end.x][end.y] = END;
    Graph::show_map(user_trajectory);
}

• file：A_star.cpp

• brief：可视化界面下方显示坐标参数

• author：AIplusX

• param[in|out]：输入：堆中内存的地址 | 输出：无

• return：无

• exception：无

• note：

• 可视化界面下方显示坐标参数

• remarks：无

void A_star::show_para_below(Point* p)
{
    wchar_t s1[5];
    _stprintf_s(s1, _T("(%d,"), p->x);
    outtextxy(0, 480, s1);
    wchar_t s2[5];
    _stprintf_s(s2, _T("%d)"), p->y);
    outtextxy(50, 480, s2);
}