Rješavač labirinta na Javi

1. Uvod

U ovom ćemo članku istražiti moguće načine kretanja labirintom pomoću Jave.

Smatrajte labirint crno-bijelom slikom, s crnim pikselima koji predstavljaju zidove, a bijelim pikselima koji predstavljaju put. Dva su bijela piksela posebna, jedan je ulaz u labirint, a drugi izlaz.

S obzirom na takav labirint, želimo pronaći put od ulaza do izlaza.

2. Modeliranje labirinta

Labirint ćemo smatrati 2D cjelovitim nizom. Značenje numeričkih vrijednosti u polju bit će prema sljedećem dogovoru:

  • 0 -> Cesta
  • 1 -> Zid
  • 2 -> Ulaz u labirint
  • 3 -> Izlaz iz labirinta
  • 4 -> Stanični dio puta od ulaza do izlaza

Modelirat ćemo labirint kao grafikon. Ulaz i izlaz su dva posebna čvora između kojih treba odrediti put.

Tipični graf ima dva svojstva, čvorove i rubove. Rub određuje povezanost grafa i povezuje jedan čvor s drugim.

Stoga ćemo pretpostaviti četiri implicitna ruba iz svakog čvora, povezujući dati čvor s njegovim lijevim, desnim, gornjim i donjim čvorom.

Definirajmo potpis metode:

riješiti javni popis (labirint labirint) {}

Ulaz u metodu je a labirint, koji sadrži 2D niz, s gore definiranom konvencijom imenovanja.

Odgovor metode je popis čvorova koji tvori put od ulaznog do izlaznog čvora.

3. Rekurzivni backtracker (DFS)

3.1. Algoritam

Jedan prilično očit pristup je istražiti sve moguće putove, koji će u konačnici pronaći put ako postoji. Ali takav će pristup imati eksponencijalnu složenost i neće se dobro razmjeriti.

Međutim, moguće je prilagoditi gore spomenuto rješenje grube sile vraćanjem i označavanjem posjećenih čvorova kako bi se put dobio u razumnom vremenu. Ovaj algoritam poznat je i kao dubinsko pretraživanje.

Ovaj algoritam može se ocrtati kao:

  1. Ako smo kod zida ili već posjećenog čvora, vratite neuspjeh
  2. Inače ako smo izlazni čvor, onda vratimo uspjeh
  3. Inače, dodajte čvor na popis staza i rekurzivno putujte u sva četiri smjera. Ako se neuspjeh vrati, uklonite čvor s putanje i vratite neuspjeh. Popis staza sadržavat će jedinstveni put kada se pronađe izlaz

Primijenimo ovaj algoritam na labirint prikazan na slici-1 (a), gdje je S početna točka, a E izlaz.

Za svaki čvor prelazimo svaki smjer redom: desno, dolje, lijevo, gore.

U 1. (b) istražujemo put i udaramo u zid. Zatim se vraćamo dok se ne pronađe čvor koji ima susjedne zidove i istražujemo drugi put kao što je prikazano u 1 (c).

Ponovno udaramo u zid i ponavljamo postupak da bismo napokon pronašli izlaz, kao što je prikazano u 1 (d):

3.2. Provedba

Pogledajmo sada implementaciju Jave:

Prvo, moramo definirati četiri smjera. To možemo definirati u smislu koordinata. Ove koordinate, kada se dodaju bilo kojoj zadanoj koordinati, vratit će jednu od susjednih koordinata:

privatni statički int [] [] SMJERI = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 

Također nam je potrebna korisna metoda koja će dodati dvije koordinate:

private Coordinate getNextCoordinate (int row, int col, int i, int j) {return new Coordinate (row + i, col + j); }

Sada možemo definirati potpis metode riješiti.Logika je ovdje jednostavna - ako postoji put od ulaza do izlaza, vratite put, inače vratite prazan popis:

javno rješavanje popisa (Maze labirint) {Staza popisa = novi ArrayList (); if (istražiti (maze, maze.getEntry (). getX (), maze.getEntry (). getY (), path)) {return path; } return Collections.emptyList (); }

Definirajmo istražiti gore navedena metoda. Ako postoji put, vratite true, sa popisom koordinata u argumentu staza. Ova metoda ima tri glavna bloka.

Prvo odbacujemo nevaljane čvorove, tj. Čvorove koji su izvan labirinta ili su dio zida. Nakon toga označavamo trenutni čvor kao posjećen, tako da više puta ne posjećujemo isti čvor.

Konačno, rekurzivno se krećemo u svim smjerovima ako izlaz nije pronađen:

privatno logičko istraživanje (labirint labirint, int redak, int col, put do popisa) {if (! maze.isValidLocation (red, col) || maze.isWall (red, col) || maze.isExplored (row, col)) { return false; } path.add (nova koordinata (red, kolona)); maze.setVisited (red, col, true); if (maze.isExit (row, col)) {return true; } for (int [] direction: DIRECTIONS) {Coordinate coordinate = getNextCoordinate (row, col, direction [0], direction [1]); if (istražiti (labirint, координата.getX (), координата.getY (), put)) {return true; }} put.remove (path.size () - 1); return false; }

Ovo rješenje koristi veličinu hrpe do veličine labirinta.

4. Varijanta - najkraći put (BFS)

4.1. Algoritam

Gore opisani rekurzivni algoritam pronalazi put, ali to nije nužno najkraći put. Da bismo pronašli najkraći put, možemo se poslužiti drugim pristupom zaokretanja grafova poznatim kao pretraživanje u širinu.

U DFS-u je prvo istraženo jedno dijete i svi njegovi unuci, prije nego što su prešli na drugo dijete. Dok ćemo u BFS-u istražiti svu neposrednu djecu prije nego što prijeđemo na unuke. To će osigurati da se svi čvorovi na određenoj udaljenosti od roditeljskog čvora istraže istovremeno.

Algoritam se može dati na sljedeći način:

  1. Dodajte početni čvor u red čekanja
  2. Iako red nije prazan, otvorite čvor, učinite sljedeće:
    1. Ako dođemo do zida ili je čvor već posjećen, preskočite na sljedeću iteraciju
    2. Ako se dosegne izlazni čvor, vratite se od trenutnog čvora do početnog čvora da biste pronašli najkraći put
    3. Inače, dodajte sve neposredne susjede u četiri smjera u red čekanja

Ovdje je jedna važna stvar da čvorovi moraju pratiti svog roditelja, tj. Od mjesta na kojem su dodani u red. Ovo je važno za pronalaženje puta kada se naiđe na izlazni čvor.

Sljedeća animacija prikazuje sve korake pri istraživanju labirinta pomoću ovog algoritma. Možemo primijetiti da se svi čvorovi na istoj udaljenosti prvo istražuju prije prelaska na sljedeću razinu:

4.2. Provedba

Ajmo sada implementirati ovaj algoritam u Javi. Ponovno ćemo upotrijebiti UPUTE varijabla definirana u prethodnom odjeljku.

Omogućimo prvo definiranje korisne metode za povratak s određenog čvora na njegov korijen. Ovo će se koristiti za traženje puta kada se pronađe izlaz:

privatni popis backtrackPath (koordinatni cur) {Staza popisa = novi ArrayList (); Koordiniraj iter = cur; while (iter! = null) {put.add (iter); iter = iter.parent; } povratni put; }

Ajmo sada definirati temeljnu metodu riješiti. Ponovno ćemo upotrijebiti tri bloka korištena u implementaciji DFS-a, tj. Provjeriti valjanost čvora, označiti posjećeni čvor i preći susjedne čvorove.

Napravit ćemo samo jednu malu izmjenu. Umjesto rekurzivnog prelaska, koristit ćemo FIFO strukturu podataka za praćenje susjeda i iteraciju nad njima:

rješenje javnog popisa (Maze labirint) {LinkedList nextToVisit = novi LinkedList (); Koordinata start = maze.getEntry (); nextToVisit.add (početak); while (! nextToVisit.isEmpty ()) {Koordinata cur = nextToVisit.remove (); if (! maze.isValidLocation (cur.getX (), cur.getY ()) || maze.isExplored (cur.getX (), cur.getY ())) {continue; } if (maze.isWall (cur.getX (), cur.getY ())) {maze.setVisited (cur.getX (), cur.getY (), true); nastaviti; } if (maze.isExit (cur.getX (), cur.getY ())) {return backtrackPath (cur); } za (int [] smjer: SMJERI) {Koordinata koordinata = nova koordinata (cur.getX () + smjer [0], cur.getY () + smjer [1], cur); nextToVisit.add (koordinata); maze.setVisited (cur.getX (), cur.getY (), true); }} return Collections.emptyList (); }

5. Zaključak

U ovom uputstvu opisali smo dva glavna algoritma grafova Dubinsko prvo pretraživanje i Širinsko prvo traženje kako bismo riješili labirint. Također smo se dotaknuli kako BFS daje najkraći put od ulaza do izlaza.

Za daljnje čitanje potražite druge metode za rješavanje labirinta, poput algoritma A * i Dijkstra.

Kao i uvijek, puni kod možete pronaći na GitHubu.