V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
nekoharuya
V2EX  ›  程序员

有人对游戏 ai 设计感兴趣无

  •  
  •   nekoharuya · 2023-05-22 07:22:34 +08:00 · 3824 次点击
    这是一个创建于 417 天前的主题,其中的信息可能已经有所发展或是发生改变。
    项目背景:github 上某不知名开源黄油
    语言:python
    目前算法:整体上依然是 goap 的思路,然后将世界变量作为条件随机场的条件参数,供 ai 决策自己要检索的目标,通过对数据结构做了优化,写了套简易的启发式检索,供 ai 决策出完整的行为链,同时由于游戏里 npc 很多(2800 个),于是又通过近似检索,评分加权等思路,做了套蚁群优化,来降低 ai 的决策次数
    目前成果:上诉这套东西都做完了,crf 的条件粗略几千个,角色属性纬度大几百个,写了套编辑器来随便增减目标,又大范围利用 chatgpt 做内容产出
    瓶颈:性能是大问题,目前我个人能力已经找不到优化空间,除非对游戏设计做减法
    需求:我想要进一步改进它,让 npc 看上去更像人,让调试变得更容易,让性能变得更好,更快,但是我自己肚子里没有墨水了,chatgpt 现在也只能对我放彩虹屁,我需要新的思路,感兴趣的话欢迎一起讨论撒
    第 1 条附言  ·  2023-05-24 13:51:49 +08:00
    我今天想到,或许还可以从蚁群优化上继续优化,依然是蚁群优化的思路,我现在的设计是在每个角色身上留下了信息素,让角色之间做近似查找,并没有严格按照蚁群优化的思想,用信息素构建路径,我刚才想到,或许可以进一步的进行优化,主要优化点有二,一是角色在决定不模仿和自己近似的角色,或者无法模仿和自己近似的角色时,进一步,通过角色的性格来投骰子,决定是否模仿其他角色,同时,以上一步中留下的信息素作为基准,得到每个角色被模仿的概率,最后连这个也不模仿了,再去自己检索到底该干啥,其二是,在角色检索目标,向下递归满足条件的目标时,查别的角色在这一步的选择,判断是否要模仿,能不能模仿,不成再自己检索
    35 条回复    2023-05-23 15:03:22 +08:00
    Eddition
        1
    Eddition  
       2023-05-22 07:29:13 +08:00 via iPhone
    差异化指令集
    nekoharuya
        2
    nekoharuya  
    OP
       2023-05-22 07:32:44 +08:00
    @Eddition 可以详细解释下吗,请原谅我没看懂
    txhwind
        3
    txhwind  
       2023-05-22 10:17:48 +08:00
    多线程、换 C
    antonius
        4
    antonius  
       2023-05-22 10:21:55 +08:00
    这么多 agent ,看你 tick 的频率,如果比较高,GOAP 开销还是不小的。优化方法也很多,不过实际情况多采用针对性优化,建议做分层(hierarchical),区分大目标小目标,缩减状态空间。或者 time-slicing ,或者降低 GOAP 搜索频率。

    还可以采用混合架构,用 Behavior Tree 或者(H)FSM 做局部优化,提高性能。
    thorneLiu
        5
    thorneLiu  
       2023-05-22 10:48:58 +08:00 via Android
    搞性能 估计得上 GPU 计算
    thetbw
        6
    thetbw  
       2023-05-22 11:58:27 +08:00
    以前就觉得,现在 ai 技术要是做到游戏中,沉浸感得多强
    nekoharuya
        7
    nekoharuya  
    OP
       2023-05-22 12:03:12 +08:00 via Android
    @antonius 时间切片之类的在行为跨度短的时候有效,但是第一次启动时,所有角色都在查找可用的目标,其实也是一个比较大的瓶颈,玩家选择睡觉这种操作的时候,步进跨度比较大,要卡很久,也是常受玩家诟病的,设计上,其实是选择了状态机和时间切片耦合的办法,ai 找到目标后就进入了状态机,状态结束后才重新查找,另外蚁群优化也是降低查询次数的方案,找到了近邻角色以后,按相似度和信息素作为决定是否模仿对方的行为的概率
    nekoharuya
        8
    nekoharuya  
    OP
       2023-05-22 12:07:32 +08:00 via Android
    @txhwind 在这套设计里,作为核心,也就是性能瓶颈最大的 crf ,和对象化的数据结构强耦合,详细来说,我通过装饰器,注册了几千个验证世界状态的函数,它们各自之间,又有一些逻辑处理,同时也必须非向量化的处理角色的属性数据,各种状态验证中,验证角色之间的社交关系,好感度,当前位置,历史状态的也不在少数,我目前应该是没有能力完成向 c 的迁移
    nekoharuya
        9
    nekoharuya  
    OP
       2023-05-22 12:13:30 +08:00 via Android
    @thorneLiu 主要是 gpu 只能解决特定算法问题,参考上面我对 txhwind 的回复
    kepenj
        10
    kepenj  
       2023-05-22 12:50:18 +08:00
    AI 这块不是很懂,纯游戏开发角度,同步并发 2800 个 NPC ,且希望行为树各不相同,不算不同层级 BTree 里面可能发起的查询分支数不同,光本地性能消耗就很可观了,还不算其他脚本的挂载。所以从源头设计控制岂不是最优,毕竟游戏还是讲究的体验(同屏 2800 小黄油...刺激...话说地址能分享一手么...
    nekoharuya
        11
    nekoharuya  
    OP
       2023-05-22 12:54:09 +08:00 via Android
    @kepenj github 上搜 dieloli 就是了,帖子里说的算法自然是成品,这个游戏我做了五年了
    aegon466
        12
    aegon466  
       2023-05-22 13:34:49 +08:00
    对技术和游戏内容都比较有兴趣 有群吗
    thorneLiu
        13
    thorneLiu  
       2023-05-22 14:02:22 +08:00 via Android
    @nekoharuya 游戏这方面我确实不懂 我只看到 AI+性能 我以为是我们做的 AI 训练推理工程化相关的内容
    我们这边基本就是 c++加异构的计算来提升性能
    antonius
        14
    antonius  
       2023-05-22 14:11:24 +08:00
    @nekoharuya 具体问题具体分析,做一次完整的性能数据采集,看看瓶颈在哪些地方。agent 较多可以考虑 AI 方面的 LOD ,不是所有 agent 都要完全执行。也可以试试 utility-based ai system 。

    除此之外,你可能要考虑优化一下底层架构,例如游戏运行时性能,解决 Python 本身的性能问题。不太了解 Python 我就不乱说了。

    性能优化是个痛苦的过程,为了性能可能要会代码搞得没那么优雅,还有不少妥协以及 hack 手法。
    nekoharuya
        15
    nekoharuya  
    OP
       2023-05-22 14:58:52 +08:00
    @antonius PreCondition 这块的处理也是有的,核心是通过实现建立好的 hash 表,从 Goal 去查它绑定的 PreCondition ,当 PreCondition 不能满足的时候,又通过事先建立好的 hash 表,从 Effect 去反查能够满足他的 Goal ,只有一个 Goal 能满足的时候就返回它,有多个的时候就通过权重抽一个,某个 Goal 有某个 PreCondition 不能满足的时候,就又递归一层,通过对数据结构的调整,以及对数据进行预热,来优化这块的时间复杂度,尽可能的做到 O1 ,至少我刚才回忆了一下,只有一两处实在绕不开的地方是 On ,底层架构的话,我已经做了非常多的优化,我的能力所限,现在要继续优化也完全找不到新的思路
    zglzy
        16
    zglzy  
       2023-05-22 15:20:52 +08:00
    有个不成熟的想法,有没有可能把计算密集的部分放在其他语言里写,做成一个 Python 包把接口提供出来就好?
    比如 C++的 PyBind
    或者用 Rust 的 PyO3 (这个我自己试过体验很好,开多线程并行也很方便)
    nekoharuya
        17
    nekoharuya  
    OP
       2023-05-22 15:23:54 +08:00
    @antonius utility-based ai system 实质上是被包含在这个算法的条件随机场(Conditional Random Field)中了,效用(utility),即 crf 中,验证函数通过世界变量获取到的条件权重,在人类的思考过程中,并不总是选择最优策略,但总的来说,人类总是更倾向于更有利的选择,所以这里做了个随机场来实现这一点,权重越大,选择对应目标的概率就越大
    nekoharuya
        18
    nekoharuya  
    OP
       2023-05-22 15:26:34 +08:00
    @zglzy 其实有尝试过,但是,数据传递和数据类型转换的成本相当的高,再者就是高度耦合的问题,详看我在 8 楼的回复
    antonius
        19
    antonius  
       2023-05-22 15:43:58 +08:00
    如果你觉得没法再优化,那就做一次 profiling ,看看瓶颈在哪些地方。
    nekoharuya
        20
    nekoharuya  
    OP
       2023-05-22 15:57:20 +08:00
    @antonius 倒也没有在虚空优化,火焰图之类的东西有在用,print 也打得多,各有优缺吧吧,但是常规的手段只能排查一些明显的瓶颈,通常也通过预热数据来解决了,比如游戏中场景树相当复杂,节点到节点之间的移动找不到什么有效的算法,最后选择上数据预热,例如在 github 的流水线中打包的时候,就把所有可能的,结果到节点之间的移动的最短路线创建好,比起死磕这块,不过直接从算法上完全避免,
    thorneLiu
        21
    thorneLiu  
       2023-05-22 16:09:01 +08:00 via Android
    看下来 讲性能提升是不是换语言更立竿见影?
    c/cpp 额 要么 rust
    nekoharuya
        22
    nekoharuya  
    OP
       2023-05-22 16:24:19 +08:00
    @thorneLiu 几个方面,一则这个项目开发了五年,数据结构之类的设计上和 python 强耦合,利用了大量的 python 的特性和设计思想,另一方面,python 的生态还是可以的,我用了许多三方库来解决问题,社区的拖拉机还是很可以的,比如用 numpy 实现,以 value 作为随机区间,随机选择一个 key ,比起我直接拿 python 写二分法,要快 40%,又或者我写的蚁群算法依赖近似度检索,chatgpt 给我挑了一堆库多半都是炼丹来实现的,我直接拿来就用,不用去关心它的设计原理,
    csulyb
        23
    csulyb  
       2023-05-22 17:21:22 +08:00
    耗时算法用 c++做吧,以前做游戏基本就是套一个行为树来实现,没有其他办法,穷举法倒也是一个办法。
    从我多年游戏来看,NPC 的智能化程度,并不影响用户的对游戏的体验,之前做游戏游戏大部分是专注于图形相关的,ai 这块基本上不会太复杂。
    nekoharuya
        24
    nekoharuya  
    OP
       2023-05-22 17:46:39 +08:00
    @csulyb 没有什么纯算法上的性能瓶颈,有数学计算的硬性需求的,大部分都通过各种库解决了,例如随机算法和检索近似对象,还有寻路,主要的性能瓶颈在硬性的计算量上,只能从整个 ai 算法的框架上做优化来规避,比如通过基本案例推导,让 npc 之间相互模仿行为,npc 每次要检索的行为树就降低了一大截,俺这个是纯文字沙盒游戏,重心就在 ai 上,我清楚这技术也是屠龙技,我搬砖多年,完全用不到,但是它酷啊,整个游戏行业,从各种 3a 到各路独立游戏,不管是什么模拟人生钢铁雄心绿帽之王,还是什么 cdda ,矮人要塞,环世界,哪个 ai 有我这个高级,你说是吧
    zglzy
        25
    zglzy  
       2023-05-22 18:30:03 +08:00
    主要是换语言就可以有免费的性能提升,我本来还想建议试试换到 PyPy ,但是好像没有看到过什么成熟的从 CPython 迁移到 PyPy 的例子就还是算了
    nekoharuya
        26
    nekoharuya  
    OP
       2023-05-22 19:24:55 +08:00 via Android
    @zglzy 项目大了,积重难返,其实也试过走 nuitka 之类的东西,把 python 转成 c ,再编译,但是有几个问题,一是现在项目和 python 耦合性太高了,不说那些复杂的语法糖,光是一个推导式,它都搞不定,更别提对各种 c 库的兼容,那些走 jit 的方案也是同理
    exch4nge
        27
    exch4nge  
       2023-05-22 19:54:29 +08:00
    不换语言的话,那就先上多线程吧
    nekoharuya
        28
    nekoharuya  
    OP
       2023-05-22 20:14:33 +08:00 via Android
    @exch4nge python 的缺陷在这里,它的多线程是是在单进程中运行的,然后 cpu 在各个线程中不断切换,于是就有了一个问题,切换也是要时间的,在这种 cpu 密集的场景下,多线程将列表处理完一遍的时间,比单线程遍历完一遍,需要更多的时间,多进程的话,进程间通信的开销更加巨大,特别是在没有 fork 的 windows 上,要计算的数据还得单独传递过去,在数据体积十分庞大的情景(特指俺这游戏),这是相当高昂的开支,另外就是沙盒游戏的通病,角色数据只能逐个迭代,不能分开算……不过,目前游戏里还是有一些多线程处理,比如 ui 的渲染在单独的线程里,也有多进程的应用,比如用子进程实现了完全不影响玩家操作的自动存档,又或者做近似对象检索的库,它建立索引的过程是多核的
    ac23
        29
    ac23  
       2023-05-23 09:35:12 +08:00
    优秀~
    ac23
        30
    ac23  
       2023-05-23 09:46:31 +08:00
    大佬,给个 GitHub 地址呀
    L1shen
        31
    L1shen  
       2023-05-23 13:52:28 +08:00
    今天还看到一个文章,用 rust 加速 python

    https://www.infoq.cn/article/DIt8eRMQd8mw1i3aV077

    如果是有明显的热点可以试试用这种方法
    nekoharuya
        32
    nekoharuya  
    OP
       2023-05-23 14:26:32 +08:00
    @L1shen 这个昨天也正好刷到,这类方案其实之前考虑过,最后还是放弃了,参考我在第 8 ,18 和 20 楼的回复
    huskar
        33
    huskar  
       2023-05-23 14:48:15 +08:00
    很感兴趣,搜了下 GOAP 感觉资料不是很多,楼主有没有介绍 GOAP 的博客?
    这篇介绍 GOAP 原理的博客 https://blog.csdn.net/LIQIANGEASTSUN/article/details/79132514 可以参考吗?

    我有做 ABM(agent-base model)模拟的经验,一开始也是用 python 结合 numpy 做,也尝试过用 cython 、mypyc 编译加速,但是用起来都有坑,最终还是改成编译语言了。感觉用 python 做计算密集还是不太行。abm 里 agent 的行为很简单,基本靠策略判断就能实现了,没有设计 ai 算法。

    另外楼主试过用强化学习实现 AI 策略吗?
    nekoharuya
        34
    nekoharuya  
    OP
       2023-05-23 14:59:58 +08:00
    @huskar 强化学习是一个方向,但是和俺这游戏设计理念不同,难点在于奖励机制不好设计,因为在这个游戏中,npc 没有一个明确的,统一的,游戏目标,npc 每个目标都是它自己顺着世界状态,推出来的,
    nekoharuya
        35
    nekoharuya  
    OP
       2023-05-23 15:03:22 +08:00
    @huskar 除了上诉的奖励机制外,世界状态通常是计算出来的,而不是可以直接查值的,例如小明有没有喜欢的人,小红和小明的性格是否合拍,也就是说,上了强化学习,也并不能减少这块的硬性计算量
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4392 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 09:56 · PVG 17:56 · LAX 02:56 · JFK 05:56
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.