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

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

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

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

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

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

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

    如果是有明显的热点可以试试用这种方法
    nekoharuya
        32
    nekoharuya  
    OP
       286 天前
    @L1shen 这个昨天也正好刷到,这类方案其实之前考虑过,最后还是放弃了,参考我在第 8 ,18 和 20 楼的回复
    huskar
        33
    huskar  
       286 天前
    很感兴趣,搜了下 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
       286 天前
    @huskar 强化学习是一个方向,但是和俺这游戏设计理念不同,难点在于奖励机制不好设计,因为在这个游戏中,npc 没有一个明确的,统一的,游戏目标,npc 每个目标都是它自己顺着世界状态,推出来的,
    nekoharuya
        35
    nekoharuya  
    OP
       286 天前
    @huskar 除了上诉的奖励机制外,世界状态通常是计算出来的,而不是可以直接查值的,例如小明有没有喜欢的人,小红和小明的性格是否合拍,也就是说,上了强化学习,也并不能减少这块的硬性计算量
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5560 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 39ms · UTC 08:15 · PVG 16:15 · LAX 00:15 · JFK 03:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.