Unity寻路软件A* pathfinding project加入influence map机制的方式 VR资源

清风 2017-08-07 11:39:34

最近一阶段重温了一些关于游戏人工智能方面的书籍。 加强了对influence map的认知。想要亲自动手实现一下。

正如文章标题所示,这篇文章讲的是:如何将influence map的机制融入到当前较火的unity寻路插件A* pathfinding project里。

先科普一下Influence Map基本概念:

influence map中文名:势力图或影响图。以下称势力图。 势力图是基于空间的,某些空间归属A,另外一些空间归属B,等等。

把问题规模缩小到一场游戏战役,每个兵种单位都占据并影响着一定的空间,且相同势力的单位对同一空间的影响可以叠加,影响值随传播距离递减。

势力图除了告诉我们某块空间的归属之外,还能告诉我们什么呢?

1,进攻方,可以根据势力图选择率先攻击敌人薄弱的地方.防御方,可以根据势力图选择一个较为安全的撤退地点。

2,进一步,统计分析,比如采取某种战略之后,观察势力图变化,可以分析之前战略效果。

3,更进一步,通过对一段时间的势力图进行对比,可以大致预测敌军的部署动向。

实现InfluenceMap的要点

1,定义各单位的势力值传播范围,形状,特性(这是Gameplay)由于每个兵种的特性和能力值不同,故每个兵种单位的影响半径与程度不尽相同。

比如:一个坦克可以影响3km之内空间,3km之内都保持较高的影响。而一个机枪兵只能影响1km以内的空间,并且超出500m之后,士兵的影响十分微弱。

坦克相比机枪兵更具影响力,所以想要抵消掉坦克的影响,我们可能需要更多的机枪兵与之对抗。这些数值根据具体的游戏逻辑来设定。

2,实现传播算法,以什么样的方式传播,各势力影响值得叠加逻辑。

3,实现衰减算法,以什么样的方式衰减,常见如影响随距离线性衰减。

本文使用的算法

1,确定传播区域,获取传播区域内node,从center node开始以广度优先遍历区域内node,更新influence值。

2,influence值随传播距离线性衰减。

这是最简单的方法,还有一些提高性能的方法,有兴趣同学可以google之。

寻路与InfluenceMap结合

通过以上的总结,我们已经知道了势力图对于战略的作用。那么对于一般的游戏,我们是否用的上呢?

我现在的想法是,Influence map可以和寻路系统进行融合。比如,NPC在寻路的时候,不是选择一条最短的路径,而是选择一条最安全的路径。

只需想象一下即可,我们需要到达A点,但最短路径上有一个敌方炮塔,我们无法对抗炮塔的攻击,那么我们需要舍近求远,绕道一个炮塔无法攻击的地点,最终到达A点。

 
 

截图体现了我们之前总结出的规律:

1,影响的传播,红色区域乃是影响的传播范围。

2,影响的衰减,随着远离中心区域,红色逐渐变浅。

3,障碍物会阻碍影响的传播。

4,寻路小机器人,寻路时试图躲避高危的红色区域。

最后的大体效果:
 
 

寻路机器人会躲避敌方静止的机器人,并且双方相互影响。

 

相关修改文件,有兴趣朋友可以继续研究

编辑器扩展涉及到的文件如下:

Base.cs  AStarPath.cs  AStarPathEditor.cs  astarclassess.cs   核心代码 Color NodeColor (GraphNode node, PathHandler data)

势力图的逻辑涉及到的文件如下:

astarclassess.cs          InfluenceUpdateObject这是一个新的类,表示那部分导航图需要更新。 可参考GraphUpdateObject

GridNode.cs / GraphNode.cs   添加node的influence信息。

GridGenerator.cs                         添加node的influence信息更新逻辑。

Seeker.cs                                      添加使用AInfluencePath寻路的逻辑。

AInfluencePath.cs         AInfluencePath : ABPath这是一个新的类,用A*算法求取的influence路径。

需要重定义public override uint GetTraversalCost (GraphNode node)

最近更新了一些细节:

主要优化了性能。因为A* pathfinding project 使用多线程。所以,在更新graph的Influence信息时,需要blockpathfinding thread.否则会出现寻路异常。

在更新完地图后 unblock pathfinding thread,为了防止频繁的block and unblock pathfinding thread,新建一个更新队列,批处理多个agent的更新请求。

如果有需要更新的Influence请求,就会请求block pathfinding thread,但该函数不会一直等待而是立即返回,下一帧查看pathfinding thread是否block。

如果后面某一帧 pathfinding thread block 那么立即批处理更新队列中的请求。 我们可以设置每帧更新请求数量的最大值,以免导致某帧会耗时过长。

没有位置和信息变化的agent不需要请求刷新Influence信息,并且同一个agent新的Influence信息会覆盖后面的信息。这样可以保证queue不会过度膨胀。

 
相关代码:
InfluenceUpdateObject 描述更新区域,更新势力,以及后续还原influence值。
 
 
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class InfluenceUpdateObject
    {
        public Bounds bounds;
        public List<GraphNode> changedNodes;
        public float deltaInfluence;
        public AInfluencePath.Faction faction;
        private List<float> backupData;
 
        public InfluenceUpdateObject(Bounds b, uint delta,Pathfinding.AInfluencePath.Faction f){
            this.bounds = b;
            this.deltaInfluence = delta;
            this.faction = f;
        }
        public virtual void WillUpdateNode (InfluenceNode node) {
            if ( node != null) {
                if (changedNodes == null) { changedNodes = ListPool<GraphNode>.Claim(); backupData = ListPool<float>.Claim(); }
                changedNodes.Add(node.node);
                backupData.Add(node.deltaInfluence);
 
            }
        }
 
        public virtual void RevertFromBackup () {
             
                if (changedNodes == null) return;
 
                 
                for (int i = 0; i < changedNodes.Count; i++) {
 
                  if (faction == AInfluencePath.Faction.BLACK) {
                      changedNodes [i].influenceOfBlack -= backupData [i];
                      if (changedNodes [i].influenceOfBlack < 0.01)
                          changedNodes [i].influenceOfBlack = 0;
                  }
                  if (faction == AInfluencePath.Faction.WHITE) {
                      changedNodes [i].influenceOfWhite -= backupData [i];
                      if (changedNodes [i].influenceOfWhite < 0.01)
                          changedNodes [i].influenceOfWhite = 0;
                 }
                     
                }
                 
                ListPool<GraphNode>.Release(changedNodes);
                ListPool<float>.Release(backupData);
                changedNodes = null;
            }
 
    }
InfluenceUpdater 该类负责更新Navgraph的influence 值。
 
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using Pathfinding;
 
public class InfluenceUpdater : MonoBehaviour {
 
    private Queue<InfluenceUpdateObject> m_queue;
    public uint maxHandleCount;
    public void AddWorkItem(InfluenceUpdateObject o){
        if(!m_queue.Contains(o))
            m_queue.Enqueue (o);
    }
    private void ProcessWorkItems(){
     
        if (m_queue.Count == 0)
            return;
        AstarPath.active.BlockPathQueueNotWait ();
        if (!AstarPath.active.IsAllPathThreadBlocked ())
            return;
        AstarPath.active.ReturnPaths (false);
        uint count = 0;
        while (m_queue.Count > 0 && count < maxHandleCount) {
             
         
 
            InfluenceUpdateObject iuo = m_queue.Dequeue ();
            foreach (IUpdatableGraph g in AstarPath.active.astarData.GetUpdateableGraphs()) {
                GridGraph gr = g as GridGraph;
                gr.UpdateInfluenceInBounds (iuo);
            }
            count++;
        }
 
         AstarPath.active.FlushWorkItems();
    }
 
    void Awake(){
        if(m_queue == null)
            m_queue = new Queue<InfluenceUpdateObject> ();
    }
    void LateUpdate(){
        ProcessWorkItems ();
    }
}
AInfluencePath 该类用来表示使用influence 作为cost的路径。
 
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using UnityEngine;
 
namespace Pathfinding
{
    public class AInfluencePath : ABPath
    {
         
        public enum Faction {BLACK,WHITE};
        private Faction faction;
        public AInfluencePath ()
        {
        }
        public static AInfluencePath Construct (Vector3 start, Vector3 end, OnPathDelegate callback = null,Faction f = Faction.BLACK) {
            var p = PathPool.GetPath<AInfluencePath>();
            p.Setup(start, end, callback);
            p.faction = f;
            return p;
        }
 
        public override uint GetTraversalCost (GraphNode node) {
            GridNode gNode = node as GridNode;
            if (gNode != null) {
                if (AInfluencePath.Faction.BLACK == faction)
                    return gNode.influenceOfWhite <= gNode.influenceOfBlack? 0 : (uint)(gNode.influenceOfWhite - gNode.influenceOfBlack);
                if (AInfluencePath.Faction.WHITE == faction)
                    return gNode.influenceOfBlack <= gNode.influenceOfWhite ? 0 :(uint)( gNode.influenceOfBlack - gNode.influenceOfWhite);
            }
            return 0;
        }
    }
}
Base.cs 在编辑模式下设置graphNode的颜色
 
[C#] 纯文本查看 复制代码
 
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public virtual Color NodeColor (GraphNode node, PathHandler data) {
            Color c = AstarColor.NodeConnection;
 
            switch (AstarPath.active.debugMode) {
            case GraphDebugMode.Areas:
                c = AstarColor.GetAreaColor(node.Area);
                break;
            case GraphDebugMode.Penalty:
                c = Color.Lerp(AstarColor.ConnectionLowLerp, AstarColor.ConnectionHighLerp, ((float)node.Penalty-AstarPath.active.debugFloor) / (AstarPath.active.debugRoof-AstarPath.active.debugFloor));
                break;
            case GraphDebugMode.Tags:
                c = AstarColor.GetAreaColor(node.Tag);
                break;
            case GraphDebugMode.Influence:
                if (Mathf.Abs(node.influenceOfBlack - node.influenceOfWhite) <= 0.00001)
                    c = new Color (1, 1, 1);
                else {
                    if (node.influenceOfBlack > node.influenceOfWhite) {
                        c = Color.Lerp(AstarColor.ConnectionLowRedLerp, AstarColor.ConnectionHighRedLerp, (Mathf.Abs(node.influenceOfBlack - node.influenceOfWhite)-AstarPath.active.debugFloor) / (AstarPath.active.debugRoof-AstarPath.active.debugFloor));
                    }
                    if (node.influenceOfBlack < node.influenceOfWhite) {
                        c = Color.Lerp(AstarColor.ConnectionLowGreenLerp, AstarColor.ConnectionHighGreenLerp, (Mathf.Abs(node.influenceOfBlack - node.influenceOfWhite)-AstarPath.active.debugFloor) / (AstarPath.active.debugRoof-AstarPath.active.debugFloor));
                    }
                }
                break;
            default:
                if (data == null) return AstarColor.NodeConnection;
 
                PathNode nodeR = data.GetPathNode(node);
 
                switch (AstarPath.active.debugMode) {
                case GraphDebugMode.G:
                    c = Color.Lerp(AstarColor.ConnectionLowLerp, AstarColor.ConnectionHighLerp, ((float)nodeR.G-AstarPath.active.debugFloor) / (AstarPath.active.debugRoof-AstarPath.active.debugFloor));
                    break;
                case GraphDebugMode.H:
                    c = Color.Lerp(AstarColor.ConnectionLowLerp, AstarColor.ConnectionHighLerp, ((float)nodeR.H-AstarPath.active.debugFloor) / (AstarPath.active.debugRoof-AstarPath.active.debugFloor));
                    break;
                case GraphDebugMode.F:
                    c = Color.Lerp(AstarColor.ConnectionLowLerp, AstarColor.ConnectionHighLerp, ((float)nodeR.F-AstarPath.active.debugFloor) / (AstarPath.active.debugRoof-AstarPath.active.debugFloor));
                    break;
                }
                break;
            }
 
            c.a *= 0.5F;
            return c;
        }
GridGenerators.cs  私有函数更新graph的influence值,为防止不断开辟内存和释放内存以及重复计算节点距离,采取了优化措施,影响了阅读性。
[C#] 纯文本查看 复制代码
 
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
private void UpdateInfluenceInternal(InfluenceUpdateObject o){
             
            var nodeCenter = GetNearest(o.bounds.center).node as GridNode;
            var radius = o.bounds.size.x <= o.bounds.size.z ? o.bounds.size.x / 2 : o.bounds.size.z / 2;
 
            nodeSet.Clear();
         
            var decay = o.deltaInfluence / radius;
 
            int popIndex = 0;
            int pushIndex = popIndex;
            if (nodeList.Count == 0) {
                nodeList.Add (new InfluenceNode (nodeCenter, o.deltaInfluence));
            } else {
                nodeList[pushIndex].node = nodeCenter;
                nodeList[pushIndex].deltaInfluence = o.deltaInfluence;
            }
 
            pushIndex++;
            while(popIndex < pushIndex)
            {
                 
                InfluenceNode iNode = nodeList[popIndex];
                popIndex++;
                GridNode curNode = iNode.node as GridNode;
                nodeSet.Add (curNode);
                o.WillUpdateNode (iNode);
                if (o.faction == AInfluencePath.Faction.BLACK) {
                    curNode.influenceOfBlack += iNode.deltaInfluence;
                }
                if (o.faction == AInfluencePath.Faction.WHITE) {
                    curNode.influenceOfWhite += iNode.deltaInfluence;               
                }
                     
 
                for (int i = 0; i < 8; i++) {
                     
                    if (curNode.GetConnectionInternal (i)) {
                        GridNode other = nodes [curNode.NodeInGridIndex + neighbourOffsets [i]];
 
                        if (other!= null && !nodeSet.Contains(other)) {
                             
                            if (o.bounds.Contains ((Vector3)other.position)) {
 
                                    var decayDis = 0.5f;
                                    if (i >= 4)
                                        decayDis = 0.7f;
                                                             
                                    float tmpDelta;
                                    if (iNode.deltaInfluence < decayDis * decay )
                                        tmpDelta = 0;
                                    else
                                        tmpDelta = iNode.deltaInfluence - (decayDis * decay );
 
                                    if (tmpDelta != 0) {
                                        if (nodeList.Count <= pushIndex) {
                                            nodeList.Add (new InfluenceNode(other,tmpDelta));
                                        }
                                        else{
                                            nodeList[pushIndex].node = other;
                                            nodeList[pushIndex].deltaInfluence = tmpDelta;
                                        }
 
                                        nodeSet.Add (other);
                                        pushIndex++;
                                    }
                                     
                            }
                        }
 
                    }
                }
                     
            }
 
 
        }
 
  上述为关键代码,要启用该功能,还需要自定义 Seeker.cs 以及 调用 Seeker的 AgentAI脚本。
99VR视界二维码
热门推荐
Hot Recommended
在线客服