C++实现的高效A*算法

A-Star Algorithm 这是使用C++实现的高效的A-Star算法。只对算法的程序实现做了尽力而为的优化，并没有对算法自身进行改良。优化措施主要在于：快速判断路径节点是否在开启/关闭列表中、快速查找最小f值的节点以及优化路径节点频繁分配内存的问题。 运行环境 支持c++11的编译器 使用示例 char maps[10][10] = { { 0, 1, 0, 0, 0, 1, 0, 0, 0, 0 }, { 0, 0, 0, 1, 0, 1, 0, 1, 0, 1 }, { 1, 1, 1, 1, 0, 1, 0, 1, 0, 1 }, { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 }, { 0, 1, 0, 1, 1, 1, 1, 1, 0, 1 }, { 0, 1, 0, 0, 0, 0, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 1, 0, 0, 0, 1, 0 }, { 1, 1, 0, 0, 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 1, 0, 1, 0 }, }; // 搜索参数 AStar::Params param; param.width = 10; param.height = 10; param.corner = false; param.start = AStar::Vec2(0, 0); param.end = AStar::Vec2(9, 9); param.can_pass = [&](const AStar::Vec2 &pos)->bool { return maps[pos.y][pos.x] == 0; }; // 执行搜索 BlockAllocator allocator; AStar algorithm(&allocator); auto path = algorithm.find(param); 编译代码 make build && cd build cmake ../example && make

#include “a_star.h“
#include 
#include 
#include 
#include “blockallocator.h“

static const int kStepValue = 10;
static const int kObliqueValue = 14;

AStar::AStar（BlockAllocator *allocator）
    : width_（0）
     height_（0）
     allocator_（allocator）
     step_val_（kStepValue）
     oblique_val_（kObliqueValue）
{
    assert（allocator_ != nullptr）;
}

AStar::~AStar（）
{
    clear（）;
}

// 获取直行估值
int AStar::get_step_value（） const
{
    return step_val_;
}

// 获取拐角估值
int AStar::get_oblique_value（） const
{
    return oblique_val_;
}

// 设置直行估值
void AStar::set_step_value（int value）
{
    step_val_ = value;
}

// 获取拐角估值
void AStar::set_oblique_value（int value）
{
    oblique_val_ = value;
}

// 清理参数
void AStar::clear（）
{
    size_t index = 0;
    const size_t max_size = width_ * height_;
    while （index < max_size）
    {
        allocator_->free（mapping_[index++] sizeof（Node））;
        index++;
    }
    open_list_.clear（）;
    can_pass_ = nullptr;
    width_ = height_ = 0;
}

// 初始化操作
void AStar::init（const Params ¶m）
{
    width_ = param.width;
    height_ = param.height;
    can_pass_ = param.can_pass;
    if （!mapping_.empty（））
    {
        memset（&mapping_[0] 0 sizeof（Node*） * mapping_.size（））;
    }
    mapping_.resize（width_ * height_ nullptr）;
}

// 参数是否有效
bool AStar::is_vlid_params（const AStar::Params ¶m）
{
    return （param.can_pass != nullptr
            && （param.width > 0 && param.height > 0）
            && （param.end.x >= 0 && param.end.x < param.width）
            && （param.end.y >= 0 && param.end.y < param.height）
            && （param.start.x >= 0 && param.start.x < param.width）
            && （param.start.y >= 0 && param.start.y < param.height）
            ）;
}

// 获取节点索引
bool AStar::get_node_index（Node *node size_t *index）
{
    *index = 0;
    const size_t size = open_list_.size（）;
    while （*index < size）
    {
        if （open_list_[*index]->pos == node->pos）
        {
            return true;
        }
        ++（*index）;
    }
    return false;
}

// 二叉堆上滤
void AStar::percolate_up（size_t hole）
{
    size_t parent = 0;
    while （hole > 0）
    {
        parent = （hole - 1） / 2;
        if （open_list_[hole]->f（） < open_list_[parent]->f（））
        {
            std::swap（open_list_[hole] open_list_[parent]）;
            hole = parent;
        }
        else
        {
            return;
        }
    }
}

// 计算G值
inline uint16_t AStar::calcul_g_value（Node *parent const Vec2 ¤t）
{
    uint16_t g_value = （（abs（current.y + current.x - parent->pos.y - parent->pos.x）） == 2 ? oblique_val_ : step_val_）;
    return g_value += parent->g;
}

// 计算F值
inline uint16_t AStar::calcul_h_value（const Vec2 ¤t const Vec2 &end）
{
    unsigned int h_value = abs（end.y + end.x - current.y - current.x）;
    return h_value * step_val_;
}

// 节点是否存在于开启列表
inline bool AStar::in_open_list（const Vec2 &pos Node *&out_node）
{
    out_node = mapping_[pos.y * width_ + pos.x];
    return out_node ? out_node-

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2017-03-13 01:46  a-star-algorithm-master\
     文件        1076  2017-03-13 01:46  a-star-algorithm-master\LICENSE
     文件        1210  2017-03-13 01:46  a-star-algorithm-master\README.md
     目录           0  2017-03-13 01:46  a-star-algorithm-master\astar\
     文件        8332  2017-03-13 01:46  a-star-algorithm-master\astar\a_star.cpp
     文件        4250  2017-03-13 01:46  a-star-algorithm-master\astar\a_star.h
     文件        4697  2017-03-13 01:46  a-star-algorithm-master\astar\blockallocator.cpp
     文件        1846  2017-03-13 01:46  a-star-algorithm-master\astar\blockallocator.h
     目录           0  2017-03-13 01:46  a-star-algorithm-master\example\
     文件         623  2017-03-13 01:46  a-star-algorithm-master\example\CMakeLists.txt
     文件        1177  2017-03-13 01:46  a-star-algorithm-master\example\test.cpp