ToDo/Pathfinding/Patent

Patent

In Section "Patents and infringement" we provide a brief discussion on patents and patent infringement. In Section "Sierra's pathfinding patent" we summarize Sierra's pathfinding patent.

Patents and infringement

A patent gives its holder the right to exclude others from using his or her invention. In exchange for that right the patent holder must fully disclose the invention in the patent document. After the patent expires others may use the invention. A patent document consists of two parts, the specification and the claims.

The specification section describes the invention in detail using everyday language. The claim section defines exactly what is patented. It uses a legal jargon that is difficult to understand for non-patent professionals. Information on how to interpret patent claims can be found in. For some patents infringement can be avoided by providing extra functionality on top of what is patented. Whether or not this is the case depends on the exact wording of the claims. For Sierra's pathfinding patent this is not the case. This means that a substantially different algorithm is required to avoid infringement.

Sierra's pathfinding patent

The AvoidPath input consists of a start point and an end point and a set of constraining polygons. The output is a path from start point to end point that does not violate any constraints. The patent states that polygons can be assumed not to be self-intersecting. The patent further implies that a point cannot be inside two or more polygons. From that we conclude that any two polygons can be assumed not to intersect. The patent describes three optimization levels. We label these from 0 (no optimization) to 2 (maximum optimization). The optimization levels determine how optimized (in terms of length) the returned path will be.

The patent mentions three types of polygons. The first type is the barred access polygon that cannot be entered. The second type is the total access polygon that cannot be entered unless the start or end point is inside the polygon. The third type is the near-point access polygon. For a point p and a polygon P the near point is a point on the edges of P at minimal distance from p. A path may start in a near-point access polygon, but it must exit the polygon through the near-point. Similarly, a path may end in such a polygon, but it must enter the polygon through the near-point. The patent does not accurately describe the semantics of the different polygon types so we had to determine them in another way. We discuss this in Polygon types section.

The patent describes AvoidPath as consisting of three phases, namely a pre-processing phase, a pathfinding phase and a post-processing phase. Even though the pre- and post-processing phases are briefly explained in the patent specification, they are not mentioned in the claims and are therefore not patented. During the pre-processing phase the input is transformed in such a way that the start and end points are not inside any polygon, and that all polygons in the set may not be entered. For example, if the start point is inside a total access polygon that polygon is removed from the polygon set. If the end point is inside a near-point access polygon the end point is moved to the near-point and the original end point will be appended to the previously computed path in the post-processing phase.

We now proceed with describing the pathfinding phase, limiting ourselves to the most important aspects. The basic idea behind the algorithm is to construct a path that follows the direct trajectory from start point to end point, except where the trajectory properly intersects a polygon (this is covered by claim 6 of the patent). If the direct trajectory properly intersects a polygon P, then there must be more than one intersection point. Let p be the intersection point closest to the start point, and q be the intersection point closest to the end point. The computed path reaches p on the direct trajectory, then goes from p to q along the edges of the polygon and then resumes the direct trajectory. There are two ways to walk from p to q; the algorithm takes the shortest one. Optimization level 0 returns such a path, as illustrated in the Figure 1.

Figure 1: A path from s to t at optimization level 0.

Figure 2: A path from s to t at optimization level 1.

At optimization level 1 the algorithm tries to optimize this path. It does this by attempting to shortcut any two nodes. A shortcut is only possible if it does not properly intersect any polygon in the polygon set. See Figure 2 for an illustration of an optimized version of the path in Figure 1.

The resulting path is not the shortest path from s to t. The reason for this is that at optimization level 0 the shortest way about each individual polygon is chosen. However, it is very possible that the shortest path takes the longer way about one or more of the polygons. Optimization level 2 takes care of this by trying all permutations of ways to walk about the polygons. For n polygons this yields 2ⁿ combinations. The algorithm chooses the shortest path out of all of these. As can be seen in Figure 3, the shortest path is indeed found for this input.

This raises the question of whether or not the algorithm is able to determine the shortest path for any input. This is not the case, as is demonstrated by the counterexample in Figure 4. The shortcut from v₀ to t cannot be taken as this would intersect polygon W. So the final path will go from v₀ to t via v₁, even though it is much shorter to go there via w₀. Point w₀ is never considered for the path as it is part of a polygon that is not intersected by the direct trajectory from s to t. This illustrates that this algorithm does not guarantee a shortest path, even at the highest optimization level.

Figure 3: A path from s to t at optimization level 2.

Figure 4: Polygons V and W and a path from s to t at optimization level 1 or 2.

The patent further makes an important note about polygon edges that lie along the display border. It is undesirable to have the path use the display border unnecessarily as this might trigger the game into loading an adjoining game scene. In order to prevent the shortest path algorithm from using polygon edges that lie along the display border, the distance for such edges is defined to be infinity.