1
\$\begingroup\$

I am building a little RTS-like game as a side project and I am currently working on pathfinding. My approach to pathfinding is heavily inspired by things I saw in the Starcraft II map editor, which enables diagonal obstacles. My map consists of tiles that are subdivided into 4 triangles each and each triangle can be passable or not passable. I then build a navigation mesh by generating polygons (with holes) of the passable area and then triangulating them. See the following pictures for an example:

enter image description here

The colored areas are the triangulated polygons that make up the navigation mesh.

As an optimization I thought it would be a good idea to subdivide the map into chunks (i.e. 32x32 grid tiles) to allow for fast updates of the mesh (as soon as a triangle changes from passable/impassable I rebuild the whole chunk and update the navigation mesh accordingly). See the following picture for an example:

enter image description here

The red lines are the chunk borders (which is also why the color of the navigation mesh sometimes changes accross the borders).

The triangulation is a separate constrained delaunay triangulation for each chunk. For the chunk-wise updates to work I had to introduce constraints at the chunk borders for the triangles to line up. Up until now everything seemed to work fine. I then went to implement some pathfinding using A* on edge midpoints and path smoothing using the Simple Stupid Funnel algorithm (see "Efficient Triangulation-Based Pathfinding" by Demyen and Buro or How does the Simple Stupid Funnel Algorithm work?).

The problem is now that some triangles have their vertices at chunk borders that don't correspond to an obstacle. If such a triangle is part of a path found by A* the funnel algorithm uses it if it was a corner point of an obstacle and produces a wrong path. See the folowing picture for an example:

enter image description here

The red area is the passable area and has no obstacles inside. The green path is the path as it is found by e.g. A* and the blue path is the smoothed path using the funnel algorithm. Since there is an extra vertex in the navigation mesh introduced by the the chunk borders (where the 4 chunks meet) the funnel algorithm handles it the same as if it was the corner of an obstacle and thus the path is not a straight line but takes a detour around the corner. Ultimately I wanted to implement something along the lines of "Compromise-free Pathfinding on a Navigation Mesh" by Cui, Harabor and Grastien to find truly optimal paths in a navigation mesh. But all of those methods seem to assume that the navigation mesh contains no extra vertices except for the corners of obstacles (and the outer border of course).

I am looking for a solution for the problem of splitting the map into chunks for efficient updates of the navigation mesh while still being able to find optimal paths in an efficient manner (e.g. i don't want to do real line of sight checks instead of the funnel algorithm). My only other option it seems would be an algorithm for dynamic constrained delaunay triangulations and having a single triangulation for the whole map (since this would not introduce extra obstacles) which for one is pretty complicated and second (and more importantly) doesn't scale.

I know that this is a pretty open question. I hope it comes clear what I am looking for, since it was kind of difficult to phrase the problem :D If anything needs clarification, please tell me :D

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.