开启辅助访问
 找回密码
 注册帐号

扫一扫,访问微社区

开发者专栏

关注:2006

当前位置:游戏蛮牛 技术专区 开发者专栏

__________________________________________________________________________________
开发者干货区版块规则:

  1、文章必须是图文形式。(至少2幅图)
      2、文章字数必须保持在1500字节以上。(编辑器右下角有字数检查)
      3、本版块只支持在游戏蛮牛原创首发,不支持转载。
      4、本版块回复不得无意义,如:顶、呵呵、不错......【真的会扣分的哦】
      5、......
__________________________________________________________________________________
查看: 1448|回复: 15

[蛮牛干货] 如何将influence map的机制融入到当前较火的unity寻路插件A* pathfinding project里

[复制链接]  [移动端链接]
排名
3
昨日变化

5733

主题

6219

帖子

2万

积分

Rank: 16

UID
1231
好友
185
蛮牛币
14289
威望
30
注册时间
2013-7-29
在线时间
2869 小时
最后登录
2017-12-13

社区QQ达人活力之星原创精华达人突出贡献奖财富之证游戏蛮牛QQ群会员蛮牛妹VIP

发表于 2017-8-4 12:21:29 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?注册帐号

x

最近一阶段重温了一些关于游戏人工智能方面的书籍。 加强了对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.png

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

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

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

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

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

最后的大体效果:
2.gif

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

3.gif

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

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

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值。

[C#] 纯文本查看 复制代码
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 值。

[C#] 纯文本查看 复制代码
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的路径。

[C#] 纯文本查看 复制代码
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#] 纯文本查看 复制代码
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#] 纯文本查看 复制代码
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脚本。
来源:RonTang

跟我念“站长妹纸萌萌哒!”我说站长,你说YO!爱你们么么哒~
回复

使用道具 举报

排名
33471
昨日变化
28

0

主题

13

帖子

30

积分

Rank: 1

UID
232491
好友
0
蛮牛币
7
威望
0
注册时间
2017-7-16
在线时间
11 小时
最后登录
2017-8-13
发表于 2017-8-4 13:55:34 | 显示全部楼层
我就看一看

回复

使用道具 举报

排名
26399
昨日变化
30

0

主题

10

帖子

32

积分

Rank: 1

UID
72230
好友
0
蛮牛币
41
威望
0
注册时间
2015-1-30
在线时间
14 小时
最后登录
2017-12-12
QQ
发表于 2017-8-4 17:39:10 | 显示全部楼层
好厲害 我來研究研究

回复 支持 反对

使用道具 举报

4四处流浪
352/500
排名
24303
昨日变化
18

0

主题

149

帖子

352

积分

Rank: 4

UID
221429
好友
0
蛮牛币
102
威望
0
注册时间
2017-5-9
在线时间
192 小时
最后登录
2017-12-14
发表于 2017-8-5 05:47:21 | 显示全部楼层
thank you for sharing post

回复 支持 反对

使用道具 举报

4四处流浪
497/500
排名
5330
昨日变化
3

1

主题

126

帖子

497

积分

Rank: 4

UID
233944
好友
0
蛮牛币
1275
威望
0
注册时间
2017-7-24
在线时间
164 小时
最后登录
2017-12-12
发表于 2017-8-7 08:57:57 | 显示全部楼层
我就是来看看 溜达一圈

回复 支持 反对

使用道具 举报

7日久生情
3282/5000
排名
4913
昨日变化
21

4

主题

2740

帖子

3282

积分

Rank: 7Rank: 7Rank: 7Rank: 7

UID
209186
好友
5
蛮牛币
3792
威望
0
注册时间
2017-3-1
在线时间
308 小时
最后登录
2017-12-14
发表于 2017-8-7 09:31:02 | 显示全部楼层
得好好的学习一下

回复 支持 反对

使用道具 举报

5熟悉之中
729/1000
排名
4228
昨日变化
19

1

主题

282

帖子

729

积分

Rank: 5Rank: 5

UID
122160
好友
0
蛮牛币
1339
威望
0
注册时间
2015-9-10
在线时间
174 小时
最后登录
2017-12-13
发表于 2017-8-7 09:35:24 | 显示全部楼层
感谢分享
[发帖际遇]: Vincher 发帖时在路边捡到 1 蛮牛币,偷偷放进了口袋. 幸运榜 / 衰神榜

回复

使用道具 举报

7日久生情
2024/5000
排名
1452
昨日变化
5

9

主题

745

帖子

2024

积分

Rank: 7Rank: 7Rank: 7Rank: 7

UID
68430
好友
3
蛮牛币
7595
威望
0
注册时间
2015-1-14
在线时间
534 小时
最后登录
2017-12-13
发表于 2017-8-7 10:17:58 | 显示全部楼层
A* pathfinding project  这东西,我一致想问~~对于帧同步的考虑,它是否可行?

回复 支持 反对

使用道具 举报

5熟悉之中
550/1000
排名
4938
昨日变化
4

3

主题

104

帖子

550

积分

Rank: 5Rank: 5

UID
156228
好友
0
蛮牛币
1509
威望
0
注册时间
2016-7-11
在线时间
197 小时
最后登录
2017-12-12

七夕浪漫情人

发表于 2017-8-7 16:28:03 | 显示全部楼层
好厉害,这个必须mark一下,找时间学习学习

回复 支持 反对

使用道具 举报

5熟悉之中
759/1000
排名
8021
昨日变化
9

2

主题

516

帖子

759

积分

Rank: 5Rank: 5

UID
220880
好友
7
蛮牛币
766
威望
0
注册时间
2017-5-6
在线时间
123 小时
最后登录
2017-11-3
发表于 2017-8-7 21:12:20 | 显示全部楼层
学习一下
[发帖际遇]: 香蕉大魔王 乐于助人,奖励 3 蛮牛币. 幸运榜 / 衰神榜

回复

使用道具 举报

3偶尔光临
287/300
排名
5582
昨日变化
4

2

主题

36

帖子

287

积分

Rank: 3Rank: 3Rank: 3

UID
43901
好友
0
蛮牛币
386
威望
0
注册时间
2014-9-6
在线时间
55 小时
最后登录
2017-11-3
发表于 2017-8-8 09:20:32 | 显示全部楼层
好厲害 我來研究研究
[发帖际遇]: 一个袋子砸在了 sun_yong 头上,sun_yong 赚了 1 蛮牛币. 幸运榜 / 衰神榜

回复 支持 反对

使用道具 举报

排名
16817
昨日变化
13

0

主题

31

帖子

90

积分

Rank: 2Rank: 2

UID
228660
好友
1
蛮牛币
85
威望
0
注册时间
2017-6-26
在线时间
31 小时
最后登录
2017-9-19
发表于 2017-8-8 09:20:45 | 显示全部楼层
感觉十分强大

回复

使用道具 举报

5熟悉之中
535/1000
排名
4981
昨日变化
6

1

主题

99

帖子

535

积分

Rank: 5Rank: 5

UID
209909
好友
0
蛮牛币
467
威望
0
注册时间
2017-3-4
在线时间
211 小时
最后登录
2017-12-11
发表于 2017-8-10 10:38:35 | 显示全部楼层
ddddddddddddd

回复

使用道具 举报

4四处流浪
424/500
排名
6490
昨日变化
9

0

主题

74

帖子

424

积分

Rank: 4

UID
25142
好友
0
蛮牛币
460
威望
0
注册时间
2014-5-15
在线时间
190 小时
最后登录
2017-12-4
发表于 2017-8-18 09:58:00 | 显示全部楼层
感覺真是太棒了!一定要好好的學習學習!感謝分享

回复 支持 反对

使用道具 举报

3偶尔光临
287/300
排名
9974
昨日变化
8

0

主题

82

帖子

287

积分

Rank: 3Rank: 3Rank: 3

UID
186767
好友
1
蛮牛币
182
威望
0
注册时间
2016-12-29
在线时间
123 小时
最后登录
2017-11-13
发表于 2017-9-7 14:24:10 | 显示全部楼层
厉害了!!!

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册帐号

本版积分规则

快速回复 返回顶部 返回列表