1.4.2  邻近性检测算法

在前面的代码示例中，我们讨论了一种检测两个限定框邻近性的简单方法。这里我们将介绍计算圆形之间以及圆形和正方形之间邻近性的其他方法。

此类算法的基本思想是首先计算两个对象中心之间的距离，然后检查某个公式的值，该公式近似地描述了对象的形状。而该方法则如同用来近似对象形状的公式一样精确，例如，在台球模拟游戏中，使用恰当的公式就可以对球之间的冲突检测获得非常好的效果。

一些最常见的公式可以用来计算正方形、圆形和多边形之间的距离。

1. 计算圆形对象之间的冲突

图1-13说明了针对那些可以用圆形框来近似表示的图形的邻近性检测算法。

当处理圆形对象时，使用毕达哥拉斯定理可以获得理想的计算效果，该定理允许使用直角三角形的其他边(除斜边外的其他两条边)平方和的平方根来计算对象中心之间的距离(即直角三角形的斜边)。

图1-13  圆形对象的邻近性检测

Dim Dx As Single = Math.Abs(Object1.CenterX - Object2.CenterX);

Dim Dy As Single = Math.Abs(Object1.CenterY - Object2.CenterY);

Dim double Distance As Double = Math.Sqrt(Dx*Dx + Dy*Dy);

If (Distance > Object1.radius Radius + Object2.radiusRadius Then)

// => The circles do not collide.

Else

// => The circles are overlapping.

End If

如果仅仅希望使用一个常量值检测距离，则不必计算它的平方根，从而使得操作更加快速。

2. 计算圆形和正方形之间的冲突

接下来要介绍的算法实际上是一个普遍使用的公式，我们称之为Arvo算法(Arvo’s Algorithm)(该算法是以Jim Arvo的名字命名的，此人提出了许多图形算法)。算法基于一个法则，该法则类似于圆形之间的邻近性检测，它再次使用毕达哥拉斯定理来帮助判定圆形和正方形是否相交。图1-14描述了圆形和正方形之间可能发生的一些不同的邻近类型。

图1-14  正方形/圆形之间的邻近

在介绍算法前，首先创建一个代码单元，即一个类，它描述了“按轴线排列限定框”的外观。使用一个类创建多个AABB(称作对象)，这是面向对象编程方法的核心思想，关于这一点，我们将随着内容的不断深入而更加详细地进行这方面的介绍。目前为止，您应该已经具备了初学者对VB语法的初步理解，因而对如下的类描述也应该感到非常熟悉：

Public Class AxisAlignedBoundingBox

Private centerXCenterX, centerYCenterY As Single ' Coordinate centers of the box

Private extentExtentX, extentExtentY As Single

' Extents (width from center) of X and Y Constructor

Public Sub New(CenterX As Single, CenterY As Single, _

ExtentX As Single, ExtentY As Single)

'Constructor details go here

End Sub 'New

Public ReadOnly Property MaxX() As Single

Get

Return CenterX + ExtentX

End Get

End Property

Public ReadOnly Property MinX() As Single

Get

Return CenterX - ExtentX

End Get

End Property

Public ReadOnly Property MaxY() As Single

Get

Return CenterY + ExtentY

End Get

End Property

Public ReadOnly Property MinY() As Single

Get

Return CenterY - ExtentY

End Get

End Property

Public Function CircleIntersect(CircleCenterX As Single, _

CircleCenterY As Single, Radius As Single) As Boolean

'Intersetcion method goes here

End Function 'CircleIntersect

End Class 'AxisAlignedBoundingBox

现在，我们已经简单描述了类，接下来介绍CircleIntersect方法：

Public Function CircleIntersect(CircleCenterX As Single, CircleCenterY As Single,

_

Radius As Single) As Boolean

Dim Dist As Single = 0

' Check X axis. If Circle is outside box limits, add to distance.

If CircleCenterX < Me.MinX Then

Dist += Math.Sqr(CircleCenterX - Me.MinX)

Else

If CircleCenterX > Me.MaxX Then

Dist += Math.Sqr(CircleCenterX - Me.MaxX)

End If ' Check Y axis. If Circle is outside box limits, add to distance.

End If

If CircleCenterY < Me.MinY Then

Dist += Math.Sqr(CircleCenterY - Me.MinY)

Else

If CircleCenterY > Me.MaxY Then

Dist += Math.Sqr(CircleCenterY - Me.MaxY)

End If ' Now that distances are added, check if the square

End If ' of the Circle's radius is longer and return the Boolean result.

Return Radius * Radius < Dist

End Function 'CircleIntersect

图1-15显示了圆和邻近某个“角”的AABB相交时的计算情况。

图1-15  执行正方形/圆形邻近性检测算法

如果您觉得这部分内容数学味太浓的话，那么可能应该暂时放弃本书的学习而去回顾一下数学要求不是很高的书籍了。坦率地说，我们并不过多强调数学对于计算机游戏开发而言有多么重要。但是，基本的代数学和几何学知识对于简单游戏的开发是一个起码的要求，并且您将很快发现，在您的游戏开发职业生涯中，要想成为一个高效的开发者，必须使用更高层次的线性代数知识和物理学知识来支持。而且，与游戏开发有关的90%以上的程序都与数学有关(由此可见代数的重要性)。