普通视图

发现新文章,点击刷新页面。
昨天以前萤火之森

用 Rust 实现简单的光线追踪

作者 猫冬
2021年5月5日 08:48

学 Rust 十来天了,自己被这个语言惊艳到,就跟着教程 Ray Tracing in One Weekend 写了个很简陋的光线追踪示例练习,项目在 Latias94/rust_raytracing

学这门语言的时候,感觉就是上手容易遇到很多新概念,容易学不下去,跟编译器作斗争…不过作为一个还很新的系统编程语言,工具链如文章、包管理、格式化、编译器等很完善,官方教程很棒,社区也很活跃。

学 Rust 的契机其实是在 V2EX 上看到有人在纠结学 Go 还是 Rust,底下的帖子也有不少夸 Rust 语言的,因此自己也开始关注 Rust 语言。后来发现 Rust 的用武之地非常广,Github 上还能找到不少 Rust 做的游戏引擎,其中一部分主打 ECS 功能,例如:bevyengine/bevyRalith/hecs 等。

学习 Rust 语言,其实也是在了解一个现代化的语言该有的样子,了解 C++ 或其他语言部分设计上的不足,以及 Rust 是打算如何从根源解决这些问题的。这部分我作为一个初学者,不打算展开讲。大家有空可以了解一下 Rust 语言,看看官方的教程《Rust 程序设计语言》

总而言之,我觉得光线追踪的教程可以作为学一门新语言后严肃学习的项目,做完成就感也满满!

顺便推荐一篇好文:新技术学习不完全指北:以 Rust 为例

最后放下示例的渲染图:

1200*800 渲染图

五一劳动节快乐!

24 天像素画从入门到放弃

作者 猫冬
2021年4月18日 20:33

前不久十分厌学,想着是不是学废了,就想找到其他的东西学学,于是有一天周日尝试了同时入门 Blender 和 像素画。

建模其实和 Unity 用初始模型搭积木差不多,入门也还好。但是自己从小就是对美术绝缘,只有初中的时候会和其他同龄人一样照着漫画书瞎画。后来就直到现在,因此开始画像素画的时候还是十分不适应,感觉每一个点都是为无用艺术界添砖加瓦。

后来决定画像素画的契机是听播客介绍到一个码农姐姐为了做游戏坚持 100 天画像素画,于是少年那颗不知天高地厚的心怦然地燃烧起来。

教练!我想学画画!

兴起

作为一个资深松鼠症患者,Steam 里早已经躺着不知道什么时候打折入手的像素画神器 “Asprite”,我原本以为一辈子再也不会下载它,这就是命运的安排吧。

很多软件能画像素画,毕竟像素画就只是由点构成的,不过好的工具能事半功倍。用习惯 PS 的美术朋友可能会选择继续用 PS 改笔触画像素画,对于我来说,功能太多的软件反而会打压我的一时兴起的兴趣,于是我跟着 Aseprite!超方便的像素画软件初学者教程 花半小时大概清楚 Aseprite 有的功能。

Aseprite 是收费的,在 Github 开源 ,如果你想自己编译,可以参考 [GUIDE] How to build Aseprite from source. (Aseprite free & legal) 。我是在 Steam 上买的,现在看了看是 70 元,买了 Win、Mac、Linus 都能用,不需要自己分开编译,更新也会更方便些。

自己一开始跟着 Youtube 博主的视频教程入门,其中有前面 Aseprite 初学者教程的作者 MortMort、开了 Pixel 101 系列教程Pixel Pete 等。

我喜欢看视频教程入门的原因有几点:

  1. 我想看他们是怎么开始构思一幅画的(像素画的型)
  2. 画像素画的过程(先画什么后画什么,颜色如何选择)
  3. 对软件的使用,如何适当地使用软件的功能更快地画出你想要的画。
  4. 了解像素画独有的技巧,如:像素抖动等

一开始我看的是 Pixel 101 的前几个教程,Pixel Pete 在像素极其有限的情况下很快就能画出不同的物品,让我知道精准控制地像素就能通过不同颜色影响画在人们脑海中的想象。

因此我对像素画的理解就是:易入门、精准控制少量颜色和少量像素、费时少易出货,需要的基础也比原画板绘少非常多。

由于我当前工作室的游戏就是像素风格,因此问了几位原画同事,都说像素画是最简单的,他们一开始有原画基础,临摹下像素画的画法,很快就都能上手画像素画了。

于是我决定开始 100 天像素画挑战,每天花一个小时左右鼠绘像素画。

学习

第一天开始画之后,我发现很多问题:

  • 一个像素能表现的东西是有限的,我要决定这个像素应该表现成什么,从而决定是什么颜色。
  • 像素画的分辨率十分低,阴影过渡和线条可能会非常生硬,画太多又会有色块现象。
  • 像素画中颜色的数量要有限制,阴影可以用两到三个颜色过渡,太多颜色会很乱。

于是找了本书 《Make Your Own Pixel Art》 参考,这本书面对的是没绘画基础的新手,用的软件也是 Aseprite。这本书讲的非常详细,我印象最深的就是我需要先学会画出不同基本模型的光照,例如圆柱、正方体等,这些形状和光照会画之后,再将它们组合起来,创造出自己的物品或角色。

对于调色板的颜色,可以在 Lospec 中选一些经典的颜色,这样我们暂时不用考虑颜色的对比、饱和度挑选等,先限制自己在调色板中用色,后期学颜色理论(Color Theory)了再自己配色。

下面是第三天时做的书中的练习,给出一个角色的剪影,我来上色。

第三天

第五天我尝试画自己的角色,画布是 $ 64 × 64 $ ,主题是太空。其中用到刚学的像素抖动,星星的表示,不过有些光影的地方还是错的。

于是每天画画,时不时尝试不同风格的像素画,中途还尝试了下画动画帧。每天也会用 Eagle 收集一下参考用的素材,这个软件看动画帧也非常方便。

Eagle

挑战途中,我还找了一些素材参考,其中十分有用的是风农翻译的蔚蓝主美 Pedra Medeiros 的一系列像素画教程:saint11像素宝典JKLLIN像素画学习系列。像素宝典里面还教了很多游戏中很有用的动画帧画法,比如攻击时的准备帧、不同风格如光魔法和黑暗魔法的表现等。

如果还想深入,我十分推荐 Michael Azzi 写的 Pixel Logic 这本书,B 站的物暗先生汉化过。这本书里面介绍了很多像素画的专有概念,还引用了很多像素游戏作为参考,如果想做一个像素游戏,你能从中获益很多。

我还经常逛逛 Twitter 的像素画标签,如:pixelartドット絵等,Artstation 的 Pixel Art 画,还有 Deviant Art 的 Pixel Art 主题。找到参考的同时,还能进一步找到自己喜欢的风格,这样可以跟着画的作者进一步了解这种风格的像素画画法。

放弃

直到第 24 天我决定放弃,其实还是时间的问题,回到家自己的时间也就两三个小时,有时候纠结一下颜色和参考,一堆时间就过去了,我希望把时间更多地重新放在技术上。

当然这 24 天我也是收获了不少,对像素画有了基本的了解,对颜色也开始有了那么点概念。工作中做游戏系统原型的时候都能不等美术资源,自己随便画图凑合用了 hhh。游戏开发者在学像素画的时候,也能请教下工作室中的美术,以后说不定还能靠着自己的像素画做独立开发,一箭双雕!

大家在一开始画的时候从小图画起,$ 16 × 16 $ 到 $ 64 × 64 $ 的画布就已经足够了,这样的画布也不需要绘画板,鼠绘就足够了,我相信画到一定程度,就会知道自己需不要一个绘画板了。

最后

本文作为学习过程的记录,希望能给读者激起学像素画的兴趣,避免走一些弯路。博主学像素画也是为了点一下独立开发的技能,虽然画的不怎么样,至少不怕画画了!

如果你对我 24 天的像素画感兴趣,可以点击下方按钮,或者博客右上角的相对应的标签查看。

Group Image Gallery
像素画

像素画挑战

博客新增公开笔记部分

作者 猫冬
2020年10月3日 23:53

我认为博客应该放一些经过思考的、实践的、适合读者阅读的文章,自己有时候也会在看其他视频教程或文章时记一些笔记。有些笔记本身不太适合分享出来,因为做笔记不可避免的会按照自己的思路和现有知识来定制,可能和别人注意重点不太一样。

因此我打算将一些比较成文的、有结构性的、有参考价值的笔记分享出来,这也能锻炼我把笔记组织成文的能力。

这些公开的笔记我放在独立的一个 Notion 页面中,这个页面可以点击博客上方的公开笔记,或者这个链接找到:公开笔记

Notion 本身对公式、排版都比较友好,但是打开可能要科学上网,我是懒得把这些文章往博客搬了…不过用 Notion 有个好处就是,我对公开笔记的编辑都能实时更新到。

正文太空了也不好,就放个我笔记的主页图吧~

2020年5月技术导读

作者 猫冬
2020年5月24日 00:05

最近一直在思考自己在技术学习上是否过于低效的问题。出现这个问题的缘由是,自己工作下班之后没多少精力和时间去留给自己学习。本来就有限的时间,如果还没有合适的学习计划,而是一昧凭兴趣去学一些离自己目标方向比较远的东西,可能会事倍功半。

就我而言,自己目前的水平更像是“磨”出来的,东学学西学学,什么都有点印象,但是专业方向的知识之间的连接却非常离散。读研的时候有大量时间给我“磨”,总归能学会点什么,但工作则不一样。

例如一本《Shader 入门精要》目前看了两次,但仍然害怕离开书来写 Shader。再者,一门技术很久不用,再拿起来也需要时间。为此,我总结了三点原因:

  1. 工作中很少用到,游戏有特效师,自己也不会主动地思考怎样的 Shader 能为游戏带来更好的效果。
  2. 学的时候只光看了,跟着书敲了,但一直没有走出书本,去自己实现自己想要的功能。
  3. 觉得 Shader 像 CSS 一样,要记各种东西,凭经验实现效果,而这种知识自己最容易不用就忘。(当然这是错的,这也是为什么我在上期导读选择跟 Games101 图形学课程打基础)

基于上面的原因,导读也是偏向自己打基础的方面。

上一期的博文在:《2020年4月技术导读》

书籍

《软技能2:软件开发者职业生涯指南》

豆瓣地址

其实正如上文所说,我学东西靠的是“磨”,但这并不是什么好的学习方式。而且除去编程,作为一个开发者,我们仍然有很多“软技能”需要注意,例如自己的职业规划、如何发现技能短板、如何推进职业生涯等等。

我相信不止是我,很多开发者也在不断地摸索如何成为一个目标中资深且专业的开发者。而本月出版的这本书就是为这方面而量身定做的,是著名的《软技能》的第二版。这本书目前看到的翻译都十分优秀,每次开卷都有益。如果你也想专注于自己的职业发展,我十分推荐这本书。

下面是书中介绍的十步学习法,自己根据它来调整了下学习计划:

十步学习法

公开课

Games101 图形学入门

这门公开课我已经在上期导读中提到:《2020年4月技术导读》,再次提到是因为经过学习,我认为课程中理论部分讲的深入浅出,而且也能了解到当下流行的图形技术和它们是怎么跟我们所学的联系在一起。

闫老师提到他的学习方式是:Why, What then How,课程也是按照这种思路来设计的。先问为什么要学这个东西,然后问学的是什么,最后了解这东西具体是怎么运作的、怎么用。How 部分是最不重要的,也是最容易忘的部分,我们只需把握好 Why 和 What 部分即可。

那课程是怎么把知识点联系起来的呢,就凭借一个个 Why 来连接。拿光线追踪来举例,下面是我做的笔记:

光线追踪笔记截图

如果你对笔记感兴趣,我也将其分享了出来:《光线追踪》

The Cherno 的游戏引擎教程

油管地址

B站搬运地址

教学版引擎仓库地址

Up 主 The Cherno 在自己的 CPP 和 OpenGL 教程之后,再基于两者推出了游戏引擎教程。引擎的仓库是跟着视频教程的进度而推进的,有兴趣的可以了解下。

The Missing Semester of Your CS Education

课程地址

B站搬运地址

这门公开课是通过知乎专栏《6.NULL:恨不相逢“未嫁时”》了解到的。

Classes teach you all about advanced topics within CS, from operating systems to machine learning, but there’s one critical subject that’s rarely covered, and is instead left to students to figure out on their own: proficiency with their tools. We’ll teach you how to master the command-line, use a powerful text editor, use fancy features of version control systems, and much more!

简而言之,这门课不是教计算机的理论,而是介绍一些常用的工具,让你在面对问题的时候有更多的手段。自己可以看看一些不熟悉的主题查漏补缺。

MIT 教授 Gilbert Strang 「线性代数」课程

课程地址

这门公开课是通过知乎专栏《86岁还在录网课:MIT教授Gilbert Strang最新「线性代数」课程上线》了解到的。

这门课程在今年录制,目前有 6 个视频讲座,对于之前录制的课程也可以在 B 站找录播,例如:麻省理工公开课:线性代数

具体介绍可以看知乎专栏,自己对于这门课程优先级比较低,线代遇坎儿了再学。

其他计算机公开课

有网友总结了国外的计算机课程,还附上了视频链接,可以参考《电子工程和计算机科学系》

文章

  • 图形程序学习经历
    • 文章作者认为从图形 API 开始从底向上了解硬件做的事情到摸透一整个流程是个好的学习过程,其中也给出了很多有价值的参考资料。作者声称能以较快速度在两个月满足工作要求,完成图形程序入门的知识体系。
  • Entity Component System for Unity: Getting Started
    • Ray Wenderlich 的教程通常会提供初始项目,手把手带你写代码,加上独特风格的配图,很适合用来入门某个技术。这次带来的是 Unity ECS 的入门,用 Entities 包实现一个坦克射击游戏。
  • Fixing Performance Problems - 2019.3
    • Unity 发表的关于解决性能问题的教程,里面有很多小知识点,对初学者可能有帮助。虽然之前好像看过,但这是 2019.3 版本的。
  • Cache的基本原理
    • 作者图文并茂地讲解了缓存内部是如何运作的,Visio 手绘风格的图画也很清晰明了。对缓存感兴趣的还可以进一步关注作者的专栏。
  • Refactoring.Guru
    • 这网站也图文并茂地介绍了重构、 设计模式、 SOLID 原则 (单一职责、 开闭原则、 里氏替换、 接口隔离以及依赖反转) 以及其他和智能编程主题相关的内容。
  • 每位程式設計師都該知道的記憶體知識
  • Zero allocation code in C# and Unity
    • 文章作者开源过叫 Svelto 的 ECS 框架,这篇文章是他对 Zero allocation 代码(也就是自己管理内存)的理解,也介绍了相关的概念、书籍和很多查看内存分配的工具,对想了解 DOTS 的同学可以阅读一下。

最后

其实本篇导读相当一部分在讲的是我个人怎么样看待自己目前学习情况,每次导读中所有的内容我其实只能看完一部分,怎么样更高效地学和怎么样更好地平衡生活是我最近不断思考的问题。当然了,我不会放弃。

这次导读分享的多是游戏内存、缓存、图形学相关的内容,自己没分享过某种具体实现的 Shader 的文章,是因为我认为自己基础要先打好,这也是我对其他 Shader 课程的态度。希望这次分享能对读者有帮助。

洞明 Unity ECS 基础概念

作者 猫冬
2019年7月15日 04:13

虽然网络上已经有不少 ECS 文档的汉化,但自己读官方文档的时候也会产生不少疑问,为此通过查询各种资料,写下本文。

本文从 ECS 官方文档出发,加之内存布局结构的讲解,力求读者能够和博主一起吃透 ECS 中的基本概念。同时建议读者可以先读读我的上一篇博文《Unity DOTS 走马观花》的 ECS 部分,本文不再复述前文已经提到过的相关概念。

ECS 与 Job System

我认为有必要重申其两者的关系。

  • Job System 能帮我们方便地写出线程安全的多线程代码,其中每个任务单元称为 Job。
  • ECS,又称实体组件系统。与传统的面向对象编程相比,ECS 是一种基于数据设计的编程模式。前文从内存结构分析了 OOP 模式的缺点,也提到了 ECS 是怎么样基于数据的设计内存结构的。

Job System 是 Unity 自带的库,而要使用 ECS 我们需要从 Package Manager 中安装 “Entities” 预览包。这两者虽说完全是两种东西,但是他们能很好地相辅相成:ECS 保证数据线性地排列在内存中,这样通过更高效的数据读取,能有效提升 Job 的执行速度,同时也给了 Burst 编译器更多优化的机会。

Entities(实体)

World中, EntityManager 管理所有实体和组件。

当你需要创建实体和为其添加组件的时候, EntityManager会一直跟踪所有独立的组件组合(也就是原型 Archetype)。

创建实体

最简单的方法就是在编辑器直接挂一个 ConvertToEntity 脚本,在运行时中把 GameObject 转成实体。

在编辑器中挂脚本,GameObject 会在运行时中转成实体

在编辑器中挂脚本,GameObject 会在运行时中转成实体

脚本中,你也可以创建系统(System)并在一个 Job 中创建多个实体,也可以通过 EntityManager.CreateEntity 方法来一次生成大量 Entity。

我们可以通过下面四种方法来创建一个实体:

  • ComponentType 数组创建一个带组件的实体
  • EntityArchetype 创建一个带组件的实体
  • 用 Instantiate 复制一个已存在的实体和其当前的数据,
  • 创建一个空的实体然后再为其添加组件

也可以通过下面的方法一次性创建多个实体:

  • CreateEntity 来创建相同原型(archetype)的实体并填满一个 NativeArray (要多少实体就提前设定好 NativeArray 的长度)
  • Instantiate 来复制一个已存在的实体并填满一个 NativeArray
  • CreateChunk 来显式创建内存块(Chunks),并且填入自定数量的给定原型的实体

增加和移除组件

实体被创建之后,我们可以增加和移除其组件。当我们这样做的时候,相关联的原型(Archetype)将会被改变, EntityManager 也需要改变内存布局,将受影响的数据移到新的内存块(new Chunk of memory),同时也会压缩原来内存块中的组件数组。

对实体的修改会带来内存结构的改变。

实体的修改包括:

  • 增加和移除组件
  • 改变 SharedComponentData的值
  • 增加和删除实体

这些操作都不能放到 Job 中执行,因为这些都会改变内存中的数据结构。因此我们需要用到命令(Commands)来保存这些操作,将这些操作存到 EntityCommandBuffer 中,然后在 Job 完成后再依次执行 EntityCommandBuffer 中储存的操作。

World(世界)

每一个 World 包含一个 EntityManager 和一系列的 ComponentSystem。一个世界中的实体、原型、系统等都不能被另外一个世界访问到。你可以创建很多 World ,例如通常我们会使用或创建一个负责主要逻辑运算的 simulation World 和负责图形渲染的 rendering World 或 presentation World

当我们点击运行按钮进入 Play Mode 时,Unity 会默认创建一个 World,并且增加项目中所有可用的 ComponentSystem。我们也可以关闭默认的 World 从而自己创建一个。

  • Default World creation code (see file: Packages/com.unity.entities/Unity.Entities.Hybrid/Injection/DefaultWorldInitialization.cs)
  • Automatic bootstrap entry point (see file:Packages/com.unity.entities/Unity.Entities.Hybrid/Injection/AutomaticWorldBootstrap.cs)

Components(组件)

ECS 中的组件是一种结构,可以通过实现下列接口来实现:

  • IComponentData
  • ISharedComponentData
  • ISystemStateComponentData
  • ISharedSystemStateComponentData

EntityManager 会组织所有实体中独立的组件组合成不同的原型(Archetypes),还会将拥有同样原型的所有实体的组件(数据)储存到一起,都放到同一个**内存块(Chunks)**中。

如果你为一个实体新增了一个组件,那么其原型就改变了,实体的数据也需要从原来的内存块移到新的内存块,因为只有相同原型的实体数据才会放到相同的内存块中。

一个原型由很多个内存块组成,这些内存块中存的都是拥有相同原型的实体。

General Purpose Component(普通用途组件)

这里指的是最普通的组件,可以通过实现 IComponentData 接口来创建。

IComponentData 不存储行为,只储存数据。IComponentData 还是一个结构体(Struct)而不是一个类(Class),这意味着被复制时默认是通过值而不是通过引用。

通常我们会用下面的模式来修改组件数据:

1
2
3
4
5
6
var transform = group.transform[index]; // Read

transform.heading = playerInput.move; // Modify
transform.position += deltaTime * playerInput.move * settings.playerMoveSpeed;

group.transform[index] = transform; // Write

IComponentData 结构不包含托管对象(managed objects)的引用,所有IComponentData 被存在无垃圾回收的块内存(chunk memory)中。

你可能还听过一种组件是不包含数据、只用来标记的“Tag”组件(Tag component),其用途也很广,例如我们可以轻易地给实体加标记来区分玩家和敌人,这样系统中能更容易通过组件的类型来筛选我们想要的实体。如果我们给一个内存块(Chunk)中的所有实体都添加"Tag“组件的话,只有内存块中对应的原型会修改,不添加数据,因此官方也推荐利用好”Tag“组件。

See file: /Packages/com.unity.entities/Unity.Entities/IComponentData.cs.

Shared components(共享组件)

Shared components 是一种特殊的组件,你可以把某些特殊的需要共享的值放到 shared component 中,从而在实体中与其他组件划分开。例如有时候我们的实体需要共享一套材质,我们可以为需要共享的材质创建 Rendering.RenderMesh,再放到 shared components 中。原型中也可以定义 shared components,这一点和其他组件是一样的。

1
2
3
4
5
6
7
8
9
[System.Serializable]
public struct RenderMesh : ISharedComponentData
{
public Mesh mesh;
public Material material;

public ShadowCastingMode castShadows;
public bool receiveShadows;
}

当你为一个实体添加一个 shared components 时, EntityManager 会把所有带有同样 shared components 的实体放到一个同样的内存块中(Chunks)。shared components 允许我们的系统去一并处理相似的(有同样 shared components 的)实体。

内存结构

每个内存块(Chunk)会有一个存放 shared components 索引的数组。这句话包含了几个要点:

  1. 对于实体来说,有同样 SharedComponentData 的实体会被一起放到同样的内存块(Chunk)中。
  2. 如果我们有两个存储在同样的内存块中的两个实体,它们有同样的 SharedComponentData 类型和值。我们修改其中一个实体的 SharedComponentData 的值,这样会导致这个实体会被移动到一个新的内存块中,因为一个内存块共享同一个数组的 SharedComponentData 索引。事实上,从一个实体中增加或者移除一个组件,或者改变 shared components 的值都会导致这种操作的发生。
  3. 其索引存储在内存块而非实体中,因此 SharedComponentData 对实体来说是低开销的。
  4. 因为内存块只需要存其索引,SharedComponentData 的内存消耗几乎可以忽略不计。

因为上面的第二个要点,我们不能滥用 shared components。滥用 shared components 将让 Unity 不能利用好内存块(Chunk),因此我们要避免添加不必要的数据或修改数据到 shared components 中。我们可以通过 Entity Debugger 来监测内存块的利用。

拿上一段 RenderMesh 的例子来说,共享材质会更有效率,因为 shared components 有其自己的 manager 和哈希表。其中 manager 带有一个存储 shared components 数据的自由列表(freelist),哈希表可以快速地找到相应的值。内存块里面存的是索引数组,需要找数据的时候就会从 Shared Component Manager 中找。

其他要点

  • EntityQuery 可以迭代所有拥有相同 SharedComponentData 的实体
  • 我们可以用 EntityQuery.SetFilter() 来迭代所有拥有某个特定 SharedComponentData 的实体。这种操作开销十分低,因为 SetFilter 内部筛选的只是 int 的索引。前面说了每个内存块都有一个SharedComponentData 索引数组,因此对于每个内存块来说,筛选(filtering)的消耗都是可以忽略不计的。
  • 怎么样获取 SharedComponentData 的值呢?EntityManager.GetAllUniqueSharedComponentData<T> 可以得到在存活的实体中(alive entities)的所有的泛型 T 类型的SharedComponentData 值,结果以参数中的列表返回,你也可以通过其重载的方法获得所有值的索引。其他获取值的方法可以参考 /Packages/com.unity.entities/Unity.Entities/EntityManagerAccessComponentData.cs。
  • SharedComponentData 是自动引用计数的,例如在没有任何内存块拥有某个SharedComponentData 索引的时候,引用计数会置零,从而知道要删除SharedComponentData 的数据 。这一点就能看出其在 ECS 的世界中是非常独特的存在,想要深入了解可以看这篇文章《Everything about ISharedComponentData》
  • SharedComponentData 应该尽量不去更改,因为更改 SharedComponentData 会导致实体的组件数据需要复制到其他的内存块中。

你也可以读读这篇更深入的文章《Everything about ISharedComponentData》

System state components(系统状态组件)

SystemStateComponentData 允许你跟踪系统(System)的资源,并允许你合适地创建和删除某些资源,这些过程中不依赖独立的回调(individual callback)。

假设有一个网络同步 System State,其监控一个 Component A 的同步,则我只需要定义一个 SystemStateComponent SA。当 Entity [有 A,无 SA] 时,表示 A 刚添加,此时添加 SA。等到 Entity [无 A,有 SA] 时,表示 A 被删除(尝试销毁Entity 时也会删除 A)。
《浅入浅出Unity ECS》 BenzzZX

SystemStateComponentDataSystemStateSharedComponentData 这两个类型与 ComponentDataSharedComponentData 十分相似,不同的是前者两个类型都是系统级别的,不会在实体删除的时候被删除。

Motivation(诱因)

System state components 有这样特殊的行为,是因为:

  • 系统可能需要保持一个基于 ComponentData 的内部状态。例如已经被分配的资源。
  • 系统需要通过值来管理这些状态,也需要管理其他系统所造成的状态改变。例如在组件中的值改变的时候,或者在相关组件被添加或者被删除的时候。
  • “没有回调”是 ECS 设计规则的重要元素。

Concept(概念)

SystemStateComponentData 普遍用法是镜像一个用户组件,并提供内部状态。

上面引用的网络同步的例子中,A 就是用户分配的 ComponentData,SA 就是系统分配的 SystemComponentData

下面以 FooComponent (ComponentData)和 FooStateComponent(SystemComponentData)做主要用途的示例。前两个用途已经在前面的网络同步例子中呈现过。

检测组件的添加

如果用户添加 FooComponent 时,FooStateComponent 还不存在。FooSystem 会在 update 中查询,如果实体只有 FooComponent 而没有 FooStateComponent,,则可以判断这个实体是新添加的。这时候 FooSystem 会加上 FooStateComponent 组件和其他需要的内部状态。

检测组件的删除

如果用户删除 FooComponent 后,FooStateComponent 仍然存在。FooSystem 会在 update 中查询,如果实体没有 FooComponent 而有 FooStateComponent,,则可以判断 FooComponent 已经被删除了。这时候 FooSystem 会给删除 FooStateComponent 组件和修改其他需要的内部状态。

监测实体的删除

通常 DestroyEntity 这个方法可以用来:

  1. 找到所有由某个实体 ID 标记的所有组件
  2. 删除那些组件
  3. 回收实体 ID 以作重用

然而,DestroyEntity 无法删除 SystemStateComponentData

在你删除实体时,EntityManager 不会移除任何 system state components,在它们没被删除的时候,EntityManager 也不会回收其实体的 ID 。这样允许系统(System)在一个实体被删除的时候,去整理内部的状态(internal state),也能清理关联着实体 ID 的相关的资源和状态。实体 ID 只会在所有 SystemStateComponentData 被删除的时候才被重用。

Dynamic Buffers(动态缓冲)

DynamicBuffer 也是组件的一种类型,它能把一个变量内存空间大小的弹性的缓冲(variable-sized, “stretchy” buffer)和一个实体关联起来。它内部存储着一定数量的元素,但如果内部所占内存空间太大,会额外划分一个堆内存(heap memory)来存储。

动态缓冲的内存管理是全自动的。与 DynamicBuffer 关联的内存由 EntityManager 来管理,这样当DynamicBuffer 组件被删除的时候,所关联的堆内存空间也会自动释放掉。

上面的解释可能略显苍白,实际上 DynamicBuffer 可以看成一个有默认大小的数组,其行为和性能都和 NativeArray(在 ECS 中常用的无 GC 容器类型)差不多,但是存储数据超过默认大小也没关系,上文提到了会创建一个堆内存来存储多的数据。DynamicBuffer 可以通过 ToNativeArray 转成 NativeArray 类型,其中只是把指针重新指向缓冲,不会复制数据。

【Unity】ECSで配列を格納する Dynamic Buffers 这篇文章中,作者用DynamicBuffer 来储存临近的圆柱体实体,从而更方便地与这些实体交互。

定义缓冲

1
2
3
4
5
6
7
8
9
10
11
12
13
// 8 指的是缓冲中默认元素的数量,例如这例子中存的是 Integer 类型
// 那么 8 integers (32 bytes)就是缓冲的默认大小
// 64 位机器中则占 16 bytes
[InternalBufferCapacity(8)]
public struct MyBufferElement : IBufferElementData
{
// 下面的隐式转换是可选的,这样可以少写些代码
public static implicit operator int(MyBufferElement e) { return e.Value; }
public static implicit operator MyBufferElement(int e) { return new MyBufferElement { Value = e }; }

// 每个缓冲元素要存储的值
public int Value;
}

可能有点奇怪,我们要定义缓冲中元素的结构而不是 Buffer 缓冲本身,其实这样在 ECS 中有两个好处:

  1. 对于 float3 或者其他常见的值类型来说,这样能支持多种 DynamicBuffer 。我们可以重用已有的缓冲元素的结构,来定义其他的 Buffers
  2. 我们可以将 Buffer 的元素类型包含在 EntityArchetypes 中,这样它会表现得像拥有一个组件一样。例如用 AddBuffer() 方法,可以通过 entityManager.AddBuffer<MyBufferElement>(entity); 来添加缓冲。

Systems(系统)

系统负责将组件数据从一个状态(state)通过逻辑处理到下一个状态。例如系统可以根据帧间隔和实体的速度,在当前帧更新所有移动实体的位置。

世界初始化后提供了三个系统组(system groups),分别是 initialization、simulation 和 presentation,它们会按顺序在每帧中执行。

系统组的概念会在下文提到。

ComponentSystem(组件系统)

ComponentSystem 通常指 ECS 实体组件系统中最基本的概念 System,它提供要执行的操作给实体。

ComponentSystem 不能包含实体的数据。从传统的开发模式来看,它与旧的 Component 类有点相似,不过 ComponentSystem 只包含方法

一个 ComponentSystem 负责更新所有匹配组件类型的实体。例如:系统可以通过条件过滤来获得所有拥有 Player 标记(Tag)和位置(Translation)的实体,再对获得的一系列 Player 实体进行处理。其中这种条件过滤由 EntityQuery 结构定义。

要注意的是,ComponentSystem 只在主线程中执行。

我们可以通过继承 ComponentSystem 抽象类来定义我们的系统。

See file: /Packages/com.unity.entities/Unity.Entities/ComponentSystem.cs.

JobComponentSystem(任务组件系统)

前文提到了 ECS 能很好的和 JobSystem 一起合作,那么这个类型就是一个很好的例子。ComponentSystem 只在主线程中执行,而 JobComponentSystem 则能在多线程中执行,更能利用多核的优势。

自动化的 Job 依赖管理

JobComponentSystem 能帮我们自动管理依赖。原理很简单,来自不同系统的 Job 可以并行地读取相同类型的 IComponentData。如果其中一个 Job 正在写(write)数据,那么所有的 Job 就不能并行地执行,而是设定它们的依赖来安排执行顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class RotationSpeedSystem : JobComponentSystem
{
[BurstCompile]
struct RotationSpeedRotation : IJobForEach<Rotation, RotationSpeed>
{
public float dt;

public void Execute(ref Rotation rotation, [ReadOnly]ref RotationSpeed speed)
{
rotation.value = math.mul(math.normalize(rotation.value), quaternion.axisAngle(math.up(), speed.speed * dt));
}
}

// 所有对 Rotation 读/写的和对 RotationSpeed 进行写操作的
// 已经排程的 Job 会自动放到 JobHandle 类型的依赖句柄 inputDeps 中
// 在方法中,我们也需要把自己的 Job 依赖加进句柄中,并在方法末尾返回回来。
protected override JobHandle OnUpdate(JobHandle inputDeps)
{
var job = new RotationSpeedRotation() { dt = Time.deltaTime };
return job.Schedule(this, inputDeps);
}
}

怎么运行的?

所有 Jobs 和系统会声明它们会读/写哪些组件类型(ComponentTypes)。JobComponentSystem 返回的 JobHandle 依赖句柄会自动注册到 EntityManager 中,以及所有包含读或写(reading or writing)信息的类型中。

这样如果一个系统对 Component A 进行写操作而之后另一个系统会对其进行读操作, JobComponentSystem 会查询读取(reading)的类型列表,然后传给你一个依赖。依赖包含第一个系统返回的 JobHandle,也就是包含“一个系统对 Component A 进行写操作”这个依赖,并将其作为第二个系统的参数传入。

JobComponentSystem 简单地按照需求维护一个依赖链,这样不会对主线程造成影响。但是如果一个非 Job 的 ComponentSystem 要存取(access)相同的数据会怎么样呢?因为所有的存取都是声明好的,因此对于所有 ComponentSystem 需要进行存取的组件类型(component type)相关联的 Jobs,ComponentSystem 都会先自动完成这些相关的 Jobs,再在 OnUpdate 中调用依赖。

依赖管理是保守的(conservative)和确定性的(deterministic)

依赖管理是保守的。 ComponentSystem 只是简单的跟踪所有使用的 EntityQuery,然后基于 EntityQuery 存储需要读或写的类型。

当在一个系统中分发多个 Jobs 的时候,依赖必须被发送到所有 Jobs 中,即使不同的 Jobs 可能需要更少的依赖。如果这里被证明有性能问题,那最好的解决方法是将系统一分为二。

依赖管理的手段也是保守的。它通过提供一个非常简单的 API 来允许确定性和正确的行为。

Sync points(同步点)

所有结构性的变化都有确切的同步点(hard sync points)。 CreateEntityInstantiate、 Destroy、 AddComponent、 RemoveComponentSetSharedComponentData 都有一个确切的同步点。这代表所有通过 JobComponentSystem 排期的 Jobs 都会在创建实体之前自动完成。

例如,在一帧中间的 EntityManager.CreateEntity 可能带来较大的停滞,因为所有在世界中的提前排期好的 Jobs 都需要完成。

如果要在游戏中避免上面提到的停滞,可以使用 EntityCommandBuffer

Multiple Worlds(多个世界)

所有世界(World)都有自己的 EntityManager ,因此 JobHandle 依赖句柄的集合都是分开的。一个世界中的确切的同步点(hard sync points)不会影响另外一个世界。因此,对于流式传输和程序化生成的场景,最后在一个世界中创建实体然后移到另一个世界作为一个事务(transaction)并在帧的开始执行。

对于上面的问题可以参考 ExclusiveEntityTransaction 和 System update order。

Entity Command Buffer(实体命令缓冲)

EntityCommandBuffer 解决了两个重要问题:

  1. 在 Job 中无法访问 EntityManager,因此不能通过它来管理实体。
  2. 当你使用 EntityManager 时(例如创建一个实体),你会使所有已被注入的数组和 EntityQuery 无效。(这里注入的概念大概是指:系统中可以设定某个过滤条件,给过滤条件加上 [inject] 后,系统会在启动时为这个属性根据条件注入数据,这样就能得到我们想要的数据。会无效是因为你修改了实体数据,那么结果可能会发生改变。)

EntityCommandBuffer 的抽象允许我们去把需要对数据的更改(changes)排好队,这个更改可以来自主线程或者 Jobs,这样数据可以晚一点在主线程接受更改,从而将其和获取数据分离开来。

我们有两种方法来使用 EntityCommandBuffer

  • 在主线程 update 的 ComponentSystem 子类有一个 PostUpdateCommands(其本身是一个EntityCommandBuffer ) 可以用,我们只要简单地把变化按顺序放进去即可。在系统的 Update 调用之后,它会立刻自动在世界(World)中进行所有数据更改。这样可以防止数组数据无效,API 也和 EntityManager 很相似。
1
2
3
4
5
6
7
8
PostUpdateCommands.CreateEntity(TwoStickBootstrap.BasicEnemyArchetype);
PostUpdateCommands.SetComponent(new Position2D { Value = spawnPosition });
PostUpdateCommands.SetComponent(new Heading2D { Value = new float2(0.0f, -1.0f) });
PostUpdateCommands.SetComponent(default(Enemy));
PostUpdateCommands.SetComponent(new Health { Value = TwoStickBootstrap.Settings.enemyInitialHealth });
PostUpdateCommands.SetComponent(new EnemyShootState { Cooldown = 0.5f });
PostUpdateCommands.SetComponent(new MoveSpeed { speed = TwoStickBootstrap.Settings.enemySpeed });
PostUpdateCommands.AddSharedComponent(TwoStickBootstrap.EnemyLook);
  • 对于 Jobs 来说,我们必须从主线程的 EntityCommandBufferSystem 中请求一个 EntityCommandBuffer,再传到 Job 里面让其调用。 每当 EntityCommandBufferSystem 进行 update,命令缓冲都会在主线程中重新把更改按创建的顺序执行一遍。这样允许我们集中进行内存管理,也保证了创建的实体和组件的确定性。

Entity Command Buffer Systems(实体命令缓冲系统)

在一个系统组中,有一个 Entity Command Buffer Systems 运行在所有系统组之前,还有一个运行在所有系统组之后。比较建议的是我们可以用已存在的命令缓存系统(command buffer system)之一,而不用创建自己的,这样可以最小化同步点(sync point)。

在 ParallelFor jobs 中使用 EntityCommandBuffers

ParallelFor jobs 使用 EntityCommandBufferEntityManager 的命令(command)时, EntityCommandBuffer.Concurrent 接口能保证线程安全和确定性的回放(deterministic playback)。

1
2
3
4
5
6
7
// See file: /Packages/com.unity.entities/Unity.Entities/EntityCommandBuffer.cs.
public Entity CreateEntity(int jobIndex, EntityArchetype archetype = new EntityArchetype())
{
...
m_Data->AddCreateCommand(chain, jobIndex, ECBCommand.CreateEntity, index, archetype, kBatchableCommand);
return new Entity {Index = index};
}

EntityCommandBuffer.Concurrent 的公共方法都会接受一个 jobIndex 参数,这样能回放(playback)已经按顺序保存好的命令。 jobIndex 作为 ID 必须在每个 Job 中唯一。从性能考虑,jobIndex 必须是传进 IJobParallelFor.Execute() 的不断增长的 index。除非你真的知道你传的是啥,否则最安全的做法就是把参数中的 index 作为 jobIndex 传进去。用其他 jobIndex 可能会产生正确的结果,但是可能在某些情况下会有严重的性能影响。

1
2
3
4
5
6
7
8
9
10
11
12
namespace Unity.Jobs
{
[JobProducerType(typeof (IJobParallelForExtensions.ParallelForJobStruct<>))]
public interface IJobParallelFor
{
/// <summary>
/// <para>Implement this method to perform work against a specific iteration index.</para>
/// </summary>
/// <param name="index">The index of the Parallel for loop at which to perform work.</param>
void Execute(int index);
}
}

System Update Order(系统更新顺序)

组件系统组(Component System Groups)其实是为了解决世界(World)中各种 update 的顺序问题。一个系统组中包含了很多需要按照顺序一起 update 的组件系统(component systems),可以来指定它成员系统(member system)的 update 顺序。

和其他系统一样, ComponentSystemGroup 也继承自 ComponentSystemBase ,因此系统组可以当成一个大的“系统”,里面也用 OnUpdate() 函数来更新系统。它也可以被指定更新的顺序(在某个系统的之前或之后更新等,下文会讲),并且也可以嵌入到其他系统组中。

默认情况下, ComponentSystemGroupOnUpdate() 方法会按照成员系统(member system)的顺序来调用他们的 Update(),如果成员系统也是一个系统组,那么这个系统组也会递归地更新它的成员系统。总体的系统遵循树的深度优先遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// See file: /Packages/com.unity.entities/Unity.Entities/ComponentSystemGroup.cs.
protected override void OnUpdate()
{
if (m_systemSortDirty)
SortSystemUpdateList();

foreach (var sys in m_systemsToUpdate)
{
try
{
sys.Update();
}
catch (Exception e)
{
Debug.LogException(e);
}
if (World.QuitUpdate)
break;
}
}

System Ordering Attributes(系统顺序属性)

  • [UpdateInGroup] 指定某个系统成为一个 ComponentSystemGroup 中的成员系统。如果没有用这个属性,这个系统会自动被添加到默认世界(default World)的 SimulationSystemGroup 中。
  • [UpdateBefore][UpdateAfter] 指定系统相对于其他系统的更新顺序。这两个系统必须在同一个系统组(system group)中,前文说到系统组也可以嵌套,因此只要两个系统身处同一个根系统组即可。
    • 例子:如果 System A 在 Group A 中、System B 在 Group B 中,而且 Group A 和 Group B 都是 Group C 的成员系统,那么 Group A 和 Group B 的相对顺序也决定着 System A 和 System B 的相对顺序,这时候就不需要明确地用属性标明顺序了。
  • [DisableAutoCreation] 阻止系统从默认的世界初始化中创建或添加到世界中。这时候我们需要显式地创建和更新系统。然而我们也可以把这个系统和它的标记(tag)加到 ComponentSystemGroup 的更新列表中(update list),这样这个系统会正常地自动更新。

Default System Groups(默认系统组)

默认世界(default World)包含 ComponentSystemGroup 实例的层次结构(hierarchy)。在 Unity Player Loop 中会添加三个根层次(root-level)的系统组。

下图中打开 Entity Debugger,也能看到这三个系统组和其顺序。

这三个系统组各司其职, InitializationSystemGroup 做初始化工作, SimulationSystemGroup 在 Update 中做主要的逻辑运算, PresentationSystemGroup 做图形渲染工作。

如果勾选 “Show Full Player Loop” 项,还能看到完整的游戏主循环,以及系统组执行的顺序。

下面列表也展示了预定义的系统组和其成员系统:

  • InitializationSystemGroup (在游戏循环(Player Loop)的 Initialization 层最后 update)
    • BeginInitializationEntityCommandBufferSystem
    • CopyInitialTransformFromGameObjectSystem
    • SubSceneLiveLinkSystem
    • SubSceneStreamingSystem
    • EndInitializationEntityCommandBufferSystem
  • SimulationSystemGroup(在游戏循环的 Update 层最后 update)
    • BeginSimulationEntityCommandBufferSystem
    • TransformSystemGroup
      • EndFrameParentSystem
      • CopyTransformFromGameObjectSystem
      • EndFrameTRSToLocalToWorldSystem
      • EndFrameTRSToLocalToParentSystem
      • EndFrameLocalToParentSystem
      • CopyTransformToGameObjectSystem
    • LateSimulationSystemGroup
    • EndSimulationEntityCommandBufferSystem
  • PresentationSystemGroup(在游戏循环的 PreLateUpdate 层最后 update)
    • BeginPresentationEntityCommandBufferSystem
    • CreateMissingRenderBoundsFromMeshRenderer
    • RenderingSystemBootstrap
    • RenderBoundsUpdateSystem
    • RenderMeshSystem
    • LODGroupSystemV1
    • LodRequirementsUpdateSystem
    • EndPresentationEntityCommandBufferSystem

P.S. 内容可能在未来有更改

Multiple Worlds(多个世界)

前文多处提到默认的世界,实际上我们可以创建多个世界。同样的组件系统(component system)的类可以在不同的世界中初始化,而且每个实例都可以处于不同的同步点以不同的速度进行update。

当前没有方法手动更新一个世界中的所有系统,但是我们可以控制哪些系统被哪个世界控制,和它们要被加到哪个现存的世界中。自定义的世界可以通过实现 ICustomBootstrap 接口来创建。

Tips and Best Practices(提示与最佳实践)

  • **用 [UpdateInGroup] 为你的系统指定一个 ComponentSystemGroup 系统组。**如果没有用这个属性,这个系统会自动被添加到默认世界(default World)的 SimulationSystemGroup 中。
  • **用手动更新循环(manually-ticked)的 ComponentSystemGroups 来 update 在主循环中的系统。**添加 [DisableAutoCreation] 阻止系统从默认的世界初始化中创建或添加到世界中。这时候我们可以在主线程中调用 World.GetOrCreateSystem() 来创建系统,调用 MySystem.Update() 来 update 系统。如果你有一个系统要在帧中早点或者晚点运行,这种做法能更简单地把系统插到主循环中。
  • **尽量使用已存在的 EntityCommandBufferSystem 而不是重新添加一个新的。**因为一个 EntityCommandBufferSystem 代表一个主线程等待子线程完成的同步点(sync point),如果重用一个在每个根系统组(root-level system group)中预定义的 Begin/End 系统,就能节省多个同步点所带来的额外时间间隔(可以回去看同步点小节的示意图,同步点的位置是由最晚执行完的子线程所决定的)。
  • **避免放自定义的逻辑到 ComponentSystemGroup.OnUpdate() 中。**虽然 ComponentSystemGroup 功能上和一个组件系统(component system)一样,但是我们应该避免这么做。因为它作为一个系统组,在外面不能马上知道成员系统是否已经执行了 update,因此推荐的做法是只让系统组当一个组(group)来用,而把逻辑放到与其分离的组件系统中,再定好该系统与系统组的相对顺序。

最后

自己才刚考完试,所以计划的文章一直拖到现在。ECS 对我而言充满着吸引力,可能有些程序员也会对性能特别执着吧,它就像魔法一样,完全不同的开发模式,还需要我们深入了解内存的结构。尽管 ECS 可能在工作中对我是一种屠龙技,但有些知识啊,学了就已经很开心了~

我的毕业季也到来了,有空的话可能会写写 Demo 把剩下的实践部分补完,当然计划也可能搁浅。不管怎么样,希望本文对 ECS 同好有所帮助,有问题也欢迎在评论指出。

参考

寻路算法-贪婪最佳优先算法

作者 猫冬
2017年12月17日 07:24

最近开始接触寻路算法,对此不太了解的话建议读者先看这篇文章《如何快速找到最优路线?深入理解游戏中寻路算法》

所有寻路算法都需要一种方法以数学的方式估算某个节点是否应该被选择。大多数游戏都会使用启发式(heuristic) ,以 h(x) 表示,就是估算从某个位置到目标位置的开销。理想情况下,启发式结果越接近真实越好。

——《游戏编程算法与技巧》

今天主要说的是贪婪最佳优先搜索(Greedy Best-First Search),贪心算法的含义是:求解问题时,总是做出在当前来说最好的选择。通俗点说就是,这是一个“短视”的算法。

为什么说是“短视”呢?首先要明白一个概念:曼哈顿距离

曼哈顿距离

曼哈顿距离被认为不能沿着对角线移动,如下图中,红、蓝、黄线都代表等距离的曼哈顿距离。绿线代表欧氏距离,如果地图允许对角线移动的话,曼哈顿距离会经常比欧式距离高。

img

在 2D 地图中,曼哈顿距离的计算如下:

img

贪婪最佳优先搜索的简介

贪婪最佳优先搜索的每一步,都会查找相邻的节点,计算它们距离终点的曼哈顿距离,即最低开销的启发式。

贪婪最佳优先搜索在障碍物少的时候足够的快,但最佳优先搜索得到的都是次优的路径。例如下图,算法不断地寻找当前 h(启发式)最小的值,但这条路径很明显不是最优的。

img

贪婪最佳优先搜索“未能远谋”,大多数游戏都要比贪婪最佳优先算法所能提供的更好的寻路,但大多数寻路算法都是基于贪婪算法,所以了解该算法很有必要。

首先是节点类,每个节点需要存储上一个节点的引用和 h 值,其他信息是为了方便算法的实现。存储上一个节点的引用是为了像一个链表一样,最后能通过引用得到路径中所有的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Node
{
// 上一个节点
public Node parent;
// 节点的 h(x) 值
public float h;
// 与当前节点相邻的节点
public List<Node> adjecent = new List<Node>();
// 节点所在的行
public int row;
// 节点所在的列
public int col;
// 清除节点信息
public void Clear()
{
parent = null;
h = 0.0f;
}
}

下面是图类,图类最主要的任务就是根据提供的二维数组初始化所有的节点,包括寻找他们的相邻节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 图类
public class Graph
{
public int rows = 0;
public int cols = 0;
public Node[] nodes;

public Graph(int[, ] grid)
{
rows = grid.GetLength(0);
cols = grid.GetLength(1);

nodes = new Node[grid.Length];
for (int i = 0; i < nodes.Length; i++)
{
Node node = new Node();
node.row = i / cols;
node.col = i - (node.row * cols);
nodes[i] = node;
}

// 找到每一个节点的相邻节点
foreach (Node node in nodes)
{
int row = node.row;
int col = node.col;
// 墙,即节点不能通过的格子
// 1 为墙,0 为可通过的格子
if (grid[row, col] != 1)
{
// 上方的节点
if (row > 0 && grid[row - 1, col] != 1)
{
node.adjecent.Add(nodes[cols * (row - 1) + col]);
}
// 右边的节点
if (col < cols - 1 && grid[row, col + 1] != 1)
{
node.adjecent.Add(nodes[cols * row + col + 1]);
}

// 下方的节点
if (row < rows - 1 && grid[row + 1, col] != 1)
{
node.adjecent.Add(nodes[cols * (row + 1) + col]);
}

// 左边的节点
if (col > 0 && grid[row, col - 1] != 1)
{
node.adjecent.Add(nodes[cols * row + col - 1]);
}
}
}
}
}

在算法类中,我们需要记录开放集合和封闭集合。开放集合指的是当前步骤我们需要考虑的节点,例如算法开始时就要考虑初始节点的相邻节点,并从其找到最低的 h(x) 值开销的节点。封闭集合存放已经计算过的节点。

1
2
3
4
// 开放集合
public List<Node> reachable;
// 封闭集合,存放已经被算法估值的节点
public List<Node> explored;

下面是算法主要的逻辑,额外的函数可以查看项目源码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public Stack<Node> Finding()
{
// 存放查找路径的栈
Stack<Node> path;
Node currentNode = reachable[0];
// 迭代查找,直至找到终点节点
while (currentNode != destination)
{
explored.Add(currentNode);
reachable.Remove(currentNode);
// 将当前节点的相邻节点加入开放集合
AddAjacent(currentNode);
// 查找了相邻节点后依然没有可以考虑的节点,查找失败。
if (reachable.Count == 0)
{
return null;
}
// 将开放集合中h值最小的节点当做当前节点
currentNode = FindLowestH();
}
// 查找成功,则根据节点parent找到查找到的路径
path = new Stack<Node>();
Node node = destination;
// 先将终点压入栈,再迭代地把node的前一个节点压入栈
path.Push(node);
while (node.parent != null)
{
path.Push(node.parent);
node = node.parent;
}
return path;
}

除此以外还有些展示算法的类,代码不在这里展出。下面是算法执行的截图,其中白色格子为可走的格子,灰色格子是不可穿越的,红色格子为查找到的路径,左上角格子为查找起点,右上角格子为查找终点。

small

big

后一个实例也展现了其"短视"的缺点,红线走了共65个格子,但蓝箭头方向只走了45个格子。

最后

还有一种方案就是直接计算起点到终点的路径,这样可以节省一点计算开销。如下方右图,左图为广度优先算法。

img

本项目源码在 Github-PathFindingDemo
了解了贪婪最佳优先算法后,下一篇文章会在本文基础上讲A* 寻路。

参考资料

❌
❌