写在前面

今天主要是实现A_star类的功能函数,但是还出现了一个链接时候的BUG,留待明天解决。

知识点

1:通常情况下文件、目录名称用小写,大写表示很重要的东西(如README)等;

2:类里面的const变量使用大写来表示;

3:类的成员函数,用动词+名词来表示,动词用小写,名词用大写,如:getH;

4:C++工程应该有一个专门的main.cpp文件;

5:“::”是C++的域解析符

今天工作

BUG显示:

看这个描述是链接时候的错误,今天没找到原因,明天继续努力!

源码:


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

#define Manhattan_Distance  0
#define Cross_Distance        1
#define Euclidean_Distance    2

typedef struct _Node {
    bool in_open_set = false;
    bool in_close_set = false;
    int Gn=0;
    int Hn=99;

    Point  coordinate;
    struct _Node* pre = nullptr;
}Node;

class A_star
{
    public:
        A_star(const Graph&);
        ~A_star();
        void Astar_algorithm();
        int find_min_Fn();
        void add_closeset(Point&);
        void add_openset(Point&);
        void Hn(const int&, const Point&, const Point&);
        void Gn();
        void Fn();
        void get_env_node();
        bool is_end();
        Point get_next();

    private:
        int F;
        int H;
        int G;
        int cross_cost = 14;
        int plane_cost = 10;
        Graph graph_para;
        std::vector<Node> openset;
        std::vector<Node> closeset;
        std::vector<Point> obstacleset;
        Point start;
        Point end;

};

int user_min(const int& x, const int& y)
{
    return (x > y ? y : x);
}

bool coordinate_similar(const Point& p1, const Point& p2)
{
    if (p1.x == p2.x && p1.y && p2.y) {
        return true;
    }
    else {
        return false;
    }
}

A_star::A_star(const Graph& graph)
{
    graph_para = graph;
    start = graph_para.get_start();
    end = graph_para.get_end();
    obstacleset = graph_para.get_obstacle();
}

A_star::~A_star()
{

}

bool A_star::is_end()
{
    for (std::vector<Node>::iterator iter = openset.begin(); iter != openset.end(); iter++) {
        if (coordinate_similar((*iter).coordinate, end))
        {
            return true;
        }
        else {
            return false;
        }
    }
}

void A_star::Astar_algorithm()
{
    add_openset(start);

    while (is_end()) {

    }

}

void A_star::add_openset(Point& p)
{
    Node node;
    node.coordinate = p;
    node.in_open_set = true;
    node.in_close_set = false;
    openset.push_back(node);
}

void A_star::add_closeset(Point& p)
{
    Node node;
    node.coordinate = p;
    node.in_open_set = false;
    node.in_close_set = true;
    closeset.push_back(node);
}

void A_star::Fn()
{
    F = H + G;
}

void A_star::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:
        H = plane_cost * (dx + dy);
        break;
    case Cross_Distance:
        H = cross_cost * (dx + dy) + (cross_cost - 2 * plane_cost) * user_min(dx, dy);
        break;
    case Euclidean_Distance:
        H = plane_cost * (dx * dx + dy * dy);
        break;
    default:
        H = -1;
        break;
    }
}

A*算法的启发函数有3种,分别如图下所示:

第一种是只能上下左右4个方向走,第二种是8个方向走,第三种是什么方向都可以走。我设计的成员函数设计了参数,届时均可以进行测试。