TlačiťTlačiť Slovenčina English Hľadať RSS

© 2005 – 2024 Roman Horváth, všetky práva vyhradené. Dnes je 28. 3. 2024.

Stránka sa načítava, prosím čakajte…

Dátum: 23. 8. 2021, pred tromi rokmi, aktualizované: 23. 8. 2021, pred tromi rokmi

V rámci tohto projektu je implementovaný algoritmus prehľadávania grafu do šírky. Najskôr si vysvetlime, čo myslíme pojmom graf.

Graf je v teórii grafov množina vrcholov, ktoré môžu byť prepájané hranami. Táto údajová štruktúra má v programovaní široké použitie. Vrcholmi môžu byť napríklad križovatky a hranami ulice, ktoré ich spájajú. Grafy môžu mať rôzne doplňujúce vlastnosti. Hrany môžu byť orientované („jednosmerky“) alebo hodnotené (dĺžky ulíc, počty pruhov…). Vrcholy môžu byť tiež hodnotené (priemerné zdržanie na križovatke). Všetko závisí od účelu použitia grafu.

Údajová štruktúra grafu môže byť implementovaná rôzne. Môže to byť dynamická údajová štruktúra, zoznam, jedno­‑ alebo viacrozmerné pole… V tomto projekte používame na vyjadrenie mapy, ktorá je naším grafom dvojrozmerné pole mapa v triede Scéna. Prvky poľa sú vrcholmi grafu a hodnoty prvkov poľa určujú hrany a to takým spôsobom, že zvolené bity hodnoty každého prvku určujú, či je vrchol jednosmerne prepojený so susediacim horný (1. bit), pravým (2. bit), spodným (3. bit) alebo ľavým (4. bit) prvkom.

Aby sme si zjednodušili prácu s bitmi, definovali sme v triede Scéna konštanty s hodnotami týchto bitov (v zmysle, že výsledná hodnota má v binárnej podobe nastavený len tento konkrétny bit).


Algoritmus prehľadávania do šírky potrebuje určité vstupné údaje a nastavenia. To zahŕňa voľbu pozícií, medzi ktorými sa má hľadať cesta: počiatočnej/štartovacej (S) a cieľovej/koncovej (F). Každý vrchol si musí byť schopný zapamätať, či bol počas aktuálneho prehľadávania navštívený, alebo nie. Volajme túto informáciu príznakom „navštívený.“ Pred hľadaním nastavíme príznaky všetkých vrcholov na „nie.“ Každý vrchol si tiež musí byť schopný zapamätať, kam (do ktorého smeru/vrcholu) sa z neho pri prehľadávaní má ísť (inak by sme neboli schopní spätne zistiť cestu). Ďalej potrebujeme zásobník vrcholov, ktoré ešte treba prehľadať. Ten na začiatku vyprázdnime.

Algoritmus potom pracuje takto:

  1. Graf začíname prehľadávať z vrcholu F (áno, začíname v koncovom bode, inak by algoritmus nenašiel správnu/najkratšiu cestu – môžete si to overiť prakticky – keď vymeníte v algoritme pozície a necháte zobraziť výslednú cestu), takže prvým krokom je vloženie vrcholu F do zásobníka vrcholov.
  2. V tomto kroku najprv overíme, či je zásobník vrcholov prázdny, ak áno, končíme neúspechom – cesta sa nenašla. Ak nie, tak vyberieme posledný vrchol zo zásobníka a zvolíme ho za aktuálny.
  3. Označíme aktuálny vrchol za navštívený. Ak je tento vrchol vrcholom S, tak sme cestu našli a končíme algoritmus úspechom – prejdeme na bod 6.
  4. Postupne zisťujeme z ktorých susedných miest sa dá dostať do tohto uzla (vrcholu). Do každého takého vrcholu, z ktorého to je možné uložíme informáciu o smere (že z toho uzla sa má ísť smerom na aktuálny vrchol) a vložíme ten vrchol na začiatok zásobníka.
  5. Vrátime sa na bod 2.
  6. Zostavíme cestu z bodu S do bodu F podľa informácií, ktoré sme ukladali v bode 4.

Implementácia

Hľadanie cesty sa spustí kliknutím pravého tlačidla myši na tú časť scény, do ktorej sa prieskumník môže zo svojej aktuálnej pozície dostať.

  
obrázok 
Prieskumník hľadá cestu na náhodne vygenerovanej scéne. 
 

~

import knižnica.*;
import static knižnica.ÚdajeUdalostí.*;

public class Prieskumník extends GRobot
{
	// Inštancia scény:
	private Scéna scéna;

	// Atribúty slúžiace na uchovanie polohy, orientácie a parametrov pohybu
	// prieskumníka:
	private int x0, y0, x1, y1;
	private double s0, s1, krok;

	private boolean kráčajHore   = false;
	private boolean kráčajVpravo = false;
	private boolean kráčajDole   = false;
	private boolean kráčajVľavo  = false;
	private boolean ajPohnúť     = true;

	// Atribúty prevodu polohy myši na polohu na scéne:
	private int xs = 0, ys = 0;

	// Aktuálna cesta:
	private final Zoznam<Integer> cesta = new Zoznam<>();


	// Konštruktor:
	private Prieskumník()
	{
		super(400, 400);

		Svet.nekresli();
		scéna = new Scéna();
		scéna.skry();
		scéna.vyprázdni();
		scéna.náhodnéPrekážky();
		scéna.nakresli();

		farba(červená);
		hrúbkaČiary(2.0);
		veľkosť(scéna.polomer() - 2 * scéna.hrúbka());
		x1 = x0 = (int)Svet.náhodnéCeléČíslo();
		y1 = y0 = (int)Svet.náhodnéCeléČíslo();
		s1 = s0 = 90;
		krok = 0.0;
		aktualizujPolohuASmer();
		Svet.vypíš(this);
		Svet.farbaTextu(hnedá);

		Svet.spustiČasovač();
	}


	// Ladenie:
	// private void ladiaceInformácie()
	// {
	// 	Svet.vymažTexty();
	// 	Svet.vypíšRiadok("Poloha a smer prieskumníka: ", x0, y0, "–",
	// 		x1, y1, ";", s0, s1, "|", krok, riadok);
	// }


	// Prevod súradníc myši na polohu na scéne:
	private void myšNaPolohuNaScéne()
	{
		double šírka = scéna.šírkaRiadka(0);
		double výška = scéna.výškaMapy();
		double polomer = scéna.polomer();
		double vľavo = šírka * polomer + polohaMyšiX();
		double hore  = výška * polomer - polohaMyšiY();

		xs = (int)(vľavo / (2 * polomer));
		ys = (int)(hore / (2 * polomer));

		// Ladenie:
		// Svet.vypíšRiadok(šírka, výška, riadok, vľavo, hore);
	}


	// Obsluha udalostí:

	@Override public void tik()
	{
		if (kráčajHore)   kráčajHore(ajPohnúť);
		if (kráčajVpravo) kráčajVpravo(ajPohnúť);
		if (kráčajDole)   kráčajDole(ajPohnúť);
		if (kráčajVľavo)  kráčajVľavo(ajPohnúť);

		if (Svet.neboloPrekreslené())
		{
			aktualizujPolohuASmer();
			Svet.prekresli();
		}
	}

	@Override public void stlačenieKlávesu()
	{
		switch (kláves())
		{
		case Kláves.HORE:
			kráčajHore = true;
			ajPohnúť = !klávesnica().isShiftDown();
			break;

		case Kláves.VPRAVO:
			kráčajVpravo = true;
			ajPohnúť = !klávesnica().isShiftDown();
			break;

		case Kláves.DOLE:
			kráčajDole = true;
			ajPohnúť = !klávesnica().isShiftDown();
			break;

		case Kláves.VĽAVO:
			kráčajVľavo = true;
			ajPohnúť = !klávesnica().isShiftDown();
			break;

		// case Kláves.ENTER: vykonaťNiečo …
		}
	}

	@Override public void uvoľnenieKlávesu()
	{
		switch (kláves())
		{
		case Kláves.HORE:   kráčajHore   = false; break;
		case Kláves.VPRAVO: kráčajVpravo = false; break;
		case Kláves.DOLE:   kráčajDole   = false; break;
		case Kláves.VĽAVO:  kráčajVľavo  = false; break;
		}
	}

	// Slúžilo iba na ladenie:
	// @Override public void pohybMyši()
	// {
	// 	myšNaPolohuNaScéne();
	// 	ladiaceInformácie();
	// }

	@Override public void klik()
	{
		myšNaPolohuNaScéne();

		if (tlačidloMyši(PRAVÉ))
		{
			boolean našiel = scéna.nájdiCestu(y0, x0, ys, xs, cesta);
			// Ladenie:
			// Svet.vypíš("Úspešnosť hľadania cesty: ", našiel);
			if (našiel)
			{
				Svet.vymažGrafiku();
				scéna.nakresli();
			}
		}
		// ladiaceInformácie();
	}


	// Pohyb prieskumníka:

	public void aktualizujPolohuASmer()
	{
		double výška = scéna.výškaMapy();

		if (y0 < 0) y0 += výška;
		y0 %= výška;
		if (y0 < 0) y0 = -y0;

		double šírkaRiadka = scéna.šírkaRiadka(y0);

		if (x0 < 0) x0 += šírkaRiadka;
		x0 %= šírkaRiadka;
		if (x0 < 0) x0 = -x0;

		if (y1 < 0) y1 += výška;
		y1 %= výška;
		if (y1 < 0) y1 = -y1;

		šírkaRiadka = scéna.šírkaRiadka(y1);

		if (x1 < 0) x1 += šírkaRiadka;
		x1 %= šírkaRiadka;
		if (x1 < 0) x1 = -x1;

		double polomer = scéna.polomer();
		double vľavo = (scéna.šírkaRiadka(0) - 1) * polomer;
		double hore = (výška - 1) * polomer;

		poloha(scéna);
		smer(scéna);

		preskočVľavo(Svet.lineárnaInterpolácia(
			vľavo - 2 * polomer * x0,
			vľavo - 2 * polomer * x1, krok));
		skoč(Svet.lineárnaInterpolácia(
			hore - 2 * polomer * y0,
			hore - 2 * polomer * y1, krok));

		vpravo(90);
		if (s1 - s0 > 180)
			vľavo(Svet.lineárnaInterpolácia(s0 + 360, s1, krok));
		else if (s0 - s1 > 180)
			vľavo(Svet.lineárnaInterpolácia(s0 - 360, s1, krok));
		else
			vľavo(Svet.lineárnaInterpolácia(s0, s1, krok));

		// ladiaceInformácie();
	}

	public void kráčajHore(boolean ajPohnúť)
	{
		if (aktívny()) return;

		if (scéna.dáSaÍsťHore(y0, x0))
		{
			s0 = 90;
			if (ajPohnúť) --y0;
			aktivuj();
		}
		else if (s0 != 90)
		{
			s0 = 90;
			aktivuj();
		}
	}

	public void kráčajVpravo(boolean ajPohnúť)
	{
		if (aktívny()) return;

		if (scéna.dáSaÍsťVpravo(y0, x0))
		{
			s0 = 0;
			if (ajPohnúť) ++x0;
			aktivuj();
		}
		else if (s0 != 0)
		{
			s0 = 0;
			aktivuj();
		}
	}

	public void kráčajDole(boolean ajPohnúť)
	{
		if (aktívny()) return;

		if (scéna.dáSaÍsťDole(y0, x0))
		{
			s0 = 270;
			if (ajPohnúť) ++y0;
			aktivuj();
		}
		else if (s0 != 270)
		{
			s0 = 270;
			aktivuj();
		}
	}

	public void kráčajVľavo(boolean ajPohnúť)
	{
		if (aktívny()) return;

		if (scéna.dáSaÍsťVľavo(y0, x0))
		{
			s0 = 180;
			if (ajPohnúť) --x0;
			aktivuj();
		}
		else if (s0 != 180)
		{
			s0 = 180;
			aktivuj();
		}
	}


	// Momentálne netreba:
	// public RiadokStĺpec polohaNaScéne()
	// {
	// 	return new RiadokStĺpec(y0, x0);
	// }


	// Reakcie robota:

	@Override public void aktivácia()
	{
		if (x0 != x1 || y0 != y1 || s0 != s1) krok = 0.8;
		Svet.žiadajPrekreslenie();
	}

	@Override public void aktivita()
	{
		if (krok > 0.0)
		{
			krok -= 0.2;
			Svet.žiadajPrekreslenie();
		}

		if (krok <= 0.0)
		{
			x1 = x0;
			y1 = y0;
			s1 = s0;
			deaktivuj();
		}
	}

	@Override public void pasivita()
	{
		if (!cesta.jePrázdny())
		{
			switch (cesta.prvý())
			{
			case Scéna.CHOĎ_HORE:   kráčajHore(true);   break;
			case Scéna.CHOĎ_VPRAVO: kráčajVpravo(true); break;
			case Scéna.CHOĎ_DOLE:   kráčajDole(true);   break;
			case Scéna.CHOĎ_VĽAVO:  kráčajVľavo(true);  break;
			}
			cesta.odober(0);
		}
	}

	@Override public void kresliTvar()
	{
		krúžok();
		vpred();
	}


	// Hlavná metóda:
	public static void main(String[] args)
	{
		Svet.použiKonfiguráciu("Prieskumník.cfg");
		new Prieskumník();
		if (Svet.prvéSpustenie()) Svet.zbaľ();
	}
}

~

import knižnica.*;
import java.util.LinkedList;

public class Scéna extends GRobot
{
	// Súbor verejných príznakov polí mapy scény.

	public final static int HORE   = 1;
	public final static int VPRAVO = 2;
	public final static int DOLE   = 4;
	public final static int VĽAVO  = 8;
	public final static int VŠADE  = 15; // 1 + 2 + 4 + 8

	public final static int CHOĎ_HORE   = 16;
	public final static int CHOĎ_VPRAVO = 32;
	public final static int CHOĎ_DOLE   = 64;
	public final static int CHOĎ_VĽAVO  = 128;
	// public final static int VŠETKY_SMERY = 240; // 16 + 32 + 64 + 128

	public final static int NAVŠTÍVENÉ = 256;
	public final static int PRÍZNAKY_CESTY = 496; // 240 + 256


	// Mapa scény.
	private int[][] mapa =
	{
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
	};


	// Údaje a metódy súvisiace s rozmermi scény.

	private double polomer = 11.0;
	private double hrúbka = 2.5;

	public double polomer()
	{
		return polomer;
	}

	public double hrúbka()
	{
		return hrúbka;
	}

	public int výškaMapy()
	{
		return mapa.length;
	}

	public int šírkaRiadka(int riadok)
	{
		if (riadok < 0 || riadok >= mapa.length) return -1;
		return mapa[riadok].length;
	}


	// Metódy slúžiace na overenie možnosti pohybu po scéne.
	// (V tejto triede ich používa iba algoritmus hľadania cesty, ale mimo
	// scény ich musia používať všetky pohyblivé postavičky na detekcie
	// kolízií so scénou.)

	public boolean dáSaÍsťHore(int riadok, int stĺpec)
	{
		return riadok >= 0 && riadok < mapa.length &&
			stĺpec >= 0 && stĺpec < mapa[riadok].length &&
			0 != (mapa[riadok][stĺpec] & HORE);
	}

	public boolean dáSaÍsťVpravo(int riadok, int stĺpec)
	{
		return riadok >= 0 && riadok < mapa.length &&
			stĺpec >= 0 && stĺpec < mapa[riadok].length &&
			0 != (mapa[riadok][stĺpec] & VPRAVO);
	}

	public boolean dáSaÍsťDole(int riadok, int stĺpec)
	{
		return riadok >= 0 && riadok < mapa.length &&
			stĺpec >= 0 && stĺpec < mapa[riadok].length &&
			0 != (mapa[riadok][stĺpec] & DOLE);
	}

	public boolean dáSaÍsťVľavo(int riadok, int stĺpec)
	{
		return riadok >= 0 && riadok < mapa.length &&
			stĺpec >= 0 && stĺpec < mapa[riadok].length &&
			0 != (mapa[riadok][stĺpec] & VĽAVO);
	}


	// Sekcia najužšie súvisiaca s určením zdroja a cieľa hľadania cesty.

	private int riadokZdroja = 0, stĺpecZdroja = 0;
	private int riadokCieľa = 0, stĺpecCieľa = 0;

	private boolean nastavZdroj(int riadok, int stĺpec)
	{
		if (riadok >= 0 && riadok < mapa.length &&
			stĺpec >= 0 && stĺpec < mapa[riadok].length)
		{
			riadokZdroja = riadok;
			stĺpecZdroja = stĺpec;
			return true;
		}
		return false;
	}

	private boolean nastavCieľ(int riadok, int stĺpec)
	{
		if (riadok >= 0 && riadok < mapa.length &&
			stĺpec >= 0 && stĺpec < mapa[riadok].length)
		{
			riadokCieľa = riadok;
			stĺpecCieľa = stĺpec;
			return true;
		}
		return false;
	}

	private boolean jeZdroj(RiadokStĺpec rs)
	{
		return riadokZdroja == rs.riadok && stĺpecZdroja == rs.stĺpec;
	}

	private boolean jeCieľ(int riadok, int stĺpec)
	{
		return riadokCieľa == riadok && stĺpecCieľa == stĺpec;
	}


	// Sekcia súvisiaca s hľadaním cesty (využíva sekcie overenia možností
	// pohybu po scéne a určenia zdroja a cieľa – vyššie).

	private class RiadokStĺpec
	{
		int riadok, stĺpec;
		int smer;

		RiadokStĺpec(int riadok, int stĺpec, int smer)
		{
			this.riadok = riadok;
			this.stĺpec = stĺpec;
			this.smer = smer;
		}

		RiadokStĺpec(int riadok, int stĺpec)
		{
			this.riadok = riadok;
			this.stĺpec = stĺpec;
			smer = -1;
		}

		@Override public String toString()
		{
			// Na ladenie:
			if (-1 == smer) return "r: " + riadok + "; s: " + stĺpec;
			return "r: " + riadok + "; s: " + stĺpec + "; sm: " + smer;
		}
	}

	private LinkedList<RiadokStĺpec> polohy = new LinkedList<>();

	private boolean jePlatné(int riadok, int stĺpec)
	{
		return riadok >= 0 && riadok < mapa.length &&
			stĺpec >= 0 && stĺpec < mapa[riadok].length;
	}

	private boolean jeNavštívené(RiadokStĺpec rs)
	{
		return rs.riadok < 0 || rs.riadok >= mapa.length ||
			rs.stĺpec < 0 || rs.stĺpec >= mapa[rs.riadok].length ||
			0 != (mapa[rs.riadok][rs.stĺpec] & NAVŠTÍVENÉ);
	}

	private void vyčistiMapu()
	{
		for (int riadok = 0; riadok < mapa.length; ++riadok)
			for (int stĺpec = 0; stĺpec < mapa[riadok].length; ++stĺpec)
				mapa[riadok][stĺpec] &= ~PRÍZNAKY_CESTY;
		polohy.clear();
	}

	private void odznačMapu()
	{
		for (int riadok = 0; riadok < mapa.length; ++riadok)
			for (int stĺpec = 0; stĺpec < mapa[riadok].length; ++stĺpec)
				mapa[riadok][stĺpec] &= ~NAVŠTÍVENÉ;
		polohy.clear();
	}

	private void očistiMapu()
	{
		for (int riadok = 0; riadok < mapa.length; ++riadok)
			for (int stĺpec = 0; stĺpec < mapa[riadok].length; ++stĺpec)
				if (0 == (mapa[riadok][stĺpec] & NAVŠTÍVENÉ))
					mapa[riadok][stĺpec] &= ~PRÍZNAKY_CESTY;
	}

	private void vyznačCestu(Zoznam<Integer> cesta)
	{
		int riadok = riadokZdroja;
		int stĺpec = stĺpecZdroja;
		int brzda = 2 * mapa.length * mapa[0].length; // záchranná brzda…
		cesta.vymaž();

		while (!jeCieľ(riadok, stĺpec) && jePlatné(riadok, stĺpec))
		{
			mapa[riadok][stĺpec] |= NAVŠTÍVENÉ;
			if (--brzda <= 0) break; // záchranná brzda…
			if (0 != (mapa[riadok][stĺpec] & CHOĎ_HORE))
			{
				cesta.pridaj(CHOĎ_HORE);
				--riadok;
			}
			else if (0 != (mapa[riadok][stĺpec] & CHOĎ_VPRAVO))
			{
				cesta.pridaj(CHOĎ_VPRAVO);
				++stĺpec;
			}
			else if (0 != (mapa[riadok][stĺpec] & CHOĎ_DOLE))
			{
				cesta.pridaj(CHOĎ_DOLE);
				++riadok;
			}
			else if (0 != (mapa[riadok][stĺpec] & CHOĎ_VĽAVO))
			{
				cesta.pridaj(CHOĎ_VĽAVO);
				--stĺpec;
			}
		}

		if (jePlatné(riadok, stĺpec))
			mapa[riadok][stĺpec] |= NAVŠTÍVENÉ;
	}

	private boolean hľadajCestu()
	{
		while (!polohy.isEmpty())
		{
			RiadokStĺpec rs = polohy.removeLast();

			if (jeNavštívené(rs)) continue;

			int pred = mapa[rs.riadok][rs.stĺpec];
			mapa[rs.riadok][rs.stĺpec] |= NAVŠTÍVENÉ;
			if (-1 != rs.smer) mapa[rs.riadok][rs.stĺpec] |= rs.smer;
			int po = mapa[rs.riadok][rs.stĺpec];

			if (jeZdroj(rs)) return true;

			if (dáSaÍsťDole(rs.riadok - 1, rs.stĺpec))
				polohy.push(new RiadokStĺpec(
					rs.riadok - 1, rs.stĺpec, CHOĎ_DOLE));

			if (dáSaÍsťVľavo(rs.riadok, rs.stĺpec + 1))
				polohy.push(new RiadokStĺpec(
					rs.riadok, rs.stĺpec + 1, CHOĎ_VĽAVO));

			if (dáSaÍsťHore(rs.riadok + 1, rs.stĺpec))
				polohy.push(new RiadokStĺpec(
					rs.riadok + 1, rs.stĺpec, CHOĎ_HORE));

			if (dáSaÍsťVpravo(rs.riadok, rs.stĺpec - 1))
				polohy.push(new RiadokStĺpec(
					rs.riadok, rs.stĺpec - 1, CHOĎ_VPRAVO));
		}

		return false;
	}

	public boolean nájdiCestu(
		int riadok0, int stĺpec0, int riadok1, int stĺpec1,
		Zoznam<Integer> cesta)
	{
		if (nastavZdroj(riadok0, stĺpec0))
		{
			vyčistiMapu();
			polohy.push(new RiadokStĺpec(riadok1, stĺpec1));

			if (hľadajCestu())
			{
				if (nastavCieľ(riadok1, stĺpec1))
				{
					odznačMapu();
					vyznačCestu(cesta);
					očistiMapu();
				}

				return true;
			}
		}
		return false;
	}


	// Rôzne metódy slúžiace na ovplyvňovanie obsahu scény (experimentálne).

	public void vyprázdni()
	{
		for (int riadok = 0; riadok < mapa.length; ++riadok)
			for (int stĺpec = 0; stĺpec < mapa[riadok].length; ++stĺpec)
				mapa[riadok][stĺpec] = VŠADE;
	}

	public void náhodnéPrekážky()
	{
		// Úplné „pomiešanie“ scény pridaním náhodných jednosmerných prekážok:
		//
		// for (int riadok = 0; riadok < mapa.length; ++riadok)
		// 	for (int stĺpec = 0; stĺpec < mapa[riadok].length; ++stĺpec)
		// 	{
		// 		switch ((int)Svet.náhodnéCeléČíslo(0, 7))
		// 		{
		// 		case 0: mapa[riadok][stĺpec] &= ~HORE;   break;
		// 		case 1: mapa[riadok][stĺpec] &= ~VPRAVO; break;
		// 		case 2: mapa[riadok][stĺpec] &= ~DOLE;   break;
		// 		case 3: mapa[riadok][stĺpec] &= ~VĽAVO;  break;
		// 		}
		// 	}

		// Zopár náhodných stien a chodieb:
		for (int i = 0; i < 20; ++i) náhodnáStena();
		for (int i = 0; i < 10; ++i) náhodnáChodba();
	}

	public void náhodnáStena()
	{
		if (0 == (int)Svet.náhodnéCeléČíslo(0, 1))
		{
			int riadok  = (int)Svet.náhodnéCeléČíslo(0, mapa.length);
			int stĺpec0 = (int)Svet.náhodnéCeléČíslo(0, mapa[0].length);
			int stĺpec1 = (int)Svet.náhodnéCeléČíslo(0, mapa[0].length);
			vodorovnáStena(riadok, stĺpec0, stĺpec1);
		}
		else
		{
			int riadok0 = (int)Svet.náhodnéCeléČíslo(0, mapa.length);
			int riadok1 = (int)Svet.náhodnéCeléČíslo(0, mapa.length);
			int stĺpec  = (int)Svet.náhodnéCeléČíslo(0, mapa[0].length);
			zvisláStena(riadok0, riadok1, stĺpec);
		}
	}

	public void vodorovnáStena(int riadok, int stĺpec0, int stĺpec1)
	{
		if (stĺpec0 > stĺpec1)
		{
			int s = stĺpec0;
			stĺpec0 = stĺpec1;
			stĺpec1 = s;
		}
		else if (stĺpec0 == stĺpec1)
		{
			if (stĺpec0 > 0) --stĺpec0;
			else ++stĺpec1;
		}

		if (0 == riadok)
		{
			for (int i = stĺpec0; i < stĺpec1; ++i)
				mapa[riadok][i] &= ~HORE;
		}
		else if (mapa.length == riadok)
		{
			--riadok;
			for (int i = stĺpec0; i < stĺpec1; ++i)
				mapa[riadok][i] &= ~DOLE;
		}
		else
		{
			for (int i = stĺpec0; i < stĺpec1; ++i)
			{
				mapa[riadok - 1][i] &= ~DOLE;
				mapa[riadok][i] &= ~HORE;
			}
		}
	}

	public void zvisláStena(int riadok0, int riadok1, int stĺpec)
	{
		if (riadok0 > riadok1)
		{
			int r = riadok0;
			riadok0 = riadok1;
			riadok1 = r;
		}
		else if (riadok0 == riadok1)
		{
			if (riadok0 > 0) --riadok0;
			else ++riadok1;
		}

		if (0 == stĺpec)
		{
			for (int i = riadok0; i < riadok1; ++i)
				mapa[i][stĺpec] &= ~VĽAVO;
		}
		else if (mapa.length == stĺpec)
		{
			--stĺpec;
			for (int i = riadok0; i < riadok1; ++i)
				mapa[i][stĺpec] &= ~VPRAVO;
		}
		else
		{
			for (int i = riadok0; i < riadok1; ++i)
			{
				mapa[i][stĺpec - 1] &= ~VPRAVO;
				mapa[i][stĺpec] &= ~VĽAVO;
			}
		}
	}

	public void náhodnáChodba()
	{
		if (0 == (int)Svet.náhodnéCeléČíslo(0, 1))
		{
			int riadok  = (int)Svet.náhodnéCeléČíslo(0, mapa.length - 1);
			int stĺpec0 = (int)Svet.náhodnéCeléČíslo(0, mapa[0].length);
			int stĺpec1 = (int)Svet.náhodnéCeléČíslo(0, mapa[0].length);
			vodorovnáStena(riadok, stĺpec0, stĺpec1);
			vodorovnáStena(riadok + 1, stĺpec0, stĺpec1);
		}
		else
		{
			int riadok0 = (int)Svet.náhodnéCeléČíslo(0, mapa.length);
			int riadok1 = (int)Svet.náhodnéCeléČíslo(0, mapa.length);
			int stĺpec  = (int)Svet.náhodnéCeléČíslo(0, mapa[0].length - 1);
			zvisláStena(riadok0, riadok1, stĺpec);
			zvisláStena(riadok0, riadok1, stĺpec + 1);
		}
	}


	// Nakreslenie scény:
	public void nakresli()
	{
		Poloha p = poloha();

		// Obkreslenie scény (viac-menej na ladenie):
		// kresliObdĺžnik((šírkaRiadka(0)) * polomer, (výškaMapy()) * polomer);

		preskočVľavo((mapa[0].length - 1) * polomer);
		skoč((mapa.length - 1) * polomer);

		for (int riadok = 0; riadok < mapa.length; ++riadok)
		{
			for (int stĺpec = 0; stĺpec < mapa[riadok].length; ++stĺpec)
			{
				double hč = hrúbkaČiary();

				// Šachovnicové obkreslenie polí scény (na ladenie):
				// hrúbkaČiary(0.5);
				// if (0 == (riadok + stĺpec) % 2)
				// 	kresliŠtvorec(polomer);

				if (0 != (mapa[riadok][stĺpec] & NAVŠTÍVENÉ))
					hrúbkaČiary(3); else hrúbkaČiary(1);

				if (0 != (mapa[riadok][stĺpec] & CHOĎ_HORE))
				{
					dopredu(2 * polomer);
					odskoč(2 * polomer);
				}

				if (0 != (mapa[riadok][stĺpec] & CHOĎ_VPRAVO))
				{
					posuňVpravo(2 * polomer);
					preskočVľavo(2 * polomer);
				}

				if (0 != (mapa[riadok][stĺpec] & CHOĎ_DOLE))
				{
					odskoč(2 * polomer);
					dopredu(2 * polomer);
				}

				if (0 != (mapa[riadok][stĺpec] & CHOĎ_VĽAVO))
				{
					preskočVľavo(2 * polomer);
					posuňVpravo(2 * polomer);
				}

				hrúbkaČiary(hč);


				if (0 == (mapa[riadok][stĺpec] & VŠADE))
				{
					vyplňŠtvorec(polomer);
				}
				else
				{
					if (0 == (mapa[riadok][stĺpec] & HORE))
					{
						skoč(polomer - hrúbka);
						vyplňObdĺžnik(polomer, hrúbka);
						odskoč(polomer - hrúbka);
					}

					if (0 == (mapa[riadok][stĺpec] & VPRAVO))
					{
						preskočVpravo(polomer - hrúbka);
						vyplňObdĺžnik(hrúbka, polomer);
						preskočVľavo(polomer - hrúbka);
					}

					if (0 == (mapa[riadok][stĺpec] & DOLE))
					{
						odskoč(polomer - hrúbka);
						vyplňObdĺžnik(polomer, hrúbka);
						skoč(polomer - hrúbka);
					}

					if (0 == (mapa[riadok][stĺpec] & VĽAVO))
					{
						preskočVľavo(polomer - hrúbka);
						vyplňObdĺžnik(hrúbka, polomer);
						preskočVpravo(polomer - hrúbka);
					}
				}

				preskočVpravo(polomer * 2);
			}

			preskočVľavo(polomer * 2 * mapa[riadok].length);
			odskoč(polomer * 2);
		}

		skočNa(p);
	}


	// „Virtuálna“ hlavná metóda (na zjednodušenie spúšťania).
	// public static void main(String[] args) { Prieskumník.main(args); }
}