none
Přesun objektu z bodu A do bodu B

    Dotaz

  • Zdravím,

    právě se potýkám s nejednoduchým (alespoň pro mě) problémem. Snažím se, aby se můj testovací objekt dostal ze své výchozí pozice do bodu B, ale brání mu v tom různé překážky, a tudíž nemůže jít přímočaře k cíli. Pro zjednodušení je to jako poslat jednotku v RTS hrách kamsi na druhou stranu mapy. Zároveň je i terén, po kterém se pohybuje, různorodý, ale principově bude stačit vyhledání možné nejkratší cesty.

    Na internetu jsem zkusil najít nějaké hotové kódy nebo návody. Jediné, co jsem našel, tak je tento návod, ale kód je psaný v Pascalu a vyřešit to v C# mi dělá trochu problém (částečně i porozumění, jak to všechno má fungovat a na jakém principu).

    Zatím jsem si vypracoval postup, že z pozice jednotky se prozkoumá okolní terén (v 8 směrech) do vzdálenosti cca 2 polí. Poté se získá hodnota obtížnosti každého jednotlivého směru. Ten, který má hodnotu nejnižší (pokud jich bude více, tak se vybere ten směr, který vede nejblíže k bodu B), tak tím se bude pokračovat. Konečný bod se zapíše. Na konečném bodu se opět budou prozkoumávat okolní pole (možná už jen do vzdálenosti 1) a bude platit stejné pravidlo. Pokud bude koncový bod na stejné pozici, tak se použije tato cesta pro jednotku.

    Ostatně tady mám hrubý algoritmus:

    Pokud má někdo alespoň malou radu, tak budu rád, a předem děkuji.



    30. listopadu 2012 20:39

Odpovědi

  • Základním pojmem je v tomto případě Dijkstrův algoritmus - ten v ohodnoceném grafu najde nejkratší cestu z bodu A do bodu B. Podrobnosti najdeš třeba na wiki.

    Dijkstra má pak úpravy jako např. A*  algoritmus, který vnáší další heuristiky zrychlující hledání cesty.

    Google pak dá spoustu odpovědí na dotaz "pathfinding in games".

    • Označen jako odpověď DISCOVERY.2 12. března 2013 18:54
    11. prosince 2012 13:13