函数：find_routes和a_star_searc - SDL中文论坛

@map：全局唯一的gamemap；
@uinits：全局唯一的unit_map；
@u：要从它开始计算可到达位置的单位；
@loc：一个坐标值，要以它为起点开始计算可到达位置；
@move_left：单位的剩余移动力。对于未移动过单位，它的值就是unit.total_movement；
@[color=Red]destinations[/color][OUT]：存储计算出可到达位置。destinations值上可认为是step数组，struct step定义：{(map_location) prev, (map_location) curr, (int) move_left}；
@force_ignore_zoc：是否强制不考虑zoc。ignore_units=true时，该值忽略；
@allow_teleport：是否要使用传送。拥有传送技能单位该值一般置true，否则false；
@viewing_team：本阵营可看见的其它阵营（包括自己），它经常等于teams；
@additional_turns：附加回合数。1：显示两回内数径，2：显示三回内路径；
@see_all：默认置false；
@ignore_units：是否忽略单位，默认false；
格子一旦被访问过，它的in值被置为search_counter + 1。
经过find_routes后形成的destinations内容
1、自已所在格子。即loc，也会在destinations中，但它的step.prev是个未定义值；
2、友方阵营单位所在格子。
3、单位有传输技能时，即allow_teleport，***
4、敌方阵营单位所在格子不在destinations中，（ignore_units=false）。上面包括两个敌方单位格子，那个后面的show_attack_options(u)添加的。
5、排序。以[X][Y]次序，x、y都0逐增。
static void find_routes(const gamemap& map, const unit_map& units,
const unit& u, const map_location& loc,
int move_left, pathfind::paths::dest_vect &destinations,
std::vector<team> const &teams,
bool force_ignore_zocs, bool allow_teleport, int turns_left,
const team &viewing_team,
bool see_all, bool ignore_units)
{
const team& current_team = teams[u.side() - 1];
std::set<map_location> teleports;
if (allow_teleport) {
teleports = pathfind::get_teleport_locations(u, units, viewing_team, see_all, ignore_units);
}
const int total_movement = u.total_movement();
// prepare self-city grid condition
// 得到属于“本城格子”判断条件
void* expediting_city_cookie = NULL;
if (units.expediting()) {
expediting_city_cookie = units.expediting_city_node();
} else if (units.city_from_loc(loc)) {
expediting_city_cookie = units.get_cookie(loc);
}
std::vector<map_location> locs(6 + teleports.size());
std::copy(teleports.begin(), teleports.end(), locs.begin() + 6);
search_counter += 2;
if (search_counter == 0) search_counter = 2;
static std::vector<node> nodes;
nodes.resize(map.w() * map.h());
indexer index(map.w(), map.h());
comp node_comp(nodes);
int xmin = loc.x, xmax = loc.x, ymin = loc.y, ymax = loc.y, nb_dest = 1;
nodes[index(loc)] = node(move_left, turns_left, map_location::null_location, loc);
std::vector<int> pq;
// 调用程序可能把move_left=0传下来，像出征，这时不要让出征到“本城格子”。为不显示“本城格子”是可出征地，办法就是让move_left=0时不执行接下的while循环体
if (move_left || turns_left) {
pq.push_back(index(loc));
}
while (!pq.empty()) {
node& n = nodes[pq.front()];
std::pop_heap(pq.begin(), pq.end(), node_comp);
pq.pop_back();
n.in = search_counter;
get_adjacent_tiles(n.curr, &locs[0]);
for (int i = teleports.count(n.curr) ? locs.size() : 6; i-- > 0; ) {
if (!locs[i].valid(map.w(), map.h())) continue;
node& next = nodes[index(locs[i])];
bool next_visited = next.in - search_counter <= 1u;
// Classic Dijkstra allow to skip chosen nodes (with next.in==search_counter)
// But the cost function and hex grid allow to also skip visited nodes:
// if next was visited, then we already have a path 'src-..-n2-next'
// - n2 was chosen before n, meaning that it is nearer to src.
// - the cost of 'n-next' can't be smaller than 'n2-next' because
// cost is independent of direction and we don't have more MP at n
// (important because more MP may allow to avoid waiting next turn)
// Thus, 'src-..-n-next' can't be shorter.
if (next_visited) continue;
int move_cost;
if (expediting_city_cookie && units.get_cookie(locs[i]) == expediting_city_cookie) {
// locs[i]是“本城格子”，消耗移动力0
move_cost = 0;
} else {
move_cost = u.movement_cost(map[locs[i]]);
}
node t = node(n.movement_left, n.turns_left, n.curr, locs[i]);
if (t.movement_left < move_cost) {
t.movement_left = total_movement;
t.turns_left--;
}
// 前半部分作用：有些单位的total_movement可能就小于在该地形上的需要移动力，即使加了一回合还是不够
if (t.movement_left < move_cost || t.turns_left < 0) continue;
t.movement_left -= move_cost;
if (!ignore_units) {
const unit *v =
get_visible_unit(units, locs[i], viewing_team, see_all);
if (v && current_team.is_enemy(v->side())) {
// 正欲展开格子上站着个敌方单位，该格子不进入OPEN
continue;
}
// move cost in any terrain cannot be zero. it is zero indicate loc is self-city grid.
if (move_cost && !force_ignore_zocs && t.movement_left > 0
&& pathfind::enemy_zoc(units, teams, locs[i], viewing_team, u.side(), see_all)
&& !u.get_ability_bool("skirmisher", locs[i])) {
// 正欲展开格子在一个敌方单位的ZOC内，一旦移动到该格子剩余移动力置0。
t.movement_left = 0;
}
}
// 确定要展开一个新的格子后，看是否要扩大容纳可到达位置的“矩形”
++nb_dest;
int x = locs[i].x;
if (x < xmin) xmin = x;
if (xmax < x) xmax = x;
int y = locs[i].y;
if (y < ymin) ymin = y;
if (ymax < y) ymax = y;
bool in_list = next.in == search_counter + 1;
t.in = search_counter + 1;
next = t;
// if already in the priority queue then we just update it, else push it.
if (in_list) { // never happen see next_visited above
std::push_heap(pq.begin(), std::find(pq.begin(), pq.end(), index(locs[i])) + 1, node_comp);
} else {
pq.push_back(index(locs[i]));
std::push_heap(pq.begin(), pq.end(), node_comp);
}
}
}
// Build the routes for every map_location that we reached.
// The ordering must be compatible with map_location::operator<.
// 根据容纳可到达位置的“矩形”，以X第一次排序Y第二次排序顺序从nodes生成destinations
destinations.reserve(nb_dest);
for (int x = xmin; x <= xmax; ++x) {
for (int y = ymin; y <= ymax; ++y)
{
const node &n = nodes[index(map_location(x, y))];
if (n.in - search_counter > 1u) continue;
pathfind::paths::step s =
{ n.curr, n.prev, n.movement_left + n.turns_left * total_movement };
destinations.push_back(s);
}
}
}

复制代码

pathfind::plain_route pathfind::a_star_search(const map_location& src, const map_location& dst,
double stop_at, const pathfind::cost_calculator *calc, const size_t width,
const size_t height, const std::set<map_location>* teleports) {
//----------------- PRE_CONDITIONS ------------------
assert(src.valid(width, height));
assert(dst.valid(width, height));
assert(calc != NULL);
assert(stop_at <= calc->getNoPathValue());
//---------------------------------------------------
DBG_PF << "A* search: " << src << " -> " << dst << '\n';
// 对shortest_path_calculator，cost()返回值和src无关，值上大概等于单位在dst这格子上消耗的移动力，和dst是什么地形相关。
if (calc->cost(dst, 0) >= stop_at) {
LOG_PF << "aborted A* search because Start or Dest is invalid\n";
pathfind::plain_route locRoute;
locRoute.move_cost = int(calc->getNoPathValue());
return locRoute;
}
if (teleports && teleports->empty()) teleports = NULL;
std::vector<map_location> locs(teleports ? 6 + teleports->size() : 6 );
if (teleports) {
std::copy(teleports->begin(), teleports->end(), locs.begin() + 6);
}
// increment search_counter but skip the range equivalent to uninitialized
search_counter += 2;
if (search_counter - bad_search_counter <= 1u)
search_counter += 2;
static std::vector<node> nodes;
nodes.resize(width * height); // this create uninitalized nodes
indexer index(width, height);
comp node_comp(nodes);
nodes[index(dst)].g = stop_at + 1;
nodes[index(src)] = node(0, src, map_location::null_location, dst, true, teleports);
std::vector<int> pq;
pq.push_back(index(src));
while (!pq.empty()) {
node& n = nodes[pq.front()];
n.in = search_counter;
std::pop_heap(pq.begin(), pq.end(), node_comp);
pq.pop_back();
if (n.t >= nodes[index(dst)].g) {
// 正常情况下，这里是退出while出口。随着枚举不断深入，dst会出现在某一次get_adjacent_tiles返回的格子中，到时nodes[index(dst)].g的值就会由初始设置的stop_at改到一个比stop_at小的值（大概等于选择了的src到dst这条路径上消耗移动力之和）
break;
}
get_adjacent_tiles(n.curr, &locs[0]);
int i = teleports && teleports->count(n.curr) ? locs.size() : 6;
for (; i-- > 0;) {
if (!locs[i].valid(width, height)) continue;
node& next = nodes[index(locs[i])];
// 如果next节点已被访问过，则门限值取next.g，否则取stop_at
double thresh = (next.in - search_counter <= 1u) ? next.g : stop_at + 1;
// cost() is always >= 1 (assumed and needed by the heuristic)
if (n.g + 1 >= thresh) continue;
// cost()返回值至少大于等于在locs[i]上的消耗移动力，移动力至少大于等于零
// 以下等式不是A*算法中的f(n) = g(n) + h(n)，而是类似g(n + 1) = g(n-1) + g(n)
double cost = n.g + calc->cost(locs[i], n.g);
if (cost >= thresh) continue;
bool in_list = next.in == search_counter + 1;
next = node(cost, locs[i], n.curr, dst, true, teleports);
if (in_list) {
std::push_heap(pq.begin(), std::find(pq.begin(), pq.end(), index(locs[i])) + 1, node_comp);
} else {
pq.push_back(index(locs[i]));
std::push_heap(pq.begin(), pq.end(), node_comp);
}
}
}
pathfind::plain_route route;
if (nodes[index(dst)].g <= stop_at) {
DBG_PF << "found solution; calculating it...\n";
route.move_cost = static_cast<int>(nodes[index(dst)].g);
for (node curr = nodes[index(dst)]; curr.prev != map_location::null_location; curr = nodes[index(curr.prev)]) {
route.steps.push_back(curr.curr);
}
route.steps.push_back(src);
std::reverse(route.steps.begin(), route.steps.end());
} else {
LOG_PF << "aborted a* search " << "\n";
route.move_cost = static_cast<int>(calc->getNoPathValue());
}
return route;
}

复制代码