Útkereső algoritmus? (lent)

Annak idején írtam egy ilyen programot. Az a* algoritmust használtam fel. Egy viszonylag egyszerű algoritmus, viszont kicsit nehéz rajz nélkül elmagyarázni. Ezért inkább nézd meg a következő videót:

http://www.youtube.com/watch?v=Kw8AMmyc6vg

Ezzel a módszerrel a tárgy nem akadhat el, mert a számítógép előbb "fejben" megoldja, és csak amikor megtalálta a helyes utat indítsa el a tárgyat.

Miért lenne bonyolult?

Na elpróbálom magyarázni akkor az a* algoritmust.

Van egy térképed. Ez legyen egy bazinagy mátrix. Az egyszerűség kedvéért csak függőleges meg vízszintes irányba lehet elmozdulni. A falakat jelölje -1 és a célt -2, a járható utat pedig -3 (tulajdonképpen mindegy mivel jelölöd). Elindulsz a start-ból. Első lépésként négy szomszédos négyzetre tudsz lépni, ha nincs melletted fal. Tulajdonképpen az összeset végigjárhatnád, de abban nincs semmi "intelligencia" és nem lenne heurisztikus keresés. A heurisztika azt jelenti, hogy van egy törvényed ami alapján ki tudod választani, hogy melyik a következő legjobb lépés, ami jelen esetben közelebb visz a célhoz. Szóval úgy járhatsz el, hogy kiszámolod egyesével, hogy még hány lépésed lenne (falon, tűzön, vizen át) ha az egyes szomszéd négyzetekre lépnél. Így mindegyik négyzet kap egy számot (ez a szám a videón a négyzetek jobb felső sarkában van). Ha ez megvan akkor a legkisebb értékkel rendelkező négyzeteket a fent leírtak alapján kiterjesztheted. A lényeg, hogy vigyázz nehogy falat akarjál kiterjeszteni.

Én c-ben írtam meg anno. Csináltam egy négyzet struktúrát. A mátrix elemei ilyen típusúak voltak. A struktúrának volt egy értéke ami jelölte, hogy az adott négyzet szerepe fal, cél, vagy járhatu út-e, mivel csak a járható utakat kell kiterjesztni. Továbbá még volt egy értéke, ami a kiterjesztés után, a céltól való távolságot tartalmazta.

Ezzel a magyarázattal tulajdonképpen csak egy rálátást akartam adni, hogy némi utánaolvasással meg tudd csinálni. Sok sikert.

Alapvetően ez elég egyszerű cucc.

Leírás és példa kód Pythonban: [link]