.[ ČeskéHry.cz ].
A* Pathfinding
Jdi na stránku Předchozí  1, 2, 3  Další
 
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> AI
Zobrazit předchozí téma :: Zobrazit následující téma  
Autor Zpráva
OndraSej



Založen: 28. 07. 2007
Příspěvky: 767
Bydliště: Brandýs nad Labem

PříspěvekZaslal: 18. červenec 2012, 17:33:31    Předmět: Odpovědět s citátem

Lorin> Zaprve, hod sem zdrojak, pak bude jednodussi najit/ukazat, kde mas chybu.

Zadruhe, myslim, ze by ses mel podivat jeste na nejake tutorialy, protoze v tom mas chaos.

Konkretne - k tomu odhadu 78 pomoci heuristicke s min a max - ukol heuristicke funkce je odhadnout zbyvajici vzdalenost do cile. Pokud start ma souradnice [3, 4] a cil ma souradnice [10, 6] (tj. cisla z tveho prispevku), tak nejkratsi cesta je udelat dva sikme kroky a 5 vodorovnych (tj. cesta pak bude [3, 4] -> [4, 5] -> [5, 6] -> [6, 6] -> ... -> [10, 6]). S cenami, ktere jsi popsal na zacatku to znamena 5*10 + 2*14 = 78. Intuitivne, tahle heuristicka funkce pocita presne delku nejkratsi cesty ze startu do cile na ctvercove mape (s tvymi cenami) za predpokladu, ze mezi nimi nejsou zadne prekazky.

Az ted jsem se dival na hodnoty H v tom tvem obrazku a H tam ma hodnoty mezi 1 a 10. Coz by ti melo prijit divne, je to odhad vzdalenosti, ale skutecne vzdalenosti (tj. hodnoty funkce G) jsou radove v desitkach az stovkach. Tak kdyz uz Euklidovskou metriku, tak bys vyslednou hodnotu mel vynasobit 10 (coz je tvoje cena za vodorovny/svisly presun a tedy vzdalenost mezi dvema sousednimi policky). Ale jak jsem psal, ta heuristika s min/max dava o neco vyssi odhady, ktere ale porad jsou zarucene nizsi nez skutecna vzdalenosti, takze je presnejsi i nez takhle upravena Euklidovska metrika.

Euklidovska metrika, kterou jsi pouzival doted, neni uplne spatne (vzdy vraci odhad nizsi nez skutecna vzdalenost, takze nemuze algoritmus rozbit), ale jeji hodnoty jsou proti skutecnym vzdalenostem tak male, ze se v algoritmu temer neprojevi a ve vsyledku bude hledani trvat skoro stejne dlouho jako u Dijkstrova alg.
_________________
http://trionteam.net
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
mar



Založen: 16. 06. 2012
Příspěvky: 602

PříspěvekZaslal: 18. červenec 2012, 18:01:28    Předmět: Odpovědět s citátem

Lorin napsal:
mar napsal:

Ne. Pokud je G aktuálního uzlu + cost (aktuální, nový) < G nového, pak se změní G u nového (=relaxace) a updatne se nový uzel v prioritní frontě

Co přesně má dělat cost(aktuální, nový)?
Co je prioritní fronta?


cost: Tím myslím cenu (ve tvém případě délku, tj. 10 nebo 14) hrany mezi aktuálním a sousedním uzlem (tím myslím ten nový).
prioritní fronta: prostě množina, kde máš páry klíč, hodnota, s tím, že je to tříděné podle klíče a umí to vytáhnout prvek s nejmenší (nebo největší) hodnotou a případně i update, tj. změnit (v našem případě snížit) klíč u nějakého prvku.
U routingu chceme tahat prvky s nejmenší hodnotou. Tou hodnoutou u A* je f = g + h.
Takže je jedno, jak budeš prioritní frontu řešit.

Takže od píky (nebudu uvažovat otevřené/zavřené uzly, optimalizace až když to bude fungovat):

kód:

A_star ( start, cíl )

    prioritní_fronta p

    nastav g u všech uzlů na nekonečno (nebo rozumné maximum)
    nastav pr (=ukazatel/index přechozího uzlu) u všech uzlů na null
    nastav g u startu na 0

    ulož ( heuristika( start, cíl ), start ) do p

    dokud p není prázdná
        vytáhni z p uzel u s nejnižším klíčem
        pokud p je cíl ukonči smyčku
        pro všechny sousední uzly n
            c je cena hrany z u do n (tj. 10 nebo 14)
            pokud c + g uzlu u je menší, než g uzlu n
                nastav pr uzlu n na u
                nastav g uzlu n na c + g uzlu u
                přidej/uprav (g uzlu n + heuristika( n, cíl ), n) do p

    pokud g u cíle není nekonečno, vytáhni cestu pomocí pr od cíle zpátky, nakonec revertuj pořadí uzlů v cestě
    jinak cesta nenalezena


Ještě dodám, že jako heuristiku použij funkci, co psal OndraSej. Ve tvém případě to zaručí nalezení optimální cesty s minimem procházených uzlů.
Doufám, že tam někde nemám chybu Smile
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 18. červenec 2012, 18:15:45    Předmět: Odpovědět s citátem

OndraSej napsal:
Zaprve, hod sem zdrojak, pak bude jednodussi najit/ukazat, kde mas chybu.


Zdroják bohužel nemám. Nejdříve jsem se snažil najít nějaký algoritmus, který bude fungovat, tak jak si představuji abych ho poté mohl přepsat. Zatím dělám jen na papíře a v grafickém editoru. Na generování správné cesty používám http://www.generation5.org/content/2002/ase.asp.

OndraSej napsal:
Az ted jsem se dival na hodnoty H v tom tvem obrazku a H tam ma hodnoty mezi 1 a 10. Coz by ti melo prijit divne, je to odhad vzdalenosti, ale skutecne vzdalenosti (tj. hodnoty funkce G) jsou radove v desitkach az stovkach. Tak kdyz uz Euklidovskou metriku, tak bys vyslednou hodnotu mel vynasobit 10 (coz je tvoje cena za vodorovny/svisly presun a tedy vzdalenost mezi dvema sousednimi policky). Ale jak jsem psal, ta heuristika s min/max dava o neco vyssi odhady, ktere ale porad jsou zarucene nizsi nez skutecna vzdalenosti, takze je presnejsi i nez takhle upravena Euklidovska metrika.

Problém je v tom, že jsem nepočítal s těmi vzdálenostmi (10, 14). Nejdříve jsem měl klasický algoritmus, který všude používal hodnotu 1 (nerozlišoval mezi pohybem horizontálním/vertikálním a šikmým. Pak jsem se dočetl, že vzdálenost šikmo je 1.4x větší než ta horizontální/vertikální).
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 602

PříspěvekZaslal: 18. červenec 2012, 18:21:23    Předmět: Odpovědět s citátem

Lorin napsal:
Pak jsem se dočetl, že vzdálenost šikmo je 1.4x větší než ta horizontální/vertikální).

1.4 je dostačující odhad. Ve skutečnosti to je druhá odmocnina ze dvou Wink
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 18. červenec 2012, 18:27:28    Předmět: Odpovědět s citátem

mar napsal:
1.4 je dostačující odhad. Ve skutečnosti to je druhá odmocnina ze dvou Wink

Máte pravdu Very Happy.

Přesně je to 1.414213562. Abych nemusel počítat s desetinnými čísly, zaokrouhlil jsem poměr na 1.0:1.4 a vynásobil 10. A ještě bych to mohl vydělit dvěma. Alespoň by nevycházela tak velká čísla.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
satik



Založen: 06. 05. 2010
Příspěvky: 161
Bydliště: Krkonose

PříspěvekZaslal: 18. červenec 2012, 19:10:35    Předmět: Odpovědět s citátem

delal jsem na toto tema jeden projekt ve skole, tady je to pro inspiraci i se zdrojakem (c#)

http://satik.eu/temp/path.zip
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
rezna



Založen: 27. 07. 2007
Příspěvky: 2156

PříspěvekZaslal: 18. červenec 2012, 20:08:12    Předmět: Odpovědět s citátem

@Lorin - ja jsem dal odkaz jiz vyse - a to na Dijkstru - az napises spravne Dijkstru muzes zkusit optimalizovat na A* - to uz je jenom banalni uprava algoritmu
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 18. červenec 2012, 20:15:29    Předmět: Odpovědět s citátem

rezna napsal:
@Lorin - ja jsem dal odkaz jiz vyse - a to na Dijkstru - az napises spravne Dijkstru muzes zkusit optimalizovat na A* - to uz je jenom banalni uprava algoritmu


Neliší se Dijkstrův algoritmus od toho A* tím, že přidám hodnotu H? V Dijkstrově algoritmu je H = 0. V A* se určuje jako vzdálenost k cíli. Takže pokud doladím (použiji výpočet od OndraSej) postup na výpočet H, mám vystaráno ne?
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
rezna



Založen: 27. 07. 2007
Příspěvky: 2156

PříspěvekZaslal: 18. červenec 2012, 20:26:56    Předmět: Odpovědět s citátem

@Lorin - to je sumak cim se lisi - naimplementuj si Dijkstru - ty zjevne blbe pocitas uz Dijkstruv pristup a nevidis v nem ten problem - proto si prvne udelej zakladni algoritmus a potom teprve res jak to vylepsit - beztak pokud nemas data 100.000 x 100.000 ctvercu tak bude Dijkstra nejakou dobu stacit
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
sonic



Založen: 19. 01. 2009
Příspěvky: 194

PříspěvekZaslal: 18. červenec 2012, 20:54:52    Předmět: Odpovědět s citátem

Pokusím se to srozumitelně a zjednodušeně vysvětlit.

Na začátku budeš mít startovní a cílový bod.
Dál budeš mít 2 seznamy - jeden Otevřený a druhý Uzavřený
V Otevřeném seznamy jsou všechny políčka, které ještě nezkontroloval. V Uzavřeném jsou už zkontrolované políčka. Seznamy budou seřazené podle F (první políčko v seznamu má nejnižší F, poslední bude mít nejvyšší).
Je důležité, aby sis u každého políčka pamatoval jeho Rodiče (tzn. políčko, z kterého ses tam dostal).

Začneš tím, že vložíš startovní bod do Otevřeného seznamu. (G startovního bodu bude 0, H bude vzdálenost k cíli a F bude akorát tady rovno H). Toto políčko nemá rodiče!

Teď použiješ cyklus a po každé uděláš:
1) Vybereš políčko z Otevřeného seznamu s nejnižším F (seznam je stále seřazen podle F, takže je to první políčko v seznamu). Toto políčko budem považovat za VÝCHOZÍ
2) Přesuň toto políčko do Uzavřeného seznamu
3) Pro všechny (všech 8) SOUSEDNÍ políčka od našeho VÝCHOZÍHO políčka udělej následující věc:
a) Pokud je toto políčko překážka nebo již je v Uzavřeném seznamu, tak ho prostě ignoruj
b) Pokud toto políčko není ještě v Otevřeném seznamu, přidej ho tam (ale seznam musí být pořád seřazen podle F) a nastav pro toto políčko jako rodiče to políčko, z kterého jsme sem přišli (označil jsem ho VÝCHOZÍ) a spočítej F, G a H hodnoty a přiřaď je tomuto políčku.
c) Pokud je políčko již v Otevřeném seznamu, zkontroluj jaké G máš u něho uložené. Pokud jeho uložené G je větší než "G VÝCHOZÍHO políčka + jeho vzdálenost k tomuto sousednímu políčku", znamená to, že jdeme tou kratší cestou. Takže změníme rodiče tohoto políčka (které je v Otevřeném seznamu) na naše VÝCHOZÍ políčko a přepočítáme všechny hodnoty (F, G a H).

S hledáním končíme tehdy, pokud dostaneme Cílové políčko do Uzavřeného seznamu nebo pokud máme Otevřený seznam prázdný (tzn. cesta neexistuje).

Cestu pak zjistíš tak, že po skončení vezmeš cílové políčko, zjistíš jeho předka (rodiče) a tak dále dokud nenarazíš na políčko sirotka (ten předka nemá). Postupuješ tedy od cíle k začátku (a můžeš si to v obráceném pořadí ukládat do nějaké seznamu s cestou).

Nevím jestli jsem to spíš nezesložitil a doufám, že je to vůbec správně :D
Koukám, že postupů je asi víc. Je teda důležitý si to nejdřív projít v hlavě a pochopit to, než to naprogramuješ.

Je důležitý, aby jsi správě spočítal G (to je G předka + vzdálenost k tomuto předkovi), H (vzdálenost k cíli) a F (součet těhlech dvou) každého políčka.
_________________
Programovat pod Windows je jako hrát hry na Macu.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 602

PříspěvekZaslal: 18. červenec 2012, 21:22:00    Předmět: Odpovědět s citátem

Když o tom ještě tak přemýšlím, je vůbec pro začátečníka potřeba řešit closed list?
Open list je stejně jenom prioritní fronta a closed list je jednoduchá optimalizace: pokud bych neřešil closed, tak stejně nenajdu kratší cestu a neprovedu relaxaci.
Nebo mi něco uniká?

@sonic: Myslím že to je správně. Ještě mě napadá, že H se dá spočítat jenom jednou při prvním otevření uzlu, ale to už je fakt jenom nepodstatný detail.

Poslední myšlenka: v C++ se dá využít std::priority_queue. Neumí sice update (a defaultně tahá nejvyšší prvek - stačí použít -f nebo naimplementovat komparátor), ale to se dá obejít použitím push (akorát pak můžu mít stejný uzel ve frontě víckrát) a následně ignorováním uzlu, který je closed poté, co ho vytáhnu z fronty. Navíc použitím něčeho, co už funguje, se vyhnu dalším chybám např. při implementaci vlastního heapu.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
if.then



Založen: 13. 04. 2008
Příspěvky: 579

PříspěvekZaslal: 18. červenec 2012, 21:40:01    Předmět: Odpovědět s citátem

Bez closed listu nevíš, co jsi už zavřel - tzn. se ti dost často budou stávat nekonečné smyčky.
_________________
For guns and glory, go to www.ceske-hry.cz.
For work and worry, execute VC++.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 602

PříspěvekZaslal: 18. červenec 2012, 22:13:03    Předmět: Odpovědět s citátem

if.then napsal:
Bez closed listu nevíš, co jsi už zavřel - tzn. se ti dost často budou stávat nekonečné smyčky.

No právě, že nebudou (viz co jsem už napsal). Sice takhle projdeš i nezavřené sousedy, jenže se neprovede relaxace (před chvílí jsem pro jistotu vyzkoušel a bez problémů).
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 24. červenec 2012, 08:34:11    Předmět: Odpovědět s citátem

Tak jsem se konečně dostal k tomu, abych to zkusil převést do kódu. Místy funguje dobře a vybírá správnou (relativně) cestu k cíli. Ale v určité chvíli začne vybírat pole blíže startu, protože i když mají velkou vzdálenost k cíli, jejich G je tak malé, že stejně zastíní pole, které jsou blíže cíli.

Co se týče kódu, je špatně dokumentovaný (spíše vůbec), není moc přehledný atd. Je v stádiu vývoje, ladění přijde na řadu po vytvoření funkčnosti.


main.cpp
kód:
#include <iostream>
#include <map>
#include "Node.hpp"
#include "PathFinder.hpp"

int main(int argc, char** argv) {
    PathFinder pf;
    std::vector<Node*> path = pf.find(0, 0, 5, 10);
   
    /*for(std::vector<Node*>::iterator it = path.begin(); it < path.end(); it++) {
        std::cout << "[" << (*it)->getY() << "," << (*it)->getX() << "]" << std::endl;
    }*/
    return 0;
}


Node.hpp
kód:

#ifndef NODE_HPP
#define   NODE_HPP

#include <iostream>
#include <cstdint>

    class Node {
        public:
            Node(int16_t y, int16_t x);
            ~Node();
           
            // Settery
            inline void setX(int16_t x) {
                this->xPosition = x;
            }
            inline void setY(int16_t y) {
                this->yPosition = y;
            }
           
            inline void setG(int32_t g) {
                this->g = g;
            }
            inline void setH(int32_t h) {
                this->h = h;
            }
            inline void setF(int32_t f) {
                this->f = f;
            }
           
            void computeF(int16_t currentY, int16_t currentX, int16_t targetY, int16_t targetX);
           
            inline void setClosed(bool closed) {
                this->isClosed = closed;
            }
            inline void setOpened(bool opened) {
                this->isOpened = opened;
            }
            inline void setWalkable(int8_t walkable) {
                this->walkable = walkable;
            }
           
            inline void setParent(int16_t y, int16_t x) {
                this->xParentPos = x;
                this->yParentPos = y;
            }
           
            // Gettery
            inline int16_t getX() {
                return this->xPosition;
            }
            inline int16_t getY() {
                return this->yPosition;
            }
           
            inline int32_t getG() {
                return this->g;
            }
            inline int32_t getH() {
                return this->h;
            }
            inline int32_t getF() {
                return this->f;
            }
           
            inline bool getClosed() {
                return this->isClosed;
            }
            inline bool getOpened() {
                return this->isOpened;
            }
            inline int8_t getWalkable() {
                return this->walkable;
            }
           
            inline int16_t getParentX() {
                return this->xParentPos;
            }
            inline int16_t getParentY() {
                return this->yParentPos;
            }
        private:
            // Souřadnice
            int16_t xPosition;
            int16_t yPosition;
           
            // Ohodnocení nodu
            int32_t g; // Vzdálenost ke startu
            int32_t h; // Vzdálenost k cíli
            int32_t f; // Součet g + h
           
            // Vlastnosti nodu
            bool isClosed; // Určuje, zda je na uzavřeném seznamu
            bool isOpened; // Určuje, zda je na otevřeném seznamu
            int8_t walkable; // 0 = Nejlépe průchodné - 255 = Neprůchodné
           
            // Souřadnice předka
            int16_t xParentPos;
            int16_t yParentPos;
    };

#endif   /* NODE_HPP */


PathFinder.hpp
kód:

#ifndef PATHFINDER_HPP
#define   PATHFINDER_HPP

#include <iostream>
#include <cstdint>
#include <map>
#include <vector>
#include "Node.hpp"
    class PathFinder {
        public:
            PathFinder();
            ~PathFinder();
           
            void addToOpenedList(int16_t y, int16_t x);
            void addToClosedList(int16_t y, int16_t x);
           
            inline void print() {
                for(int16_t y = 0; y <= 10; y++) {
                    for(int16_t x = 0; x <= 10; x++) {
                        std::cout << "[" << y << "," << x << "]: " << map[y][x] << std::endl;
                    }
                }
            }
           
            std::vector<Node*> find(int16_t startY, int16_t startX, int16_t targetY, int16_t targetX);
            void close();

        private:
            std::multimap<int32_t, Node*> openedList;
           
            Node *map[11][11];
           
            int16_t targetX;
            int16_t targetY;
           
            void loadMap();
            bool isTargetReached();
                       
            void getSurroundNodes(int16_t currentY, int16_t currentX);
            int8_t getSurroundNodePosition(int16_t currentY, int16_t currentX, int16_t surroundY, int16_t surroundX);
           
            inline bool isOnOpenedList(int16_t y, int16_t x) {
                return this->map[y][x]->getOpened();
            }
            inline bool isOnClosedList(int16_t y, int16_t x) {
                return this->map[y][x]->getClosed();
            }
           
    };

#endif   /* PATHFINDER_HPP */


Node.cpp
kód:

#include <cstdint>
#include "Node.hpp"

Node::Node(int16_t y, int16_t x) {
    this->yPosition = y;
    this->xPosition = x;
   
    this->walkable = 0;
    this->isClosed = false;
    this->isOpened = false;
}

Node::~Node() {
   
}

void Node::computeF(int16_t currentY, int16_t currentX, int16_t targetY, int16_t targetX) {
    int16_t dx = abs(currentX - targetX);
    int16_t dy = abs(currentY - targetY);
   
    this->h = ( 7*(std::min( dx , dy )) + 5*( std::max(dx, dy) - std::min(dx, dy) ));
    std::cout << "Vypocitavam F pro [" << currentY << "," << currentX << "]" << " = " << this->g << " + (" << dx << "," << dy << ")" << this->h << std::endl;
    this->f = this->g + this->h;
}


PathFinder.cpp
kód:

#include <cstdint>
#include <map>
#include <vector>
#include <algorithm>
#include "Node.hpp"
#include "PathFinder.hpp"

PathFinder::PathFinder() {
    loadMap();
}

PathFinder::~PathFinder() {
    close();
}

void PathFinder::addToOpenedList(int16_t y, int16_t x) {
    std::cout << "Pridavam na Otevreny seznam: [" << y << "," << x << "]" << std::endl;
   
    map[y][x]->setOpened(true);
    map[y][x]->computeF(y, x, this->targetY, this->targetX);
    this->openedList.insert( std::pair<int32_t, Node* >(map[y][x]->getF(), map[y][x]) );
}

void PathFinder::addToClosedList(int16_t y, int16_t x) {
    std::cout << "Pridavam na Uzavreny seznam: [" << y << "," << x << "]" << std::endl;
   
    map[y][x]->setClosed(true);
   
}
           
std::vector<Node*> PathFinder::find(int16_t startY, int16_t startX, int16_t targetY, int16_t targetX) {
    // Vektor obsahující ukazatele na nody, ze kterých se skládá cesta
    std::vector<Node*> path;
    // Iterator, používá se pro přístup k otevřenému seznamu
    std::multimap<int32_t, Node*>::iterator it;
   
    // Nastaví souřadnice cíle
    this->targetY = targetY-1;
    this->targetX = targetX-1;
   
    // Nastaví hodnotu G startu na 0
    map[startY][startX]->setG(0);   
    // Startovní pole přidá na otevřený seznam
    addToOpenedList(startY, startX);
   
    std::cout << map[startY][startX]->getF() << std::endl;
   
    /**************************************************************************
    // Výpočet hodnoty F pro start
    int16_t dx = abs(startX - targetX);
    int16_t dy = abs(startY - targetY);
    map[startY][startX]->setF(( 7*(std::min( dx , dy )) + 5*( std::max(dx, dy) - std::min(dx, dy) )));
    **************************************************************************/
   
    // Nastaví proměnné. Používají se v smyčce.
    int16_t currentY = startY;
    int16_t currentX = startX;
   
    // Probíhá dokud není dosažen cíl - Dokud není cíl na uzavřeném seznamu
    while (isTargetReached() == false ) {
        // Pokud je otevřený seznam prázdný, cesta neexistuje
        if (openedList.empty() == true) {
            path.erase(path.begin(), path.end());
            break;
        }
       
        // Nastaví iterator na první položku v otevřeném seznamu - Položku s nejnižším F
        it = openedList.begin();
       
        std::cout << "Pocet sousedu: " << openedList.size() << std::endl;
        for(std::multimap<int32_t, Node*>::iterator i = openedList.begin(); i != openedList.end(); i++ ) {
            std::cout << (*i).first << " [" << (*i).second->getY() << "," << (*i).second->getX() << "] = F = G(" << (*i).second->getG() << ") + H(" << (*i).second->getH() << ") = " << (*i).second->getF() << std::endl;
        }
       
        std::cout << "Prechazim na [" << (*it).second->getY() << "," << (*it).second->getX() << "]" << std::endl;

        // Nastaví rodiče vybraného nodu na předchozí node
        ((*it).second)->setParent(currentY, currentX);
        // Vybraný node přidá na uzavřený seznam
        addToClosedList( (*it).second->getY(), (*it).second->getX() );
       
        // Nastaví souřadnice aktuálního nodu na vybraný nod s nejnižší F
        currentY = (*it).second->getY();
        currentX = (*it).second->getX();
       
        // Vybraný node smaže z otevřeném seznamu
        openedList.erase(it);

        if (isTargetReached() == false ) {
            getSurroundNodes(currentY, currentX);
        } else {
            break;
        }
       
    }
    return path;
}

void PathFinder::close() {
    std::cout << "Mazu" << std::endl;
    for(int16_t y = 0; y <= 10; y++) {
        for (int16_t x = 0; x <= 10; x++) {
            delete this->map[y][x];
        }
    }
}

void PathFinder::loadMap() {
    std::cout << "Nacitam..." << std::endl;
    for(int16_t y = 0; y <= 10; y++) {
        for (int16_t x = 0; x <= 10; x++) {
            this->map[y][x] = new Node(x, y);
            this->map[y][x]->setParent(-1, -1);
        }
    }
    std::cout << "Hotovo" << std::endl;
}

bool PathFinder::isTargetReached() {
    if (map[targetY][targetX]->getClosed() == true) {
        std::cout << "Cil nalezen" << std::endl;
        return true;
    } else {
        std::cout << this->map[targetY][targetX]->getClosed() << std::endl;
        return false;
    }
}
                       
void PathFinder::getSurroundNodes(int16_t currentY, int16_t currentX) {
    std::cout << "Hledam sousedy: [" << currentY << "," << currentX << "]" << std::endl;
   
    for(int16_t y = currentY-1; y <= currentY+1; y++) {
        // Pokud je souřadnice Y mimo mapu
        if (y > 10 || y < 0) {
            std::cout << "[" << y << "] - Presah hodnoty Y" << std::endl;
            continue;
        }
       
        for(int16_t x = currentX-1; x <= currentX+1; x++) {
            // Pokud je souřadnice X mimo mapu
            if (x > 10 || x < 0) {
                std::cout << "[" << y << "," << x << "] - Presah hodnoty X" << std::endl;
                continue;
            }
           
            // Pokud je pole na uzavřeném seznamu, nebo není průchodné, ignoruje se
            if(map[y][x]->getClosed() == true || map[y][x]->getWalkable() == 255) {
                std::cout << "[" << y << "," << x << "] - Nepruchodne nebo na closed" << std::endl;
                continue;
            }
           
            // V průběhu smyčky přeskočí aktuální pole
            if (y == currentY && x == currentX) {
                std::cout << "[" << y << "," << x << "] - Aktualni pole" << std::endl;
                continue;
            }
           
            // Pokud pole není na otevřeném seznamu
            if(map[y][x]->getOpened() == false) {
                std::cout << "[" << y << "," << x << "] - Pridavam na otevreny seznam" << std::endl;
                map[y][x]->setG( map[currentY][currentX]->getG() + getSurroundNodePosition(currentY, currentX, y, x) );
                map[y][x]->setParent(currentY, currentX);
                // Přidá ho na otevřený seznam
                addToOpenedList(y, x);
           
            // v opačném případě zkontroluje, zda jdeme tou správnou cestou
            } else {
                // Pokud je G pole menší než G aktuálního pole + vzdálenost cesty k poli
                if (map[y][x]->getG() > getSurroundNodePosition(currentY, currentX, y, x) + map[currentY][currentX]->getG() ) {
                    std::cout << "UPDATE!" << std::endl;
                    std::pair<std::multimap<int32_t, Node*>::iterator, std::multimap<int32_t, Node*>::iterator > elements = openedList.equal_range(map[y][x]->getF());
                   
                    for (std::multimap<int32_t, Node*>::iterator it = elements.first; it != elements.second; it++) {
                        if ((*it).second->getY() == currentY && (*it).second->getX() == currentX) {
                            map[y][x]->setParent(currentY, currentX);
                            map[y][x]->setG( map[currentY][currentX]->getG() + getSurroundNodePosition(currentY, currentX, y, x) );
                            //map[y][x]->computeF(currentY, currentX, this->targetY, this->targetX);
                            openedList.erase(it);
                            addToOpenedList(y, x);
                        }
                    }
                   
                }
            }
        }
    }
}


int8_t PathFinder::getSurroundNodePosition(int16_t currentY, int16_t currentX, int16_t surroundY, int16_t surroundX) {
    // Pokud se liší horizontální i vertikální pozice polí
    if (currentX != surroundX && currentY != surroundY) {
        // Šikmo
        return 7;
    } else {
        // Vodorovně/vertikálně
        return 5;
    }
}


Děkuji za jakékoli nápady.


Naposledy upravil Lorin dne 24. červenec 2012, 11:06:42, celkově upraveno 2 krát
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
OndraSej



Založen: 28. 07. 2007
Příspěvky: 767
Bydliště: Brandýs nad Labem

PříspěvekZaslal: 24. červenec 2012, 09:34:24    Předmět: Odpovědět s citátem

Lorin> Porad mam pocit, ze spatne rozumis tomu, co a jak by ten algoritmus mel delat (shameless self-promo: doporucuju druhy dil knihy Game industry, ktery ted nekdy vychazi/vyjde, je to tam podrobne popsane), radeji se na to jeste jednou podivej (ale napred docti tady, snad to bude stacit).

Vec, kterou mas spatne (PathFinder::find(?)), je, ze do vysledne cesty pridavas vrcholy potom, co je presunes z OPEN do CLOSED. To ale je spatne, protoze timhle zpracovanim projde vic vrcholu, nez jen ty na vysledne ceste. Kolik jich tam projde, zavisi na tom, jak dobrou mas heuristickou funkci.
Pokud je dokonala (tj. vrati vzdy presne delku nejkratsi cesty k cili), pak by tenhle postup opravdu fungoval, ale pak bys nepotreboval nic z A* a stacilo by ti jit podle toho, co ti rekne heuristicka funkce. Pokud naopak mas spatnou heuristiku (nebo nemas zadnou), muzes takhle zpracovat vsechny policka mapy, nez konecne najdes cil. Takze to, ze po case algoritmus zacne prochazet opet policka kolem startu, je normalni a spravne chovani.
Spravny postup v tomhle kroce je (1) napred prochazet seznam OPEN, dokud nenajdes cil (nebo dokud ho nevyprazdnis) a potom pouzit ty ukazatele na rodice (v tvojem kodu parentX a parentY) k tomu, abys tu cestu zrekonstruoval. To musis udelat smerem od cila - tj. v cili se podivas na rodice a zaradis ho na konec cesty, v rodici cile se podivas na rodice a zaradis ho na predposledni misto v ceste, a tak dal, dokud nedojdes do startu. Implementacne je jednodussi si vrcholy ulozit do vectoru v opacnem poradi (tj. cil jako prvni, jeho rodic druhy, ?) a pak ho obratit.

Mozna tam je jeste neco, ale ted nemam cas to doprojit dukladne - jeste se na to behem dne podivam.
_________________
http://trionteam.net
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Zobrazit příspěvky z předchozích:   
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> AI Časy uváděny v GMT + 1 hodina
Jdi na stránku Předchozí  1, 2, 3  Další
Strana 2 z 3

 
Přejdi na:  
Nemůžete odesílat nové téma do tohoto fóra
Nemůžete odpovídat na témata v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete hlasovat v tomto fóru


Powered by phpBB © 2001, 2005 phpBB Group


Vzhled udelal powermac
Styl "vykraden" z phpBB stylu MonkiDream - upraveno by rezna