C++ Pathfinding optimalisatie en multithreading

[switchboy]

Het probleem

Ik ben bezig een spelletje met 'RTS besturing' te maken. Nu heb ik een werkend pathfinding algoritme alleen in moeilijke situaties doet dit algoritme er 'enkele seconden' over om een oplossing te vinden. Dit zorgt helaas op zo'n moment voor een complete lock-up van het spelletje.

De belangrijkste situaties waarin dit optreed zijn:
1. Een grote afstand op een 'grote map' die vooral leeg is
2. Een niet bestaande route op een 'grote map'

Een 'grote map' bestaat hier uit 40000 tegels.

Welke oplossingen heb ik geprobeerd?

Two way flood fill

Hiermee is probleem twee al voor een groot deel de wereld uit geholpen als de obstructie tenminste een beetje in de buurt van de actor of het doel ligt. Als tijdelijke pleister draait dit nu tegelijk met A* en stop A* als hij een niet oplosbare situatie tegenkomt.

Aparte thread voor updates

Dit werkt goed en zorgt er in ieder geval voor de view van de game door blijft updaten en dat dit probleem geen complete lock-up meer veroorzaakt. Echter staan alle actors stil bij een zware route want op dit moment gebeurd het berekenen van de route bij een actor update.

Aparte thread voor actor updates welke ik ook nog asynchroom laat verlopen

Zelfde als hierboven met het voordeel dat er meerdere zware routes tegelijk in plaats van achter elkaar uitgerekend kunnen worden. Waardoor als je een groep ergens heen stuurt het in totaal korter duurt.

Het A* algoritme optimaliseren

Dit is best een uitdaging gezien ik als amateur die zichzelf wat C++ geleerd heeft eigenlijk maar wat aanmodder.
- Ik heb zoveel mogelijk berekeningen die iedere iteratie hetzelfde zijn vervangen voor een statische int die aan het begin 1x uitgerekend wordt.
- In plaats van dat ik alle buurcellen (waarbij ik dynamisch rekening moet houden met het passeerbaar zijn van een cell) aan een cel toevoeg bij het bouwen van van de cell vector voeg ik deze nu pas toe als het algoritme de cell voor het eerst tegen komt. Bij een makkelijk vindbaar doel scheelt dit toch wel tijd gezien er dan weinig cellen geëvalueerd moeten worden.

Optimalisatie A* welke niet lukt

- Het liefst zou ik de array met standaard 8 buurcellen die of -1 zijn of een id hebben willen vervangen voor een lijst. Waar gewoon de gevonden buurcellen instaan. Alleen vind de vector waar een struct inzit waarin die lijst weer zou moeten zitten het volgende commando niet fijn:
cellsList[i].neighbours.push_back() == stackoverflow
cellsList[i].neighbours.front() == stackoverflow
enzovoorts...
Met andere woorden geen idee hoe ik die lijst moet benaderen om er iets in te zetten en uit te halen. Een array werkte wel, dan maar dat.
Nu kan het dus zo zijn dat voor een cell met maar 1 buurman waar ik heenkan ik 8 keer een adres in een array moet checken.

Multithreaded bi-derectional A*

Dit geeft misschien niet het meest optimale pad maar is in theorie wel twee keer zo snel! Het is in theorie ook simpel te maken. Je wisselt het begin en eindpunt om in het al bestaande algortime voor de tweede thread en je laat aan het einde als er een botsing was de eerste thread de route vanaf het startpunt tot de botsing in de lijst zetten en hierna mag de tweede thread de cellen van de botsing naar het doel toevoegen.

Los van elkaar heb ik het zo werkend gekregen. Het pijnpunt is echter omdat ik het vanwege de snelheid in twee threads wil hebben dat ik van beide threads een lijst met gecheckte cellen moet bijhouden welke de andere thread in moet kunnen zien om een botsing te kunnen detecteren. Hiervoor had ik twee arrays gemaakt waar de ene thread in schrijft en de andere in leest en vicaversa. Echter als ik met deze aanpassing de twee pathfinding threads draai geeft hij een segmentation fault terug. Het gekke is dat in de debugger hij deze regel aangeeft als pijnpunt: regel 124 in bijgevoegde source

code:

if(!cellsList[newCellId].visited)

Beide threads hebben echter hun eigen 'cellsList' dus dat zou geen probleem moeten geven. Wat wel is dat de gewraakte lees en schrijfacties naar de twee arrays wel plaats gaan vinden als deze if statement true is. Dus mogelijk dat de debugger daarom hier blijft hangen?
Het werkt namelijk prima als ik de twee threads naast elkaar heb draaien en die lees en schrijfacties naar die array heb weggecomment.

De array vervangen voor een vector geeft hetzelfde gedrag. Met of zonder mutex lock.

Wat wil ik nog gaan proberen?

De pathfinding uit de actor update halen

Op dit moment roept een de update functie van de actor de pathfinding aan als die erachter komt dat er nog een pad berekend moet worden. Ik zou dit los kunnen koppelen en een aparte pathupdater thread kunnen maken die de hele tijd alle actors langsgaat en paden uitrekend waar nodig. Op die manier blijft de rest van het spel doorgaan.

[h2]Single threaded bidirectional A*[h2]
Als ik geen oplossing vindt voor het eerder beschreven probleem

Waypoints op de map

Liever niet gezien de map met gebouwen en actors die niet tegelijk op een hokje mogen de map nogal dynamisch maken.

Tot slot

Zoals jullie zien is het performance probleem van de pathfinding een aardige bezighouder voor mij geweest. Ik heb hierdoor wel voor het eerst ooit verdiept in multithreading! Dus leerzaam is het zeker. Ik heb alleen wel het idee dat het een beetje een roadblock begint te worden om dit spel verder af te maken. Als jullie verdere suggesties hebben of een idee waarom hij segmentation faults uit blijft spugen sta ik open voor suggesties!

Sauce

code:

struct Cells{
        int positionX, positionY, parentCellId, cummulativeCost, cellId;
        double costToGoal, totalCostGuess;
        bool visited = false;
        bool obstacle = false;
        int neighbours[8];
};


struct routeCell
{
    int positionX;
    int positionY;
    int visited;
    int parentCellId;
};



void actors::calculateRoute()
{
    this->noPathPossible = false;
    this->forwardIsDone = false;
    this->collisionCell = -1;
    this->mapArray.reserve(MAP_HEIGHT*MAP_WIDTH);
    this->mapArrayBack.reserve(MAP_HEIGHT*MAP_WIDTH);
    for(int i = 0; i < MAP_HEIGHT*MAP_WIDTH; i++)
    {
        this->mapArray[i] = 0;
        this->mapArrayBack[i] = 0;
    }
    std::thread pathfinding(&actors::pathAStar, &listOfActors[this->actorId], false);
    std::thread pathfindingBackwards(&actors::pathAStar, &listOfActors[this->actorId], true);
    if(canTargetBeReached())
    {
        pathfinding.join();
        pathfindingBackwards.join();
    }
    else
    {
        this->noPathPossible = true;
        pathfinding.join();
        pathfindingBackwards.join();
    }
}


std::mutex mtx;

void actors::pathAStar(bool backward)
{
    std::vector<Cells> cellsList;
    cellsList.reserve(MAP_HEIGHT*MAP_WIDTH);
    updateCells(this->actorGoal[0], this->actorGoal[1], cellsList);
    std::list<Cells> listToCheck;
    std::list<Cells> checkedList;
    int startCell;
    int endCell;
    if(!backward)
    {
        startCell = (actorCords[0]*MAP_HEIGHT)+actorCords[1]; //eigen positie
        endCell = (actorGoal[0]*MAP_HEIGHT)+actorGoal[1]; //doel positie
    }
    else
    {
        endCell = (actorCords[0]*MAP_HEIGHT)+actorCords[1]; //eigen positie
        startCell = (actorGoal[0]*MAP_HEIGHT)+actorGoal[1]; //doel positie
    }
    bool endReached = false;

    //check of de doelcel niet 1 hokje weg is
    if(((actorCords[0]-actorGoal[0] == 0) ||(actorCords[0]-actorGoal[0] == -1) ||(actorCords[0]-actorGoal[0] == 1)) && ((actorCords[1]-actorGoal[1] == 0) ||(actorCords[1]-actorGoal[1] == -1) ||(actorCords[1]-actorGoal[1] == 1)))
    {
        if(!cellsList[endCell].obstacle)
        {
            this->pathFound = true;
            endReached = true;
        }
        else
        {
            this->pathFound = false;
        }
    }
    else
    {
        this->pathFound = false;
        addNeighbours(startCell, cellsList);
        cellsList[startCell].visited = true;
        listToCheck.push_back(cellsList[startCell]);
    }

    while(!listToCheck.empty() && startCell != endCell)
    {
        if(this->collisionCell != -1)
        {
            listToCheck.clear();
            this->pathFound = true;
        }
        //sorteer de lijst en zet de cell met de laagste cost to goal bovenaan om het eerst te testen
        listToCheck.sort([](const Cells &f, const Cells &s)
        {
            return f.totalCostGuess < s.totalCostGuess;
        });
        //Check of de te checken cell het doel is. Als dat zo is zijn we klaar
        if(listToCheck.front().cellId == endCell)
        {
            listToCheck.clear();
            this->pathFound = true;
        }
        else if(this->noPathPossible)
        {
            listToCheck.clear();
        }
        else
        {
            for(int q = 0; q < 8; q++)
            {
                if(listToCheck.front().neighbours[q] != -1)
                {
                    int newCellId = listToCheck.front().neighbours[q];
                    //We have found neighbours!
                    //check if neighbours was found before
                    if(!cellsList[newCellId].visited)
                    {
                        //Deze cell heeft geen parent is is dus nooit eerder gevonden! De buren moeten dus toegevoegd worden!
                        addNeighbours(newCellId, cellsList);
                        //De cell waarvan we de neighbours onderzoeken is dus automagisch tot nu toe de kortste route hiernaartoe
                        cellsList[newCellId].parentCellId = listToCheck.front().cellId;
                        //Nu moeten de kosten voor de route hiernatoe uitgerekend worden (Dit zijn de kosten van naar de buurman gaan +1
                        cellsList[newCellId].cummulativeCost = listToCheck.front().cummulativeCost+1;
                        //Als laatste zetten we de cell in de lijst met cellen die gecheckt moet worden
                        listToCheck.push_back(cellsList[newCellId]);
                        //Bereken de afstand naar het doel
                        cellsList[newCellId].costToGoal = dist(cellsList[newCellId].positionX,cellsList[newCellId].positionY,cellsList[endCell].positionX,cellsList[endCell].positionY);
                        cellsList[newCellId].totalCostGuess = cellsList[newCellId].costToGoal + cellsList[newCellId].cummulativeCost;
                        cellsList[newCellId].visited = true;
                        while(!mtx.try_lock()){}
                        if(backward)
                        {
                            if(this->mapArray[newCellId] == 1)
                            {
                                //Collisiion!
                                this->collisionCell = newCellId;
                            }
                            else
                            {
                                this->mapArrayBack[newCellId] = 1;

                            }
                        }
                        else
                        {
                            if(this->mapArrayBack[newCellId] == 1)
                            {
                                //Collisiion!
                                this->collisionCell = newCellId;
                            }
                            else
                            {
                                this->mapArray[newCellId] = 1;
                            }
                        }
                        mtx.unlock();
                    }
                    else
                    {
                        //Deze cell is al eerder gevonden, staat dus al in de te checken cell lijst
                        if(listToCheck.front().cummulativeCost+1 < cellsList[newCellId].cummulativeCost)
                        {
                            //Er is een kortere route naar deze cell! Pas de parent cell dus aan en geef een nieuwe cummulative Cost;
                            cellsList[newCellId].parentCellId = listToCheck.front().cellId;
                            cellsList[newCellId].cummulativeCost = listToCheck.front().cummulativeCost+1;
                            cellsList[newCellId].totalCostGuess = cellsList[newCellId].costToGoal + cellsList[newCellId].cummulativeCost;
                        }
                    }
                }
            }
            checkedList.push_back(listToCheck.front());
            listToCheck.pop_front();
        }
    }



    //Zet de te lopen route in een lijst
    if(!backward)
    {
        this->route.clear();
        if(this->collisionCell == -1)
        {
            this->route.push_back({cellsList[endCell].positionX, cellsList[endCell].positionY, cellsList[endCell].visited, cellsList[endCell].parentCellId});
        }
        else
        {
            this->route.push_back({cellsList[collisionCell].positionX, cellsList[collisionCell].positionY, cellsList[collisionCell].visited, cellsList[collisionCell].parentCellId});
            this->forwardIsDone = true;
        }
        if(this->pathFound)
        {
            while(!endReached)
            {
                if(route.back().visited == true)
                {

                    this->route.push_back({cellsList[route.back().parentCellId].positionX, cellsList[route.back().parentCellId].positionY, cellsList[route.back().parentCellId].visited, cellsList[route.back().parentCellId].parentCellId});
                    if(this->route.back().parentCellId == startCell)
                    {
                        endReached = true;
                    }
                }
                else
                {
                    endReached = true;
                }
            }
        }
    }
    else if(this->pathFound && this->collisionCell != -1)
    {
        while(!this->forwardIsDone)
        {
            //wait
        }
        while(!endReached)
        {
            if(route.front().visited == true)
            {
                this->route.push_front({cellsList[route.front().parentCellId].positionX, cellsList[route.front().parentCellId].positionY, cellsList[route.front().parentCellId].visited, cellsList[route.front().parentCellId].parentCellId});
                if(this->route.front().parentCellId == startCell)
                {
                    this->route.push_front({cellsList[route.front().parentCellId].positionX, cellsList[route.front().parentCellId].positionY, cellsList[route.front().parentCellId].visited, cellsList[route.front().parentCellId].parentCellId});
                    endReached = true;
                }
            }
            else
            {
                endReached = true;
            }
        }
    }
}

complete bron: https://github.com/switchboy/isometric

[Ghehe]

Kan je niet optimaliseren door paden voor te berekenen of te cachen? Of een simpelere graph maken met enkel de belangrijke punten (zoals op een wegenkaart enkel autostrades te tonen)?

[Bolukan]

Ik moest gelijk hieraan denken: Wikipedia: Pathfinding. Maar de kern is, is A* met een perfecte oplossing wel nodig?

[Christiaan676]

Aangezien je alle routes op het zelfde netwerk aan het bereken bent, zijn er technieken om wat eenmalige voorwerk te doen om de rest van de berekening te versnellen. Bijvoorbeeld https://en.m.wikipedia.org/wiki/Contraction_hierarchies.

[armageddon_2k1]

Ik vind de uitkomsten wel verrassend. Wij gebruiken A* in onze webapp waar we soms 100 verschillende paden binnen 500ms in Javascript(!) genereren. Ik heb bijna niks hoeven te optimaliseren, behalve een juiste heuristic te kiezen en een goede data structuur voor de “frontier”. Dat moet natuurlijk een priority queue zijn die op heuristic sorteert.

De verkeerde data structuur voor je frontier zorgt ervoor dat ie makkelijk opblaast. Ik kan je code niet goed lezen op m’n phone maar ik kan moeilijk zien waar ie de juiste volgende stap kiest op basis van de heuristic.

Ps, de laden zijn soms 200 stappen lang. Over een grid.

[ Voor 21% gewijzigd door armageddon_2k1 op 15-04-2020 21:37 ]

[switchboy]

Voor een framerate van 60 fps heb ik 16ms per frame. Waarin ook nog alle andere dingen in moeten gebeuren om de wereld een update te geven en te rekenen. Korte routes lukken in die tijd prima.
Het gaat hier om de hele map oversteken 200 tegels. Jouw algoritme zou hier 5ms voor nodig hebben. Die van mij 2000 worst case (lege map). Daar moet dus nog wel wat qua optimalisatie te halen zijn.

Wat ik zat nog zat te denken is dat ik misschien alsnog teveel data heen en weer kopieer. Als ik namelijk een cel aan de te checken lijst toevoeg dan voeg ik niet een pointer naar die cel of alleen een cell id toe maar kopieert hij alle data van die cel. Dat zijn 4 integers 1 bool en een array van 8 integers. Dat is misschien wel deel van het probleem.

De andere verdachte is de sorteer functie van die lijst die op basis van de totale geschatte kosten de beste volgende tegel voor de volgende evaluatie vooraan zet. Nu ik me bedacht dat ik bij eerste discovery de cel in de te doorzoeken lijst kopieer hij nooit geupdate scores meekrijgt die misschien later voor die cel gevonden worden!

Oftewel ik moet even kijken of het met een referentie niet veel sneller en accurater wordt...

Ik denk dat ik het antwoord al weet... Ik zal het terugkoppelen als ik van t weekend weer wat heb kunnen hobbyen!

[CCJJVV]

Ik ben bang dat de dingen die voor jou misschien heel logisch hebben geleken als optimalisatie stappen eigenlijk tegen je gaan werken. Neem bijvoorbeeld de if-statement op regel 72 met 6?!? OR statements.

Zoals in de pseudo-code van A* op wikipedia te zien is moet je enkel kijken of de huidige cell het doel is.
Nu voer je de check veel te vaak uit en ook meerdere malen voor dezelfde cel.

Neem het veld:

code:

1    2     3    4
5    6     7    8
9    10    11   12
13   14    15   16

Stel we staan nu op cel 6, dan kijken we in jouw geval of het doel 1 cel vanaf de huidige cel ligt. Je kijkt dus of het doel op cel 1,2,3,5,7,9,10 of 11 ligt. Stel dat is niet zo dan hebben we dus voor niks 6 statements uit moeten voeren. Dan gaan we vervolgens naar 11, we kijken weer of het doel 1 cel vanaf 11 ligt. Nu kijken we dus of 6,7,8,10,12,14,15,16 het doel is. Dit terwijl we net van 6 komen en dus niet het doel kan zijn en we daarnaast 7,8 en 10 al bij cel 6 hebben bekeken.

Mijn tip zou zijn: begin even opnieuw met het implementeren van A* en blijf zo dicht mogelijk bij de implementatie die in pseudo code gegeven is.

[RobIII]

Daarbij; eens een cell bezocht kun je natuurlijk, zolang de situatie er in / omheen niet verandert het resultaat cachen (zoals bijv. hier beschreven wordt - de video gaat wal over breadth-first maar het idee is 'tzelfde; een soort memoization). Het is gekkenwerk elk frame je "hele" speelveld te doorlopen; hell: je kunt ook gewoon elke seconde (of 2, 3, ...) een A* doen en de overige frames gewoon op dat plan doorgaan - afhankelijk van het type game kan dat mogelijk ook best. Verder sluit ik me aan bij @Christiaan676.

[ Voor 3% gewijzigd door RobIII op 16-04-2020 00:20 ]

[Gomez12]

Bijvraag dan, maar waarom zou je een complete pathfinding over de complete route moeten doen?

Kan je niet een directe omgeving creeren van 100x100 daarin doe je actieve pathfinding per cel.
En daarbuiten doe je grovere pathfinding per 10 cellen oid?

Mij is altijd geleerd dat je niets moet doen als je niets toont, dat dat de beste optimalisatie is.
Oftewel toon je een minimap/heb je globaal wat beweging nodig dan moet je dat niet hetzelfde berekenen als wat je onscreen toont.

Ik zou zeggen onscreen (met een marge van 10% oid zodat je geen scroll issues krijgt) reken je met een factor 1, cirkel daarbuiten met een factor 10 en cirkel daar weer buiten met een factor 100.
Het is niet zo relevant dat een npc aan de andere kant van de map door een boom heenloopt (dat detail is toch niet zichtbaar), zolang hij maar niet door een berg heenloopt.

Enige waar je op moet letten is dat je sommige dingen dan wel een minimum width moet geven, want als je met een factor 100 rekent en je stadsmuren zijn 90 breed dan kunnen mensen daar gewoon doorheen gaan etc.

[CCJJVV]

RobIII schreef op donderdag 16 april 2020 @ 00:17:
Daarbij; eens een cell bezocht kun je natuurlijk, zolang de situatie er in / omheen niet verandert het resultaat cachen (zoals bijv. hier beschreven wordt - de video gaat wal over breadth-first maar het idee is 'tzelfde; een soort memoization). Het is gekkenwerk elk frame je "hele" speelveld te doorlopen; hell: je kunt ook gewoon elke seconde (of 2, 3, ...) een A* doen en de overige frames gewoon op dat plan doorgaan - afhankelijk van het type game kan dat mogelijk ook best. Verder sluit ik me aan bij @Christiaan676.

Omdat de usecase van het algoritme uit het verhaal van TS niet volledig duidelijk is zie ik persoonlijk nog niet echt in hoe de "caching" manier uit het filmpje moet gaan helpen. Als TS inderdaad veel paden naar hetzelfde punt wilt berekenen is dit een prima oplossing.

Verder is het voor zover ik nu even snel kan beredeneren niet echt mogelijk om de uitkomst van A* te "cachen", uiteraard kan je het korste pad onthouden en alle andere paden naar alle andere bezochten punten. Maar al deze paden zullen vanaf de begin positie van A* zijn verplaatst de actor zich 1 cell naar rechts dan is de hele "cache" van A* waardeloos en kan alleen het gevonden korste pad nog gebruikt worden. Verplaatst de actor zich niet na het uitvoeren van A* of verplaatst hij zicht terug en niks is veranderd en wil hij opeens naar een ander punt dat al bezocht was bij het uitvoeren van A* dan is deze "cache" pas te gebruiken. Geen idee inhoeverre er veel veranderingen in het spel TS gebeuren maar dit allemaal cachen + controleren of er iets veranderd is lijkt mij meer werk dan A* even optimaliseren.

Wil TS echter éénmaal van punt a naar punt b dan lijkt mij A* alsnog handiger, maar zoals ik al zei heeft TS daar nog niet genoeg informatie overgegeven.

Ik moet je wel gelijk geven dat het natuurlijk waar is dat A* niet elk frame uitgevoerd moet worden en al helemaal niet als er niks veranderd, maar in dat geval mag het alsnog niet zo zijn dat je 2 seconden moet wachten op een pad. Er zal dan toch gekeken moeten worden waar TS de fout in gaat met zijn implementatie van A*.

[ Voor 5% gewijzigd door CCJJVV op 16-04-2020 01:47 ]

[RobIII]

CCJJVV schreef op donderdag 16 april 2020 @ 01:44:
Maar al deze paden zullen vanaf de begin positie van A* zijn verplaatst de actor zich 1 cell naar rechts dan is de hele "cache" van A* waardeloos en kan alleen het gevonden korste pad nog gebruikt worden

Ik ben 't met je eens dat de use-case van TS niet heel erg duidelijk is en het daardoor een beetje koffiedik kijken is, maar even specifiek inhakend hierop: als de speler zich maar één cell verplaatst (en voor de speler gelden dezelfde regels als NPC's) dan zou je, afhankelijk van de afstand bijvoorbeeld (ver of dichtbij de speler), natuurlijk alleen maar die ene verplaatsing aan je gevonden pad toe te voegen; periodiek kun je het hele pad her-evalueren voor een optimalere route en de rest van de tijd gebruik je het cached pad. Maar dat is natuurlijk afhankelijk van het soort game, hoe 'sterk' je je NPC's wil hebben etc. etc. Als ik je achterna zit door Nederland en ik zit in Maastricht en jij in Groningen en jij verplaatst je naar de buren (en dan weer naar diens buren en ...), moet ik dan echt m'n routeplanner weer aanzwengelen elke keer als jij een deur opschuift? Of blijf ik tot ik Groningen in rij dezelfde wegen gebruiken? Pas als ik in de buurt kom, of als jij meer dan X verplaatst bent, ga je eens je route her-evalueren. Dus om je cache meteen waardeloos te beschouwen bij een move... misschien, misschien ook niet. Ik gooi alleen maar wat balletjes op

[ Voor 17% gewijzigd door RobIII op 16-04-2020 01:56 ]

[CCJJVV]

RobIII schreef op donderdag 16 april 2020 @ 01:52:
[...]

Ik ben 't met je eens dat de use-case van TS niet heel erg duidelijk is en het daardoor een beetje koffiedik kijken is, maar even specifiek inhakend hierop: als de speler zich maar één cell verplaatst (en voor de speler gelden dezelfde regels als NPC's) dan zou je, afhankelijk van de afstand bijvoorbeeld (ver of dichtbij de speler), natuurlijk alleen maar die ene verplaatsing aan je gevonden pad toe te voegen; periodiek kun je het hele pad her-evalueren voor een optimalere route en de rest van de tijd gebruik je het cached pad. Maar dat is natuurlijk afhankelijk van het soort game, hoe 'sterk' je je NPC's wil hebben etc. etc. Als ik je achterna zit door Nederland en ik zit in Maastricht en jij in Groningen en jij verplaatst je naar de buren (en dan weer naar diens buren en ...), moet ik dan echt m'n routeplanner weer aanzwengelen elke keer als jij een deur opschuift? Of blijf ik tot ik Groningen in rij dezelfde wegen gebruiken? Pas als ik in de buurt kom, of als jij meer dan X verplaatst bent, ga je eens je route her-evalueren. Dus om je cache meteen waardeloos te beschouwen bij een move... misschien, misschien ook niet. Ik gooi alleen maar wat balletjes op

Of het helemaal waardeloos is valt natuurlijk over te twisten, waar ik dagelijks mee te maken heb zou dit een ja zijn. In een game kan ik inderdaad goed begrijpen dat dit nog gezien wordt als waardevol. Toch zie ik nog niet echt in waar en hoe je de grens dan zou trekken tussen waardevol en waardeloos. Ik zie zo 1,2,3 niet in hoe je efficiënt kan kijken of er een verandering heeft plaatst gevonden in het speelveld. Het kan maar zo zijn dat een NPC net de cell heeft ingenomen waardoor het hele pad ook met een omweg bij lange na niet meer het kortste pad is.
Het zou best kunnen zijn dat ik hier een onnodig groot probleem van maak omdat ik zelf altijd gegarandeerd het kortste pad/ max-flow o.i.d. wil hebben.

Wat meer informatie van TS zou al flink kunnen helpen naar het vinden van de beste oplossing.

[Gomez12]

CCJJVV schreef op donderdag 16 april 2020 @ 02:02:
[...]
Of het helemaal waardeloos is valt natuurlijk over te twisten, waar ik dagelijks mee te maken heb zou dit een ja zijn. In een game kan ik inderdaad goed begrijpen dat dit nog gezien wordt als waardevol. Toch zie ik nog niet echt in waar en hoe je de grens dan zou trekken tussen waardevol en waardeloos.

Bij een game heb je veelal een vrij directe scheiding tussen lokaal gebied (/spelerveld) en niet lokaal gebied (/rest).
Waarbij je qua niet-lokaal alles kan laten schieten, je kan gewoon die berekenening ook gewoon afknallen als die te lang duurt voor niet-lokaal en dan gewoon door blijven op hetzelfde pad etc.

Sterker nog, het is een gigantische goedkope extra bijdrage voor de gemiddelde game om dit erin te hebben zitten, want het genereert een stukje randomness voor de grotere afstand.
Het voorkomt dat als jij npc 1 op tijdstip x op het speelveld zet, dat je die altijd op tijdstip y op positie z gaat terugvinden (wat je wel hebt met een "perfecte a*" benadering), globaal gezien zal hij er meestal wel langskomen, maar het kan vandaag net 5 seconden eerder zijn dan gisteren omdat zijn voorliggende pad anders is.

Ik zie zo 1,2,3 niet in hoe je efficiënt kan kijken of er een verandering heeft plaatst gevonden in het speelveld. Het kan maar zo zijn dat een NPC net de cell heeft ingenomen waardoor het hele pad ook met een omweg bij lange na niet meer het kortste pad is.

Dat is het voordeel van een spel, daar geldt in principe juist absoluut niet gegarandeerd het kortste pad.
Neem jouw voorbeeld, alleen nu zitten er 2000 tegels tussen, hoe weet de NPC dan ingame dat zijn pad over 2000 tegels geblokkeerd gaat zijn? Ingame heeft de NPC maar een zicht van 10 tegels en zal hij dus zijn oude pad moeten blijven vervolgen tot hij 1990 tegels gelopen heeft.

Of neem het voorbeeld van RobIII, als de npc in Groningen vertrekt naar Amsterdam, hoe weet ik dat als speler als ik van Maastricht naar Groningen rijd? Je kan het uitrekenen, maar hoe verklaar je het ingame? In de "realiteit" moet ik eerst naar Groningen rijden, daar constateren dat de npc er niet is en daar mogelijk een clue vinden dat de npc nu in Amsterdam zit en dan kan ik onderweg naar Amsterdam, alleen die route blijft gewoon gelijk tot ik in Amsterdam zit, ongeacht of de npc nu weer naar Maastricht doorrijd of niet, dat weet ik niet zolang ik niet in Amsterdam ben.

In wezen is in-game elk path met een doel, een fixed path totdat de NPC ingame kan constateren dat het path incorrect is, of de npc ingame kan constateren dat het doel weg is.
Zolang de npc dat niet ingame kan constateren blijft het gewoon doorgaan op zijn huidige path.

Het zou best kunnen zijn dat ik hier een onnodig groot probleem van maak omdat ik zelf altijd gegarandeerd het kortste pad/ max-flow o.i.d. wil hebben.

Dat wil je in-game juist bijna altijd expliciet niet, dan krijg je alleen maar 100% scripted / voorspelbare acties... Je wilt ingame een beetje variatie, je wilt niet hebben dat er een ideaal pad voor de speler ontstaat waarmee hij gegarandeerd altijd wint omdat naar gelang zijn acties de kortste paden altijd gelijk zijn (bij een gelijk startpositie)

[switchboy]

RobIII schreef op donderdag 16 april 2020 @ 00:17:
Daarbij; eens een cell bezocht kun je natuurlijk, zolang de situatie er in / omheen niet verandert het resultaat cachen (zoals bijv. hier beschreven wordt - de video gaat wal over breadth-first maar het idee is 'tzelfde; een soort memoization). Het is gekkenwerk elk frame je "hele" speelveld te doorlopen; hell: je kunt ook gewoon elke seconde (of 2, 3, ...) een A* doen en de overige frames gewoon op dat plan doorgaan - afhankelijk van het type game kan dat mogelijk ook best. Verder sluit ik me aan bij @Christiaan676.

Dat doe ik ook. Ik doe pas opnieuw aan pathfinding als ik tegen een onverwacht obstakel bots.

CCJJVV schreef op woensdag 15 april 2020 @ 23:27:
Ik ben bang dat de dingen die voor jou misschien heel logisch hebben geleken als optimalisatie stappen eigenlijk tegen je gaan werken. Neem bijvoorbeeld de if-statement op regel 72 met 6?!? OR statements.

Zoals in de pseudo-code van A* op wikipedia te zien is moet je enkel kijken of de huidige cell het doel is.
Nu voer je de check veel te vaak uit en ook meerdere malen voor dezelfde cel.

Neem het veld:

code:

1    2     3    4
5    6     7    8
9    10    11   12
13   14    15   16

Stel we staan nu op cel 6, dan kijken we in jouw geval of het doel 1 cel vanaf de huidige cel ligt. Je kijkt dus of het doel op cel 1,2,3,5,7,9,10 of 11 ligt. Stel dat is niet zo dan hebben we dus voor niks 6 statements uit moeten voeren. Dan gaan we vervolgens naar 11, we kijken weer of het doel 1 cel vanaf 11 ligt. Nu kijken we dus of 6,7,8,10,12,14,15,16 het doel is. Dit terwijl we net van 6 komen en dus niet het doel kan zijn en we daarnaast 7,8 en 10 al bij cel 6 hebben bekeken.

Mijn tip zou zijn: begin even opnieuw met het implementeren van A* en blijf zo dicht mogelijk bij de implementatie die in pseudo code gegeven is.

Zal ik naar kijken, echter regel 72 kijkt of de doelcel niet een buurman van de startcel is en voorkomt dan dat heel A* gaat lopen. Wordt in principe maar 1x uitgevoerd.

Gomez12 schreef op donderdag 16 april 2020 @ 00:20:
Bijvraag dan, maar waarom zou je een complete pathfinding over de complete route moeten doen?

Kan je niet een directe omgeving creeren van 100x100 daarin doe je actieve pathfinding per cel.
En daarbuiten doe je grovere pathfinding per 10 cellen oid?

Mij is altijd geleerd dat je niets moet doen als je niets toont, dat dat de beste optimalisatie is.
Oftewel toon je een minimap/heb je globaal wat beweging nodig dan moet je dat niet hetzelfde berekenen als wat je onscreen toont.

Ik zou zeggen onscreen (met een marge van 10% oid zodat je geen scroll issues krijgt) reken je met een factor 1, cirkel daarbuiten met een factor 10 en cirkel daar weer buiten met een factor 100.
Het is niet zo relevant dat een npc aan de andere kant van de map door een boom heenloopt (dat detail is toch niet zichtbaar), zolang hij maar niet door een berg heenloopt.

Enige waar je op moet letten is dat je sommige dingen dan wel een minimum width moet geven, want als je met een factor 100 rekent en je stadsmuren zijn 90 breed dan kunnen mensen daar gewoon doorheen gaan etc.

Zou kunnen echter zou je obstakels kunnen gaan missen waardoor je actor bijvoorbeeld eerst 20 stappen de verkeerde kant op loopt en vervolgens tegen iets opbotst en een heel stuk terug moet. Met een beetje ongelukkig geplaatste obstakels die steeds net gemist worden kan hij in theorie ook gaan ijsberen zonder bij het doel te komen.

Gomez12 schreef op donderdag 16 april 2020 @ 08:03:
[...]

Bij een game heb je veelal een vrij directe scheiding tussen lokaal gebied (/spelerveld) en niet lokaal gebied (/rest).
Waarbij je qua niet-lokaal alles kan laten schieten, je kan gewoon die berekenening ook gewoon afknallen als die te lang duurt voor niet-lokaal en dan gewoon door blijven op hetzelfde pad etc.

Sterker nog, het is een gigantische goedkope extra bijdrage voor de gemiddelde game om dit erin te hebben zitten, want het genereert een stukje randomness voor de grotere afstand.
Het voorkomt dat als jij npc 1 op tijdstip x op het speelveld zet, dat je die altijd op tijdstip y op positie z gaat terugvinden (wat je wel hebt met een "perfecte a*" benadering), globaal gezien zal hij er meestal wel langskomen, maar het kan vandaag net 5 seconden eerder zijn dan gisteren omdat zijn voorliggende pad anders is.


[...]

Dat is het voordeel van een spel, daar geldt in principe juist absoluut niet gegarandeerd het kortste pad.
Neem jouw voorbeeld, alleen nu zitten er 2000 tegels tussen, hoe weet de NPC dan ingame dat zijn pad over 2000 tegels geblokkeerd gaat zijn? Ingame heeft de NPC maar een zicht van 10 tegels en zal hij dus zijn oude pad moeten blijven vervolgen tot hij 1990 tegels gelopen heeft.

Of neem het voorbeeld van RobIII, als de npc in Groningen vertrekt naar Amsterdam, hoe weet ik dat als speler als ik van Maastricht naar Groningen rijd? Je kan het uitrekenen, maar hoe verklaar je het ingame? In de "realiteit" moet ik eerst naar Groningen rijden, daar constateren dat de npc er niet is en daar mogelijk een clue vinden dat de npc nu in Amsterdam zit en dan kan ik onderweg naar Amsterdam, alleen die route blijft gewoon gelijk tot ik in Amsterdam zit, ongeacht of de npc nu weer naar Maastricht doorrijd of niet, dat weet ik niet zolang ik niet in Amsterdam ben.

In wezen is in-game elk path met een doel, een fixed path totdat de NPC ingame kan constateren dat het path incorrect is, of de npc ingame kan constateren dat het doel weg is.
Zolang de npc dat niet ingame kan constateren blijft het gewoon doorgaan op zijn huidige path.


[...]

Dat wil je in-game juist bijna altijd expliciet niet, dan krijg je alleen maar 100% scripted / voorspelbare acties... Je wilt ingame een beetje variatie, je wilt niet hebben dat er een ideaal pad voor de speler ontstaat waarmee hij gegarandeerd altijd wint omdat naar gelang zijn acties de kortste paden altijd gelijk zijn (bij een gelijk startpositie)

Voor een rts ben ik het daar niet helemaal mee eens. Daar heb je behalve het instellen van het doel weinig verdere controle over je units. En sloppy pathfinding kan dan een enorme verstoring van de gameplay geven. Wat wél leuk is om toe te voegen is dat je pathfinding pas obstakels kan zien als ze ooit uit de fog-of-war tevoorschijn zijn gekomen. Maar je actor zou wmb nooit een pad moeten gaan volgen waarvan je op de minimap al kan zien dat het niet gaat werken.

Een cache bijhouden met welke tegels obstakels bevatten, dat doe ik al. De functie ispassable checkt in principe een array van de hele map waar een 0 of 1 op kan staan. Actors objecten en de map tegels zorgen voor een update van deze array als ze gecreëerd worden of van positie veranderen.

[Butsnik]

switchboy schreef op woensdag 15 april 2020 @ 22:51:
Voor een framerate van 60 fps heb ik 16ms per frame. Waarin ook nog alle andere dingen in moeten gebeuren om de wereld een update te geven en te rekenen. Korte routes lukken in die tijd prima.
Het gaat hier om de hele map oversteken 200 tegels. Jouw algoritme zou hier 5ms voor nodig hebben. Die van mij 2000 worst case (lege map). Daar moet dus nog wel wat qua optimalisatie te halen zijn.

Bedoel je met een lege map helemaal geen obstakels? Want in dat geval zou A* direct het pad naar het doel moeten vinden en zou je net iets van 200 updates (recht pad, 1 per update) hebben.

Weet je zeker dat je implementatie klopt verder. Misschien goed om het een en ander te visualiseren zoals hier: https://www.reddit.com/r/...algorithms_visualized_oc/. Zo weet je zeker dat je in de goede volgorde zoekt.

[ Voor 3% gewijzigd door Butsnik op 16-04-2020 10:38 ]

[RobIII]

switchboy schreef op donderdag 16 april 2020 @ 08:50:
Een cache bijhouden met welke tegels obstakels bevatten, dat doe ik al. De functie ispassable checkt in principe een array van de hele map waar een 0 of 1 op kan staan. Actors objecten en de map tegels zorgen voor een update van deze array als ze gecreëerd worden of van positie veranderen.

De me een lol en zet je algoritme eens in pseudocode hier neer? die 250 regels code die je nu post zijn vrij lastig mentaal te bevatten / overzien, maar als je 't in een regel of 20/30 pseudocode kunt neerzetten (inc. dus optimalisaties en dingen die je nu uit je TS evt. achterwege hebt gelaten) dan kunnen we misschien makkelijker zeggen waar 't fout gaat of wat je nog zou kunnen proberen.
Verder wil ik je adviseren te profilen. Meten == weten. Dus meet eens waar de meeste tijd in gaat zitten en kijk dan eens wat je daar eventueel aan zou kunnen verbeteren.

[armageddon_2k1]

Probeer ook eens een testcase te maken met een klein grid en log of print welke stappen er genomen worden. Met een juist geïmplementeerd algoritme zie je meteen of alles klopt.

[switchboy]

Na van

code:

std::list<Cells> listToCheck;

code:

std::list<Cells*> listToCheck;

gemaakt te hebben waardoor het object cell niets gekopieerd wordt in de lijst met te checken cellen. maar in plaats daarvan een pointer opslaat en hij hierdoor ook juist sorteerd ) waardoor de cel met de echte laagste cummulatieve geschatte kosten bovenaan de lijst (als er bv naderhand van die specifieke cell een lagere cummulatieve score berekend wordt door een andere route) is de pathfinding van >5000ms naar near instantaan gegaan!

Bedankt voor het meedenken allemaal!

Voor de geïnterseerden dit is de meat en patatoes van het algoritme:

code:

while(!listToCheck.empty() && startCell != endCell)
    {
        //sorteer de lijst en zet de cell met de laagste cost to goal bovenaan om het eerst te testen
        listToCheck.sort([](const Cells* f, const Cells* s)
        {
            return f->totalCostGuess < s->totalCostGuess;
        });

        //Check of de te checken cell het doel is. Als dat zo is zijn we klaar
        if((*listToCheck.front()).cellId == endCell)
        {
            listToCheck.clear();
            this->pathFound = true;
        }
       //check of de floodfill niet al heeft bepaald of het pad onmogelijk is
        else if(this->noPathPossible)
        {
            listToCheck.clear();
        }
        else if(!listToCheck.empty())
        {
            for(int q = 0; q < 8; q++)
            {
                if((*listToCheck.front()).neighbours[q] != -1)
                {
                    int newCellId = (*listToCheck.front()).neighbours[q];
                    //We have found neighbours!
                    //check if neighbours was found before
                    if(!cellsList[newCellId].visited)
                    {
                        //Deze cell heeft geen parent is is dus nooit eerder gevonden! De buren moeten dus toegevoegd worden!
                        addNeighbours(newCellId, cellsList);
                        //De cell waarvan we de neighbours onderzoeken is dus automagisch tot nu toe de kortste route hiernaartoe
                        cellsList[newCellId].parentCellId = (*listToCheck.front()).cellId;
                        //Nu moeten de kosten voor de route hiernatoe uitgerekend worden (Dit zijn de kosten van naar de buurman gaan +1
                        cellsList[newCellId].cummulativeCost = (*listToCheck.front()).cummulativeCost+1;
                        //Als laatste zetten we de cell in de lijst met cellen die gecheckt moet worden
                        listToCheck.push_back(&cellsList[newCellId]);
                        //Bereken de afstand naar het doel
                        cellsList[newCellId].costToGoal = dist(cellsList[newCellId].positionX,cellsList[newCellId].positionY,cellsList[endCell].positionX,cellsList[endCell].positionY);
                        cellsList[newCellId].totalCostGuess = cellsList[newCellId].costToGoal + cellsList[newCellId].cummulativeCost;
                        cellsList[newCellId].visited = true;
                    }
                    else
                    {
                        //Deze cell is al eerder gevonden, staat dus al in de te checken cell lijst
                        if((*listToCheck.front()).cummulativeCost+1 < cellsList[newCellId].cummulativeCost)
                        {
                            //Er is een kortere route naar deze cell! Pas de parent cell dus aan en geef een nieuwe cummulative Cost;
                            cellsList[newCellId].parentCellId = (*listToCheck.front()).cellId;
                            cellsList[newCellId].cummulativeCost = (*listToCheck.front()).cummulativeCost+1;
                            cellsList[newCellId].totalCostGuess = cellsList[newCellId].costToGoal + cellsList[newCellId].cummulativeCost;
                        }
                    }
                }
            }
            //Haalt de cell waarvan we net alle buren beken hebben uit de lijst
            listToCheck.pop_front();
        }
    }

[ Voor 90% gewijzigd door switchboy op 17-04-2020 21:54 ]

[Vaan Banaan]

Even los van wat je exact wil: als je de Engelse taal goed kan volgen, zou ik de A* pathfinding YouTube serie van Sebastian Lague aanraden.
Het is een 10 delige serie over pathfinding in Unity (C#)
Unity is wel 3d, dus er wordt een hoop met 3d vectoren --> grid (2d) gesmeten.
Maar die gast kan heel goed uitleggen, waarom hij alle stappen doet.

Ter lering ende vermaeck
Deel 1: Algemene A* uitleg
Deel 2: Grid definitie (3d --> 2d)
Deel 3: A* algoritme in Unity (met list en hashset)
Deel 4: optimalisatie (gebruik van een heap om via een snelle sort de laagste cost vooraan de array te krijgen)
Deel 5: Units, waypoints, pathRequestManager
Deel 6: Weights (over weg lopen is makkelijker dan gras)
Deel 7: Weights smoothing
Deel 8: Path smoothing deel 1
Deel 9: Path smoothing deel 2
Deel 10: Threading
YouTube: A* Pathfinding Tutorial (Unity)

[MartenBE]

Als je pathfinding wil toepassen in een 2D grid zal Jump Point Search waarschijnlijk hogere snelheden halen dan andere A* varianten.

[Josk79]

Dit stukje uit je oorspronkelijke routine was mogelijk ook een grote performance-vreter:

code:

        while(!this->forwardIsDone)
        {
            //wait
        }

...maar niet meer aan de orde want je hebt het opgelost zie ik!

[switchboy]

Ik weet het is een kick van een oud topic, maar mijn inziens wel relevant:

Om nog even terug te komen op wat pathfinding ik wilde mijn routine wat leuker maken voor het spel door wanneer een doel niet bereikt kan worden de actor dan wel naar de tegel te laten lopen die geschat het dichts bij het doel is. Nu dacht ik dat ik hier handig het A* mechanisme voor kon misbruiken omdat dit toch al draaide. Als ik van alle tegels aan het eind wanneer de te onderzoeken lijst leeg is degene met de laagste geschatte kosten kan vinden kan ik vanaf hier het pad terug naar de actor maken door net als met een normale route van parent naar parent te springen. Dit zou zonder extra kosten het gewenste gedrag moeten geven.

Zo gezegd zo gedaan:

code:

void actors::calculateRoute()
{
    if(this->routeNeedsPath)
    {
        this->realPath = false;
        this->pathAStar();
        this->routeNeedsPath = false;
        if (!this->realPath) {
            this->timeLastPathTry = currentGame.elapsedTime;
        }
    }
}

void actors::pathAStar()
{
    std::vector<Cells> cellsList;
    cellsList.reserve(MAP_HEIGHT*MAP_WIDTH);
    int startCell = (actorCords[0]*MAP_HEIGHT)+actorCords[1]; //eigen positie
    int endCell = (actorGoal[0]*MAP_HEIGHT)+actorGoal[1]; //doel positie
    updateCells(endCell, startCell, cellsList);
    std::list<Cells*> listToCheck;
    std::list<Cells*> checkedList;
    bool endReached = false;

    //check of de doelcel niet 1 hokje weg is 
    if(((actorCords[0]-actorGoal[0] == 0) ||(actorCords[0]-actorGoal[0] == -1) ||(actorCords[0]-actorGoal[0] == 1)) && ((actorCords[1]-actorGoal[1] == 0) ||(actorCords[1]-actorGoal[1] == -1) ||(actorCords[1]-actorGoal[1] == 1)))
    {
        //en geen obstakel is of het hokje van de actor zelf is
        if(!cellsList[endCell].obstacle || (actorCords[0] == actorGoal[0] && actorCords[1] == actorGoal[1]))
        {
            this->pathFound = true;
            endReached = true;
        }
        else
        {
            this->pathFound = false;
        }
    }
    else
    {
        //De startcell initialiseren
        this->pathFound = false;
        cellsList[startCell].addNeighbours(cellsList);
        cellsList[startCell].totalCostGuess = dist(cellsList[startCell].positionX, cellsList[startCell].positionY, cellsList[endCell].positionX, cellsList[endCell].positionY);
        cellsList[startCell].visited = true;
        //De startcel in de lijst van te checken cellen zetten om te kunnen beginnen
        listToCheck.push_back(&cellsList[startCell]);
    }

    while(!listToCheck.empty() && startCell != endCell)
    {
        //sorteer de lijst en zet de cell met de laagste cost to goal bovenaan om het eerst te testen
        listToCheck.sort([](const Cells* f, const Cells* s)
        {
            return f->totalCostGuess < s->totalCostGuess;
        });

        //Check of de te checken cell het doel is. Als dat zo is zijn we klaar
        if((*listToCheck.front()).cellId == endCell)
        {
            listToCheck.clear();
            this->pathFound = true;
        }
        else if(!listToCheck.empty())
        {
            //Loop door de lijst van "buurcellen van de te checken cell"
            for (std::vector<int>::const_iterator iterator =  (*listToCheck.front()).neighbours.begin(), end =  (*listToCheck.front()).neighbours.end(); iterator != end; ++iterator)
            {
                //Kijk of deze cell eerder bezocht is
                if(!cellsList[*iterator].visited)
                {
                    //Deze cell heeft geen parent is is dus nooit eerder gevonden! De buren moeten dus toegevoegd worden!
                    cellsList[*iterator].addNeighbours(cellsList);
                    //De cell waarvan we de neighbours onderzoeken is uiteraard tot nu toe de kortste route hiernaartoe
                    cellsList[*iterator].parentCellId = (*listToCheck.front()).cellId;
                    //Nu moeten de kosten voor de route hiernatoe uitgerekend worden (Dit zijn de kosten van naar de parent gaan +1)
                    cellsList[*iterator].cummulativeCost = (*listToCheck.front()).cummulativeCost+1;
                    //Als laatste zetten we de cell in de lijst met cellen die gecheckt moet worden
                    listToCheck.push_back(&cellsList[*iterator]);
                    //En we schatten vanaf deze cell de kosten naar het doel
                    cellsList[*iterator].costToGoal = dist(cellsList[*iterator].positionX,cellsList[*iterator].positionY,cellsList[endCell].positionX,cellsList[endCell].positionY);
                    //Waardoor we dus de totale kosten kunnen schatten
                    cellsList[*iterator].totalCostGuess = cellsList[*iterator].costToGoal + cellsList[*iterator].cummulativeCost;
                    //We zijn voor nu klaar met deze tegel en laten een vlag achter dat de tegel al eens bekeken is
                    cellsList[*iterator].visited = true;
                }
                else
                {
                    //Deze tegel is al eerder gevonden, de buren staan dus al in de te checken cell lijst en hoeft niet opnieuw gechecked te worden
                    //We moeten wel weten of de route waarmee deze tegel nu is aangedaan niet korter is dan een eerder gevonden route
                    if((*listToCheck.front()).cummulativeCost+1 < cellsList[*iterator].cummulativeCost)
                    {
                        //Er is een kortere route naar deze cell! Pas de parent cell dus aan en geef een nieuwe cummulative Cost;
                        cellsList[*iterator].parentCellId = (*listToCheck.front()).cellId;
                        cellsList[*iterator].cummulativeCost = (*listToCheck.front()).cummulativeCost+1;
                        //Uiteraard verranderd dit dan ook de geschatte totale kosten vanaf deze tegel
                        cellsList[*iterator].totalCostGuess = cellsList[*iterator].costToGoal + cellsList[*iterator].cummulativeCost;
                    }
                }
            }
            //zet de tegel op de bezochte tegellijst
            checkedList.push_back(&cellsList[(*listToCheck.front()).cellId]);
            //en haal hem van de te bezoeken tegellijst
            listToCheck.pop_front();
        }
    }
    //Alle tegels die te bereiken zijn zijn bekeken of er is een route gevonden.
    //Maak een route door de parent cells achter elkaar te zetten tot de begin cell
    this->route.clear();
    if(this->pathFound)
    {
        //Er is een pad naar het doel gevonden! Stippel de route maar uit!
        routing(cellsList, endCell, startCell, endReached);
        this->realPath = true; //Vlaggetje dat de route naar het eindpunt gaat en er in princiepe geen herbereking nodig is
    }
    else {
        //We kunnen niet bij het doel komen, dan gaan we maar naar de geschatte dichtsbijzijnde cell waar we naartoe kunnen! (En die heeft de laagst geschatte totale kosten...)
        if (!checkedList.empty()) {
            checkedList.sort([](const Cells* f, const Cells* s)
                {
                    return f->totalCostGuess < s->totalCostGuess;
                });
            //Een bereikbare tegel met de laagst geschatte totale kosten staat nu vooraan in de rij van de bezochte tegels
            std::cout << "No path possible!" << std::endl << "Closest cell: " << (*checkedList.front()).cellId << std::endl << "Actors current cell: " << cellsList[startCell].cellId << std::endl << std::endl;
            //Stippel de route hiernaartoe uit
            routing(cellsList, (*checkedList.front()).cellId, startCell, endReached);
            this->pathFound = true; //Er is geen pad naar het doel maar wel een pad naar de dichtsbijzijnde plek, de actor moet dus wel gaan lopen
            this->realPath = false; //Vlaggetje op false laten staan zodat op een later tijdstip er opnieuw geprobeerd kan worden of er nu wél een pad naar het doel is
        }
    }
}

void actors::routing(std::vector<Cells>& cellsList, int& endCell, int& startCell, bool& endReached)
{
    //Zet de tegel waarnaartoe gelopen wordt in de lijst
    this->route.push_back({ cellsList[endCell].positionX, cellsList[endCell].positionY, cellsList[endCell].visited, cellsList[endCell].parentCellId });
    while (!endReached)
    {
        if (route.back().visited == true)
        {
            //Voeg voor iedere tegel de parent toe aan de lijst (dit was de tegel met de korste weg naar deze tegel)
            this->route.push_back({ cellsList[route.back().parentCellId].positionX, cellsList[route.back().parentCellId].positionY, cellsList[route.back().parentCellId].visited, cellsList[route.back().parentCellId].parentCellId });
            if (this->route.back().parentCellId == startCell) {
                    //Als de nu volgende parentCell de tegel is waar de actor op staat zijn we klaar.
                    endReached = true;
            }
            //Fix voor een bug waarin op een of andere manier géén parent cell ingevult staat en dus nul zou zijn. (al zou dat niet moeten kunnen)
            if (this->route.back().parentCellId == 0) {
                //We gaan kijken of het een logische buur kan zijn, gelukkig hoeven we maar drie posities te controleren:
                if (this->route.back().positionX == 0 && this->route.back().positionX == 1) {
                    //Logische parent; doe niets!
                }
                else if(this->route.back().positionX == 0 && this->route.back().positionX == 1) {
                    //Logische parent; doe niets!
                }
                else if (this->route.back().positionX == 1 && this->route.back().positionX == 1) {
                    //Logische parent; doe niets!
                }
                else {
                    //Onlogisch! breek de route af zonder de parent cell toe te voegen
                    endReached = true;
                }
            }
        }
        else
        {
            //Blijkbaar is deze tegel nooit geevalueerd of het is de starttegel; onlogisch! breek het route maken af!
            endReached = true;
        }
    }
}

De normale pathfinding werkt nog steeds prima. Maar voor niet bereikbare plaatsen werkt dit stukje code soms wel, soms helemaal niet en soms springt de actor eerst naar cell 0 om hierna terug te springen en soort van het gewenste gedrag te vertonen. Hoe kleiner het eiland van de actor hoe minder vaak het goed gaat. Dus ik denk dat de geschatte kosten dan misschien gek uitvallen?


Ik heb de code van veel commentaar voorzien zodat duidelijk is wat op iedere regel gebeurd.

Hier staat hij in verband op github: https://github.com/switch.../master/IsoRTS/actors.cpp

[eheijnen]

Kleinigheidje waarschijnlijk, dat me opviel in de code.

De twee constanten MAP_WIDTH en MAP_HEIGHT worden op diverse plaatsen in de code telkens weer met elkaar vermenigvuldigd. Kan zijn dat daar code bij is die veel gerepeteerd wordt en dit dan overvloedig gebeurd.

Een constante met de AREA zou hier beter van dienst kunnen zijn.

[switchboy]

eheijnen schreef op woensdag 23 juni 2021 @ 07:41:
Kleinigheidje waarschijnlijk, dat me opviel in de code.

De twee constanten MAP_WIDTH en MAP_HEIGHT worden op diverse plaatsen in de code telkens weer met elkaar vermenigvuldigd. Kan zijn dat daar code bij is die veel gerepeteerd wordt en dit dan overvloedig gebeurd.

Een constante met de AREA zou hier beter van dienst kunnen zijn.

Hij gebruikt de map hoogte en breedte hier om van een x-y systeem naar een cellId te gaan. Dus daar helpt helaas een map area weinig mee.

Ik heb het 'probleem' opgelost. Ik zat te suffen. Ik zette de cell met de laagst geschatte totale kosten bovenaan als en dat werd de nieuwe doelcel. Echter had ik de de cell met korste nog over zijnde afstand moeten gebruiken. Na dit aangepast te hebben werkt het naar behoren. Tevens check ik nu beter of de target cell niet de cell is waarop de actor al staat. Helaas had ik mijn functie alweer helemaal verbose gemaakt zodat hij zo'n beetje iedere stap in het debug window propt voor ik het door had.

Het kwartje viel pas toen ik ging gewichtheffen vanmorgen.

code:

            checkedList.sort([](const Cells* f, const Cells* s)
                {
                    return f->costToGoal < s->costToGoal;
                });

De fix.

[Matis]

Haha, mooi om te lezen.

Softwareproblemen lossen bij mij ook op tijdens hardlopen