[FND] Navigation system

[Reid]

One of the core feature that I try to implement for SoM is to use Tiled as our main level editor to store our maps, tilesets, collisions and spawns data.
We could use Godot's map editor but all of our data were made with Tiled for almost two decades so let's not try to rewrite every maps and break the compatibility between TMW and SoM.

For this I've been using vnen's map importer ( https://github.com/vnen/godot-tiled-importer ).
After adding all of our missing features on the first half of 2022 I then had to rewrite a large part of this plugin to make it work with Godot4's new map system during this summer.

The work started with this commit and ended up a bit later in September: https://gitlab.com/sourceofmana/sourceo ... 2ad700b5ad

Almost everything is working for us except:

• tile animations which changed a bit and forces us to change all animated tilesets
• spawn locations because we didn't have anything to test it with

We can now import our map inside Godot4 quite easily and start to add a new and important feature: the navigation system

Our navigation is entirely working with Godot features to let our mobs, NPCs and player walk within our World service ( https://gitlab.com/sourceofmana/sourceo ... d/World.gd )

We give a navigation mesh to Godot and all of its displacement logic is done internally and magically to our eyes.
So, what is missing? Well, we have to create this navigation mesh. And it is not as easy as it sounds as we have to keep this process as easy as possible for future contributors and to import maps from other projects.

Example:

navigation.png (316.29 KiB) Viewed 1024 times

[Reid]

So far, we are generating these navigation mesh as follow:

1. Parse all tiles
2. Store all collisions as polygons inside an array
3. Parse all polygons
4. Merge polygons between each others if

   • a. one is not inside another (to prevent to merge inner and outer polygons together)

   • b. one is touching another

   • c. the result of the merge gives two polygons (an inner, an outer)

5. Grow polygons of 15px to prevent some navigation issue with our entities collisions
6. Call again the merge process in case an upscaled polygon is touching another one
7. Store the result into a NavigationMesh
8. Triangulate the result to permit mobs, NPCs and players to spawn and walks inside a delimited area

Our primary issue during the first point of our merge process, we need to skip polygons that are inside another polygons because we have to keep some rogue collisions like this:

rogue.png (25.92 KiB) Viewed 1031 times

But then we can't merge such cases of collisions:

inner.png (23.5 KiB) Viewed 1031 times

And as a result, this merge algorithm create some artefacts:

bad result.png (93.72 KiB) Viewed 1031 times

The merge process is currently done this way:

Code: Select all

func merge_polygons(pool : Array, has_debug : bool = false):
    while(true):
        var polygons_to_remove : Array = []
        var polygons_to_skip : Array = []
 
    for pol_index in pool.size():
        if polygons_to_remove.has(pol_index) or polygons_to_skip.has(pol_index):
            continue
 
        if has_debug: print("Reducing polygons: ", pol_index, " / ", pool.size()-1)
        var current_polygon : PackedVector2Array = pool[pol_index]
 
        for pol_subindex in range(pol_index + 1, pool.size()):
            if polygons_to_remove.has(pol_subindex) or polygons_to_skip.has(pol_subindex):
                continue
 
            var other_polygon : PackedVector2Array = pool[pol_subindex]
 
# CRITICAL PART
                if both_cyclic_polygon(current_polygon, other_polygon):
                    if has_debug: print("\t", pol_subindex, " already cycled with ", pol_index)
                    continue
# CRITICAL PART
 
            var merged_polygon : Array = Geometry2D.merge_polygons(current_polygon, other_polygon)
            if merged_polygon.size() == 1:
                if has_debug: print("\t", pol_subindex, " merged with ", pol_index)
                pool[pol_subindex] = merged_polygon[0]
                polygons_to_remove.append(pol_index)
                polygons_to_skip.append(pol_subindex)
                break
            elif merged_polygon.size() == 2:
                if both_cyclic_polygon(merged_polygon[0], merged_polygon[1]):
                    if has_debug: print("\t", pol_subindex, " newly cycling with ", pol_index)
                    pool[pol_index] = merged_polygon[0]
                    pool[pol_subindex] = merged_polygon[1]
                    polygons_to_remove.erase(pol_index)
                    polygons_to_remove.erase(pol_subindex)
                    polygons_to_skip.append(pol_subindex)
                    continue
 
    polygons_to_remove.sort()
    if polygons_to_remove.size() == 0:
        break
 
    for rem_index in range(polygons_to_remove.size() -1, -1, -1):
        pool.remove_at(polygons_to_remove[rem_index])
 
    if has_debug: print("")

For more information:
In most cases, an inner polygon has to be merged into an outer polygon. But once all map border collisions are merged within each others we have as a result two polygons:

• an outer polygon of the map size
• an inner polygon of the walkable part
• multiple inner polygons for rogue collisions
  These polygons can't be merged together and it's this kind of exception that create our conflicts.

At the end of this process we then ditch away all walkable polygons that are outside the map size and we end up with the wanted walkable zones for our entities as follow:

result.png (68.72 KiB) Viewed 1031 times

As of today, I have no idea how to fix this inner/outer polygon issue and I'm running in circle by disabling/re-enabling this 4.a. part of the algorithm

[Reid]

I found a solution to this issue!
We now have 5 out of 6 maps that import correctly and generate a very good triangulation for our navigation mesh!

The solution was to split the merging process into multiple steps:

1. Merge every polygons without creating any inner/outer polygons (i.e.: only add merging results that generate one and only one polygon)

2. Grow our polygons to prevent some collision issues while moving in game

3. Repeat first step to merge grown polygons with each others if some vertices or edges are on top of each others after the upscale (optional on some maps)

4. Merge every polygons into some inner/outer polygons

5. Remove every polygons that are outside the AABB region of the map

6. Remove every points that are near each others (less than 3pixels) to reduce the complexity on the triangulation and the size of the navigation mesh (WIP)

Triangulation.png (126.46 KiB) Viewed 971 times