:::: 菜单 ::::

基于目标的矢量场寻路

# 基于目标的矢量场寻路

Understanding Goal-Based Vector Field Pathfinding https://gamedevelopment.tutsplus.com/tutorials/understanding-goal-based-vector-field-pathfinding–gamedev-9007

本文讲解矢量场寻路,以及它相对于传统寻路算法的优势,传统算法比如Dijkstra’s算法。对 [Dijkstra’s algorithm](https://en.wikipedia.org/wiki/Dijkstra’s_algorithm ) 和 [potential fields](http://aigamedev.com/open/tutorials/potential-fields/) 的基础理解会更加利于理解本文。

## 简介

寻路有很多解决方案,每种方案各有利弊。许多寻路算法都是为每个寻路计算出一条到达目的地的路径,这意味着有越多的寻路就会有越多翻倍的计算量。这在很多情况下是可接受的,但在有成千上万的寻路需要时,需要有更高效的方式才行。

矢量场寻路,这种方式计算图中从目标到每个节点的路径。为了巩固说明,我会用我自己实现的专用例子来解释这个算法。

注意:矢量场寻路通常可被抽象为节点和图;尽管我采用的网格方式,但并不意味着这个算法只限于基于网格的世界。

## 视频概述

矢量场寻路分三步:

– 创建一个热力图,描述地图上每个节点到目标的路径距离
– 创建一个矢量场,指出走向目标的朝向。
– 所有寻找该公共目标的粒子都使用这矢量场来导航至目标。

视频显示了最终效果,并给你下文完整教程这个概念的全面概览。

## 生成热力图

热力图存储着这张地图上每个点到目标点的路径距离。路径距离和欧几里得距离不同之处在于,它是仅途经可通行地形上两点间的距离。比如GPS总是计算路径距离,对他来说,公路就是唯一可通行地形。

下面,你可以看到路径距离和直线距离的区别。红色是目标点,粉色是随便点的一个起点。渲染为绿色的是不可通行的格子。如你所见,路径距离(黄色)是9,白色直线距离(浅蓝色)大概是4.12。

每个格子左上角的数字显示的是与目标的路径距离,由热力图生成算法计算得出。注意两点之间可能有不止一条路径距离;本文中我们只对最短的感兴趣。

![Efficient_Pathing_Path_vs_Linear_Distance](基于目标的矢量场寻路.assets/Efficient_Pathing_Path_vs_Linear_Distance.png)

热力图生成算法是一个*wavefront 算法*。从目标处开始取值为0,然后向外流动来填满所有可通行的区域。有两步骤:

– 从目标格开始,标记路径距离为0.
– 然后,每个已标记格子周围找到未标记的相邻格子,把他们标记为`前一个格子的路径距离+1`
– 重复,直到可抵达的全部格子被标记满。

注意:wavefront算法是一个网格上的广度优先搜索,记录了它移动到每个格子全程走了多少步。这有时候也被称为`brushfire算法`。

## 生成矢量场

现在我们已经有生成好的每个格子与目标点的路径距离,我们可以容易确定通往目标的路径。在运行时为每个寻路者逐帧计算也是可行的,但把矢量场一次计算好,然后让所有寻路者引用这个矢量场的做法通常更好。

矢量场在每个格子存储一个矢量,指向通往目标的斜角。这有一幅可视化的矢量场,这些矢量从各格子中心全程指向通向目标(红色)的最短路径。

![Efficient_Pathing_Vector_Field_Visualization](基于目标的矢量场寻路.assets/Efficient_Pathing_Vector_Field_Visualization.png)

矢量场通过检查热力图每次生成一个格子。x和y是分别计算的:

“`
Vector.x = left_tile.distance – right_tile.distance
Vector.y = up_tile.distance – down_tile.distance
“`

注意:每个格子的`distance`变量存的就是之前wavefront算法计算好的路径距离。

如果引用的格子(上下左右)是无法抵达的,也就没有可用的距离数据,那么直接用当前格子的距离值作为替代。当路径矢量被粗略计算好后,再归一化一下,避免之后数据出现错位问题。

## 寻路者的移动

既然现在矢量场已经被计算好了,寻路者就很容易计算移动量。设`vector_field(x,y)`返回已计算好的`(x,y)`格处的矢量,`desired_velocity`是一个纯量,以下为计算在格子`(x,y)`处的粒子的速度:

“`
velocity_vector = vector_field(x, y) * desired_velocity
“`

粒子只需要开始按照矢量指示的方向移动就行了。这是最简单的方式,而**流场**可用于实现更复杂的移动系统。

比如,这篇文章[Understanding Steering Behaviors](http://gamedev.tutsplus.com/series/understanding-steering-behaviors/) 里阐述的技术可用于寻路移动。在特定情况,上文中我们计算好的`velocity_vector`被用作`desired_velocity`,转向行为会负责在每个时间片计算真正的移动量。

### 局部最优

计算移动的时候,有时会出现一个问题,称作`局部最优`。当格子上同时有2个最优(最短)路径可以抵达目标时出现。

下图中可看到此问题。粉色格子处有一个路径矢量分量x和y皆为0。

![Efficient_Pathing_Local_Optima](基于目标的矢量场寻路.assets/Efficient_Pathing_Local_Optima.png)

局部最优会导致寻路者卡住,它们引用了一个无法指引前进方向的矢量场。当这种情况发生时,寻路者会持续定在那一格不动,直到修复。

我发现解决这个问题最简明的方法是把热力图和矢量场细分一次。热力图和矢量场的每格被拆分为4小格。细分后的网格,问题依然存在,它只是略微减小了。

真正管用的是用细分后的4个小格用作目标格,而非仅有1个目标格。要做到这样,我们必须修改第一步骤里的生成热力图的算法。我们之前是只放一个目标格子,起始路径距离为0,现在我们放4个靠在一起的格子作目标。

有很多方式来选取这4个格子,但如何选择基本上是无关紧要的——只要这四个格子是临近的、可通行的,这技术就可行。

这有一个改过的步骤,用来做热力图生成:

– 从4个目标格子开始,4个格子全部标记路径距离为0
– 然后,每个已标记格子周围找到未标记的相邻格子,把他们标记为`前一个格子的路径距离+1`
– 重复,直到可抵达的全部格子被标记满。

至此,这是最终结果,可清晰看出,局部最优问题已被终结。

![Efficient_Pathing_Local_Optima_Solved](https://cdn.tutsplus.com/cdn-cgi/image/width=600/gamedev/uploads/2013/06/Efficient_Pathing_Local_Optima_Solved.png)

最燃这个解法非常简明,但远不够理想。用这方法意味着计算热力图和矢量场消耗了4倍时间,因为增加到了4倍的网格。

其他解法需要在这问题基础上做一些核查,查明应去的朝向,这个核查会显著降低粒子移动的计算。而我的做法,细分地图可能是最佳选项。

## 总结

希望这个教程教会了你在网格世界中实现基于目标的矢量场寻路。记住,这类型寻路的核心都在于:粒子随着格子的距离函数(前往目标)的斜率移动。

实现略复杂些,但可拆解为下面三个可管理的步骤:

– 热力图生成
– 矢量场生成
– 粒子移动


DAZ导入unity,眼睛白色的修正

DAZ导入unity,眼睛白色的修正:

fbx 导入设置-材质 改成
Location=“use external materials”
Naming=“From Model’s Material”

然后应用,材质球里重新设置,针对眼球表面

Cornea 、 EyeMoisture 材质球改成 Standard(Roughness setup)

RenderingMode=Transparent
Albedo = “Checkmark” (😂)

其实就是要把他们改成transparent就行;

对Eyelashes材质球 改成 RenderingMode=“Fade”


为解决GooglePlay要求64位支持的问题,cocos老项目的一点笔记

有个老项目,为解决Google要求64位支持的问题,准备把cocos升级一下,然后发现不需要,据说只要编译64位版本就可以。依稀记得当时删了arm64-v8a的。

Google的教程: https://developer.android.com/distribute/best-practices/develop/64-bit#test_your_app_on_64-bit_hardware 里面说了3种情况,用Gradle编译、CMake编译、ndk-build编译,不同。 cocos2dx根据我测试发现是ndk-build模式,取决于gradle.properties里的配置PROP_APP_ABI。

帖子:[Support for 64bit on cocos2d-x on Android](https://discuss.cocos2d-x.org/t/critical-support-for-64bit-on-cocos2d-x-on-android/45516/14):

我实际进行的操作:

1. 修改配置加arm64-v8a

2. 升级了Gradle和studio,升级了最低sdk到16和编译sdk到28
3. 重写了一些java代码,deprecated method
4.

5.

6. 所有compile不支持了,改成implementation或者api



Multipart body must have at least one part

使用RN出这个错误,经检查有问题的代码是:

被调用来发送get的请求,传入的dataObj是{},而FormData至少有一个字段才行。如果没有post的字段,就不要发送FormData。


再见,FLASH

跟flash在一起十五年了。
小的时候,关于Adobe,我先接触的是Photoshop和ImageReady。
后来Macromedia被Adobe收购,网页三剑客成了Adobe前缀,才真正围绕Adobe很多年。
曾经的梦想是“成为Flash大师。提供卓越的网页用户交互解决方案。” 仿佛已经通关毕业了去往新战场了。
最近这十年,从as3崛起到整个Flash被颠覆,看着Adobe一点一点在移动互联网时代把Flash葬送掉,我已经没有了感觉。
反正,现在也没什么地方能用得上Flash了。反正,现在也没什么地方能用得上Adobe全家桶了。
至少有ES6已经足够完善,标准、跨平台、全栈通吃。有ReactNative做App,UI方便好用。
有Unity超方便的工作流,跟美术沟通画草图,我都在Unity编辑器里做了。启动速度比Flash快得多。
有Sketch超级方便快速矢量又超大与时俱进的素材库,启动速度又快,还比PS和AI轻量便宜气质佳。
唯一舍不得的就是用了好几年的IntelliJ IDEA,这货写AS3是神器,当然也可以写白鹭和Laya,曾经装了IDEA就搞定半边天的时代不再了。
现在,我需要WebStorm写JSX配合ReactNative;需要Consulo写C#配合Unity;需要AndroidStudio写Java native code;需要AppCode写C++和iOS native code;
从渣渣FlexBuilder,到用FDT很多年,最后终于转向JetBrains全家桶,世界变得越来越美好了,足够应付所有Coding的事情了。
对Flash的感情其实很复杂,现在人老了,免不了怀旧,我怀念小时候玩红警,玩帝国,星际,后来还有魔兽,也怀念最初的渗透“东北人都是活雷锋”的FlashMTV,还有数不清的南方公园。
可是又知道,一切记忆里的东西,还是存在记忆里吧, nothing lasts forever。
要说Adobe真心不是一家令我喜爱的公司,迪士尼才是,苹果才是。Adobe终结了我的Flash情结,却给不了什么替代品,它只是在时代面前弱小的存在,像大部分实体一样。最后它自己也会成为一份记忆,也许就在我退休之前。
再见了Flash,再见Adobe。


编写的ANE出现Extension context为null的解决

调用ANE的as代码:

会发现_context总是null,原因是jar的生成过程用的JDK1.7,ane对JDK1.7支持不好。 以前我都是用的1.6所以没注意到。

需要在编译的graddle里设置采用JDK1.6:


我的独立游戏-开心饭店上架了

开心饭店

开心饭店是一款策略为主的模拟经营游戏,靠你的聪明智慧,将一家小饭店逐步做大。带来壮观的客流量和丰厚的收入! 不同于大多数游戏,在这里,你是老板你做主,你不需要亲力亲为,你只要做决策。员工会按照你的部署搞定每天的正常营业!

行人在外面路过,有几率成为顾客进入店铺消费。厨师够棒,迎宾够美,自然顾客多多啦。

顾客的满意度至关重要,每个顾客的耐心都是有限的,得让顾客尽快受到很好的服务,一个跑得快的服务员必不可少,厨艺高超的厨师也会让顾客更满意。满意的顾客不仅付钱,还会产生人气,人气高了饭店才能越扩越大噢!

你的员工各自才干不同,敏捷高的人适合做服务员,厨艺好的适合做厨师,计算好的适合做收银员,魅力高的适合做迎宾。 店里四种职业各司其职、互相配合,服务顾客。雇佣到合适的人才,你就等着数钱吧!

除了核心的厨师服务员收银员迎宾互相配合的职业系统、菜式升级树、采购食材、招聘伙计、员工管理、店内道具、店铺装潢、店铺扩建等功能外,试想,送给厨师一本《膳食宝典》,不仅可以讨好厨师的忠心,还加厨艺点数多有趣?

 专题页面 |  App Store |  apk安装包


3D对象投射到2D视图的几个参数

FOV (Field of view) 视场

操纵FOV属性值,可以使得3D显示对象呈现出近大远小的样子。FOV属性表达的是一个角度,0~180度之间,表示透视投影的力度。数值越大,应用到显示对象上在z轴上的畸变越强。较小的值会使得缩放尺度很小、物体在空间内的先后距离会很微小。较大的值会导致更大的畸变、使物体呈现出更大的移动。最大值为179.99999……度,会得到极度的鱼眼镜头效果。最小值为0.0000……1,0和180都是非法值。

Projection Center 投影中心

投影中心表示的是透视投影的消失点。是一个偏移值,追加在默认注册点也就是舞台左上角(0,0)上。 呈现在观察者越远处的物体,往消失点歪斜,直到最终消失。想象看无穷长的大厅,你放眼望去,会看到墙体的边缘交汇在远处视线尽头的消失点。 如果消失点在舞台中心,大厅的最远处就在中心点消失。默认值通常是舞台中心。如果需要最远景消失在画面右侧,就把投影中心设为舞台的最右侧一点坐标。

Focal length 焦距

焦距表示 原始视图点(0,0,0)和显示对象自身z轴位置两者间的距离。 长的焦距类似长焦距镜头,有一个狭窄的视图、物体间的距离被缩短。短的焦距类似广角镜头,让你得到一个很宽广的视图但是有很大的畸变。中等焦距大约接近人眼看世界。 往往焦距是在透视变换(如物体移动)时动态重计算的,但你可以主动设置它。

默认的透视投影参数

  • FOV: 55
  • perspectiveCenter: stagewidth/2, stageHeight/2
  • focalLength: stageWidth/ 2 * ( cos(fieldOfView/2) / sin(fieldOfView/2) )

例如:当舞台大小500*500,设置以下值:

  • fieldOfView: 55
  • perspectiveCenter: 250,250
  • focalLength: 480.24554443359375

游戏设计与人的六大需求

我花费了许多时间思考电子游戏,远不止从概念到完工。无论制作还是玩或参与社区讨论,我意识到有些事情我想分享出来。

游戏设计既是有机感性的又是结构理性的,随着我越是与过程和结果打交道,我越意识到,在游戏设计中有些隐藏的核心价值,这些价值紧密联系了人的六大需求。一个游戏越切合这些价值/需求,主观上讲就越是好游戏。

第一关: 大海捞针

你可能知道,有海量的电子游戏在很多平台上发行,数量与日俱增,且每过一天,找到你会喜爱的游戏变得越来越难。例如,在Steam平台上的游戏,按“特色”、“受欢迎”、“新上”和“最近更新”排序。更深入到搜索选项中,会有风格、用户关键词、评级、用户评级和独特功能和分类。这虽然好,但绝对没有好过直接告诉我我会喜爱哪款游戏。最好仔细猜测。

[ 阅读全文 ]


页面:1234567...15