人工智能、数理算法

oraclelang

　一旦我们更新了碰撞中的个体，下一步工作就又回到寻找优先权最高的个体的碰撞上来了。我们将一直重复这一步骤直到所有的碰撞都被解决。

　　你可以在两个地方使用这一系统：碰撞解决部分或碰撞预测系统中。碰撞解决的规则必须被修改以适应对于个体优先级的要求，这样的修改并不难，但会增加一定的代码量。或者你可以修改你的碰撞预测系统使得只会发生两个个体碰撞的情况，然而这样做你仍然需要先找出一次碰撞中的全部个体并作出操作。

解决堆叠峡谷问题(The Stacked Canyon Problem)

　　所有移动系统的最终目的都是要实现智能的移动效果，而所有处理中最能体现智能的就是处理堆叠峡谷问题了(什么是堆叠峡谷问题呢？事实上当一个个体要从一群排列紧凑的个体之间穿过时所需要解决的问题就是堆叠峡谷问题，图21就是一个例子)。虽然此类问题并不能简单的一次解决，但我们可以重用前面的一些简单方法来解决它。


图21.堆叠峡谷问题

oraclelang

第一步是鉴定是否为一个堆叠峡谷问题。这是非常重要的，因为我们将要利用前进个体(driving unit)的优先级。当然我们可以利用每个个体自身的优先级来要求其它个体让出道路，但是更好的解决方法是使用前进个体的优先级。判断一个堆叠峡谷问题可以有两种方法：观察前进个体是否会把一个阻碍其移动的个体推到另一个身上或者观察移动个体的碰撞列表以寻找多重的碰撞。不论采用哪种方法，被推动的个体都应该拥有与前进个体相同的移动优先级。

oraclelang

一旦我们判断出将要解决一个堆叠峡谷问题，就可以采用一种简单的递归调用个体协调运动系统的方法来解决它。把第一个被推动的个体作为前进个体处理其于第二个个体之间的关系，并如此循环。每一个个体被它的前进个体推动直到它可以移动到一边而让出道路。当最后一个个体也从陆上让开后，原来的前进个体就可以继续移动了。

oraclelang

　一个好的习惯是将已经移开的个体在移回原位。为了能够这样做，我们应该记录整个推动过程并在问题解决后倒序的执行该过程。另外如果负责移动的代码能够辨别出前进个体是否归属于一个组队，那就能保证组队中每个个体都能在原来阻碍道路的个体返回原位置之前通过。

注意

优化你的整体系统。如果你只是要做一个2D游戏，那就会有许多多余的计算是可以取消和简单化的。不论你是要做2D游戏还是3D的，你的碰撞检测系统都需要一个优秀的经过优化的个体分拣系统，这类系统已经不再仅仅用于绘图了。

对高级寻道和低级寻道使用不同的方法。过去大多数游戏对这两种寻道方式使用相同的算法。这样做的害处是如果对高级寻道使用低级寻道的算法将使高级寻道变得缓慢并且不能用于寻找长的通路；相反的，如果对低级寻道使用高级寻道的算法将会造成结果并没有将道路上的所有障碍物考虑在内或者造成一个个体能从其它个体之中穿过。一定要抓住要点制作两套寻道系统。

oraclelang

无论你做什么，个体总会交叠碰撞在一起。个体的交叠和碰撞是不可避免的，或者按最好情况说将是非常难以操作的。你最好尽早处理这些碰撞问题，这将使你的游戏更好一些。游戏的地图已经越来越复杂了，并且还会加入随机地图的处理。一个好的移动系统将能够很好的处理随机地图和相应的一切细节。

清楚地了解UL是怎样影响个体移动的。可变化的UL时间将是你的移动系统所必须解决的一大难题。可以使用一个简单的修正机制来解决此类大部分的问题。

只涉及单个UL的做法是过时的。没有计划的编制不可能解决好个体移动的协调问题，如果不记录上一次UL中的操作和将来要发生的问题又是不可能制作好的计划的。一个能够运作良好的移动协调系统必须在任何时候都能够参考以前的碰撞列表和预测碰撞的列表。切记解决碰撞的过程中出现的较小的变化是可以忽略的。

oraclelang

不要再出现傻乎乎的个体移动


　　简单的个体移动是简单的。一套优秀的协调系统是我们所应该追求的，因为它能使你的游戏步上一个等级并能增加玩家的乐趣。在本次的文章中我们研究了一个移动协调系统的基础功能--使用多个UL时间制定行动计划以及一套可以解决任何两个个体碰撞的方法等等。现在你应该不会再满足于你的游戏中那些傻乎乎的个体移动了。

oraclelang

一、引言

　　计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。

二、目录

oraclelang

三、算法介绍

　　矢量的概念：

　　如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。

　　矢量加减法：

　　设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P，P - Q = - ( Q - P )。

oraclelang

　矢量叉积：

　　计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = ( x1, y1 )，Q = ( x2, y2 )，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P × Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。

　　叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：

　　若 P × Q > 0 , 则P在Q的顺时针方向。
　　若 P × Q < 0 , 则P在Q的逆时针方向。
　　若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向

oraclelang

折线段的拐向判断：

　　折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向：

　　若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。

　　若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。

　　若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线