1 Smoothing Voronoi-based Path with Minimized Length and Visibility using Composite Bezier Curves Ilya Makarov 1 and Pavel Polyakov 2 1 National Research University Higher School of Economics, Department of Data Analysis and Artificial Intelligence, 3 Kochnovskiy Proezd, 125319 Moscow, Russia, iamakarov@hse.ru, revan1986@mail.ru http://www.hse.ru/en/staff/iamakarov 2 National Research University Higher School of Economics, 3 Kochnovskiy Proezd, 125319 Moscow, Russia, polyakovpavel96@gmail.com Abstract. We present an obstacle avoiding path planning method based on a Voronoi diagram. We use a tactical visibility measure to obtain the shortest path length with the lowest local probability to be discovered based on the map topology. A Voronoi-based navigation mesh for finding the shortest smooth path with the lowest visibility along the path is used. The piecewise linear rough path in the Voronoi diagram is compared with collision free composite Bezier curves with shortest curve length. Whether we use visibility component or not, the smooth path length does not differ more than 12%. This allows us to use tactical information from map geometry without significant loss in path length. Keywords: Path Planning, Voronoi Diagram, Bezier Curve 1 Introduction Path planning and path finding problems play one of the main topics in robotic and automation fields, especially for dynamically changing environments. There are a large variety of algorithms for different tasks, such as in [1], [2], [3], [4], [5]. In [6] J. Reif proved that the path planning problem is PSPACE-complete. In addition to the storage problem, Reif also proved that the path planning prob- lem is NP-complete. The exponential time and storage requirements combined together create an open research problem. The path planning is represented by two diverse strategies, separating offline computing of initially known BOT and global characteristics from constructing sensor-based local environment. Voronoi diagrams are the simplest case of a k -nearest neighbour classification rule with k = 1 . There are certain types of continuous locational optimization problems that can be solved through modifications of the Voronoi diagram (see [7]). In game programming, Voronoi diagrams are used to make a partition of a navigation mesh to find a collision free path in both global [1] and local environ- ments [4,8]. The path is a piecewise linear path or a curve smoothed with the help 2 of splines. In the first case, the actor movements look bad when programming BOT with human-like behavior. The smooth path is constructed by connecting splines with some functional property, such as continuity of the first or second derivatives. The resulting path should be continuous itself. The authors of [9,10] make a path by splines through the way points on a map. A rather different approach is presented in the works by [2,4,11,12], in which authors use Bezier curves to construct the path based on obstacle vertices’ points. We combine these two approaches by choosing composite Bezier curves to implement the second strategy of writing obstacle-avoiding path. In [2] the au- thor started to use a set of control points for one Bezier curve instead of using the reference points as way points. In [13] the connection of reference points by taking each point as a way point leads to longer path length, by comparing to their connection by taking each point as a control point of Bezier curves. Using a composite Bezier curve they obtain a reduction of 8.33% of the path length. In this paper, we propose an obstacle avoiding smooth path planning algo- rithm with visibility component. We increase the average path length without visibility in comparison to the works [13,14] to obtain more realistic trajectories. 2 Voronoi-based navigation mesh 2.1 Definition Regular navigation meshes consisting of convex polygons without any additional constraints seem to be perfect for path finding only until we need to calcu- late navigation characteristics using tactical properties of a map. Different ap- proaches can be used to achieve this goal. However, without applying structural changes to the navigation mesh itself they are either not efficient enough or too difficult to implement. In this paper, we study a special navigation mesh type called Voronoi-based navigation mesh, which is designed to find paths consider- ing properties such as visibility/cover, curvature of path trajectory and general penalties for traveling in particular areas. Let P = {p0 , p1 , . . . , pn } be a set of points (called sites) placed on a map manually or automatically with precom- puted tactical properties. Let V D(pi ) = {x : |pi − x| ≤ |pj − x|, ∀j 6= i, x ∈ R2 } (1) be polygons of a navigation mesh. To support multi-layered environments, sev- eral surfaces (simply connected closed surfaces with Z = const ) are also placed on a map. Each surface determines an area where a Voronoi diagram should be constructed, before being projected on a level geometry. A union of diagrams constructed in all surfaces is called a Voronoi-based navigation mesh. Examples of such map partitions are shown on Figure 1 and Figure 2. The navigation area is similar to Riemann’s variety and is homeomorphic to the plane R2 . 3 Fig. 1. VD-based Navigation Mesh Fig. 2. Navigation Links 3 Construction and Memory Storage of Voronoi Diagram 3.1 Voronoi diagram The Voronoi diagrams (VD) in each surface are independently computed in Θ(n log n) time using Fortune’s algorithm presented in [15]. The polygons lying outside an area determined by the corresponding surface are discarded. A dia- gram itself is stored in DCEL format, which guarantee Θ(n) memory footprint. The number of vertices and edges of VD are not greater than 2n and 3n , re- spectively. In addition, a quad tree for each diagram is built so that the solution to the point location problem can be found in short time. In [16] authors give a new randomized incremental algorithm for the con- struction of planar Voronoi diagrams in O (n log n) time and O (n) space. Im- provements of this work can also be found in [17]. 3.2 Projection and obstacle detection First, the polygon vertices are projected from surface’s Z onto the geometry. It is important to move vertices at some ε –height above the ground so that obstacle detection will work correctly for non-flat areas, such as stairs or hills. After that, the polygon’s Z is calculated as an average of its vertexes. Once navigation mesh is properly located in 3D space, a number of geome- try flags for each polygon can be computed. We iterate through all edges of a mesh (there are Θ(n) edges) and perform the following: obstacle collision check along an edge; ground collision check under an edge; height above an edge eval- uation for both crouch and jump. These flags are then copied from edges to adjacent polygons using logical OR. That is a way to gather information about the geometry of each polygon. This step requires Θ(n) ray casts. 4 3.3 Building navigation links This step requires the exploration of jump-points on a navigation mesh and O (n2 ) ray casts in worst case. In practice, this number can be greatly reduced to O (n) on real maps with bounded gravitation fields. For each of the polygons lying near the surface border, we use the following strategy to find link candi- dates: polygons should belong to different surfaces, both be navigable and the distance between the Voronoi sites inside them should not exceed a constant d derived from gravity field. A set of polygons lying within a range d from a given one in each surface can be found using a corresponding quad tree. In addition, link candidate is eliminated if a segment of polygons’ sites intersects the edge of the border face which is not near the border. Each link candidate is tested with two possible scenarios: jump (Figure 2) and walking off a ledge. The first one can be checked with a few ray casts and physics calculations. The second one minimizes unnecessary jumping and requires a number of ground height checks between two polygons. 3.4 Calculating tactical properties We introduce a method for calculating visibility as a characteristic of Voronoi regions areas. All the values are computed offline as parts of map tactical prop- erties and can be combined with on-line computed enemies’ locations frag map. Let visibility be a value from 0 to 1 indicating the amount of area visible from a polygon within a given range. One may argue how visibility should be converted into a number, but in fact, it gives us believable tactical results. Similar algorithm of calculating tactical map properties are presented in [18]. for Polygon in Polygons do if Polygon.IsNavigable() then Polygon.Visibility = 0 for Other in Polygons do if Other.IsNavigable() then Hits = 0 for (H1 , H2 ) in { CrouchHeight, FullHeight } do Hits += CheckCollision(Polygon.Location+ H1 ,Other.Location+ H2 ) if Distance(Polygon,Other) < d then Polygon.Visibility += Area(Other) ∗ Hits / 4 Polygon.Visibility = Min(1,Polygon.Visibility / c) Algorithm 1: Visibility Computation The threshold parameters d and c should be chosen experimentally depend- ing on the game engine and the empirical estimation of the visibility map (see [19]). It is clear that c should be about π ∗ d2 but it is not necessary. 5 Fig. 3. Visibility Based on Voronoi Diagram The result of the Algorithm 1 is shown on Figure 3. The darker the polygon is, the worse the visibility is in it. All non navigable areas have red colour. We will further improve the representation of visibility and distance struc- tures with BSP-trees. 4 Path planning 4.1 Path finding The work with navigation proceeds in the following steps: 1. BOT makes a query to navigation system; 2. Navigation system uses A∗ (or I–ARA ∗ anytime algorithm from [20] for large maps) finding a sequence of adjacent polygons on navigation mesh; 3. A sequence of polygons is converted into a sequence of points; 4. BOT receives a sequence of points and build a collision free path to walk. 4.2 Weight function and heuristics We design the interface for interaction between querier and navigation system at each iteration of A∗ algorithm as follows: float GetPenaltyForRotation(); float GetPenaltyMultiplierForCrouch(); float GetPenaltyForJump(); float GetAdditionalPenalty(PreviousPolygon,NextPolygon); FVector2D GetInitialRotation(); 6 Using the first three methods, a querier can manage penalties for path’s curvature, crouching and jumping. The last function is a method for querier to influence navigation with respect to previous movement direction. GetAddi- tionalPenalty is used by querier to modify path penalty according to tactical properties of “previous” and “next” polygons and depending on its current pref- erences, similar to Markov’s chains. There are also so-called general penalties, such as base cost, base enter cost and no way flag, which can be dynamically modified by any game event. // Zeroth is Polygon visited before First // Negative distance means no way def Distance(Querier,Zeroth,First,Second,bJumpRequired): if not Second.IsNavigable() or Second.bNoWay then return -1 Penalty = Querier.GetAdditionalPenalty(First,Second) if Penalty < 0 then return -1 Direction ← Calculate direction from First to Second if ∃ Zeroth then PreviousDirection ← Calculate direction from Zeroth to First else PreviousDirection ← Querier.GetInitialRotation() // stands for dot product of normalized vectors Rotation = 1 - < Direction,PreviousDirection > Penalty += Rotation ∗ Max(0,Querier.GetPenaltyForRotation()) BaseCost = (First.BaseCost + Second.BaseCost) / 2 if First.bCrouchedOnly or Second.bCrouchedOnly then BaseCost *= Max(1,Querier.GetPenaltyMultiplierForCrouch()) Penalty += Distance(First,Second) * BaseCost + Second.BaseEnterCost if bJumpRequired then Penalty += Max(0,Querier.GetPenaltyForJump() return Penalty Algorithm 2: Calculating Weight Function For proper work of A ∗ algorithm, each penalty is jammed to a limited range, so the resulting penalty is not less than the Euclidean distance, which is used as heuristics in our implementation. 7 4.3 Post processing path Once a path is found, it should be converted into a point sequence. Apart from how this is done in regular navigation meshes, potential field or Funnel algo- rithms (see [19,21]) are not of any use because they can not smooth the paths furhter. There are two ways polygons in navigation mesh can be connected: by link and by edge. In the first case, positions of points are chosen as coordinates of sites. In the second one, point can take different positions on an edge connecting two sequential polygons in a path. We use a weighted approach to choose this point in order to produce believable (in the sense of [22]) and natural looking paths. Let pi−1 be a point already chosen, and pi+1 be a site position of the next polygon. Then pi is a point to be chosen. Also let v1 and v2 be vertices of an edge connecting polygons i and i + 1 . We have: dj = distance(vj , line(pi−1 , pi+1 )), (2) wj = rand(1, b)/dj , j = 1, 2, (3) v1 ∗ w 1 + v2 ∗ w 2 pi = , (4) w1 + w2 where b stands for the amount of randomness. We recommend to set b around the value 2 so that it does not overweight distance modifier, and at the same time produce paths that appear to be “unique” (it looks unnatural when BOT is travelling along the same trajectory all the time, especially when there are several BOTs going one after another). The distance to the line modifier is used for removing zigzag effects and as a first attempt to smooth the path. Figure 4 shows how a typical path may look after this step. Fig. 4. Post Processed Random Path Fig. 5. Smooth Path 8 4.4 Building Bezier curve When developing a BOT navigation, smoothing is one of the key steps. It is the first thing for a human to distinguish a BOT from a human player. Several approaches can be used to smooth movements. For example, a potential method when a force proportional to distance from obstacle is applied to a BOT, limiting rotation rate of a BOT when moving between points, and splines. Bezier curves seem to be the most suitable because they lie strictly inside the convex hull of way points1 . This fact guarantees that the smoothed path is collision-free, and that a BOT will not be stuck into an obstacle. In addition, the path does not pass through a majority of points it is built on, and that is actually why we do not eliminate the points with a Funnel or another algorithm. We use all these points to smooth paths. In this section we present how to build a composite Bezier curve, as shown on Figure 5. We also improve the results of [13,14], obtaining worse length path for realistic motion and detour around the obstacles. The first step is an insertion of additional points into a path so that the distance between sequential ones is greater than some predetermined constant. In practice, it greatly enhances results of the further step where we split a path into several pieces to build a Bezier curve in each one. Points of each piece of the path should lie in a collision-free convex hull so we have to choose the subsequences of points with no obstacles in their convex hull and ensure that there are no any holes under it. We want to minimize over all partitions: X distance(P iece.F irstP oint, P iece.LastP oint) → min (5) Also if two partitions lengths differs on a small ε then we choose the one with less parts as a composite Bezier curve produces worse smoothing when it consists of a big number of small curves. This strategy roughly minimizes a length of the resulting curve and allows better smoothing behavior on turns. 1 http://www.ams.org/samplings/feature-column/fcarc-bezier 9 The following algorithm for path subdivision is used: CollideArray[N][N] ← initialized by false Partition[N][N] ← struct { Value,Parts,End } for k in range(1,N) do for i in range(0,N - k) do j=i+k if CollideArray[i][j - 1] or CollideArray[i + 1][j] or CheckCollision(PathPoints[i],PathPoints[j]) then CollideArray[i][j] = true if CollideArray[i][j] then Partition[i][j].Value = +∞ else Partition[i][j].Value = distance(PathPoints[i],PathPoints[j]) Partition[i][j].Parts = 1 Partition[i][j].End = j for l in range(i + 1,j) do ValueAlternative = Partition[i][l].Value + Partition[l][j].Value PartsAlternative = Partition[i][l].Parts + Partition[l][j].Parts if Partition[i][j].Value > ValueAlternative + ε or (abs(Partition[i][j].Value - ValueAlternative) < ε and PartsAlternative < Partition[i][l].Parts) then Partition[i][j].Value = ValueAlternative Partition[i][j].Parts = PartsAlternative Partition[i][j].End = l Algorithm 3: Composite Bezier Curve Construction Once array Partition is computed, we can get indexes of the path subdivision using a simple recursive backtracking algorithm. def Backtracking(Partition,i,j,Indexes): if j == Partition[i][j].End then Indexes.Add(j) else Backtracking(Partition,i,Partition[i][j].End,Indexes) Backtracking(Partition,Partition[i][j].End,j,Indexes) Algorithm 4: Backtracking Our next step is removal of crowded control points in each part of the path, therefore decreasing the curvature and the length of a curve. This can be done directly by verifying that points are not closer than some e > 0 and that there are not too many control points. 10 The final step of building a composite Bezier curve is the “repairing” of a derivative at parts’ connection locations. This can be achieved by inserting ad- ditional control points at these locations in order to ensure that we have at least continuously differentiable trajectories. Complete algorithms for constructing composite Bezier curves can be found in [13,14]. Now, a BOT can start moving along it. In general, there may be difficulties with the correct calculation of the current and the next positions on the curve, so we use the simplest prediction for small time interval and correct path finder. 5 Experiment and Conclusion In practice, the contribution of visibility component to remain undetected during BOT motion is very low if we are not taking into account the enemies’ move- ments. We consider the relative dependence of the smooth low-visibility path length with the length of the shortest path obtained by Recast navigation mesh. We take 1000 different start and end locations on the map shown on Figure 3. The average difference (AD, %) and variance of difference (VD, %) from the shortest path length for the next paths were calculated during the experiment: [Case 1 & 2] Piecewise path with visibility penalty set to 0 and 10, respectively; [Case 3 & 4] Smoothed path with visibility penalty set to 0 and 10, respectively. We perform the exepriment in Unreal Engine 4 2 . Results are shown in Table 1. Table 1. Comparison with the Shortest Path Length \ 1 2 3 4 AD, % 5.9 12.5 27 37.2 VD, % 0.3 1 0.7 2.1 We can see that the resulting difference between the smooth paths with and without a visibility component does not exceed 10–12%, so taking into account tactical information seems to be a useful decision. The difference in 15–25% between smooth path length from our algorithm and the results from [13,14] is not too significant because we mainly focus on constructing realistic randomized paths for BOTs. When implementing such an algorithm in 3D first-person shooter, our algorithm provides more realistic mo- tion behaviours than the minimized CBR-based path, while saving the property of the path to be suboptimal. 2 https://www.unrealengine.com 11 Figure 6 illustrates the visual comparison between piecewise linear path, smoothed path and the shortest path drawn in yellow(1), pink(2) and green(3) color respectively. Fig. 6. Path Comparision We will continue the evaluation of this method by applying it to BOTs’ formations and by simplifying the computational part of the visibility measure, expanding Markov’s processes based approach for BOT motion from [23]. References 1. Bhattacharya, P., Gavrilova, Marina L.: Voronoi diagram in optimal path plan- ning. In: 4th IEEE International Symposium on Voronoi Diagrams in Science and Engineering. (2007) 38–47 2. Choi, J.w., Curry, Renwick E., Elkaim, Gabriel H.: Obstacle avoiding real-time trajectory generation and control of omnidirectional vehicles. In: American Control Conference. (2009) 3. Gulati, S., Kuipers, B.: High performance control for graceful motion of an intelli- gent wheelchair. In: IEEE International Conference on Robotics and Automation. (2008) 3932–3938 4. Guechi, E.H., Lauber, J., Dambrine, M.: On-line moving-obstacle avoidance using piecewise bezier curves with unknown obstacle trajectory. In: 16th Mediterranean Conference on Control and Automation. (2008) 505–510 5. Nagatani, K., Iwai, Y., Tanaka, Y.: Sensor based navigation for car-like mobile robots using generalized voronoi graph. In: IEEE International Conference on Intelligent Robots and Systems. (2001) 1017–1022 6. Reif, J. H.: Complexity of the mover’s problem and generalizations. 20th Annual IEEE Conference on Foundations of Computer Science (1979) 421–427 7. Okabe, A., Suzuki, A.: Locational optimization problems solved through voronoi diagrams. European Journal of Operational Research 98(3) (1997) 445–456 8. Mohammadi, S., Hazar, N.: A voronoi-based reactive approach for mobile robot navigation. Advances in Computer Science and Engineering 6 (2009) 901–904 12 9. Eren, H., Fung, C.C., Evans, J.: Implementation of the spline method for mobile robot path control. In: 16th IEEE Instrumentation and Measurement Technology Conference. Volume 2. (1999) 739–744 10. Magid, E., Keren, D., Rivlin, E., Yavneh, I.: Spline-based robot navigation. In: International Conference on Intelilgent Robots and Systems. (2006) 2296–2301 11. Hwang, J.H., Arkin, R.C., Kwon, D.S.: Mobile robots at your fingertip: Bezier curve on-line trajectory generation for supervisory control. In: IEEE International Conference on Intelligent Robots and Systems. Volume 2. (2003) 1444–1449 12. Škrjanc, I., Klančar, G.: Cooperative collision avoidance between multiple robots based on bezier curves. In: 29th International Conference on Information Technol- ogy Interfaces. (2007) 451–456 13. Ho, Y.J., Liu, J.S.: Smoothing voronoi-based obstacle-avoiding path by length- minimizing composite bezier curve. In: International Conference on Service and Interactive Robotics. (2009) 14. Ho, Y.J., Liu, J. S.: Collision-free curvature-bounded smooth path planning using composite bezier curve based on voronoi diagram. In: IEEE International Sympo- sium on Computational Intelligence in Robotics and Automation. (2009) 463–468 15. Fortune, S.: A sweepline algorithm for voronoi diagrams. In: 2nd Annual Sympo- sium on Computational geometry. (1986) 313–322 16. Guibas, Leonidas J., Knuth, Donald E., Sharir, M.: Randomized incremental construction of delaunay and voronoi diagrams. Algorithmica 7(1) (1992) 381–413 17. van Toll, W.G., Cook, A.F., Geraerts, R.: A navigation mesh for dynamic envi- ronments. Comput. Animat. Virtual Worlds 23(6) (November 2012) 535–546 18. Funge, J., Millington, I.: Artificial Intelligence for Games. M. Kaufmann (2009) 19. Barraquand, J., Latombe, J.: Robot motion planning: A distributed approach. International Journal of Robotics Research 10(6) (1991) 628–649 20. Koenig, S., Sun, X., Uras, T., Yeoh, W.: Incremental ARA ∗ : An incremental anytime search algorithm for moving-target search. In: Proceedings of the Twenty- Second International Conference on Automated Planning and Scheduling. (2012) 21. Ish-Shalom, J.: The funnel algorithm and task level robot control. In: IEEE International Conference on Robotics and Automation. Volume 4. (1987) 25–32 22. Hingston, P.: Believable Bots: Can Computers Play Like People? Springer (2012) 23. Makarov, I., Tokmakov, M., Tokmakova, L.: Imitation of human behavior in 3D- shooter game. In: 4th International Conference on Analysis of Images, Social Networks and Texts. (2015) 64–77