ebSkola

4. tēma / 4.4

4.4 Pathfinding ar A*

Stundas uzdevums: Saprast un implementēt pathfinding (ceļa meklēšana) algoritmu spēles AI.

SR 2.4.19. Algoritmu efektivitāte SR 2.4.16. Datu struktūras

80 min plāns: Teorija un paraugs (~10 min) · 1. uzdevums (~20 min) - sagatavo navigācijas reģionu · 2. uzdevums (~25 min) - liec ienaidniekam sekot ceļam · 3. uzdevums (~20 min) - salīdzini taisno kustību ar pathfinding · Iesniegšana (~5 min).

Pirms sāc: atver savu projektu ar stāvokļu mašīnu no 4.3 stundas. Šodien ienaidnieks vairs neiestrēgs aiz sienas.

Teorija: A* algoritms un NavigationAgent2D

Reālistiska AI prasa pathfinding - meklēt īsāko ceļu starp diviem punktiem, izvairoties no šķēršļiem.

A* algoritms izmanto:

  • g(n) - faktiskais ceļa garums no sākuma līdz n.
  • h(n) - heuristika (taisns attālums līdz mērķim).
  • f(n) = g(n) + h(n) - kopējais novērtējums.

Godot 4 piedāvā NavigationAgent2D kas to dara automātiski.

using Godot;

public partial class Enemy : CharacterBody2D
{
    private NavigationAgent2D navAgent;
    private Vector2 playerPos;
    [Export] public float Speed = 180.0f;

    public override void _Ready()
    {
        navAgent = GetNode<NavigationAgent2D>("NavigationAgent2D");
        navAgent.TargetPosition = playerPos;
    }

    public override void _PhysicsProcess(double delta)
    {
        if (navAgent.IsNavigationFinished()) return;

        Vector2 nextPos = navAgent.GetNextPathPosition();
        Vector2 dir = (nextPos - Position).Normalized();
        Velocity = dir * Speed;
        MoveAndSlide();
    }
}

Kā šo izmantot projektā

Atceries: ar redzamu efektu editorā nepietiek. Paskaidro, kura C# klase glabā stāvokli, kura metode to maina un kā Godot node struktūra izmanto šo kodu.

Pārbaudi: C# kodā pamatoti izvēlēti List, Dictionary vai HashSet, AI stāvokļi ir skaidri, un sarežģītākas sistēmas var profilēt vai atkļūdot.

public class AiDataCheckpoint
{
    public string Lesson = "4.4 Pathfinding ar A*";
    public bool UsesCSharp = true;
    public bool ChoosesContainer = true;
    public bool SeparatesAiState = true;
    public bool HandlesRemovalSafely = true;
}

Praktiskie uzdevumi

1. uzdevums -

Sagatavo navigācijas reģionu

Beigās Godot zinās, pa kurām vietām drīkst staigāt.

  1. Pievieno scēnai mezglu NavigationRegion2D.
  2. Izveido tam NavigationPolygon resursu Inspector panelī.
  3. Uzzīmē daudzstūri, kas aptver visu staigājamo laukumu.
  4. Pievieno laukumā divas sienas kā StaticBody2D.
  5. Izgriez navigācijas daudzstūrī caurumus ap sienām.
  6. Nospied Bake NavigationPolygon.
  7. Pārbaudi, ka zilā zona neiet pāri sienām.

Gatavs, kad: navigācijas zona aptver grīdu, bet ne sienas, un tā ir redzama editorā zilā krāsā.

2. uzdevums -

Liec ienaidniekam sekot ceļam

Beigās ienaidnieks apstaigās sienu, nevis iestrēgs tajā.

  1. Pievieno ienaidniekam bērnu NavigationAgent2D.
  2. Atver ienaidnieka C# failu un pārliecinies, ka sākumā ir using Godot;.
  3. Paņem aģentu kodā ar NavigationAgent2D agent = GetNode<NavigationAgent2D>("NavigationAgent2D");.
  4. Iestati mērķi ar agent.TargetPosition = playerPos;.
  5. Paņem nākamo punktu ar Vector2 next = agent.GetNextPathPosition();.
  6. Virzies uz to ar (next - Position).Normalized() * Speed.
  7. Būvē un noliec spēlētāju aiz sienas.

Gatavs, kad: ienaidnieks apiet sienu apkārt un nonāk pie spēlētāja, nevis spiežas sienā.

3. uzdevums -

Salīdzini taisno kustību ar pathfinding

Beigās tu redzēsi, ko tieši pathfinding atrisina.

  1. Nomaini kodu uz taisnu kustību tieši pret spēlētāju, bez agenta.
  2. Noliec spēlētāju aiz sienas un palaid.
  3. Pieraksti, kur ienaidnieks apstājās.
  4. Ieliec pathfinding kodu atpakaļ un atkārto to pašu testu.
  5. Pieraksti, cik ilgi tagad aizņēma nonākšana pie spēlētāja.
  6. Pārbaudi, kas notiek, ja spēlētājs ir ārpus navigācijas zonas.
  7. Pieraksti, ko dara g un ko h A* algoritmā.

Gatavs, kad: bez pathfinding ienaidnieks iestrēgst pie sienas, bet ar to - apiet apkārt.

Papildu uzdevums - Zīmē ceļu uz ekrāna

Ja pamatdarbs ir gatavs, parādi, pa kuru ceļu ienaidnieks iet.

  1. Paņem pilnu ceļu ar agent.GetCurrentNavigationPath();.
  2. Pievieno scēnai Line2D mezglu.
  3. Iestati tā punktus uz ceļa punktiem katrā kadrā.
  4. Palaid un vēro, kā līnija mainās, kustinot spēlētāju.
  5. Pieraksti, cik punktu parasti ir ceļā.

Gatavs, kad: ekrānā redzama līnija, kas rāda ienaidnieka plānoto ceļu ap sienu.

Ko sagatavo

Stundas mērķis: Tavā līmenī ir izcepts navigācijas reģions, un ienaidnieks ar NavigationAgent2D apiet sienas, lai nonāktu pie spēlētāja, nevis iestrēgst pret tām.

GitHub krātuvē jābūt:

  1. README.md ievietota video saite, kurā ienaidnieks apiet sienu, lai nonāktu pie spēlētāja.
  2. Ekrānuzņēmums ar navigācijas zonu editorā (zilā zona ap sienām).
  3. Fails Enemy.cs ar NavigationAgent2D kodu.
  4. README.md: ko A* algoritmā nozīmē g un ko h.

Kā iesniedz: Veic commit un push. Skolotāja norādītajā vietā ievieto tikai GitHub krātuves saiti; visiem prasītajiem failiem, README.md pierakstiem un pierādījumiem jābūt pašā krātuvē.

Biežākās kļūdas

  • NavigationAgent neatrod ceļu: NavigationPolygon nav baked vai nepareiza forma.
  • Ienaidnieki iestrēgst stūros: Path radius pārāk mazs vai šķēršļi pārāk tuvu.
  • Slow performance: Pārāk daudz NavigationAgent - pārbaudi update freq.

Godot ekrānuzņēmumi

Godot editor ar baked navigation mesh: zilā krāsā navigējamās zonas, sarkanā - šķēršļi (sienas).
Godot editor ar baked navigation mesh: zilā krāsā navigējamās zonas, sarkanā - šķēršļi (sienas).
Spēles aina: ienaidnieks atrod ceļu ap U-formas sienu, lai sasniegtu spēlētāju centrā.
Spēles aina: ienaidnieks atrod ceļu ap U-formas sienu, lai sasniegtu spēlētāju centrā.

Koda piemērs (paplašināts)

using Godot;

public partial class Enemy : CharacterBody2D
{
    private NavigationAgent2D navAgent;
    private Player player;
    [Export] public float Speed = 180.0f;

    public override void _Ready()
    {
        navAgent = GetNode<NavigationAgent2D>("NavigationAgent2D");
        navAgent.AvoidanceEnabled = true;
        UpdateTarget();
    }

    public override void _PhysicsProcess(double delta)
    {
        if (navAgent.IsNavigationFinished()) return;

        Vector2 next = navAgent.GetNextPathPosition();
        Vector2 direction = (next - Position).Normalized();

        Velocity = direction * Speed;
        MoveAndSlide();
    }

    private void UpdateTarget()
    {
        if (player != null) navAgent.TargetPosition = player.Position;
    }
}
Ienaidnieks atrod ceļu ap šķēršļiem un dzenas spēlētājam pa optimālo trasi, vairāki ienaidnieki nesaduras.