This article is currently only a proposal

The features or design guidelines described in this article are only a proposal made by one or some persons. It has not been evaluated or accepted by the core development team yet. Feel free to add your personal opinion about them or make counter proposals.

This page was created to document the collision detection algorithms used in The Mana World. After the algorithms are converted to C++ and added to the code base it is very difficult to verify the assumptions and math of the author. Therefore an explanation of the algorithms used, is given below. Of course any improvements or clarifications can allso be added and discussed on this page.

Strictly speaking, the algorithms discussed here, compute if two geometric figures intersect. However, the result is then used in a dynamic game. In the game world two objects will collide if their movement areas intersect.

Circle-Sector with Disk

By Avaniel 20:37, 27 February 2007 (CET)

In order to determine if a circle-sector and a disk collide, we start with transforming the coordinates of the 2d space in such a way that the center of the circle-sector is located at the origin. The circle-sector can then be defined by a radius R, a half-top-angle alpha and a placement angle beta, as shown in diagram (1).

The disk can simply be defined by its center-point P and its radius R_P, where point P can be anywhere in the 2d space. See diagram (CSD-1) for an overview.

Diagram (CSD-1) - Overview of the Circle-Sector and Disk

In order to determine if the circle-sector and the circle intersect, the x-y plane is divided in 6 Voronoi like regions. The regions are based on the vertexes O-A, O-B and the arc A-B. They are shown in diagram (CSD-2).

Diagram (CSD-2) - The x-y plane divide in 6 'Voronoi' regions

For each region it is now determined what the pre-conditions for an overlap are, if P is in that region. If necessary, the pre-conditions for point P being in the region will be derived as well.

In the following text, a subscript x and y are used to indicate x and y coordinate of a point. If the coordinates considered are in a tranformed coordinate system, an extra indicator will be added. For example the x-coordinate of point A in the x₁-y₁ coordinate system is denoted as: A_x1

Region 1

Region 1 is highlighted in diagram (CSD-3), it includes the interior of the Circle-sector. For region 1, the coordinates for point P are transformed to coordinate system 1 (shown in diagram (CSD-4)). An example of a region 1 collision is given here.

Diagram (CSD-3) - 'Voronoi' region 1 highlighted

Diagram (CSD-4) - Coordinate system 1

The coordinates for point P in coordinate system 1 are:

P_x1 = P_x cos(beta-alpha) + P_y sin(beta-alpha)

P_y1 = P_y cos(beta-alpha) - P_x sin(beta-alpha)

Using goniometric relations this can be simplified to:

P_x1 = P_x {cos(alpha)cos(beta) + sin(alpha)sin(beta)} + P_y {-sin(alpha)cos(beta) + cos(alpha)sin(beta)}

P_y1 = P_y {cos(alpha)cos(beta) + sin(alpha)sin(beta)} - P_x {-sin(alpha)cos(beta) + cos(alpha)sin(beta)}

Point P is inside region 1 if

P_x1 >= 0 , P_y1 >= 0 and P_y1 <= P_x1 tan(2alpha) = P_x1 {2sin(alpha)cos(alpha) / (cos²(alpha) - sin²(alpha))}

The Circle-sector and the disc then intersect if

P_x² + P_y² <= (R + R_P)²

Region 2

Region 2 is highlighted in diagram (CSD-5). For this region no coordinate transformations are necessary. An example of a region 2 collision is given here.

Diagram (CSD-5) - 'Voronoi' region 2 highlighted

If point P is inside region 2, the circle-sector and the disk can only intersect if point B is inside the circle.

(P_x - B_x)² + (P_y - B_y)² <= R_P²

The coordinates of point B are:

B_x = R cos(alpha + beta) = R {cos(alpha)cos(beta) - sin(alpha)sin(beta)}

B_y = R sin(alpha + beta) = R {sin(alpha)cos(beta) + cos(alpha)sin(beta)}

With the coordinates for B the condition can now be evaluated.

Region 3

Region 3 is highlighted in diagram (CSD-6). For this region no coordinate transformations are necessary. An example of a region 3 collision is given here.

Diagram (CSD-6) - 'Voronoi' region 3 highlighted

Analogous to region 2, the circle-sector and the disk can only intersect if point A is inside the disk. The condition for this is:

(P_x - A_x)² + (P_y - A_y)² <= R_P²

The coordinates of point A are:

A_x = R cos(-alpha + beta) = R {cos(alpha)cos(beta) + sin(alpha)sin(beta)}

A_y = R sin(-alpha + beta) = R {-sin(alpha)cos(beta) + cos(alpha)sin(beta)}

With the coordinates for A the condition can now be evaluated.

Region 4

Region 4 is highlighted in diagram (CSD-7). For this region no coordinate transformations are necessary. An example of a region 4 collision is given here.

Diagram (CSD-7) - 'Voronoi' region 4 highlighted

Analogous to regions 2 and 3, the circle-sector and the disk can only intersect if point O is inside the disk. The condition for this is:

P_x² + P_y² <= R_P²

Region 5

Region 5 is highlighted in diagram (CSD-8). For region 5, the coordinates for point P are transformed to coordinate system 2 (shown in diagram (CSD-9)). An example of a region 5 collision is given here.

Diagram (CSD-8) - 'Voronoi' region 5 highlighted

Diagram (CSD-9) - Coordinate system 2

In the local coordinates the following conditions for P being in region 5, can be formulated:

P_x2 <= 0, P_x2 >= -R and P_y2 >= 0

The condition for the circle-sector and the disk intersecting is:

P_y2 <= R_P

The coordinates for P in coordinate system 2 are given by:

P_x2 = P_xcos(alpha + beta + pi) + P_ysin(alpha + beta + pi)

P_y2 = P_ycos(alpha + beta + pi) - P_xsin(alpha + beta + pi)

Using the goniometric relations to handle the pi term first, the coordinates become:

P_x2 = -P_xcos(alpha + beta) + P_ysin(alpha + beta )

P_y2 = -P_ycos(alpha + beta) - P_xsin(alpha + beta )

Now using the goniometric relations to seperate alpha and beta:

P_x2 = -P_x{cos(alpha)cos(beta) - sin(alpha)sin(beta)} + P_y{sin(alpha)cos(beta) + cos(alpha)sin(beta)}

P_y2 = -P_y{cos(alpha)cos(beta) - sin(alpha)sin(beta)} - P_x{sin(alpha)cos(beta) + cos(alpha)sin(beta)}

The conditions can now be evaluated.

Region 6

Region 6 is highlighted in diagram (CSD-10). For region 6, the coordinates for point P are transformed to coordinate system 3 (shown in diagram (CSD-11)). An example of a region 6 collision is given here.

Diagram (CSD-10) - 'Voronoi' region 6 highlighted

Diagram (CSD-11) - Coordinate system 3

In the local coordinates the following conditions for P being in region 6, can be formulated:

P_x3 >= 0, P_x3 <= R and P_y3 >= 0

The condition for the circle-sector and the disk intersecting is:

P_y3 <= R_P

The coordinates for P in coordinate system 3 are given by:

P_x3 = P_xcos(alpha + beta) + P_ysin(alpha + beta)

P_y3 = P_ycos(alpha + beta) - P_xsin(alpha + beta)

Now using the goniometric relations to seperate alpha and beta:

P_x3 = P_x{cos(alpha)cos(beta) - sin(alpha)sin(beta)} + P_y{sin(alpha)cos(beta) + cos(alpha)sin(beta)}

P_y3 = P_y{cos(alpha)cos(beta) - sin(alpha)sin(beta)} - P_x{sin(alpha)cos(beta) + cos(alpha)sin(beta)}

The conditions can now be evaluated.

Bounding Circle

The above laid out method is mathematically accurate and sufficient. However, it is not very fast. By applying a bounding circle and checking if the disk intersects with that, a lot of the work above can be simplified to just a few equations. An overview of the bounding circle is given in diagram (CSD-12). For these calculations coordinate system 4 will be used, which is shown in diagram (CSD-13).

Diagram (CSD-12) - Overview of the bounding circle

Diagram (CSD-13) - Coordinate system 4

The radius of the bounding circle R_C is given by:

R_C = R / (2*cos(alpha))

The coordinates of the center point in coordinate system 4 are then given by:

C_x4 = R / (2*cos(alpha))

C_y4 = 0

The coordinates for P in coordinate system 4 are given by:

P_x4 = P_xcos(beta) + P_ysin(beta)

P_y4 = P_ycos(beta) - P_xsin(beta)

The condition for the disk intersecting the bounding circle is then given by:

(P_x4 - C_x4)² + (P_y4 - C_y4)² <= (R_P + R_C)²

Inserting the values for C_x4, C_x4 and R_C, into the condition yields:

(P_x4² + P_y4²)*cos(alpha) - P_x4*R <= R_P²*cos(alpha) + R_P*R

To achieve this result, both sides where multiplied by (2*cos(alpha)), which means that an extra condition is imposed.:

cos(alpha) > 0; alpha < 90^o

Together with the observation that the bounding circle becomes infinitly large at a value for alpha of 90^o, we have to limit alpha to a maximum of 85^o, for practical reasons.

The condition can now be evaluated.

The Algorithm

The following values need to be given; the radius of the circle-sector R, the half-top-angle alpha, the placement angle beta, the coordinates of the center of the circle-sector, the coordinates of the center of the disk P and the radius of the disk R_P.

• Subtract the coordinates of the center of the circle sector from the coordinates of point P, thereby obtaining the coordinates of P in the primary coordinate system.
• Calculate sin(alpha), cos(alpha), sin(beta) and cos(beta) and store them in temporary variables.
• Calculate the coordinates of point P in coordinate system 4.
• Check for an intersection with the bounding circle.
  • Return false if there is no intersection.
• Calculate the coordinates of point P in coordinate system 1.
• Check if P is is region 5 (realising that coordinate system 2 is the exact opposite of coordinate system 1).
  • Check for a region 5 intersection. Return the result.
• Calculate tan(2alpha).
• Check if P is is region 1.
  • Check for a region 1 intersection. Return the result.
• Calculate the coordinates of point P in coordinate system 3.
• Check if P is is region 6.
  • Check for a region 6 intersection. Return the result.
• If P is not in region 1, region 5 or region 6, but the disk does intersect the bounding circle, then the intersection must be in region 2, region 3, or region 4.

Any but the first five steps can be moved, if that is found to be more appropriate. The algorithm includes 5 calls to a trigonomic function.

In the current combat implementation sin(beta) and cos(beta) do not need to be calculated at runtime. Beta is determined by the direction the attacker is facing. There are only four possible values for beta; 0, pi/2, pi and pi*3/2. Because the half-top-angle is a property of the weapon used, sin(alpha), cos(alpha) and tan(2alpha) could be computed on startup of the game-server and stored for use.

Simplified collision test

By Bjørn 00:32, 28 February 2007 (CET)

Since our enemies aren't exactly circles anyway, I'm prepared to do away with some of the above complexity. However if the above is efficiently and understandable enough, I'm prepared to go with it. What I would propose is visualized as follows:

Overview of a simplified test

In essense, the gradiented area is checked for collision instead of the exact circle. It would only require the areas with blue and red dotted lines to be checked on intersection and the circle radii to be checked for proximity. Something like:

blueA = dir - widenessAngle

blueB = dir + widenessAngle

redA = cos(diskY / diskX) - cos(diskRadius / dist)

redB = cos(diskY / diskX) + cos(diskRadius / dist)

diskDist = sqrt(diskX*diskX + diskY*diskY)

collision = redA < blueB && redB > blueA && diskDist - diskRadius < circleRadius

Ok that's two trigonomic function calls, two divisions and one sqrt (which could be avoided when circleRadius and diskRadius where given in their squared form).

The squareroot can be avoided by using:

diskDist² <= (diskRadius + circleRadius)²

However all the trigonomic function calls, contain a distance and are not cacheable (in a meaningfull way).

Avaniel 01:30, 28 February 2007 (CET)

Hmm, or maybe I should just let the pros handle this...