.[ ČeskéHry.cz ].
Algoritmus na určení dosahu v dvourozměrném poli

 
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> Obecné
Zobrazit předchozí téma :: Zobrazit následující téma  
Autor Zpráva
GooDer



Založen: 10. 08. 2007
Příspěvky: 8

PříspěvekZaslal: 12. prosinec 2015, 18:37:27    Předmět: Algoritmus na určení dosahu v dvourozměrném poli Odpovědět s citátem

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é Twisted Evil

Předem děkuji za pomoc.



Naposledy upravil GooDer dne 19. prosinec 2015, 13:50:42, celkově upraveno 1 krát
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 510

PříspěvekZaslal: 12. prosinec 2015, 19:07:25    Předmět: Re: Algoritmus na určení dosahu v dvourozměrném poli Odpovědět s citátem

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):

kód:

void func(int range)
{
    vector<index> last, tmp;
    mark(start);
    last.push_back(start);
    for (i=0; i<range; i++) {
        tmp.clear();
        for (j=0; j<last.size(); j++) {
            index idx = last[j];
            output(idx);    // func output
            add_neighbors(idx, tmp);
        }
        swap(last, tmp);
    }
}

void add_neighbors(index idx, vector<index> &outv)
{
    for (all neighbors n of idx) {
        if (blocked(n) || marked(n))
           continue;
        mark(n);
        outv.push_back(n);
    }
}
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
GooDer



Založen: 10. 08. 2007
Příspěvky: 8

PříspěvekZaslal: 13. prosinec 2015, 01:21:27    Předmět: Odpovědět s citátem

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 Smile
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
quas4



Založen: 18. 10. 2007
Příspěvky: 199

PříspěvekZaslal: 14. prosinec 2015, 00:37:22    Předmět: Re: Algoritmus na určení dosahu v dvourozměrném poli Odpovědět s citátem

GooDer napsal:

potřeboval bych poradit s algoritmem, který by v neznámém 2D prostoru


...rad poradim, ale na tomto jsem se pri cteni postu zastavil. Jako programator pises "v neznamem 2D prostoru"? V jakem smyslu je neznamy? Ty nebo nekdo jiny ho nezna? Programovani exaktni.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
GooDer



Založen: 10. 08. 2007
Příspěvky: 8

PříspěvekZaslal: 15. prosinec 2015, 21:26:26    Předmět: Odpovědět s citátem

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.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
pcmaster



Založen: 28. 07. 2007
Příspěvky: 1752

PříspěvekZaslal: 17. prosinec 2015, 13:54:17    Předmět: Odpovědět s citátem

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 Cool 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.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
GooDer



Založen: 10. 08. 2007
Příspěvky: 8

PříspěvekZaslal: 19. prosinec 2015, 13:51:57    Předmět: Odpovědět s citátem

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 Rolling Eyes
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Zobrazit příspěvky z předchozích:   
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> Obecné Časy uváděny v GMT + 1 hodina
Strana 1 z 1

 
Přejdi na:  
Nemůžete odesílat nové téma do tohoto fóra
Nemůžete odpovídat na témata v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete hlasovat v tomto fóru


Powered by phpBB © 2001, 2005 phpBB Group


Vzhled udelal powermac
Styl "vykraden" z phpBB stylu MonkiDream - upraveno by rezna