Průchod bludištěm – Pascal – Fórum – Programujte.com

Zdravim. Vytvořil jsem bludiště a snažím se napsat algoritmus na hledání nejkratší cesty. Už jsem očísloval jednotlivá políčka, ale nějak jsem se zasekl na hledání cesty z konečného bodu do začátku. Potřebuji jen trochu nakopnout, vím že to je zcela triviální věc.

Pro začátek něco jednoduchého:
1) Každé políčko má svoje ID
2) Každé políčko může obsahovat hodnotu
3) Nastav všem políčkům hodnotu na -1 (nějakou mimo rozsah ID)
4) Nastav startovnímu políčku jako hodnotu jeho ID
5) Procházej cyklem pořád celé bludiště, dokud se nezmění hodnota koncového políčka
6) Pokud narazíš na políčko, které nemá hodnotu -1, nastav políčkům kolem něj jako hodnotu jeho ID, ale jenom pokud mají hodnotu -1 ... a samozřejmě pokud to není "překážka" ale "cesta"
7) Nejkratší cesta pak je seznam hodnot políček od cíle. (Hodnota cíle je ID předešlého pole apod.)

Je v tom jeden malý zádrhel. Pokud to má vždy najít nejkratší cestu, musíš při každém průchodu bludištěm (od začátku do konce) zapisovat hodnoty (v kroku 6) do "nového" bludiště a ty pak po dokončení průchodu bludištěm zase nakopírovat do originálu.

Kdybys to z mojeho výkladu nepochopil (což bych se ti ani nedivil :))) ) tak napiš, skusím to nějak narychlo napsat v mateřském jazyce... (takovém, kterému rozumí počítač :p) a popsat kód. Jinak na wikině hledej něco jako hledání do šířky.

To Foowie :

Co to je ta hodnota?

OK, zvládl jsem to po bod 7. Přes ten se né a né dostat. Můžeš to prosím napsat v mateřském jazyku (doufám, že to nebudou jedničky a nuly :smile5: ).

To dejvid16 : To dejvid16 :

Mohu se vás zeptat jaký pascal si mám stáhnout?

Taaak ... K ránu jsem to napsal (takže neručím za 100% funkčnost, ale vypadá to že to jede), ale okomentoval jsem to až teďka. Je to v javě (u pascalu jsem skončil, když jsem nezjistil jak se v metodě defunuje vícerozměrné pole jako parametr), ale snad to z toho nějak pochopíš :)

import java.util.Random;



public class Main {



	final int velikost = 10; // Velikost bludiště



	final char volno = ' '; // Znak pro volnou plochu

	final char zed = '#'; // Znak pro zeď

	final char cesta = '+'; // Znak pro nalezenou cestu

	final char start = 'S'; // Znak pro start

	final char end = 'S'; // Znak pro cíl



	final int neprozkoumano = -1;  // Konstanta pro neprozkoumanou oblast



	protected char[][] bludiste; // Nakreslené bludiště pomocí výše uvedených znaků

	protected int[][] hodnoty; // Pomocné pole s indexem sousedního pole "nejbližšího ke startu"

	protected int endIndex; // index pozice konce



	// Konstruktor, start = pozice startu, end = pozice konce

	public Main(int startX, int startY, int endX, int endY) {

		Random rnd = new Random(); // Vytvořím si generátor náhodných čísel

		bludiste = new char[velikost][]; // "Vytvořím bludiště (1.rozměr)"

		hodnoty = new int[velikost][]; // "Vytvořím matici pomocných hodnot (1.rozměr)"

		for(int i = 0; i < velikost; i++) {

			bludiste[i] = new char[velikost]; // "Vytvořím bludiště (2.rozměr)" pro každý 1. rozměr

			hodnoty[i] = new int[velikost]; // "Vytvořím matici pomocných hodnot (2.rozměr) pro každý 1. rozměr"

			for(int j = 0; j < velikost; j++) { // Pro každé políčko bludiště

				bludiste[i][j] = (rnd.nextInt(3) == 0) ? zed : volno; // Vložím náhodně zeď nebo volné políčko (s poměrem 1:2)

				hodnoty[i][j] = neprozkoumano; // Nastavím do pomocných hodnot, že všechny pole jsou neprozkoumány

			}

		}

		bludiste[startX][startY] = start; // Nastavím do bludiště start

		bludiste[endX][endY] = end; // Nastavím do bludiště konec

		hodnoty[startX][startY] = toIndex(startX, startY); // Do políčka se startem nastavím jeho vlastní index

		endIndex = toIndex(endX, endY); // Uložím si index konce *1

	}



	// Vykreslí bludiště

	public void render() {

		for(int i = 0; i < velikost; i++) { // Cykly pro celou matici

			for(int j = 0; j < velikost; j++)

				System.out.print(bludiste[j][i] + " "); // Vykreslí políčko

			System.out.println(); // Konec čádku, odentruje

		}

	}



	// Převede xovou a yovou souřadnici na index

	public int toIndex(int x, int y) {

		return y * velikost + x;

	}

	// Zjistí z indexu xovou souřadnici

	public int xFromIndex(int index) {

		return index % velikost;

	}

	// Zjistí z indexu yovou souřadnici

	public int yFromIndex(int index) {

		return index / velikost;

	}



	// Projde jednou bludiště a rozšíří matici hodnot, vrátí false pokud cesta neexistuje

	public boolean findStep() {

		int[][] vysledky = new int[velikost][]; // Pomocná matice

		for(int i = 0; i < velikost; i++) { // Vytvoříme pomocnou matici a inicializujeme jí

			vysledky[i] = new int[velikost];

			for(int j = 0; j < velikost; j++)

				vysledky[i][j] = neprozkoumano;

		}



		for(int i = 0; i < velikost; i++) { // Cyklus pro celé bludiště

			for(int j = 0; j < velikost; j++) {

				if( hodnoty[i][j] != neprozkoumano ) { // Pokud dané políčko již bylo někdy prozkoumáno a byla do ní uložena hodnota, rozšiř pole hodnot i do okolí

					for(int k = -1; k <= 1; k++) { // Cyklus pro okolní políčka

						for(int l = -1; l <= 1; l++) {

							if( (i+k >= 0) && (j+l >= 0) && (i+k < velikost) && (j+l < velikost) // Pokud nejsme mimo matici

									&& !(k == 0 && l == 0) // A nejsme na prostředním políčku (ze kterého vycházíme)

									&& hodnoty[i+k][j+l] == neprozkoumano // A toto okolní políčko jetště nebylo prozkoumáno

									&& bludiste[i+k][j+l] != zed // A na tomto okolním políčku není zeď

									&& Math.abs(k) + Math.abs(l) != 2 // Pokud se hledá cesta do 8 stran a né do 4 tak stačí zakomentovat

							)

								vysledky[i+k][j+l] = toIndex(i, j); // Pokud je splněna podmínka, dá se do pomocné matice pozice políčka, které je soused a je nejblíže ke startu

						}

					}

				}

			}

		}

		boolean zmeneno = false; // Nebyla provedena žádná změna, cesta neexistuje

		for(int i = 0; i < velikost; i++) { // Projdeme celou pomocnou matici

			for(int j = 0; j < velikost; j++) {

				if(vysledky[i][j] != neprozkoumano) { // A pokud je v ní nějaká hodnota (políčko bylo prozkoumáno)

					hodnoty[i][j] = vysledky[i][j]; // Zkopírujeme to do hodnot

					zmeneno = true; // Byla provedena změna, cesta může existovat

				}

			}

		}

		return zmeneno; // Vrátím jestli cesta může existovat

	}



	// Nalezne cestu v bludišti

	public void findWay() {

		while( hodnoty[xFromIndex(endIndex)][yFromIndex(endIndex)] == neprozkoumano ) { // Dokud koncové políčko nemá statuc "neprozkoumáno"

			if( !findStep() ) { // Volám metodu na jeden průchod bludištěm, pokud ceta neexistuje, vypíšu to

				System.out.println("Cesta neexistuje !");

				return;

			}

		}

		// Teďka budem zpětně vyznačovat nalezenou cestu

		int index = endIndex; // Aktuální políčko cesty nastavíme na koncový index

		while( true ) { // Infinity loop :p

			int x = xFromIndex(index); // Zjistíme si x a y pozici aktuálního políčka v cestě

			int y = yFromIndex(index);

			if( !(index == endIndex) && !(index == hodnoty[x][y]) ) // Pokud to není start ani cíl

				bludiste[x][y] = cesta; // Vyznačíme v bludišti jako cestu

			if( index == hodnoty[x][y] ) // Pokud další políčko je to samé políčko, dorazili jsme na start. (Toto pole má hodnotu samo sebe díky *1)

				break;

			index = hodnoty[x][y]; // Do aktuálně prozkoumávaného políčka cesty vložíme "předka" aktuálního políčka

		}

	}



	// Zavolá se při spuštění (něco jako begin end.)

    public static void main(String[] args) {

		Main program = new Main(3, 0, 5, 9); // Vytvořím si nový program, s x a y pozicí startu a cíle

		program.findWay(); // Naleznu cestu

		program.render(); // Vykreslím

    }



}

    + S #       #   

    + # #           

  # + + #     #     

#     + + + + # # # 

    #       + + # # 

#   #     #   +     

#   #   # #   + #   

      #     # + #   

        # #   +   # 

    # #   S + + #   







    # S #   #   # # 

# #   + + + + + # # 

  #     # #   + + + 

      #     # # # + 

  # #       #     + 

#       # #     # + 

  #     #         + 

    #   #     # # + 

          # + + + + 

        # S + #     





Cesta neexistuje !

#     S #   #       

        #   #   # # 

#   #     #   #     

#   #         # #   

            # #     

      #             

  # # # #   #   # # 

# #       # # #     

#   #   #         # 

  #     # S         





  #   S + + +       

# #   #     +       

    #       +     # 

  #     # # +     # 

    #     # +       

  #         +       

            + # #   

  # # #     + #     

            +       

#       # S +   # # 





Případně něco většího:



#               #   S + #     #     # #       # # #   #           # #           # # #       # # #   

# #             # # # + # #   #       # #   #         #       #       #     #         #           # 

    #   #     + + + + +         #     #                       #             #         # #         # 

  # #   # + + + # # # #       #       #   # #   #   # #   #   #         #       # # #   #       #   

  #     + + #         #                 #     # #   #         #   #         # #   #       # # #     

  # + + + #   # #   #   # #       #         # # #     # # #       #       #   #   #       #         

# + + # #   #   #     #   #   # # #   # # #     #       #   #   #     #         #     # #         # 

  + #         # #   #       #   # # #   #     #       #                     #     #   #           # 

# + # #     #     #   #     # #         # #     # #         #         #     # #       #   #   #     

  + + + + + + # #   #   + + +   # #       #   # #     #   #   #     # #       # #     #       #     

#     #     + + + + + + + # +     #   #   # # #     #       #           #   #       #       # # #   

    # #         #       # + +             #       #   #   # #       #       # #     #     #         

    # # # #           #   + #       # # #     #   #           #   # # #     # #           #         

#           #   # # #   + +       #       #   #     #     # #     #       #   #         #           

# #   # # #       #   + + #     #   #   #   # # #   #   # # # # #   #     #                       # 

#       #           # + # # # #     #           #   # #     #               #     #     #     # # # 

    # # #     #     # +   #   #         # # #     #   # #       # # #         # #     #             

  #     #         #   +   # #   # #   #     #   #   #   # #     # # #   #             #   # #   #   

# #   #   #   # #     + # # #   #                   # #   #           # # # #   #   #           #   

      # #   # #     # +     #   #   #     #             #         # # # #     #             #       

    #       # #       +         # #   # #       #       #     #     # # # # # # # # #         # #   

#             #       +           #     #       #         # #     #   #         #       #     #     

    # #       # #     + #   #       #       # #   # #     #       #       #   #   # #   #     #     

#     # #     #   #   + #         #       #       # # #   # #     #       #           # # # # # # # 

      #       # # #   +   #           #             #     #     #   #               #   # # # #     

#   #       # #       + #     #   # #         #         #             #   #           #   # #     # 

  # #               # +   # #       #     #   #   #   #   #     # # #         #       # # #         

  #     #             + # # #           # # #               #       # # #       # # #           # # 

    # #     #     # # + # # # #         #   #   #               #         #   #                 #   

    # #   #   #   #   + + + + # #   # #               # # #   #         #   # #           # #     # 

    #       #   #   #       + +           #         #             #   #       # #     # #         # 

                      #     # +               # #   #     # # # #       #         #     #   #   #   

  #       #         #         +   #           #   #   # #                   # #         #     #     

    # # # #         #       # +   # #   # #   # # # # #   # #   #                 # # #   # # #     

          # #       # # # #   +       # # # #     # # #       #       # #   #             #       # 

          #           # + + + + # #   # # # # #             #   #       #     #     #   #       #   

          #       #   # + #     #   #           # #       # #   #   #   #   #         #         #   

        # #       # #   + + # #       # #             # # #   # #     #   # #     # #   # #     # # 

# # # #     #   #   #     + #         #         + + +   #         #         #   #                   

    #                 # # + + + + + + #         + # +   # #   #   # # #     #       #               

              # # #     #   #     # + + + + + + + # + #       #   #             #     #             

  #   #     #                 #   #         # # #   + # # #   #     #     #     # # #     #   #     

# #     #     #           #             #     #     + #         #     #   #   # #           # #   # 

# # # #   #         #       # #       #       # #   + + #   #     #       #     # #   #   #   #   # 

      #     #     # #   #       #       #   # #       + + + +       # #     # #   # #   #           

    #           #   #   #       #       #     # #       #   S                     #   #     # # #   

#       #       #   #     # #               #       #     # # #     # #   #   # # #       #         

# #       #           #       #   # # #       #     #         # #   #       # # # #     # #       # 

#       #             # #     # #       #             #           #   # #     # #     #       #   # 

#   #     # #               #   # # # #   # #       #         #         # #   # #                   

To dejvid16 : Hodnota (proměnná), která obsahuje index na předchozí políčko směrem ke startu. Pokud půjdeš v cyklu po těch hodnotách dostaneš se odkudkoliv nejkratší cestou ke startu.

To dejvid16 : No, stáhni si Delphi http://www.slunecnice.cz/sw/delphi/. Je to IDE s "psacalem"

To Foowie :

Děkuji a mohl bys te mi napsat jak to mám stáhnout? Já to stáhuji a akorád to mohu přehrát

dejvid16 napsal:
To Foowie :

Děkuji a mohl bys te mi napsat jak to mám stáhnout? Já to stáhuji a akorád to mohu přehrát

To Foowie :

Dobrý den skoušel jsem co se dalo ale nějak mi to nejde, neměl byste jinou stránku? Kde bych to mohl ještě stáhnout? Pascal turbo 6.0? Předem děkuji

To dejvid16 : http://www.porse.cz/Turbo_Pascal.html

To Foowie :
Tak už jsem si to stáhl ale nepustí mě to k tomu nějak, mohl byste mi říct jestli to dělám správně?

Když jsem si to stáhl tak jsem dal zip a dal jsem otevřít a potom se mi tam oběvili nějaké sloupečky tak jsem klikl na setup exe a ono mi to napsalo že se nějak operace nezdařila byl tam červený křížek kdyštak používám vistu

Lepší je ten zip rozbalit a spustit tu instalaci z rozbalené složky. Samozřejmě je nutné, abys měl adminovská práva na počítači.

To z_moravec :

No právě já bych to chtěl nainstalovat jenže to nejde právě ona se mi tam zobrazí nějaký červenyý křížek

Kde se ti objeví červený křížek? Zkus psát věty tak, aby to dávalo smysl.

To z_moravec :
Ne vy mi asi nerozumíte já jsem to stáhl a dal jsem otevřít zip a potom se mi zobrazí červený křížek

To je sice pěkné, ale bez věštecké koule to asi nevyřešíme.

Čím ten zip rozbaluješ? Ten setup.exe spouštíš z rozbalené složky nebo např. z winzipu? Kdy se ti objeví ten červený křížek a co znamená (u chybového hlášení bývá většinou i text)?

To z_moravec :

Ono se mi to stáhne že jo tak dám otevřít složku kliknu na otevření složky kliknu pravým na zip a potom se mi tam zobrazí Setup Exe pod tím je psáno _ISDEL.EXE atd

musíš to stáhnuté nejprve extrahovat a potom teprve spustit setup.exe

To crAzY^ :

Také děkuji a mohl byste mě na to trošku navést? Jsem začátečník a nemám stím moc skuností děkuji

To dejvid16 :

A nebo mám na ploše Pascal free ale nevím jestli je to stejné

Pokud mas na plose Freepascal, neni co resit - proste ho spust a programuj :-).
Mam dojem, ze TP ti pod Vistou vubec nepujde, protoze je to DOSovsky program a ty Vista z principu nepodporuje.

To AJRIMMER : Asi uz s tim jdu pozde, ale mozna by se ti mohl hodit tenhle clanek: http://sdraco.ic.cz/index.php?art=algoritmus-sireni-do-sirky-vlna-hledani-cesty-v-bludisti popisujici hledani cesty v bludisti. A bez Javy, jenom v cestine :-).

To Mircosoft :

Dobře už to mám naistalované ten Pascal free a tedka bych jestli bych mohl poprosit o nějaký článek pro začátečníky t pacsaclu free děkuji

To dejvid16 : ide je stejne jako u borlandu...
ja radeji pouzival jen ciste exe pro zkompilovani.. tj fpc.exe kod.pas (musis mit adresar freepascalu v PATH - jinak se musi zadat cela cesta)

To KIIV :
Těďka jsem vás nepochopil :((

To dejvid16 :
no radsi bych se naucil trosku ovladat kompa atd, nez se pustim do programovani..;)

>Dejvid16: Umis spustit IDE (tj. vyvojove prostredi cili editor) Freepascalu? Jestli ne, vyzkousej, ktery EXE to je (pravdepodobne je nekde v podadresari BIN). To je naprosty zaklad.
Uvidis obrazovku v textovem rezimu s velkym cerno-bilo-zelenym ANSI artem "FPC" na pozadi. Nahore je menu File, Edit atd.. Pres File - New si otevres novy soubor. Do nej pises program. File - Save nebo F2 uklada (napoprve se zepta na jmeno souboru, pak uz uklada porad do toho sameho bez ptani), F9 kompiluje (tj. preklada napsany zdrojak do EXE), Ctrl+F9 kompiluje a rovnou spousti.

Zaklad programu vypada takhle:

program Pokus;

BEGIN

END.

To Mircosoft :

Tak už mi free pascal funkuje a tedka mohu normálně do něj psát?

To dejvid16 : Proč se proboha ptáš? Není rychlejší to spustit a vyzkoušet?

OMG, tohle snad ani neni možný, člověk co neumí zapnou ide a chce procházet bludiště. Nechceš poradit nějaký začátečnický tutorialy na doom 3? Ne sorry, taky jsem kdysy začínal, ale sčítáním čísel a ne tímhle :smile12:

To soul_draco : Vážený pane, mohl jste si všimnout, že to nepsala jedna a tatáž osoba. Už jen styl psaní je naprosto odlišný.

To survik1 :

Osoba napsala do tohoto topicu, takže pokud je svéprávná, chce procházet bludiště, také se výše ptá, co znamená hodnota :-)

To soul_draco : Jednodušše nepochopil teoretickou odpověď, na tom nevidím nic špatného. Hlava mi taky občas nebere ani samozřejmosti. A nezapomínejte, že se jedná o dvě různé osoby. Jedna osoba řeší jak procházet bludištěm a druhá jak nainstalovat pascal. V tom vidím podstatný rozdíl ;)