Hogyan írnátok olyan programot ami megkeresi és kirajzolja a labirintusban kifelé vezető útját?

Szerintem itt két dologról beszélünk.

Az egyik, ami magát a képet ismeri fel és dolgozza fel, a másik dolog pedig maga az algoritmus, ami már nem egy képpel fog dolgozni, hanem egy tömbbel.

Az a kérdés, hogy te ennek melyik felére vagy kíváncsi?

Kérdésedre válaszolva ez az első feladatkörbe tartozik, amikor feldolgozod a képet és egy tömböt gyártasz belőle úgy tudod megállapítani hogy egy adott mezőben merre lehet lépni, hogy melyik oldala fehér.

Szia.

Ha lebontjuk épitőelemeire a labirintust akkor miból áll :

- útból

- falból

- megtett útból/bejárt útból

- Elágazásokból

Ennek a labirintusnak a leképezéséhez kell kb. egy 62x86-os tömb (mivel a fehér "útak" sokkal vastagabbak mint a lila "falak", ha úgy rajzolnád meg, hogy a lila falak és a fehér utak is csak egy-egy egységek lennének akkor kapod kb a 62x/86-os méretet. (Ugy nagyjából számoltam meg)

Tehát felveszel egy 62x86-os bájtos tömböt, és feltöltöd a labirintus elemeivel. Kinevezel egy-egy számot falnak és útnak is illetve megtett utnak (pl út=0, fal=255, megtett út=128)

Innentől kezdve ha megadod az induló poziciót X,Z koordinátakban akkor el tudod dönteni, minden egyes pozicióban, hogy hogyan tovább.

Csak feltételek kérdése :

Balról jobbra menés feltétele vagy jobbról balra menés :

Ha tömb[x,y-1]=255 és tömb[x,y+1]=255

Magyarul, ha a poziciód feletti sorban és a poziciód alatti sorban fal van akkor csak balra vagy jobbra mehetsz.

Fentről lefelé vagy lentről felfelé haladás :

Ha tömb[x-1,y]=255 és tömb[x+1,y]=255

Magyarul, ha a poziciódtól balra illetve jobbra is fal van akkor csak lefelé vagy felfelé mehetsz.

Leprogramozod a négy irányt. Balról jobbra, Jobbról balra, Fentről lefelé, Lentről felfelé.

Aztán már csak az elágazásokat kell leprogramozni (Azok a pontok ahol két vagy több irányba is tudsz menni, - ahonnan érkezel az itt most nem számit iránynak). Illetve létre kell hozni egy algoritmust ami eldönti, hogy meylik elágazáson haladjon tovább. (Ilyen algoritmus pl. a mindig balra vagy mindig jobbra algoritmus. Tehát az elágazásból mindig balra mész először (vagy jobbra)).

Ha ez megvan akkor már csak a backtrtack algoritmust kell megvalósitani :

Ha elágazáshoz érsz, akkor azt letárolod. (minden egyes elágazást).

Ha zsákutszába érsz akkor vissza a legutóljára letárolt elágazáshoz és kiválasztani a következő irányt.

Ha már minden irány volt (akkor az azt jelenti, hogy abból az elágazásból nem lehet kijutni), tehát még egy elágazást (még egy szintet) vissza kell ugrani.

Előbb utóbb megtalálod a kivezető utat.

Sok sikert.

Üdv.

Ha megnézed a képet én azt mondanám, hogy egy 18x18 pixeles négyzet lenne egy mező, a fal pedig 3px széles.

A képen 41*30 mező van eszerint.

Csinálsz ennek megfelelően egy 40*30-as tömböt, amiben van valamilyen típusú adat ami tárolja hogy merre lehet menni, de ebbe nem megyek bele részletesen, mert a képfeldolgozás érdekel.

Ekkor végignézed a képet mezőnként, azaz csinálsz egy ciklust, ami elindul 0-tól, ez lesz egy "sor" ezen belül egy másikat ez lesz egy oszlop.

Az első meződ így a 2,2 pixel és a 20,20 pixel közötti rész, ha 0-tól indexeljük, hiszen 3 pixel a "fal".

Neked elég megnézni minden oldalán, hogy a mellette levő pixelnek mi a színe és ezalapján eltárolni a tömbödben hogy van-e arra út vagy nincs.

Így pl. én megnézem "balról" azaz pl. az 11,1 pixelt nézem, hogy ez milyen színű(átlagolod az y koordinátát, és az x-ből pedig a bal oldalához képest kivonsz egyet).

Ugyanígy felfele a 1,11 jobbra a 11,21, lefele pedig a 21,11 pixelt.

Nyilván a ciklusod változóit felhasználva fogod minden egyes mezőnél ezt elvégezni, ez csak az első mező volt mint példa.

Persze a képre nagyítva sajnos nem teljesen egyértelmű a helyzet, mert csak fehér és lila színű pixelek vannak, így vagy átszínezed és abból indulsz ki hogy csak ez a két szín szerepelhet, vagy nehezebb a dolgod a szín felismerésénél.

Ha van még kérdésed, írhatsz privátba is ha akarsz, mert már túl hosszú lesz ez a kérdés :)

Mintha egy fájlt keresnél egy merevlemezen, hogy érthetőbb legyen. Van egy csomó mappa és fájl. A mappákban még több mappa. Elindulsz a gyökér első eleme felé, ami mondjuk egy mappa. Ha annak az első eleme is mappa, belelépsz abba is. Ha ott nincs, mész a mappa második elemére, ha az is mappa, abba is belelépsz. Ha kiderül, hogy nincs ebben a mappában a keresett fájlunk, továbblépünk a gyökérelem második elemére. Stb stb. Addig megy ez, míg végül a keresett fájl vagy meg lesz, vagy nem.

Jelen esetben a keresett fájl a kijárat a labirintusból (vagy valami kulcs, arany vagy valami értékes, amit meg kell találni benne). Az elágazások a mappák. Tehát egy labirintust is fel lehetne írni fa alakban. A többi már csicsa és sok óra programozás kérdése.

Szia.

Végigmész először vizszintesen a linkelt képen és megszámolod a "lila" falakat és a "fehér" utvonalakat, igy kapod meg a 65-öt (ujraszámoltam), aztán ugyanezt megcsinálod függőlegesen is és akkor kapod meg a 85-öt. tehát a tömb mérete 65x85.

De bekockáztam neked az általad linkelt képet, hogy szerintem hogyan alakul ki a tömb (csak a tetejét és jobb oldalát) : [link]

Sok sikert.

Üdv.