#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_;
}

//?設(shè)置直行估值
void?AStar::set_step_value（int?value）
{
????step_val_?=?value;
}

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

//?清理參數(shù)
void?AStar::clear（）
{
????size_t?index?=?0;
????const?size_t?max_size?=?width_?*?height_;
????while?（index?????{
????????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）;
}

//?參數(shù)是否有效
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.end.y?>=?0?&&?param.end.y?????????????&&?（param.start.x?>=?0?&&?param.start.x?????????????&&?（param.start.y?>=?0?&&?param.start.y?????????????）;
}

//?獲取節(jié)點(diǎn)索引
bool?AStar::get_node_index（Node?*node?size_t?*index）
{
????*index?=?0;
????const?size_t?size?=?open_list_.size（）;
????while?（*index?????{
????????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（）?f（））
????????{
????????????std::swap（open_list_[hole]?open_list_[parent]）;
????????????hole?=?parent;
????????}
????????else
????????{
????????????return;
????????}
????}
}

//?計(jì)算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;
}

//?計(jì)算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_;
}

//?節(jié)點(diǎn)是否存在于開啟列表
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-