Heuristieken Verbeteren

Wanneer de heuristieke waarde dichter bij de werkelijke afstand komt te liggen, neemt het aantal knopen dat A moet verkennen af. Op deze pagina wordt een methode beschreven om de heuristiek te verbeteren om A te versnellen, gevolgd door demonstraties met kaarten uit echte spellen.

1. Het gebruik van de heuristiek in A*

A gebruikt een heuristiek om de zoektocht naar het doel te sturen. Je kunt dit zien als wind die ons in de juiste richting duwt. Wanneer de heuristiek ons in de juiste richting stuurt, draait A sneller.

Echter, soms stuurt de heuristiek ons de verkeerde kant op. Dit gebeurt omdat de gebruikelijke afstandgebaseerde heuristieken geen rekening houden met muren en obstakels.

2. De perfecte heuristiek

Ideaal gezien zouden we een heuristiek vinden die muren herkent en nooit in de verkeerde richting wijst: de "perfecte" heuristiek.

Hoewel het mogelijk is om deze te berekenen, is de perfecte heuristiek verschillend voor elke doelpositie en elke configuratie van muren. Als het doel of de muren veranderen, verandert de heuristiek mee.

Indien het doel en de muren ongewijzigd blijven, kunnen we flow field pathfinding gebruiken. Maar meestal is het doel variabel. Het is onpraktisch om bij elke A*-run een nieuwe perfecte heuristiek te berekenen, en het is even onpraktisch om deze vooraf voor alle mogelijke doelen te berekenen en op te slaan vanwege de enorme hoeveelheid data.

De oplossing is om de heuristiek één keer te berekenen en deze vervolgens voor meerdere A*-runs met verschillende doelen te hergebruiken.

3. Hergebruik van een perfecte heuristiek

Stel dat we een perfecte heuristiek berekenen naar een specifiek punt, dat we een "landmark" (herkenningspunt) noemen. Kan dit helpen bij het vinden van de weg naar een ander doel? Ja, in bepaalde gevallen.

Het idee is dat als we al het pad van startpunt B naar landmark L kennen, we ook het kortste pad naar elk punt X langs die route kennen:

• Pad van B naar L bevat X.
• Het totale pad is dan: pad van B naar X + pad van X naar L.

Je kunt het landmark zien als een ver verwijderd object. Iemand vertelt je: "Loop vanaf je huis (B) richting de Eiffeltoren (L) totdat je bij het huis van Daniel (X) bent". Het doel is niet om de Eiffeltoren te bereiken, maar de Eiffeltoren geeft ons de juiste richting aan. Het werkelijke doel, het huis van Daniel, ligt op die route.

De meeste doelen liggen niet precies op het pad B → L, maar ze liggen er soms wel dicht bij. We kunnen de driehoeksongelijkheid gebruiken om dit te kwantificeren. De driehoeksongelijkheid stelt dat de som van twee zijden van een driehoek minstens zo lang is als de derde zijde. Aangepast voor gerichte grafen betekent dit:

cost(B, X) + cost(X, L) ≥ cost(B, L)

Om een ondergrens te berekenen voor de kosten van B naar X, herschrijven we dit als:

cost(B, X) ≥ cost(B, L) - cost(X, L)

Dit is het kernidee. Het is onpraktisch om alle kosten tussen alle locaties vooraf te berekenen, maar als we de kosten naar één specifieke locatie (L) hebben berekend, kunnen we dat gebruiken om de kosten naar een andere locatie (X) te schatten. In academische literatuur wordt dit ook wel de "differentiële heuristiek" genoemd.

4. Meerdere landmarks

Een enkel landmark is alleen nuttig als het zich "na" het doel bevindt ten opzichte van het startpunt. Omdat een enkel punt niet voor alle mogelijke paden gunstig gepositioneerd kan zijn, hebben we meerdere landmarks nodig ($L1, L2, L_3$, etc.).

Elk landmark geeft ons een ondergrens voor de heuristiek:

• cost(B, X) ≥ cost(B, L₁) - cost(X, L₁)
• cost(B, X) ≥ cost(B, L₂) - cost(X, L₂)
• ...
• cost(B, X) ≥ cost(B, L<0xE2><0x82><0x99>) - cost(X, L<0xE2><0x82><0x99>)

We nemen de maximumwaarde (max()) van al deze resultaten om de hoogst mogelijke ondergrens te kiezen.

5. Plaatsing van landmarks

De beste positie voor een landmark hangt af van het startpunt B en het doel X. We willen dat het landmark "na" het doel ligt, maar wat "na" is, verschilt per route. Het doel is om landmarks zo te plaatsen dat ze zoveel mogelijk (start, doel)-paren verbeteren.

Bij het bepalen van het aantal en de plaatsing van landmarks moet rekening worden gehouden met het volgende:

• Waarschijnlijkheid van paden: In een colony builder zoals Dwarf Fortress zijn paden naar en van de hoofdbasis belangrijker dan paden tussen een bos en een mijn.
• Waarde van optimalisatie: Als pathfinding de framerate beperkt, is het zinvoller om focus te leggen op lange paden die rekenintensief zijn, in plaats van korte paden.
• Statische versus dynamische kaarten:
• Bij statische kaarten kunnen landmarks vooraf optimaal worden geplaatst via een editor.
• Bij dynamische kaarten (waarbij muren veranderen) moet men oppassen. Als een kostenverlaging optreedt (bijv. een muur wordt gesloopt), kan de heuristiek de afstand overschatten, waardoor A* een suboptimaal pad vindt totdat de kostentabel is bijgewerkt.
• Als kosten toenemen (bijv. een nieuwe muur), zal de heuristiek lager zijn dan gewenst en duurt de zoektocht langer, maar blijft het resultaat optimaal.
• Veelbezochte gebieden: Wanneer veel eenheden naar gemeenschappelijke ruimtes trekken, is het raadzaam om landmarks nabij deze gebieden te plaatsen.
• Kaarttype: Een RTS-spel heeft andere behoeften dan een dungeon crawler met kamers en gangen.

Zelfs als een landmark niet optimaal is geplaatst, zal het de zoektocht meestal nog steeds enigszins helpen, en het is in ieder geval nooit slechter dan de standaard A*-heuristiek.

6. Geautomatiseerde plaatsing

Een project-onafhankelijke manier om landmarks te plaatsen is door bij te houden welke locaties gunstig zijn voor een groot aantal willekeurig gekozen paden. Dit resulteert vaak in punten aan de buitenranden van de kaart.

Bij het toevoegen van meerdere landmarks moet elk nieuw punt worden geëvalueerd op basis van wat het toevoegt ten opzichte van de reeds bestaande landmarks; ze moeten dus verspreid over de kaart liggen.

7. Implementatie

De aanpassing vindt uitsluitend plaats in de heuristieke functie die aan A wordt meegegeven; de A-algoritme zelf hoeft niet te worden gewijzigd.

Stappenplan:

1. Landmarks kiezen: Via een editor (statisch) of via willekeurige kaartanalyse (procedureel).
2. Kaart analyseren: Maak een 2D-array aan: cost[nodeId][landmarkId].
3. Kosten berekenen: Voer voor elk landmark het algoritme van Dijkstra uit. In een gerichte graaf moeten alle randen worden omgekeerd (single goal in plaats van single source). Bij gewichten van 1 kan Breadth First Search (BFS) worden gebruikt.

Voorbeeldcode voor precalculatie (ongerichte grafen):

const L = [ /* array van landmark locaties */ ];
let L_cost = [ /* array[nodeId] van arrays[landmarkId] */ ];

for (let landmarkId = 0; landmarkId < L.length; landmarkId++) {
    let output = dijkstraSearch(L[landmarkId]);
    for (let nodeId = 0; nodeId < graph.num_nodes; nodeId++) {
        L_cost[nodeId][landmarkId] = output.cost_so_far[nodeId];
    }
}

1. Heuristiek aanpassen: De bestaande heuristiek (bijv. Manhattan) wordt aangevuld met de hoogste ondergrens van de landmarks.

Voorbeeldcode voor de nieuwe heuristieke functie:

function heuristicLandmark(B, X) {
    let h = heuristicManhattan(B, X); // of een andere basis-heuristiek
    for (let i = 0; i < L.length; i++) {
        let lowerBound = L_cost[B][i] - L_cost[X][i];
        lowerBound = Math.abs(lowerBound); // voor ongerichte grafen
        if (lowerBound > h) {
            h = lowerBound;
        }
    }
    return h;
}

8. Demo's

De differentiële heuristiek is getest op kaarten uit Dragon Age, een doolhof en Cogmind. Allemaal zijn dit ongerichte grafen. In de visualisaties geven blauwe gebieden de knopen aan die door de verbeterde heuristiek niet langer hoeven te worden doorzocht.

• Dragon Age, The Circle Tower: De effectiviteit hangt sterk af van de plaatsing van het landmark ten opzichte van het startpad.
• Cogmind, Factory 5: Toont aan dat landmarks het meest helpen wanneer ze "voorbij" het doel liggen en relatief dichter bij het startpunt staan dan het doel zelf. Slimme plaatsing via analyse vermindert het aantal benodigde landmarks.
• Doolhof (Maze): A* met een standaard afstandsheuristiek presteert slecht in doolhoven, maar slechts vier strategische landmarks maken hier een enorm verschil.
• Dragon Age, Lothering: Werkt goed bij kaarten met grote open vlaktes.
• Cogmind, Research 2 & Factory 4: Effectief voor kamers-en-gangen structuren, zoals gebruikelijk in traditionele Roguelike dungeons.

9. Verder lezen

Deze techniek maakt gebruik van Cartesiaanse coördinaten om een graaf-gebaseerde heuristiek te bouwen met "landmark" nodes (ook wel pivots of beacons genoemd).

Referenties:

• Computing the Shortest Path: A Search Meets Graph Theory (2004, Goldberg & Harrison): Combineert bidirectionele A-zoektocht met landmark-gebaseerde heuristieken voor wegennetwerken.
• Routing information organization... (1994, Hotz): Introduceerde het gebruik van de driehoeksongelijkheid met landmarks voor internetrouting.
• Approximate Distance Oracles (2005, Thorup & Zwick): Theorie over het berekenen van geschatte afstanden tussen willekeurige knopen in een graaf via een "distance oracle".
• Predicting Internet Network Distance... (2002, Ng & Zhang): Gebruikt landmark-heuristieken om Cartesiaanse coördinaten toe te kennen aan nodes in een netwerk.
• Euclidean Heuristic Optimization (2011, Rayner, Bowling, Sturvetant): Transformeert Cartesiaanse coördinaten zodat standaard afstandsheuristieken beter werken.
• The Compressed Differential Heuristic (2011, Goldenberg et al.): Bespreekt compressie van landmark-data om meer landmarks in dezelfde ruimte op te slaan en zo de heuristiek te verbeteren.
• Approximating Shortest Paths using Landmarks (2008, Grant & Mould): Onderzoekt alternatieve plaatsingen van landmarks langs het pad.
• Hub Labels: Theory and Practice (2014, Delling et al.): Gebruikt "hubs" als tussenstations op het pad B → L → X.
• Abstraction-Based Heuristics with True Distance Computations (2009, Felner et al.): Maakt onderscheid tussen de "differentiële heuristiek" (B → X → L) en de "canonieke heuristiek" (B → L → L → L → X).

--- Voetnoten: [1] Driehoeksongelijkheid: Wikipedia [2] Video-uitleg van Thomas Nobes: YouTube [3] Kaarten van Dragon Age via movingai.com [4] Cogmind door Josh Ge [5-16] Zie bronvermeldingen in de oorspronkelijke tekst voor specifieke academische papers en mirrors.