Zobrazit předchozí téma :: Zobrazit následující téma |
Autor |
Zpráva |
if.then
Založen: 13. 04. 2008 Příspěvky: 579
|
Zaslal: 24. červenec 2012, 14:23:18 Předmět: |
|
|
No kód je zdokumentovaný málo a hlavně špatně (v metodě find je třeba velikost openedListu na výstupu popsána jako "počet sousedů", což mi prostě hlava nebere).
Heuristiku máš velmi zajímavou, pro začátek bys měl použít asi Euklideovskou vzdálenost, protože ta by v otevřeném terénu měla nacházet ideální cesty /tipuji, kdyžtak mě opravte/ (hm, co se teď koukám na svůj kód, tak používám jenom Manhattanskou vzdálenost a taky to funguje dobře... takže jednu z těchto dvou).
Co jsem opravdu nepochopil (a v čem asi bude chyba) je tenhle kus kódu v metodě find:
kód: |
// Nastaví rodiče vybraného nodu na předchozí node
((*it).second)->setParent(currentY, currentX); |
Was? Rodiče nastavuješ už při zrození nebo updatu nodu, proč tam máš tohle? To může vést k dost solidním chybám. Odstranit.
Jinak mi to přijde celkem správně, ale samozřejmě jsem nezkoumal vše, takže asi tak. _________________ For guns and glory, go to www.ceske-hry.cz.
For work and worry, execute VC++. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
OndraSej
![](images/avatars/199514602546ab340a5d041.jpg)
Založen: 28. 07. 2007 Příspěvky: 767 Bydliště: Brandýs nad Labem
|
Zaslal: 24. červenec 2012, 16:48:57 Předmět: |
|
|
if.then> Opravuji te. Pokud mas ctvercove dlazdice s pohybem sikmo, pak Manhattanska metrika je spatne (neni pripustna) a Euklidovska dava prilis nizke odkazy, ta pouzita je optimalni (to jsme tu resili nekde na prvni/zacatku druhe stranky).
Ten setParent spatne je, to by se melo dit pri aktualizaci G. Ale tohle je cele o tom, ze cestu nejde stavit uvnitr toho cyklu, kde se presouvaji uzly z OPEN do CLOSED. _________________ http://trionteam.net |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
if.then
Založen: 13. 04. 2008 Příspěvky: 579
|
Zaslal: 24. červenec 2012, 17:16:02 Předmět: |
|
|
OK, díky za opravu. _________________ For guns and glory, go to www.ceske-hry.cz.
For work and worry, execute VC++. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
Lorin
Založen: 18. 07. 2012 Příspěvky: 16
|
Zaslal: 24. červenec 2012, 20:23:11 Předmět: |
|
|
if.then napsal: |
No kód je zdokumentovaný málo a hlavně špatně (v metodě find je třeba velikost openedListu na výstupu popsána jako "počet sousedů", což mi prostě hlava nebere). |
Pozůstatek z doby, kdy tam opravdu byl výpis sousedů...
if.then napsal: |
kód: |
// Nastaví rodiče vybraného nodu na předchozí node
((*it).second)->setParent(currentY, currentX);
|
|
Odstraněno.
Kód ještě trochu pozměním, opravím dokumentaci a přidám pár dalších funkcí. Cestu to až na jednu nevysvětlitelnou okliku hledá dobře. Uvidím, jestli to bude blbnout i po přepsání. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
mar
Založen: 16. 06. 2012 Příspěvky: 607
|
Zaslal: 24. červenec 2012, 22:05:28 Předmět: |
|
|
Ještě poslední poznámka k té heuristice: problém u čtvercových dlaždic je, že existuje (může a v 99% případů to tak bude) víc cest se stejnou kvalitou, takže ani při té správné heuristice to neprojde nejmenší možný počet.
Je potřeba vyrešit shody drobnou modifikací heuristiky, viz
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#a-stars-use-of-the-heuristic
kód: |
dx1 = fx - tx
dy1 = fy - ty
dx2 = sx - tx
dy2 = sy - ty
cross = abs( dx1*dy2 - dx2*dy1 )
kde fx, fy jsou souřadnice uzlu, pro který heuristiku počítám
sx, sy jsou souřadnice startu
a tx, ty jsou souřadnice cíle
|
a na závěr přičíst řekněme tisícinu crossu (záleží na použitých jednotkách a maximální možné délce cesty) (=2d vektorový součin) k heuristice. Tím se ještě podstatně sníží počet procházených uzlů, obzvlášť na cestě bez překážek. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
rezna
Založen: 27. 07. 2007 Příspěvky: 2156
|
Zaslal: 25. červenec 2012, 07:39:59 Předmět: |
|
|
heuristik a jejich uprav existuji kvanta - a to vse uz zalezi od aplikace dane heuristiky - resp. taky ve spravnem oceneni pohybu - a to treba jestli neni v danem okamziku zpomalujici zatacet - pak je treba manhattanskou heuristiku doplnit o preferenci rovneho pohybu a zatacet jen v nutnych pripadech ... |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
mar
Založen: 16. 06. 2012 Příspěvky: 607
|
Zaslal: 25. červenec 2012, 08:31:06 Předmět: |
|
|
@rezna: bavil jsem se o vyřešení shod v konkrétním případě.
penalizaci otáčení bych asi radši přidal do costu hrany. Je jedno, kam to dát, ale přijde mi to logičtější takhle. Penalizace uzlu můžu dát do heuristiky, protože ve výsledku se to stejně sečte. Prostě pro mě je heuristika něco, co mě táhne k cíli, nic víc.
Obecně prostě zvolit heuristiku takovou, která mi bude v mém případě nejvíc vyhovovat. Takže si napsat referenční implementaci a vizualizovat si, co mi to všechno prolezlo a podle toho se dál zařídit je IMHO nejlepší cesta. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
rezna
Založen: 27. 07. 2007 Příspěvky: 2156
|
Zaslal: 25. červenec 2012, 09:36:11 Předmět: |
|
|
mar proto tady uz nejakou dobu bojuju za to at si prvne naimplementi dijkstru bez heuristik a pak zacne resit dal .... |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
mar
Založen: 16. 06. 2012 Příspěvky: 607
|
Zaslal: 25. červenec 2012, 09:59:49 Předmět: |
|
|
No tady je asi koukám zvykem se na něco zeptat a pak si to buď udělat stejně podle sebe nebo to nevnímat a zeptat se znova na totéž.
V obou případech pak postrádám logiku toho, proč se tedy vůbec ptát...
Jinak naprosto souhlasím. Pokud jsem sváteční plavec tak asi rovnou nepůjdu přeplavat La Manche. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
|