SLG的敵人AI 偽代碼算法，求個優化思路

电子最终龙

每次寫AI的時候都會覺得自己的遊戲AI課程白上了……orz
這次要做SLG，寫了遍歷之後發現技能多移動範圍廣的單位行動居然能卡個兩三秒
無奈之下暫時模仿貪婪算法寫了個最弱目標優先
運算時間沒錯是最小化了……
但是少了技能預讀，AI不會找人多的位置放技能傷害最大化，不會補刀，也不會卡敵人的攻擊距離……
總之趕腳好低端{:2_271:}

求吐槽，求指點，求優化，各種求{:2_272:}

1. # AI主流程。battler: 行動方，map: 當前地圖站位分佈集
   
2. def 最弱優先攻擊（battler, map)
   
3.   route = move_to(battler, 搜索防禦最低目標(battler))
   
4.   if battler.未施放增益法術?
   
5.     skill_id = battler.增益法術id
   
6.        return 生成行動(route, 增益法術id)
   
7.   elsif battler.生命小於10%?
   
8.       if battler.能治療?
   
9.         return 生成行動(route, 治療id)
   
10.       end
    
11.       if battler.有藥吃?
    
12.         return 生成行動(route, 吃藥id)
    
13.       end
    
14.   end
    
15.   if 範圍內無可用目標
    
16.   return 生成行動(route, 加速技能id)
    
17.   end
    
18.   skill_id, target_pos = 計算攻擊技能和落點(battler, 搜索防禦最低目標(battler))
    
19.   return 生成行動(route, skill_id, target_pos)
    
20. end
    
21. 
    
22. # 搜索battler的移動+攻擊範圍內防禦最低的敵人，返回最接近目標的可移動座標
    
23. # battler: 當前行動方，map: 地圖站位分佈集
    
24. def 搜索防禦最低目標(battler, map)
    
25.     if 範圍內無可用目標
    
26.     # 搜索最近目標target，算法略
    
27.     return target.x, target.y
    
28.   else # 範圍內有可用目標時
    
29.   # 計算範圍內所有目標中防禦最低的target, 算法略
    
30.   return target.x, target.y
    
31. end
    
32. 
    
33. # 貪婪尋路計算移動路點集
    
34. # battler: 行動方，x, y: 目標路點座標
    
35. def move_to(battler, x, y)
    
36.   #創建路點集route
    
37.   route = []
    
38.   # 計算路點集，算法略
    
39.   return route
    
40. end

复制代码

end55rpg

应该首先考虑找小孩和女人，为啥，TM最弱。
                                      -------------------------图灵原理

电子最终龙

end55rpg 发表于 2013-8-1 18:40
应该首先考虑找小孩和女人，为啥，TM最弱。
                                      --------------------- ...

已經包含搜索最弱目標的方法了，現在缺的是傷害最大化以及補刀的計算……

Sion

得把每个行动都遍历一遍，记录下每个行动的结果（包含移动、伤害与目标等信息），按行动的目标来分组。
然后在计算每个目标所受到的所有行动组合能得到的最大伤害（通常就选取敌方单位造成最高伤害的技能就行了），如果伤害足够死亡的话，AI就集体采取这种行动。
不过这样集火玩家，玩家会火大的吧。

电子最终龙

Sion 发表于 2013-8-1 19:13
得把每个行动都遍历一遍，记录下每个行动的结果（包含移动、伤害与目标等信息），按行动的目标来分组。
然 ...

讓AI卡玩家的攻擊距離運算量就真的喪心病狂了
行動遍歷的話……
假設敵人有3個範圍攻擊技能，遊戲設定技能允許打空氣
技能的選取距離是3，傷害範圍是2，那麼一個技能的有效落點就有25個座標
3個技能就是25*3=75個座標
然後敵人移動範圍是5且無不可通行路點，則可移動座標有（1+3+5+7+9）*2+11=61個
那麼有效行動組合就有75*61=4575個……
於是AI要運算4575種走法再選取最優解

所以才希望有比遍歷更效率的算法啊

Sion

AOE释放思路

技能伤害范围为2，应该指包含中心以及周围4点的，一个十字形的伤害吧？
如果友军的数目不是太多，可以这样（假设20个）
1、先绘制移动路径，记录下可以抵达的点。（一次绘制路径计算消耗）
2、每个友军加上它周围4个点（就是跟技能范围一样的图形）在这些点上测试技能伤害。测试之前先排除不
     可能释放技能的点。大概就是看技能释放点周围，根据技能射程划定的范围内，是否包含可以抵达的点。
     （计算次数为 20*5*3，其实可以根据距离先排除一些肯定够不到的目标。）
3、选择伤害量最高的行动即可。

电子最终龙

Sion 发表于 2013-8-1 20:39
AOE释放思路

技能伤害范围为2，应该指包含中心以及周围4点的，一个十字形的伤害吧？

選取有效目標為中心，傷害範圍為半徑的座標集，計算座標集中最優落點，然後以最優落點為中心計算有效移動座標，無有效移動座標則返回，排除最優落點重新搜索最優落點這樣？
唔……假設AI有3個射程3範圍2的技能，有效範圍內目標有10個，則需要模擬運算40*3=120次并進行排序，再進行最多120次的移動路點匹配
運算量確實少了，受教

PS：因為遊戲是半即時讀條，不考慮AI互相配合的話也沒有卡位不卡位的問題了。

Sion

电子最终龙 发表于 2013-8-1 19:43
選取有效目標為中心，傷害範圍為半徑的座標集，計算座標集中最優落點，然後以最優落點為中心計算有效移動 ...

计算伤害之前先计算是否可以对该点释放，最坏的情况每个技能释放点要遍历移动路径点 25 次。
可以根据你的需要来选择，通常就把路径点集按照移动的步数排序，优先尝试移动距离比较短的那些点。
只要可以释放技能，就终止尝试，记录当前路径点的坐标。
这样，先得到可以释放技能的点，然后再计算伤害，把<伤害、移动目标点、技能释放点>捆绑存储。
然后找出伤害最高的，同时就可以读取到移动的目标点与技能释放的坐标。

电子最终龙

Sion 发表于 2013-8-1 22:13
计算伤害之前先计算是否可以对该点释放，最坏的情况每个技能释放点要遍历移动路径点 25 次。
可以根据你 ...

如果 補刀 > 最大傷害 > 最近距離 這個優先等級呢？
那麼還是應該先做傷害模擬，再賦值選施放點集吧

小传子

我觉得SLG好多AI都大同小异，没什么比较特别的地方，我觉得应该加一个统一的“点杀” “团护”这样的分歧判断，利用多种AI结合的力量的话，AI的难度会提高好几个档次，也会让玩家觉得更有趣