这是一个创建于 551 天前的主题，其中的信息可能已经有所发展或是发生改变。
项目背景:github 上某不知名开源黄油
语言:python
目前算法:整体上依然是 goap 的思路，然后将世界变量作为条件随机场的条件参数，供 ai 决策自己要检索的目标，通过对数据结构做了优化，写了套简易的启发式检索，供 ai 决策出完整的行为链，同时由于游戏里 npc 很多(2800 个)，于是又通过近似检索，评分加权等思路，做了套蚁群优化，来降低 ai 的决策次数
目前成果:上诉这套东西都做完了，crf 的条件粗略几千个，角色属性纬度大几百个，写了套编辑器来随便增减目标，又大范围利用 chatgpt 做内容产出
瓶颈:性能是大问题，目前我个人能力已经找不到优化空间，除非对游戏设计做减法
需求:我想要进一步改进它，让 npc 看上去更像人，让调试变得更容易，让性能变得更好，更快，但是我自己肚子里没有墨水了，chatgpt 现在也只能对我放彩虹屁，我需要新的思路，感兴趣的话欢迎一起讨论撒
语言:python
目前算法:整体上依然是 goap 的思路，然后将世界变量作为条件随机场的条件参数，供 ai 决策自己要检索的目标，通过对数据结构做了优化，写了套简易的启发式检索，供 ai 决策出完整的行为链，同时由于游戏里 npc 很多(2800 个)，于是又通过近似检索，评分加权等思路，做了套蚁群优化，来降低 ai 的决策次数
目前成果:上诉这套东西都做完了，crf 的条件粗略几千个，角色属性纬度大几百个，写了套编辑器来随便增减目标，又大范围利用 chatgpt 做内容产出
瓶颈:性能是大问题，目前我个人能力已经找不到优化空间，除非对游戏设计做减法
需求:我想要进一步改进它，让 npc 看上去更像人，让调试变得更容易，让性能变得更好，更快，但是我自己肚子里没有墨水了，chatgpt 现在也只能对我放彩虹屁，我需要新的思路，感兴趣的话欢迎一起讨论撒
第 1 条附言 · 2023-05-24 13:51:49 +08:00
我今天想到，或许还可以从蚁群优化上继续优化，依然是蚁群优化的思路，我现在的设计是在每个角色身上留下了信息素，让角色之间做近似查找，并没有严格按照蚁群优化的思想，用信息素构建路径，我刚才想到，或许可以进一步的进行优化，主要优化点有二，一是角色在决定不模仿和自己近似的角色，或者无法模仿和自己近似的角色时，进一步，通过角色的性格来投骰子，决定是否模仿其他角色，同时，以上一步中留下的信息素作为基准，得到每个角色被模仿的概率，最后连这个也不模仿了，再去自己检索到底该干啥，其二是，在角色检索目标，向下递归满足条件的目标时，查别的角色在这一步的选择，判断是否要模仿，能不能模仿，不成再自己检索
 |
1
Eddition 2023-05-22 07:29:13 +08:00 via iPhone
差异化指令集
|
 |
2
nekoharuya OP @Eddition 可以详细解释下吗，请原谅我没看懂
|
 |
3
txhwind 2023-05-22 10:17:48 +08:00
多线程、换 C
|
 |
4
antonius 2023-05-22 10:21:55 +08:00
这么多 agent ，看你 tick 的频率，如果比较高，GOAP 开销还是不小的。优化方法也很多，不过实际情况多采用针对性优化，建议做分层(hierarchical)，区分大目标小目标，缩减状态空间。或者 time-slicing ，或者降低 GOAP 搜索频率。
还可以采用混合架构，用 Behavior Tree 或者(H)FSM 做局部优化，提高性能。 |
 |
5
thorneLiu 2023-05-22 10:48:58 +08:00 via Android
搞性能 估计得上 GPU 计算
|
 |
6
thetbw 2023-05-22 11:58:27 +08:00
以前就觉得，现在 ai 技术要是做到游戏中，沉浸感得多强
|
|
7
nekoharuya OP @antonius 时间切片之类的在行为跨度短的时候有效，但是第一次启动时，所有角色都在查找可用的目标，其实也是一个比较大的瓶颈，玩家选择睡觉这种操作的时候，步进跨度比较大，要卡很久，也是常受玩家诟病的，设计上，其实是选择了状态机和时间切片耦合的办法，ai 找到目标后就进入了状态机，状态结束后才重新查找，另外蚁群优化也是降低查询次数的方案，找到了近邻角色以后，按相似度和信息素作为决定是否模仿对方的行为的概率
|
|
8
nekoharuya OP @txhwind 在这套设计里，作为核心，也就是性能瓶颈最大的 crf ，和对象化的数据结构强耦合，详细来说，我通过装饰器，注册了几千个验证世界状态的函数，它们各自之间，又有一些逻辑处理，同时也必须非向量化的处理角色的属性数据，各种状态验证中，验证角色之间的社交关系，好感度，当前位置，历史状态的也不在少数，我目前应该是没有能力完成向 c 的迁移
|
|
9
nekoharuya OP @thorneLiu 主要是 gpu 只能解决特定算法问题，参考上面我对 txhwind 的回复
|
 |
10
kepenj 2023-05-22 12:50:18 +08:00
AI 这块不是很懂，纯游戏开发角度，同步并发 2800 个 NPC ，且希望行为树各不相同，不算不同层级 BTree 里面可能发起的查询分支数不同，光本地性能消耗就很可观了，还不算其他脚本的挂载。所以从源头设计控制岂不是最优，毕竟游戏还是讲究的体验（同屏 2800 小黄油...刺激...话说地址能分享一手么...
|
|
11
nekoharuya OP @kepenj github 上搜 dieloli 就是了，帖子里说的算法自然是成品，这个游戏我做了五年了
|
 |
12
aegon466 2023-05-22 13:34:49 +08:00
对技术和游戏内容都比较有兴趣 有群吗
|
|
13
thorneLiu 2023-05-22 14:02:22 +08:00 via Android
@nekoharuya 游戏这方面我确实不懂 我只看到 AI+性能 我以为是我们做的 AI 训练推理工程化相关的内容
我们这边基本就是 c++加异构的计算来提升性能 |
|
14
antonius 2023-05-22 14:11:24 +08:00
@nekoharuya 具体问题具体分析，做一次完整的性能数据采集，看看瓶颈在哪些地方。agent 较多可以考虑 AI 方面的 LOD ，不是所有 agent 都要完全执行。也可以试试 utility-based ai system 。
除此之外，你可能要考虑优化一下底层架构，例如游戏运行时性能，解决 Python 本身的性能问题。不太了解 Python 我就不乱说了。 性能优化是个痛苦的过程，为了性能可能要会代码搞得没那么优雅，还有不少妥协以及 hack 手法。 |
|
15
nekoharuya OP @antonius PreCondition 这块的处理也是有的，核心是通过实现建立好的 hash 表，从 Goal 去查它绑定的 PreCondition ，当 PreCondition 不能满足的时候，又通过事先建立好的 hash 表，从 Effect 去反查能够满足他的 Goal ，只有一个 Goal 能满足的时候就返回它，有多个的时候就通过权重抽一个，某个 Goal 有某个 PreCondition 不能满足的时候，就又递归一层，通过对数据结构的调整，以及对数据进行预热，来优化这块的时间复杂度，尽可能的做到 O1 ，至少我刚才回忆了一下，只有一两处实在绕不开的地方是 On ，底层架构的话，我已经做了非常多的优化，我的能力所限，现在要继续优化也完全找不到新的思路
|
 |
16
zglzy 2023-05-22 15:20:52 +08:00
有个不成熟的想法，有没有可能把计算密集的部分放在其他语言里写，做成一个 Python 包把接口提供出来就好？
比如 C++的 PyBind 或者用 Rust 的 PyO3 （这个我自己试过体验很好，开多线程并行也很方便） |
|
17
nekoharuya OP @antonius utility-based ai system 实质上是被包含在这个算法的条件随机场(Conditional Random Field)中了，效用(utility)，即 crf 中，验证函数通过世界变量获取到的条件权重，在人类的思考过程中，并不总是选择最优策略，但总的来说，人类总是更倾向于更有利的选择，所以这里做了个随机场来实现这一点，权重越大，选择对应目标的概率就越大
|
|
18
nekoharuya OP @zglzy 其实有尝试过，但是，数据传递和数据类型转换的成本相当的高，再者就是高度耦合的问题，详看我在 8 楼的回复
|
|
19
antonius 2023-05-22 15:43:58 +08:00
如果你觉得没法再优化，那就做一次 profiling ，看看瓶颈在哪些地方。
|
|
20
nekoharuya OP @antonius 倒也没有在虚空优化，火焰图之类的东西有在用，print 也打得多，各有优缺吧吧，但是常规的手段只能排查一些明显的瓶颈，通常也通过预热数据来解决了，比如游戏中场景树相当复杂，节点到节点之间的移动找不到什么有效的算法，最后选择上数据预热，例如在 github 的流水线中打包的时候，就把所有可能的，结果到节点之间的移动的最短路线创建好，比起死磕这块，不过直接从算法上完全避免，
|
|
21
thorneLiu 2023-05-22 16:09:01 +08:00 via Android
看下来 讲性能提升是不是换语言更立竿见影？
c/cpp 额 要么 rust |
|
22
nekoharuya OP @thorneLiu 几个方面，一则这个项目开发了五年，数据结构之类的设计上和 python 强耦合，利用了大量的 python 的特性和设计思想，另一方面，python 的生态还是可以的，我用了许多三方库来解决问题，社区的拖拉机还是很可以的，比如用 numpy 实现，以 value 作为随机区间，随机选择一个 key ，比起我直接拿 python 写二分法，要快 40%，又或者我写的蚁群算法依赖近似度检索，chatgpt 给我挑了一堆库多半都是炼丹来实现的，我直接拿来就用，不用去关心它的设计原理，
|
 |
23
csulyb 2023-05-22 17:21:22 +08:00
耗时算法用 c++做吧，以前做游戏基本就是套一个行为树来实现，没有其他办法，穷举法倒也是一个办法。
从我多年游戏来看，NPC 的智能化程度，并不影响用户的对游戏的体验，之前做游戏游戏大部分是专注于图形相关的，ai 这块基本上不会太复杂。 |
|
24
nekoharuya OP @csulyb 没有什么纯算法上的性能瓶颈，有数学计算的硬性需求的，大部分都通过各种库解决了，例如随机算法和检索近似对象，还有寻路，主要的性能瓶颈在硬性的计算量上，只能从整个 ai 算法的框架上做优化来规避，比如通过基本案例推导，让 npc 之间相互模仿行为，npc 每次要检索的行为树就降低了一大截，俺这个是纯文字沙盒游戏，重心就在 ai 上，我清楚这技术也是屠龙技，我搬砖多年，完全用不到，但是它酷啊，整个游戏行业，从各种 3a 到各路独立游戏，不管是什么模拟人生钢铁雄心绿帽之王，还是什么 cdda ，矮人要塞，环世界，哪个 ai 有我这个高级，你说是吧
|
|
25
zglzy 2023-05-22 18:30:03 +08:00
主要是换语言就可以有免费的性能提升，我本来还想建议试试换到 PyPy ，但是好像没有看到过什么成熟的从 CPython 迁移到 PyPy 的例子就还是算了
|
|
26
nekoharuya OP @zglzy 项目大了，积重难返，其实也试过走 nuitka 之类的东西，把 python 转成 c ，再编译，但是有几个问题，一是现在项目和 python 耦合性太高了，不说那些复杂的语法糖，光是一个推导式，它都搞不定，更别提对各种 c 库的兼容，那些走 jit 的方案也是同理
|
 |
27
exch4nge 2023-05-22 19:54:29 +08:00
不换语言的话，那就先上多线程吧
|
|
28
nekoharuya OP @exch4nge python 的缺陷在这里，它的多线程是是在单进程中运行的，然后 cpu 在各个线程中不断切换，于是就有了一个问题，切换也是要时间的，在这种 cpu 密集的场景下，多线程将列表处理完一遍的时间，比单线程遍历完一遍，需要更多的时间，多进程的话，进程间通信的开销更加巨大，特别是在没有 fork 的 windows 上，要计算的数据还得单独传递过去，在数据体积十分庞大的情景(特指俺这游戏)，这是相当高昂的开支，另外就是沙盒游戏的通病，角色数据只能逐个迭代，不能分开算……不过，目前游戏里还是有一些多线程处理，比如 ui 的渲染在单独的线程里，也有多进程的应用，比如用子进程实现了完全不影响玩家操作的自动存档，又或者做近似对象检索的库，它建立索引的过程是多核的
|
 |
29
ac23 2023-05-23 09:35:12 +08:00
优秀~
|
|
30
ac23 2023-05-23 09:46:31 +08:00
大佬，给个 GitHub 地址呀
|
 |
31
L1shen 2023-05-23 13:52:28 +08:00
|
|
32
nekoharuya OP @L1shen 这个昨天也正好刷到，这类方案其实之前考虑过，最后还是放弃了，参考我在第 8 ，18 和 20 楼的回复
|
 |
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 策略吗？ |
|
34
nekoharuya OP @huskar 强化学习是一个方向，但是和俺这游戏设计理念不同，难点在于奖励机制不好设计，因为在这个游戏中，npc 没有一个明确的，统一的，游戏目标，npc 每个目标都是它自己顺着世界状态，推出来的，
|
|
35
nekoharuya OP @huskar 除了上诉的奖励机制外，世界状态通常是计算出来的，而不是可以直接查值的，例如小明有没有喜欢的人，小红和小明的性格是否合拍，也就是说，上了强化学习，也并不能减少这块的硬性计算量
|
Select Language