| 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
|
 Zaslal: 18. červenec 2012, 17:33:31 Předmět: |
 |
|
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 |
|
 |
mar
Založen: 16. 06. 2012
Příspěvky: 607
|
| Zaslal: 18. červenec 2012, 18:01:28 Předmět: |
|
|
| 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  |
|
| Návrat nahoru |
|
|
Lorin
Založen: 18. 07. 2012
Příspěvky: 16
|
| Zaslal: 18. červenec 2012, 18:15:45 Předmět: |
|
|
| 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 |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 607
|
| Zaslal: 18. červenec 2012, 18:21:23 Předmět: |
|
|
| 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  |
|
| Návrat nahoru |
|
|
Lorin
Založen: 18. 07. 2012
Příspěvky: 16
|
| Zaslal: 18. červenec 2012, 18:27:28 Předmět: |
|
|
| mar napsal: |
| 1.4 je dostačující odhad. Ve skutečnosti to je druhá odmocnina ze dvou |
Máte pravdu  .
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 |
|
|
satik
Založen: 06. 05. 2010
Příspěvky: 161
Bydliště: Krkonose
|
| Zaslal: 18. červenec 2012, 19:10:35 Předmět: |
|
|
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 |
|
|
rezna
Založen: 27. 07. 2007
Příspěvky: 2156
|
| Zaslal: 18. červenec 2012, 20:08:12 Předmět: |
|
|
| @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 |
|
|
Lorin
Založen: 18. 07. 2012
Příspěvky: 16
|
| Zaslal: 18. červenec 2012, 20:15:29 Předmět: |
|
|
| 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 |
|
|
rezna
Založen: 27. 07. 2007
Příspěvky: 2156
|
| Zaslal: 18. červenec 2012, 20:26:56 Předmět: |
|
|
| @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 |
|
|
sonic
Založen: 19. 01. 2009
Příspěvky: 194
|
| Zaslal: 18. červenec 2012, 20:54:52 Předmět: |
|
|
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 |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 607
|
| Zaslal: 18. červenec 2012, 21:22:00 Předmět: |
|
|
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 |
|
|
if.then
Založen: 13. 04. 2008
Příspěvky: 579
|
| Zaslal: 18. červenec 2012, 21:40:01 Předmět: |
|
|
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 |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 607
|
| Zaslal: 18. červenec 2012, 22:13:03 Předmět: |
|
|
| 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 |
|
|
Lorin
Založen: 18. 07. 2012
Příspěvky: 16
|
| Zaslal: 24. červenec 2012, 08:34:11 Předmět: |
|
|
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 |
|
|
OndraSej
Založen: 28. 07. 2007
Příspěvky: 767
Bydliště: Brandýs nad Labem
|
| Zaslal: 24. červenec 2012, 09:34:24 Předmět: |
|
|
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 |
|
|
|
Hlavní strana
FAQ
Test
Hledat
Seznam uživatelů
Uživatelské skupiny
Registrace
Ke Stažení
Nastavení
Přihlášení
Calendar
