10. Navigation Mesh Generation

Genereer dynamisch een NavigationMesh van road tiles voor pathfinding

Overzicht

In dit hoofdstuk leer je:

• RoadNavigation.cs (NavigationRegion3D) maken

• Dynamic NavMesh generation van road tiles

• GetRoadCells() helper implementeren

• Manual geometry creation (vertices + polygons)

• RegenerateNavigationMesh() aanroepen bij road changes

• NavigationMesh.Clear() en AddPolygon()

Wat is een Navigation System?

Godot's navigation system gebruikt NavigationMesh voor pathfinding. Een NavigationMesh is een verzameling van polygonen die bepalen waar characters kunnen lopen/rijden.

In dit hoofdstuk:

• Genereer een NavigationMesh dynamisch vanaf de GridMap roads

• Elke road tile wordt een quad polygon (4 vertices)

• Update de mesh automatisch wanneer wegen worden toegevoegd/verwijderd

• Voertuigen gebruiken deze mesh om routes te berekenen (hoofdstuk 11)

Waarom dynamisch? Static navigation meshes werken niet voor city builders - spelers bouwen het wegennetwerk tijdens gameplay! De mesh moet real-time regenereren.

RoadNavigation script aanmaken

Maak een nieuwe script die de navigation geometry genereert.

Nieuwe Godot-specifieke elementen:

• NavigationRegion3D - Node die een navigeerbaar gebied definieert

• NavigationMesh - Mesh data voor pathfinding

• MapToLocal() - Converteer GridMap cell coördinaten naar wereld positie

1. Maak een nieuw script scripts/RoadNavigation.cs

2. Maak de class aan die inherit van NavigationRegion3D:

using Godot;
using System.Collections.Generic;
using System.Linq;

public partial class RoadNavigation : NavigationRegion3D
{
}

1. Voeg een GridMap export toe:

public partial class RoadNavigation : NavigationRegion3D
{
    [Export] public GridMap GridMap { get; set; }
}

1. Sla het script op

IsRoadTile helper method

Voeg dezelfde helper toe als in RoadPlacer om road tiles te identificeren.

1. Voeg de IsRoadTile() method toe onderaan de class:

        return roadCells;
    }

    private bool IsRoadTile(int tileId) => tileId >= 10 && tileId <= 14;
}

1. Sla het script op

GetRoadCells implementeren

Maak een method om alle road tiles in de GridMap te vinden.

Nieuwe Godot-specifieke elementen:

• GetUsedCells() - Geeft alle non-empty cells in de GridMap

1. Voeg een lege GetRoadCells() method toe:

    }

    private List<Vector3I> GetRoadCells()
    {
    }
}

1. Maak een lege lijst voor road cells:

    private List<Vector3I> GetRoadCells()
    {
        var roadCells = new List<Vector3I>();
    }

1. Haal alle gebruikte cells op:

    private List<Vector3I> GetRoadCells()
    {
        var roadCells = new List<Vector3I>();
        var usedCells = GridMap.GetUsedCells();
    }

1. Loop door alle cells en check of ze roads zijn:

    private List<Vector3I> GetRoadCells()
    {
        var roadCells = new List<Vector3I>();
        var usedCells = GridMap.GetUsedCells();

        foreach (Vector3I cell in usedCells)
        {
            int tileId = GridMap.GetCellItem(cell);
            if (IsRoadTile(tileId))
            {
                roadCells.Add(cell);
            }
        }
    }

1. Return de lijst:

            }
        }

        return roadCells;
    }

1. Sla het script op

UpdateNavMesh implementeren

Maak een method om de NavigationRegion3D te forceren de mesh te updaten.

1. Voeg een lege UpdateNavMesh() method toe:

    private void UpdateNavMesh()
    {
    }

1. Sla de huidige NavigationMesh tijdelijk op:

    private void UpdateNavMesh()
    {
        var temp = NavigationMesh;
    }

1. Zet NavigationMesh op null:

    private void UpdateNavMesh()
    {
        var temp = NavigationMesh;
        NavigationMesh = null;
    }

1. Zet de mesh terug. Dit triggert een rebuild van de interne navigation data:

    private void UpdateNavMesh()
    {
        var temp = NavigationMesh;
        NavigationMesh = null;
        NavigationMesh = temp;
    }

Waarom null/restore?

• NavigationRegion3D update alleen bij property changes

• Setting naar null en terug forceert een rebuild

• Anders blijft de engine de oude mesh gebruiken

1. Sla het script op

RegenerateNavigationMesh method

Maak de hoofdmethod die de navigation mesh regenereert wanneer wegen veranderen.

1. Voeg een lege RegenerateNavigationMesh() method toe:

    [Export] public GridMap GridMap { get; set; }

    public void RegenerateNavigationMesh()
    {
    }
}

1. Haal alle road cells op:

    public void RegenerateNavigationMesh()
    {
        var roadCells = GetRoadCells();
    }

1. Genereer de navigation geometry:

    public void RegenerateNavigationMesh()
    {
        var roadCells = GetRoadCells();
        CreateNavigationGeometry(roadCells);
    }

1. Update de NavigationMesh:

    public void RegenerateNavigationMesh()
    {
        var roadCells = GetRoadCells();
        CreateNavigationGeometry(roadCells);
        UpdateNavMesh();
    }

1. Sla het script op

CreateNavigationGeometry implementeren

Maak een method die quad polygonen genereert voor elke road tile.

Nieuwe C#-specifieke elementen:

• Clear() - Verwijdert alle vertices en polygonen uit de NavigationMesh

• AddPolygon() - Voegt een polygon toe met vertex indices

1. Voeg een lege CreateNavigationGeometry() method toe:

    private void CreateNavigationGeometry(List<Vector3I> roadCells)
    {
    }

    private bool IsRoadTile(int tileId) => tileId >= 10 && tileId <= 14;
}

1. Clear de bestaande mesh data:

    private void CreateNavigationGeometry(List<Vector3I> roadCells)
    {
        NavigationMesh.Clear();
    }

1. Maak een lijst voor vertices:

    private void CreateNavigationGeometry(List<Vector3I> roadCells)
    {
        NavigationMesh.Clear();

        var vertices = new List<Vector3>();
    }

1. Loop door alle road cells:

    private void CreateNavigationGeometry(List<Vector3I> roadCells)
    {
        NavigationMesh.Clear();
        var vertices = new List<Vector3>();

        foreach (Vector3I cell in roadCells)
        {
        }
    }

1. Bereken de wereld positie van de cell:

        foreach (Vector3I cell in roadCells)
        {
            Vector3 cellLocalPos = GridMap.MapToLocal(cell);
        }

MapToLocal:

• Converteer GridMap cell (0, 0, 0) → wereld positie (0.5, 0, 0.5)

• GridMap cells zijn 1x1x1 units groot

• Cell center offset = +0.5 in X en Z

1. Bereken de vier hoeken van de quad. Elke road tile wordt een vierkant van 1x1 units:

        foreach (Vector3I cell in roadCells)
        {
            Vector3 cellLocalPos = GridMap.MapToLocal(cell);

            Vector3 topLeft = cellLocalPos + new Vector3(-0.5f, 0, -0.5f);
            Vector3 topRight = cellLocalPos + new Vector3(0.5f, 0, -0.5f);
            Vector3 bottomLeft = cellLocalPos + new Vector3(-0.5f, 0, 0.5f);
            Vector3 bottomRight = cellLocalPos + new Vector3(0.5f, 0, 0.5f);
        }

Quad layout:

topLeft (-0.5, 0, -0.5)    topRight (0.5, 0, -0.5)
        ●──────────────────●
        │                  │
        │   cell center    │
        │     (0,0,0)      │
        │                  │
        ●──────────────────●
bottomLeft (-0.5, 0, 0.5)  bottomRight (0.5, 0, 0.5)

1. Voeg de vertices toe aan de lijst:

            Vector3 bottomRight = cellLocalPos + new Vector3(0.5f, 0, 0.5f);

            vertices.Add(topLeft);
            vertices.Add(topRight);
            vertices.Add(bottomRight);
            vertices.Add(bottomLeft);
        }

1. Zet de vertices in de NavigationMesh. Dit moet VOOR het toevoegen van polygonen:

            vertices.Add(bottomLeft);
        }

        NavigationMesh.Vertices = vertices.ToArray();
    }

Waarom eerst vertices?

• AddPolygon() gebruikt indices (0, 1, 2, 3...)

• Vertices moeten al bestaan voordat je naar ze refereert

• ToArray() converteer List naar Vector3[]

1. Voeg polygonen toe. Elke quad heeft 4 vertices, dus elke polygon gebruikt indices i, i+1, i+2, i+3:

        NavigationMesh.Vertices = vertices.ToArray();

        for (int i = 0; i < NavigationMesh.Vertices.Length; i += 4)
        {
            NavigationMesh.AddPolygon([i, i + 1, i + 2, i + 3]);
        }
    }

Polygon indices:

• Cell 0: vertices 0-3 → polygon [0, 1, 2, 3]

• Cell 1: vertices 4-7 → polygon [4, 5, 6, 7]

• Cell 2: vertices 8-11 → polygon [8, 9, 10, 11]

• i += 4 springt naar de volgende quad

1. Sla het script op

_Ready implementeren

Genereer de initiële navigation mesh wanneer de scene start.

1. Voeg een lege _Ready() method toe:

    [Export] public GridMap GridMap { get; set; }

    public override void _Ready()
    {
    }

1. Roep RegenerateNavigationMesh() aan:

    public override void _Ready()
    {
        RegenerateNavigationMesh();
    }

1. Sla het script op

RoadNavigation node toevoegen

Voeg de RoadNavigation node toe aan de Main scene en configureer.

1. Open scenes/Main.tscn

2. Voeg een NavigationRegion3D node toe als child van Main

3. Hernoem naar RoadNavigation

4. Selecteer RoadNavigation in de Scene Tree

5. In de Inspector → Script: attach scripts/RoadNavigation.cs

6. In de Inspector → NavigationRegion3D sectie:

   • Klik New NavigationMesh naast NavigationMesh property

   • Dit maakt een lege mesh aan die RoadNavigation.cs zal vullen

7. In de Inspector → RoadNavigation script sectie:

   • Sleep GridMap node naar de GridMap export property

8. Sla de scene op (Ctrl+S)

RoadPlacer koppelen aan RoadNavigation

Update RoadPlacer om de navigation mesh te regenereren bij elke wijziging.

1. Open scripts/RoadPlacer.cs

2. Voeg een RoadNavigation export toe bovenaan (na de RoadCost export):

    [Export] public int RoadCost { get; set; } = 50;
    [Export] public RoadNavigation RoadNavigation { get; set; }

    [ExportGroup("Tile IDs (for Auto-Tiling)")]

1. Voeg RegenerateNavigationMesh() calls toe in Build(). Deze method bestaat al - voeg de regel toe aan het einde:

    public override void Build()
    {
        Vector3I? cell = Raycaster.GetCellUnderMouse();
        if (cell == null) return;

        var moneyManager = GetNode<MoneyManager>("/root/MoneyManager");
        if (!moneyManager.TrySpend(RoadCost))
            return;

        GridMap.SetCellItem(cell.Value, StraightId);
        UpdateSurroundingTiles(cell.Value);
        RoadNavigation?.RegenerateNavigationMesh();
    }

Null-conditional operator: ?. roept alleen de method aan als RoadNavigation niet null is

1. Voeg ook een call toe in TryRemoveRoad():

    private void TryRemoveRoad()
    {
        Vector3I? cell = Raycaster.GetCellUnderMouse();
        if (cell == null) return;

        if (!IsRoadTile(GridMap.GetCellItem(cell.Value)))
        {
            GD.Print("Not a road tile!");
            return;
        }

        GridMap.SetCellItem(cell.Value, GrassTileId);
        UpdateSurroundingTiles(cell.Value);
        RoadNavigation?.RegenerateNavigationMesh();
    }

1. Sla het script op

RoadNavigation export instellen

Koppel de RoadNavigation node in de Inspector.

1. Open scenes/Main.tscn (als deze nog niet open is)

2. Selecteer RoadPlacer in de Scene Tree

3. In de Inspector → RoadPlacer script sectie:

   • Sleep RoadNavigation node naar de Road Navigation export property

4. Sla de scene op (Ctrl+S)

Testen

Test of de navigation mesh correct wordt gegenereerd.

1. Start het spel (F5)

2. Selecteer road (arrow buttons) en plaats enkele wegen

3. Selecteer RoadNavigation in de Remote scene tree (niet de lokale Scene tree!)

4. In de Inspector → NavigationRegion3D sectie:

   • Klik op de NavigationMesh resource

   • Check of Vertices array gevuld is (4 vertices per road tile)

   • Check of Polygons array gevuld is (1 polygon per road tile)

5. Debug visualisatie (optioneel):

   • Menu → Debug → Visible Navigation

   • Je ziet blauwe quads op elke road tile

   • Dit visualiseert de navigeerbare gebieden

6. Verwijder een road met rechtermuisklik

7. Check of de vertices/polygons array kleiner wordt

Werkt alles? Sluit het spel (F8)

Volledig script

Klik hier voor het volledige RoadNavigation.cs script

using Godot;
using System.Collections.Generic;
using System.Linq;

public partial class RoadNavigation : NavigationRegion3D
{
    [Export] public GridMap GridMap { get; set; }

    public override void _Ready()
    {
        RegenerateNavigationMesh();
    }

    public void RegenerateNavigationMesh()
    {
        var roadCells = GetRoadCells();
        CreateNavigationGeometry(roadCells);
        UpdateNavMesh();
    }

    private void UpdateNavMesh()
    {
        var temp = NavigationMesh;
        NavigationMesh = null;
        NavigationMesh = temp;
    }

    private List<Vector3I> GetRoadCells()
    {
        var roadCells = new List<Vector3I>();
        var usedCells = GridMap.GetUsedCells();

        foreach (Vector3I cell in usedCells)
        {
            int tileId = GridMap.GetCellItem(cell);
            if (IsRoadTile(tileId))
            {
                roadCells.Add(cell);
            }
        }

        return roadCells;
    }

    private void CreateNavigationGeometry(List<Vector3I> roadCells)
    {
        NavigationMesh.Clear();

        var vertices = new List<Vector3>();

        foreach (Vector3I cell in roadCells)
        {
            Vector3 cellLocalPos = GridMap.MapToLocal(cell);

            Vector3 topLeft = cellLocalPos + new Vector3(-0.5f, 0, -0.5f);
            Vector3 topRight = cellLocalPos + new Vector3(0.5f, 0, -0.5f);
            Vector3 bottomLeft = cellLocalPos + new Vector3(-0.5f, 0, 0.5f);
            Vector3 bottomRight = cellLocalPos + new Vector3(0.5f, 0, 0.5f);

            vertices.Add(topLeft);
            vertices.Add(topRight);
            vertices.Add(bottomRight);
            vertices.Add(bottomLeft);
        }

        NavigationMesh.Vertices = vertices.ToArray();

        for (int i = 0; i < NavigationMesh.Vertices.Length; i += 4)
        {
            NavigationMesh.AddPolygon([i, i + 1, i + 2, i + 3]);
        }
    }

    private bool IsRoadTile(int tileId) => tileId >= 10 && tileId <= 14;
}