编码冒险:蚂蚁与黏菌模拟

Coding Adventure: Ant and Slime Simulations

频道:Sebastian Lague · 时长:17:53 · 发布:2021-03-25 · 播放:2196539

在 YouTube 观看

简介

Sebastian Lague探索了一种受蚂蚁启发的算法,并使用计算着色器模拟了蚂蚁和黏菌的行为。两个模拟的源代码均可获取。

HN 为什么推荐

HN推荐它作为简单规则和计算着色器能产生什么效果的美丽示例,许多评论者受到启发。

让人想起编码可以多么美丽 — HN, 2024

计算机图形与渲染 · 创意编程与生成艺术

中文字幕节选

大家好,欢迎来到新一期的 Coding Adventures。今天我们将要尝试一些小小的蚂蚁和 黏菌模拟——但首先,我想请你 想象自己是一个商人,四处奔波 从一个城镇到另一个城镇,也许卖卖卷心菜。 所以你想找到一条路径,带你 穿过地图上的所有城镇,最后 以最短的距离回到家中。 这里有一些稍微有点令人困惑的代码,它 递归地生成这个问题的所有可能解, 而每一个解 都在这个函数里进行评估, 只需计算路径的长度, 如果它是我们目前找到的最优解,就把它保存下来。 那么对于这12个城镇,让我们试着运行 这个程序,它只需要大约一秒钟 就能算出结果,这就是你的最优卷心菜路线。 但现在假设这里冒出了一个新城镇, 你显然也想去那里看看。 那么,让我们再次运行程序。这一次,它花了很长时间才 算出答案。问题在于,唯一解的数量等于 点数减一的阶乘,再除以2。 所以3个城镇时,只有1个解, 但当我们达到区区20个城镇时, 就已经有大约60千万亿个可能的解了,简直离谱。 即使使用更复杂的算法, 找到最优解也非常昂贵,而且往往完全 不可行, 因此人们开发了许多有趣的技术 来快速找到接近完美的解。 在我稍微研究这些技术时, 我对其中一种方法特别感兴趣: 蚁群优化,它 的灵感来源于——你猜对了!——蚂蚁的觅食行为。 基本上,它的做法是:我们在其中一个城镇放置一只虚拟 蚂蚁,然后它需要 选择一个尚未访问过的新城镇前往。 蚂蚁会偏好附近的地方, 所以我将每个城镇的吸引力计算为 1除以距离,再取某个幂次。 这个幂次越高, 蚂蚁就越强烈地偏好附近的城镇。它 会随机做出最终决定,但 概率是根据那个吸引力值加权的。 那么让我们看看这只冒险的小蚂蚁执行任务吧。 现在它已经访问了每个城镇,我们可以回溯 它的脚步,看看它走过的路径。这 不是一条绝佳的路径,但解决整个 问题对一只小蚂蚁来说要求太高了,所以 让我们给它一些朋友来帮助探索。 当它们都完成旅程后,我们要做的是根据每条路径的好坏 给它们打分,这些分数就像 信息素轨迹一样,用来帮助引导下一轮蚂蚁。 所以最终每只蚂蚁选择路径中的下一个城镇 都是基于概率的,取决于 到该城镇的距离以及那里 信息素轨迹的强度。这样,每一批新 蚂蚁都会探索目前找到的最佳路径的随机变体, 任何改进 都会通过信息素得到强化。 让我们用之前那二十个城镇 来试试这个新方法,看看它是否 真的有效。我把模拟速度调慢了,这样我们 就能了解信息素轨迹 随时间的变化,而这里它已经稳定成一条看起来非常不错的路径。它 大约用了50只蚂蚁在一瞬间就找到了这个,相比之前 我们要面对的6个世纪,这是个不错的改进,尽管 当然,代价是我们无法保证 这实际上就是最优解。 只是为了好玩——请尽量控制住你们的兴奋——我要把这个 扩大到一百个城镇。这里我再次展示 信息素轨迹的慢速视图, 但也许同样有趣的是,如果我再次运行 它,改为显示蚂蚁目前找到的

HN 上的讨论

当时我也失去了编码的乐趣,但我重新找回了它。一个关键点是,如果不是绝对必要,就忽略学习新技术,专注于创造新事物。我想这一切都始于 Sebastian Lague 的视频,它提醒了我编码可以多么美丽。[ [VIDEO] ] — Risord, 2024-08
Sebastian Lague 制作了一个很棒的视频“蚂蚁和黏菌模拟”,探讨了寻路算法如何利用轨迹和基于梯度的信号来解决空间问题:[VIDEO] — Udo, 2023-05
说到蚂蚁和黏菌模拟,最近这个 Coding Adventures 视频真是让人脑洞大开:[VIDEO](尤其是大约 10 分钟开始的第二部分)。 — ehsankia, 2021-04
我喜欢蚂蚁并用代码复制它们的行为!你可能会喜欢这些项目:Sebastian Lague 的“编码冒险:蚂蚁和黏菌模拟”:视频:[VIDEO] 代码 [LINK] Pezzza's Work 的“C++ 蚂蚁模拟 1,第一种方法”:视频:[LINK] 代码:[LINK] — Nezteb, 2023-05
感谢分享!我还没看完整个视频,但肯定会看。最近因为这个视频对计算着色器产生了兴趣:[VIDEO],推荐给那些想看看计算着色器能做什么的人。 — Berg0X00, 2021-06

相关视频