ai移动

ancientcc

二楼：calculate_possible_moves2/calculate_possible_moves
三楼：有一只部队A，知道它的起点(from)和要到达目的地(to)，如何选择一条最好路径？(ai_default::move_unit)

ancientcc

calculate_possible_moves不支持统一处理城外/城内部队，将来会逐渐不使用calculate_possible_moves

AI移动要解决一个问题是可移动到哪里？即AI要知道地图上部队分布及自己/他人能移动到信息。这些移动到信息的获取是通过calculate_possible_moves2/calculate_possible_moves。
移动到信息包括脚印信息和端到端信息。
脚印信息（std::map<map_location, pathfind::paths>）：它的key是符合条件了的单位。像本AI所有单位，像本AI所有敌对单位。它的value则是基于key构造出的pathfind::paths对象。脚印信息以std::map<location,paths>表示，它的长度就是符合条件的起点单位个数。

端到端信息（std::multimap<map_location,map_location>）：它存储在srcdst和dstsrc变量，因为两个变量意义相近，这里具体说明srcdst。srcdst的key是符合条件的单位，和脚印信息中的key一样意义。它的value是该key在移动力范围内，再结合ZOC等规则限制所有可踩到的点，这个value是脚印信息中value(paths.destinations)的子集，它去除三种情况，1）value格子站了个单位；2）value格子是友邻村庄；3）key正站在value格子上。端到端信息以std::multimap<map_location, map_location>表示，它的长度N1*AI1 + N2*AI2 + ..... + N3*AI3，Ni：单位AIi可踩到点数。

功能：以给定的参数和ai当前状态为条件，从全地图单位中过滤出起点单位，形成它们的脚印信息，它们的可移动端到端信息。

参数：
@units[in]：全局unit_map对象。
@res[out]：用于存放形成的脚印信息。
@srcdst[out]：用于存放形成的可移动的端到端信息
@dstsrc[out]：用于存放形成的可移动的端到端信息。在值上，它和srcdst具有相同长度，在具体元素上，它的起点就是srcdst终点，它的终点就是srcdst起点
@enemy[in]：形成搜索条件的参数。true，起点单位必须属于和本ai敌对阵营；flase，起点单位必须属于和本ai非敌对阵营
@assume_full_movement[in]：形成搜索条件的参数。只在enemy=false时生效。true，起点单位可以是本ai阵营或友军阵营；flase，起点单位需是本ai阵营。注：assume_full_movement并不仅仅是是否要在符合条件单位中加入友军单位，它还控制着形成pathfind::paths是否要使用全移动力。true时，那些已没有移动力但符合条件单位还是会枚举出全部信息。

获得移动信息通用逻辑
1、形成troops。
2、调用calculate_possible_move2得到res、srcdst和dstsrc。
作为特殊情况，当troops中只有一只部队时，是调用另个形式的calculate_possible_move2，这也是为什么要存在两个calculate_possible_move2函数的原因。

A：假设loc是某个符合条件单位A所在格子，srcdst和dstsrc是否包括了<loc, loc>？
Q：这个要看A的剩余移动力。剩余移动力大于零时，包括，否则不包括。这个包括/不包括和assume_full_movement无关。
注：res肯定包括。

ancientcc

方法一
1）计算A在from的可到达格子集合std::vector<map_location> srcdst。
2）用种近似算法，像distance_between(dst, to)，逐个计算集合srcdst中元素dst到to分数。挑出个最好分数best_dst。
3）把A从from移动到best_dst。
这种方法存在问题是A只挑个座标距离最近的，而不管路途中地形。这往往会使骑兵冲进山坳，然后就傻傻的走不出山坳。

方法二
1）调用a_star_search，设个不会超过的移动阈值，搜出一条路径route。
2）用这个route调用::move_unit。即使A的移动力其实无法完成route，::move_unit自会中途退出。

程序采用方法二

设定“合适”门限
要为a_star_search设一个“适合”的门限。这个门限有几个要求：
1）尽可能绕过站了敌方部队格子。要让a_start_search尽可能绕过这些部队，因而在这些格子上的cost要比没有部队时高。
2）不能让挑选不可经过地形格子。像山岭对于骑兵。这时这个cost应该是“绝对”高，不能让a_star_search选择这条路径。
3）对于最小值，必须大于（2*站了敌方部队格子的cost)。当计划攻城时，目标格子往往就是敌方城市中心格子，中心格子加上旁边一个格子就是两格。

以上可以看出，这个门限取多少和“站了敌方部队格子”、“不可经过地形格子”消耗多少移动力密切相关。程序中对于这两个值分别是：
站了敌方部队格子：getUnitHoldValue()(424242.0)
不可经过地形格子：getNoPathValue()(42424242.0)

当前设定门限值：calc.getUnitHoldValue() * 3 + 10000.0
让最多可以穿过3个敌方部队，后面10000.0是留给“可到达”格子上消耗移动力。

ai_default::move_unit
dst_must_reachable指示此个移动是否强制要末尾格子是“可到达”格子。对于移动+攻击，移动+建造这类移动，要求要移动部队必须可以站在末尾格子。

由于传给ai_default::move_unit的to上可能就站有部队，这时需要把这些结尾站有部队格子从搜出的路径上去除掉。以最后一个“站”在的格子赋给to。

1. while (!dst_must_reachable) {
   
2.         to = route_.steps.back();
   
3.         if (!units_.count(to)) {
   
4.                 break;
   
5.         }
   
6.         if (to == from) {
   
7.                 // A(city)(city), A will enter it
   
8.                 return map_location();
   
9.         }
   
10.         route_.steps.pop_back();
    
11. }

复制代码

以上删结尾格子的while，当中if (to == from)是可能成立的。

轮到袁绍行动，曹彰被灭，鞠义站在曹彰位置。颜良认为不适合攻城，于是计划穿过鞠义到濮阳中心格子。由于鞠义是已方阵营部队，在它之上只须耗“可到达”移动力，加上要路过的濮阳两格子，但这三个格子全站有部队，导致(to == from)成立。

当城内部队无法移出城时（包括出征+战斗和只是出征）
1、只有确定移出城的部队才需要调用erase；
2、对于未能移出部队则调用un.remove_movement_ai()。这个操作对只是出征无作用，但出征+战斗时需要。

1. if (move_spectator.get_unit().valid() && move_spectator.get_unit()->first != from) {
   
2.         // move_unit may be not move! reside troop ratain in city.
   
3.         reside_troops.erase(reside_troops.begin() + units_.last_expedite_index());
   
4. } else {
   
5.         un.remove_movement_ai();
   
6. }

复制代码

在此图下，
轮到孙坚。
徐盛移到(51,28)（伏击有效），陆逊移到(50,28)。

轮到刘表。
有一个部队移动(51,29)，占掉这格子。
分析攻击路径，决定采用路径是(53,30)-->(52,30)-->(51,29)-->(51,28)，去攻击位在(50,28)的陆逊。

本计划到达(51,28)，但在这格子上站有敌对伏击部队，而偏偏(51,29)上又有一个已方部队，致使蔡瑁只能待在城里。由于没移动，蔡瑁和未计算前一致。

下一次攻击分析时，当前状态和上一次一样，导致系统死循环。

????(51,29)上要是有已方部队，(51,28)上怎么可能还有伏击部队？——出问题时应该检查(51,28)、(51,29)上到底为什么不时移动到，是部队的话应该检查是什么部队。

如果出现此种问题，想到办法是一旦遇到这个无法移动情况就把该部队移动力置0，使得分析攻击路径时不再考虑这只城内部队。un.remove_movement_ai()实现置0操作。

当要移动部队是城内部队时，参数std::pair<unit*, int>& pair中的first为何是城市指针，而不是部队指针？
因为之前移动操作影响，部队指针可能已经失效。

1. unit* unit_ptr = NULL;
   
2. if (pair.second >= 0) {
   
3.         unit_ptr = &unit_2_artifical(pair.first)->reside_troops()[pair.second];
   
4. } else {
   
5.         unit_ptr = pair.first;
   
6. }

复制代码

对于移动，它一般是数只部队被组成一个要移动集合，然后逐只移动。这就造成一个问题，之前移动操作会影响集合中未移动部队指针。
当城外部队移动到城内时，这只部队是添加在该城的reside_troop末尾，但这个push_back会影响已先前已在部队的内存位置，进而影响属于该城的而未移动部队指针，使这些指针的指向处于不可预知状态

这种影响不会涉及城外部队，但要注意城外部队一旦移动后，这个指针可能已经无效，像部队入城了。

对于攻击时的std::pair<unit*, int>，这个first还是城内部队指针。1）每次攻击分析时都会重新构造一个pair集合；2）攻击分析过程中用部队指针可以快速进行指针值比较。

std::vector<>.push_back、erase函数
push_back操作是在vector添加单位，要注意操作会影响先前已存在单位的内存位置！
如果先前vector中已有4个unit对象，一旦向这个vector添加一个unit，这个unit是会被放在末尾，但同时会改变之前四个unit的内存位置，导致如果程序有指向之前四个unit对象指针的话，这些指针将可能变得无效。

同样的，erase是在vector删除间接，要注意操作也会影响先前已存在单位的内存位置！（参考ai::build）
如果先前vector中已有4个unit对象，一旦向这个vector删除一个unit，删除的uniti若不是末尾，它就可能改变它自已和在它之后的unit的内存位置，导致如果程序有指向它自已和之后unit对象指针的话，这些指针将可能变得无效。

它们改为后内存位置是随机的，程序要确保不使用此时指针。即遇到过程中会删除unit时，删除之后的操作要重计算指针。