So far, we are generating these navigation mesh as follow:
- Parse all tiles
- Store all collisions as polygons inside an array
- Parse all polygons
- 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)
- Grow polygons of 15px to prevent some navigation issue with our entities collisions
- Call again the merge process in case an upscaled polygon is touching another one
- Store the result into a NavigationMesh
- 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 2132 times
But then we can't merge such cases of collisions:
- inner.png (23.5 KiB) Viewed 2132 times
And as a result, this merge algorithm create some artefacts:
- bad result.png (93.72 KiB) Viewed 2132 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 2132 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
"Time is an illusion. Lunchtime doubly so."
-- Ford Prefect