SCI/FreeSCI/Pathfinding/Implementation

Implementation

In this chapter we discuss the more important aspects of the implementation. In Section 6.1 we discuss the data types we used. Section 6.2 has some details on basic geometry functions and how they were used in the implementation. Some details on the implementation of the path-finding functionality can be found in Section 6.3. And Section 6.4 discusses the issue of rounding real numbers to integers.

This report does not contain the actual program text that we produced. The program text is spread across the following four files that can be found on-line:

• http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/engine/kpathing.c?op=file&rev=1571&sc=0
• http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/scicore/aatree.c?op=file&rev=1571&sc=0
• http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/include/aatree.h?op=file&rev=1571&sc=0
• http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/include/list.h?op=file&rev=1571&sc=0

Data types

As the input and output consists of all integers we decided to avoid floating point arithmetic whenever possible. The main reason is that floating point arithmetic can be very slow on hardware without a floating point unit, as the computations must be handled in software in that case. Furthermore, using integers guarantees that the computational results are exact, contrary to floating point arithmetic.

A potential pitfall here is overflow. However, in our case this is not a big problem as FreeSCI is written for machines with an integer size of at least 32 bits and the integer size in SCI is only 16 bits.

The two main choices for the polygon data type are an array of vertices, or a circular list of vertices. Arrays are convenient when vertices of a polygon are processed sequentially, but this is not the case here as the visibility graph algorithm processes the vertices by angle. Therefore we chose lists instead of arrays. As C does not provide any built-in list data types we took and modified the list macros from FreeBSD’s queue.h header file . We decided to order the vertices in such a way that the barred area is always left of an edge. That means that barred, total and near-point access polygons use anticlockwise ordering, and contained access polygons use clockwise ordering. As we have seen in Section 3.5, SCI games do not have such a fixed vertex ordering, so we added code to detect the current vertex ordering, and reverse it if necessary.

For the balanced search tree required for the visibility graph algorithm we implemented an Andersson tree . Andersson trees are easier to implement than other BB-trees yet offer similar performance. For storing the visibility graph itself we decided to use an adjacency matrix.

Basic geometry

We implemented basic geometry functions such as those in [9]. Some examples of those functions are:

• Left, which takes three points p₀, p₁ and p₂ and returns true if p₂ lies left of the directed line (p₀, p₁).
• Collinear, which takes three points p₀ , p₁ and p₂ and returns true if p₀, p₁ and p₂ are collinear.

These functions are the foundation for implementing some of the more complex functions. We give several examples in the remainder of this section.

Given two edges (p₀, p₁) and (p₁, p₂) we use Left to detect the convexity of the vertex at p₁. Namely, the vertex at p1 is convex if Left(p₀, p₁ , p₂). This relies on a fixed vertex ordering as described in Section 6.1.

As we described in Chapter 4, we need to compute the blocking point for keyboard support. The blocking point is the first intersection point p that is encountered when traveling the direct trajectory from start point s to end point t that has the property that the line (t, p) intersects the inside of the polygon that contains p, locally at p. We refer to this property as Inside(p, t). We make a case distinction on whether or not p lies exactly on a vertex. If p does not lie on a vertex it lies on exactly one edge (p₀ , p₁). Because of the vertex ordering we know that the inside of the polygon is left of that edge. This implies that Inside(p, t) if Left(p₀ , p₁, t). If p lies on a vertex there are two neighbouring vertices at p₀ and p₁. We now need to make another case distinction on the convexity of the vertex at p (using Left as demonstrated earlier in this section).

If the vertex at p is convex that implies that Inside(p, t) if Left(p₀ , p, t) and Left(p, p₁ , t). If the vertex at p is not convex that implies that Inside(p, t) if Left(p₀ , p, t) or Left(p, p₁, t).

One of the steps in the visibility graph algorithm is the ordering by angle of vertices around a specific point p. The angle is 0 for points on the ray extending right from p, and increases clockwise. Let α(q, p) denote the angle (in degrees) of point q relative to point p. We used the Qsort POSIX function to do the ordering. This function calls a callback function for comparing two elements (in our case points). The arctangent function could be used here to compute the two angles, but this function is generally very slow. We chose a different solution that is outlined below.

We partition the plane around p into two parts (we ignore the trivial partition {p} for which no angle can be determined). Partition A = {(x, y) ∈ ℤ²|y < y(p)∨(y = y(p)∧x > x(p))}, being the set of all points q for which 0 ≤ α(q,p) < 180. Partition B ={(x,y) ∈ ℤ²|y > y(p)∨(y = y(p)∧x < x(p))}, being the set of all points q for which 180 ≤ α(q, p) < 360.

If the two points p₀ and p₁ that are to be compared are not in the same partition the one in partition A is trivially at a smaller angle. Otherwise, p₀ and p₁ are in the same partition. Two things have been accomplished by partitioning the plane in this way. The first is that Collinear(p, p₀, p₁) holds if α(p₀, p) = α(p₁, p) (distance from p is the comparison criteria in this case). The second is that Left(p, p₀ , p₁ ) holds if α(p₁, p) < α(p₀ , p). We implemented the sorting by angle using Left and Collinear in this manner, thus avoiding the use of expensive trigonometry functions.

Pathfinding

The first step of ShortestPath is to check for both the start and end point whether it is contained in the barred area of any polygon in the polygon set P. If necessary, we then deal with this situation according to the specification in Chapter 4. If a start or end point p is contained in a total access polygon we remove that polygon from P. For other polygon types we compute the near point of p and use that for pathfinding instead. We add the original point p to the path during the post-processing phase. The only exception is the case where the end point is contained in the barred area of a barred or contained access polygon. In that case the path ends at the near point of p, rather than p.

We find the near point of p by first computing, for each edge e of P, the point on e that is closest to p. This is straightforward . If P has n vertices this gives us n candidates. Out of all the candidates at minimal distance from p we randomly pick one as the near point.

After the pre-processing step the start and end points are not strictly contained in the barred area of any of the polygons.

However, they may lie on an edge. Before we execute the visibility graph algorithm, we merge them into the polygon set, generally as a polygon of a single vertex. As the algorithm does not support intersecting polygons, we must be careful when merging a point p that lies on an edge of one of the polygons in the polygon set. In order to solve this problem we first check if a vertex is already present at p, if that is the case then we do nothing. If there is no matching vertex we check if there is an edge e = (p₀, p₁) that contains _p, if there is then we split _e into two edges (p₀, p) and (p, p₁). This ensures that no intersecting polygons are created. After executing the visibility graph algorithm we use Dijkstra’s algorithm to find a path in the visibility graph.

Rounding real numbers

Even though we use integers almost everywhere in the implementation we cannot completely avoid the use of real numbers. The two main instances where we use real numbers are when computing intersections and near points. We round the real numbers to integers right away. However, we must take care not to round to a point that is in the barred area of a polygon, because that would make that point unreachable. First we strengthen Assumption 2 as follows:

Assumption 3

Let P be the polygon set. For all points p ∈ ℚ² that lie on an edge of one of the polygons in P, there is at least one point p′ ∈ ℤ² at distance < √2 from p that is not strictly contained in the barred area of any polygon in P.

This means that besides intersecting polygons, we also exclude polygons that are very close together. It would be very hard to manoeuvre Ego between two such polygons with the directional keys on the keyboard. We therefore believe that the input polygon set will not contain polygons that are very close together.

When rounding a point p ∈ ℚ² we first try the closest point p′ ∈ ℤ². If p′ is contained in the barred area of a polygon we try all other points in ℤ² at a distance less than √2 from p until we find one for which this is not the case.

References