1. @map：全局唯一的gamemap；
   
2. @uinits：全局唯一的unit_map；
   
3. @u：要从它开始计算可到达位置的单位；
   
4. @loc：一个坐标值，要以它为起点开始计算可到达位置；
   
5. @move_left：单位的剩余移动力。对于未移动过单位，它的值就是unit.total_movement；
   
6. @[color=Red]destinations[/color][OUT]：存储计算出可到达位置。destinations值上可认为是step数组，struct step定义：{(map_location)  prev, (map_location) curr, (int) move_left}；
   
7. @force_ignore_zoc：是否强制不考虑zoc。ignore_units=true时，该值忽略；
   
8. @allow_teleport：是否要使用传送。拥有传送技能单位该值一般置true，否则false；
   
9. @viewing_team：本阵营可看见的其它阵营（包括自己），它经常等于teams；
   
10. @additional_turns：附加回合数。1：显示两回内数径，2：显示三回内路径；
    
11. @see_all：默认置false；
    
12. @ignore_units：是否忽略单位，默认false；
    
13. 
    
14. 格子一旦被访问过，它的in值被置为search_counter + 1。
    
15. 经过find_routes后形成的destinations内容
    
16. 1、自已所在格子。即loc，也会在destinations中，但它的step.prev是个未定义值；
    
17. 2、友方阵营单位所在格子。
    
18. 3、单位有传输技能时，即allow_teleport，***
    
19. 4、敌方阵营单位所在格子不在destinations中，（ignore_units=false）。上面包括两个敌方单位格子，那个后面的show_attack_options(u)添加的。
    
20. 5、排序。以[X][Y]次序，x、y都0逐增。
    
21. 
    
22. static void find_routes(const gamemap& map, const unit_map& units,
    
23.                 const unit& u, const map_location& loc,
    
24.                 int move_left, pathfind::paths::dest_vect &destinations,
    
25.                 std::vector<team> const &teams,
    
26.                 bool force_ignore_zocs, bool allow_teleport, int turns_left,
    
27.                 const team &viewing_team,
    
28.                 bool see_all, bool ignore_units)
    
29. {
    
30.         const team& current_team = teams[u.side() - 1];
    
31.         std::set<map_location> teleports;
    
32.         if (allow_teleport) {
    
33.           teleports = pathfind::get_teleport_locations(u, units, viewing_team, see_all, ignore_units);
    
34.         }
    
35. 
    
36.         const int total_movement = u.total_movement();
    
37. 
    
38.         // prepare self-city grid condition
    
39.         // 得到属于“本城格子”判断条件
    
40.         void* expediting_city_cookie = NULL;
    
41.         if (units.expediting()) {
    
42.                 expediting_city_cookie = units.expediting_city_node();
    
43.         } else if (units.city_from_loc(loc)) {
    
44.                 expediting_city_cookie = units.get_cookie(loc);
    
45.         }
    
46. 
    
47.         std::vector<map_location> locs(6 + teleports.size());
    
48.         std::copy(teleports.begin(), teleports.end(), locs.begin() + 6);
    
49. 
    
50.         search_counter += 2;
    
51.         if (search_counter == 0) search_counter = 2;
    
52. 
    
53.         static std::vector<node> nodes;
    
54.         nodes.resize(map.w() * map.h());
    
55. 
    
56.         indexer index(map.w(), map.h());
    
57.         comp node_comp(nodes);
    
58. 
    
59.         int xmin = loc.x, xmax = loc.x, ymin = loc.y, ymax = loc.y, nb_dest = 1;
    
60. 
    
61.         nodes[index(loc)] = node(move_left, turns_left, map_location::null_location, loc);
    
62.         std::vector<int> pq;
    
63.         // 调用程序可能把move_left=0传下来，像出征，这时不要让出征到“本城格子”。为不显示“本城格子”是可出征地，办法就是让move_left=0时不执行接下的while循环体
    
64.         if (move_left || turns_left) {
    
65.                 pq.push_back(index(loc));
    
66.         }
    
67. 
    
68.         while (!pq.empty()) {
    
69.                 node& n = nodes[pq.front()];
    
70.                 std::pop_heap(pq.begin(), pq.end(), node_comp);
    
71.                 pq.pop_back();
    
72.                 n.in = search_counter;
    
73. 
    
74.                 get_adjacent_tiles(n.curr, &locs[0]);
    
75.                 for (int i = teleports.count(n.curr) ? locs.size() : 6; i-- > 0; ) {
    
76.                         if (!locs[i].valid(map.w(), map.h())) continue;
    
77. 
    
78.                         node& next = nodes[index(locs[i])];
    
79. 
    
80.                         bool next_visited = next.in - search_counter <= 1u;
    
81. 
    
82.                         // Classic Dijkstra allow to skip chosen nodes (with next.in==search_counter)
    
83.                         // But the cost function and hex grid allow to also skip visited nodes:
    
84.                         // if next was visited, then we already have a path 'src-..-n2-next'
    
85.                         // - n2 was chosen before n, meaning that it is nearer to src.
    
86.                         // - the cost of 'n-next' can't be smaller than 'n2-next' because
    
87.                         //   cost is independent of direction and we don't have more MP at n
    
88.                         //   (important because more MP may allow to avoid waiting next turn)
    
89.                         // Thus, 'src-..-n-next' can't be shorter.
    
90.                         if (next_visited) continue;
    
91. 
    
92.                         int move_cost;
    
93.                         if (expediting_city_cookie && units.get_cookie(locs[i]) == expediting_city_cookie) {
    
94.                                 // locs[i]是“本城格子”，消耗移动力0
    
95.                                 move_cost = 0;
    
96.                         } else {
    
97.                                 move_cost = u.movement_cost(map[locs[i]]);
    
98.                         }
    
99.                                
    
100. 
     
101.                         node t = node(n.movement_left, n.turns_left, n.curr, locs[i]);
     
102.                         if (t.movement_left < move_cost) {
     
103.                                 t.movement_left = total_movement;
     
104.                                 t.turns_left--;
     
105.                         }
     
106. 
     
107.                         // 前半部分作用：有些单位的total_movement可能就小于在该地形上的需要移动力，即使加了一回合还是不够
     
108.                         if (t.movement_left < move_cost || t.turns_left < 0) continue;
     
109. 
     
110.                         t.movement_left -= move_cost;
     
111. 
     
112.                         if (!ignore_units) {
     
113.                                 const unit *v =
     
114.                                         get_visible_unit(units, locs[i], viewing_team, see_all);
     
115.                                 if (v && current_team.is_enemy(v->side())) {
     
116.                                         // 正欲展开格子上站着个敌方单位，该格子不进入OPEN
     
117.                                         continue;
     
118.                                 }
     
119. 
     
120.                                 // move cost in any terrain cannot be zero. it is zero indicate loc is self-city grid.
     
121.                                 if (move_cost && !force_ignore_zocs && t.movement_left > 0
     
122.                                     && pathfind::enemy_zoc(units, teams, locs[i], viewing_team, u.side(), see_all)
     
123.                                                 && !u.get_ability_bool("skirmisher", locs[i])) {
     
124.                                         // 正欲展开格子在一个敌方单位的ZOC内，一旦移动到该格子剩余移动力置0。
     
125.                                         t.movement_left = 0;
     
126.                                 }
     
127.                         }
     
128. 
     
129.                         // 确定要展开一个新的格子后，看是否要扩大容纳可到达位置的“矩形”
     
130.                         ++nb_dest;
     
131.                         int x = locs[i].x;
     
132.                         if (x < xmin) xmin = x;
     
133.                         if (xmax < x) xmax = x;
     
134.                         int y = locs[i].y;
     
135.                         if (y < ymin) ymin = y;
     
136.                         if (ymax < y) ymax = y;
     
137. 
     
138.                         bool in_list = next.in == search_counter + 1;
     
139.                         t.in = search_counter + 1;
     
140.                         next = t;
     
141. 
     
142.                         // if already in the priority queue then we just update it, else push it.
     
143.                         if (in_list) { // never happen see next_visited above
     
144.                                 std::push_heap(pq.begin(), std::find(pq.begin(), pq.end(), index(locs[i])) + 1, node_comp);
     
145.                         } else {
     
146.                                 pq.push_back(index(locs[i]));
     
147.                                 std::push_heap(pq.begin(), pq.end(), node_comp);
     
148.                         }
     
149.                 }
     
150.         }
     
151. 
     
152.         // Build the routes for every map_location that we reached.
     
153.         // The ordering must be compatible with map_location::operator<.
     
154.         // 根据容纳可到达位置的“矩形”，以X第一次排序Y第二次排序顺序从nodes生成destinations
     
155.         destinations.reserve(nb_dest);
     
156.         for (int x = xmin; x <= xmax; ++x) {
     
157.                 for (int y = ymin; y <= ymax; ++y)
     
158.                 {
     
159.                         const node &n = nodes[index(map_location(x, y))];
     
160.                         if (n.in - search_counter > 1u) continue;
     
161.                         pathfind::paths::step s =
     
162.                                 { n.curr, n.prev, n.movement_left + n.turns_left * total_movement };
     
163.                         destinations.push_back(s);
     
164.                 }
     
165.         }
     
166. }

复制代码

node中in字段

说到in字段则必须说search_counter变量。search_counter是一个全局变量，但在一次find_routes过程中它的值保持不变。search_counter最小值是2（不可能是0和1）。

in变量用于判断某一格子在此次find_routes时是否已被访问过。此次find_routes没被访问过时，值是不确定的，但满足：1）是偶数；2）(in - search_counter <= 1u)成立，这个式子中in可能比search_counter小，但因为是无符号数，<还是成立。

对in变量，要标志node是否访问过，用个bool变量不是更简单，干吗要in又要search_counter，这不是增加复杂度吗？——这么做原因是nodes是个静态变量（node中的元素数是地图格子数，初始化须要点时间）。第N+1次用的是第N次操作结果，N+1次的in值自然也要基于N次in值。

要用bool变量标识的话，逃不掉各个node中开辟个状态变量方法，这个变量在搜索前全部置为false，访问过后置为true。用了以上in+serach_counter方法后，省略了这个全置false过程。

和in状态相关的另一个可能疑问，函数每次搜索前会调用nodes.resize，nodes.resize会不会把所有in复位为0？
——不会。以下是resize的函数实现：

1. void resize(size_type new_size) { resize(new_size, T()); }
   
2. void resize(size_type new_size, const T& x)
   
3. {
   
4.         if (new_size < size()) {
   
5.                 erase(begin() + new_size, end()); // erase区间范围以外的数据，确保区间以外的数据无效
   
6.         } else {
   
7.                 insert(end(), new_size - size(), x); // 填补区间范围内空缺的数据，确保区间内的数据有效
   
8.         }
   
9. }

复制代码