写在前面

上次的语法问题没有解决，我换了一种更为清晰的实现思路，将在接下来给出。今天也实现了A*算法的逻辑设计。

知识点

1：C++类的前向声明写法：

class Graph

实现

首先是数据流转方向，具体如下图所示：

首先利用user_para在Graph对象user_graph中生成起点，终点，障碍物的坐标，并且通过user_graph对象的get方法做为接口将起点，终点，障碍物的坐标和user_para参数传递给A_star类的对象astar，最终在astar对象里完成算法的构建和路径的生成。

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();
}

8邻域法的搜索方式如下图所示：

整张地图是向右为x轴正方向，向下为y轴正方向，因此我定义了2个数组，这样就可以通过一次循环遍历周围8个点了（思路来自github程序，侵权请评论，马上删除）。具体实现如下所示：

    for (int i = 0; i < env_nums; i++){
        Point search_p(p.x + offset_x[i], p.y + offset_y[i]);

    }

然后就是A*算法的逻辑了，这边我参考了知乎大佬的伪代码，超链接如下所示：

路径规划之 A* 算法;

昨天比较匆忙还没有实现完全：

void A_star::Astar_algorithm()
{
    add_openset(start);
    int max_Fn_idx(0);
    Point max_Fn_p = start;

    while (!openset.empty()) {
        max_Fn_idx = find_min_Fn(max_Fn_p);

        if (is_end(openset[max_Fn_idx])) {

        }else{
            delete_openset(max_Fn_idx);
            add_closeset(max_Fn_p);
            search_8_block(max_Fn_p);
        }
    }

}

整体逻辑如上所示，今天还有一部分没有实现，明天一定完成！

接下来介绍一下部分功能函数：

这4个函数就是open_set和close_set增删的实现，利用的STL的vector模块：

void A_star::add_openset(Point& p)
{
    openset.push_back(p);
}

void A_star::add_closeset(Point& p)
{
    closeset.push_back(p);
}

void A_star::delete_openset(const int& idx)
{
    openset.erase(openset.begin() + idx);
}

void A_star::delete_closeset(const int& idx)
{
    closeset.erase(closeset.begin() + idx);
}

还有就是启发函数Hn的计算方法了，我在函数的输入设计了一个参数，可以通过这个参数修改启发函数的形式：

void A_star::calcu_Hn(const int& move_type, const Point& p1, const Point& p2)
{
    int dx = abs(p1.x - p2.x);
    int    dy = abs(p1.y - p2.y);
    switch (move_type)
    {
    case Manhattan_Distance:
        Hn = plane_cost * (dx + dy);
        break;
    case Cross_Distance:
        Hn = cross_cost * (dx + dy) + (cross_cost - 2 * plane_cost) * user_min(dx, dy);
        break;
    case Euclidean_Distance:
        Hn = plane_cost * (dx * dx + dy * dy);
        break;
    default:
        Hn = -1;
        break;
    }
}

明天就是完成整个A*算法的逻辑设计以及实现并结束这个系列啦~