8

主题

1

回帖

349

积分

优秀创作者

积分
349
发表于  2023-6-8 10:02:15 | 显示全部楼层 |阅读模式 5202 0

算法教程

在学习这个算法之前,你需要初步了解单位移动,以及坐标系的基础知识,本教程只提供算法,不提供做法。

原文档可查看:https://docs.qq.com/doc/DZUZFZmhFV0VXdGlE


Part1. 环绕

魔兽里用的最多的算法之一就是环绕了,然而说到环绕,不得不提极坐标系(如下图):


和平面直角坐标系一样,极坐标系内的每个点也有两个参数 (r,θ)

r表示到圆心的距离,θ表示从0°逆时针旋转到该点的角度。


也许你还在思考平面直角坐标系中圆的公式:

但是这个方程却没办法转化为直观的环绕算式。说真的,为什么不尝试用极坐标系来思考这个图形呢?

圆的基本定义就是:到定点的距离等于定长的点的集合,而在一个极坐标系中,如果圆心就在原点的,那么我们只需要保持r不变,θ随时间递增就可以了。



如果用触发写,那就是这样:

        环绕:

                事件:

                        时间 - 每t秒触发事件

                条件:

                动作:

                        设置 - θ = θ + 1

                        单位 - 立即移动 环绕马甲 到(从 圆心 开始,距离为 r ,方向为 θ 度的位移处)


这里就不排泄了,毕竟我们只说算法,不过仍旧有一点要提醒,θ这个角度虽然在数学上一直这么增长下去是没问题的,不过在触发器里,这是个实数变量,有取值范围,所以永久的旋转记得要用mod公式进行处理。

极坐标和直角坐标是可以转化的,魔兽里用的单位坐标其实也是直角坐标系坐标,那么怎么转化呢?


从这个三角形中就能看出,(r,θ)这个点的X坐标就是r × cos θ,而Y坐标就是r × sin θ。(由此可见,数学基础还是很重要的)

因此,上面的环绕算法也可以写成:


写成触发就是这样:

环绕:

                事件:

                        时间 - 每t秒触发事件

                条件:

                动作:

                        设置 - θ = θ + 1

                        设置 - X = r × cos θ

                        设置 - Y = r × sin θ

                        单位 - 立即移动 环绕马甲 到(X , Y)

能够运用极坐标和直角坐标这可是一个熟练we玩家的基本素质哦。



Part2. 冲锋

魔兽里用的最多的算法之二就是冲锋了,说起冲锋,其实就是一条线段的运动轨迹,或许你会优先想到这样的直线方程:

Y = kX + b

X作为自变量,匀速变化,形成一个匀速运动,然而,有破绽。如果X是个固定的增量,那么Y的取值就受到直线斜率的影响了,马甲的实际移动距离就会随k值变化了。

因此,我们继续用极坐标系的思路来做这个运动,只要保持θ不变,r随时间增加就行,因为马甲移动距离就是r的增加量,所以只要r增速固定,马甲的移动速度就不会改变。

        冲锋:

                事件:

                        时间 - 每t秒触发事件

                条件:

                动作:

                        设置 - r = r + v

                        单位 - 立即移动 冲锋马甲 到(从 圆心 开始,距离为 r ,方向为 θ 度的位移处)


(这里v表示速度)

当然,改成平面直角坐标系也是一样的简单:

环绕:

                事件:

                        时间 - 每t秒触发事件

                条件:

                动作:

                        设置 - r = r+v

                        设置 - X = r × cos θ

                        设置 - Y = r × sin θ

                        单位 - 立即移动 冲锋马甲 到(X , Y)


到此,魔兽里最基本的两个算法就讲解完毕了。



Part3. 跳跃

魔兽里用的最多的算法之三就是跳跃了,说起跳跃,其实就是抛物线中的一段,这在物理和数学中都有提到,虽然是用的不同的方式,但是两种思路都能创建抛物线。

数学上的抛物线的公式是这样的:

Y = aX2 + bX + c

只要a<0就能形成开口向下的跳跃轨迹,而a的值也影响着抛物线的形状。

当然,这种原始的抛物线方程并不适合计算跳跃轨迹,通常,我们让起跳点处于X轴上,而让最高点处于Y轴上


只要a<0就能形成开口向下的跳跃轨迹,而a的值也影响着抛物线的形状。

一般跳跃首先都会确定下起跳点X1和落点X2,这段距离我们记作s

如果是跳跃的曲线形状相同,则公式简化成:

y = a (x + s/2)( x - s/2)

取值范围:( -s/2 < x < s/2)


如图所示,这种写法,跳跃的起点和终点就是 (-2,0) 和 (2,0),而前面的系数-0.5影响曲线的最大高度

如果是跳跃的高度相同(最高点高度都为H),则公式简化成:

取值范围:( -s/2 < x < s/2)


如图所示,这种写法,跳跃的高度为3,跳跃距离为10

跳跃:

                事件:

                        时间 - 每t秒触发事件

                条件:

                动作:

                        设置 - X = X+1

                        如果所有条件成立则做动作1,否则做动作2

                                if条件

                                        X 大于或等于 s/2

                                Then动作

                                        设置 - Y = a (X + s/2)( X - s/2)

                                        单位 - 立即移动 跳跃马甲 到(X , Y)

用这个算式之前我们要先设置好X的取值,设置好常数a的取值。

通常我们用抛物线都是做成立体的,这个算式里的Y就是飞行高度,只要调整好角度,你就能得到一个很简单的跳跃。当然,用另一个公式也能得到另一种抛物线。


前面说完的数学算法,接下来说说更容易理解的物理算法。

在物理上,跳跃运动可以分解为横向的水平运动和一个纵向的上抛运动。

横向运动就是冲锋的算法,不再解释。

纵向运动就要说说那个有关重力加速度的公式了:

t是自变量,表示时间,h是你当前离地面高度,a是下落的加速度,一般取负值,v0是起跳速率

这种做法,需要先确定出初速度v0和加速度a,好处是,坐标轴原点是你的起跳位置,你而且整个函数是实时计算,不需要在开始就确定落点的位置,对于跳过悬崖、地面隆起这种起、落点位置高度不一的地形,能更好的画出曲线。



这是一个参数方程,x代表时间,f(x)表示水平方向的位移,g(x)表示竖直方向的位移。


椭圆

椭圆目前应用较少,常见的有dota里凤凰的伊卡洛斯之击,兽王的飞斧使用了椭圆形轨道。

其实椭圆的最简单的理解就是横坐标或纵坐标被缩放的圆形。

毕竟圆形和椭圆方程有很大的相似之处:

圆形方程:

椭圆方程:

当然,这个算是仍旧不能作为魔兽里的轨迹算式,但是我们可以参考圆形的轨迹写出椭圆:


和前面圆形的参数方程有很高的相似度,仅仅是一个常数发生了变化。这也是椭圆最常用也最好用的轨迹。

(和圆形做法相似,就不再写触发范例了)


关于椭圆的角度偏移,并没有很好的算法,通常计算出点到中心的距离和角度,然后加上角度偏移,得到新的点,以此方法算出整个轨迹。

以上就是初级算法教程了,做图者和算法大神没必要继续往下看了,一来没卵用,二来浪费时间……



圆锥曲线

虽然最开始地方说了极坐标系很重要,然而后面教程多半是做的直角坐标系演示,于是决定补上一个极坐标公式:

方程如下:

r=ep/(1-e cosθ)

e表示离心率。如果e < 1,曲线为椭圆(越接近0则椭圆越圆,越接近1则椭圆越长),如果e = 1,曲线为抛物线,如果e > 1,则表示双曲线。

p表示焦点到准线的距离。


以上的图形都是以0°-180°线作为对称轴的,那么怎么能让图案变化角度呢?其实很简单:

只要在公式里用θ减去你想要逆时针旋转的角度就行。如图:


随机布点        圆形布点

通常圆范围内的随机布点常用:

r =(随机实数,最小值0,最大值X)

θ =(随机实数,最小值0,最大值360)

以(r, θ)创建极坐标位移点的方式进行随机布点。结果中心点密度高,周围密度低,就如下图:


而想获得均匀的布点,应该使用:

r =(随机实数,最小值0,最大值X2)的平方根

θ =(随机实数,最小值0,最大值360)

以(r, θ)创建极坐标位移点的方式进行随机布点。结果就能获得比较均匀的随机布点,如下图:


至于怎么理解,可以用上一些积分的思想。细的我就不说了,因为我也说不清……


        球面布点

对于球面的布点,最容易想到的则是分解成两个角度,一个角度是点到z轴的方向,另一个角度是从点到球心的线段与水平的夹角。

如果你使用如下算法:

θ1 =(随机实数,最小值0,最大值360)

θ2 =(随机实数,最小值0,最大值360)

Ux = R × cosθ1 × cosθ2

Uy = R × sinθ1 × cosθ2

Uz = R × sinθ2 + R

则得到的会是下边的随机布点球面:


这个球面在上部和下部点会很密集,如果换做顶视角会更明显


可以使用如下算法均匀布点

θ1 =(随机实数,最小值0,最大值360)

θ2 = arcsin(随机实数,最小值-1,最大值1)

Ux = R × cosθ1 × cosθ2

Uy = R × sinθ1 × cosθ2

Uz = R × sinθ2 + R


同样也需要一点积分的知识来理解,可以去网上搜索球体表面积的推导算法。