Algoritmus na určení dosahu v dvourozměrném poli

[GooDer]

Zdravím všechny,

potřeboval bych poradit s algoritmem, který by ve 2D prostoru vrátil všechna pole v určité vzdálenosti od počátečního bodu.

Mám 2D mapu složenou z polí, kde má každé pole odkaz na svého souseda vertikálně, horizontálně i diagonálně.

Níže je názorný obrázek problému, kde černá pole jsou neprůchozí, bílá průchozí, zelený je počáteční bod, červeně ukázka reference pole na ostatní a žlutě je podbarvený dosah pro 4 body pohybu (diagonální pohyb je za 1 bod).

Napsal jsem si rekurzivní metodu, která sice správně vybere pole, ale při rekurzi se dost pohybuje tam a zpět, takže pro 4 pole udělá 204 rekurzí a pro 8 už něco kolem 340 000, což je nemyslitelné

Předem děkuji za pomoc.

[mar]

Jestli to správně chápu, chceš projít všechna dosažitelná pole v určité vzdálenosti?

Proč si jednoduše neoznačit pole, která už jsi prošel (a ta ignorovat)?

EDIT:Myslím tím označovat už při ukládání indexu pole na stack; rekurzi nepotřebuješ,
prostě budeš ve smyčce tahat z vlastního stacku a to pole pak zpracuješ (podobně jako u hlednání nejkratší cesty, ale tady ti postačí stack místo prioritní fronty)

Možná úplně nejlepší by bylo to udělat breadth-first (pseudo-kód, bez záruky, že bude fungovat):

[GooDer]

Díky za nasměrování na breadth-first algoritmus. Nakonec jsem zjistil, že mám chybu v propojení některých polí. Na některých místech se pole tvářila, že už končí a nepokračují dál, takže když se mi povedlo napsat lepší rekurzivní algoritmus, tak nevybral všechna pole.

I tak mi to pomohlo se rekurze zbavit a za to děkuji

[quas4]

[GooDer]

Tím jsem myslel, že dostanu do algoritmu vstupní pole (čtverec mapy), který zná přímo jen pole kolem sebe a nemá přehled, jak vypadají vazby dál. Tedy kde je nějaká překážka.

[pcmaster]

Ani ja tomu nerozumiem. Co neznamy? Komu/comu neznamy?

BFS (a generalizovane Dijskstra i A*) i DFS algoritmus predsa pracuju s grafom a kazdy uzol "vidi" len uzly s ktorymi je hranamy spojeny.

Tu je uzlom jedno policko a hrany vedu k okolitym 4 (ci polickam. Policko na jednom konci mapy netusi nic o druhom konci mapy.

Algoritmus vzdy pre dane policko skuma okolite policka.

Skus nam vysvetlit, comu nerozumies.
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[GooDer]

Ještě jednou děkuji marovi za pomoc a pro ostatní jsem smazal z dotazu slovo "neznámý", aby se vám lépe spalo