Archive:Collision determination

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 give 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_x² <= (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 give 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 give 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 give 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 give 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 give 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.

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.
• Check for a region 4 intersection.
• Calculate sin(alpha), cos(alpha), sin(beta) and cos(beta) and store them in temporary variables.
• Calculate the coordinates of point A.
• Check for a region 3 intersection.
• Calculate the coordinates of point B.
• Check for a region 2 intersection.
• Calculate the coordinates of point P in coordinate system 2.
• Check for a region 5 intersection.
• Calculate the coordinates of point P in coordinate system 3.
• Check for a region 6 intersection.
• Calculate the coordinates of point P in coordinate system 1.
• Check for a region 1 intersection.

Any but the first three steps can be moved, if that is found to be more appropriate. The algorithm includes 4 calls to a trigonomic function and just 1 division.

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.