Ez a modul tartalmazza a legrövidebb útvonal megtalálásához szükséges függvényeket. Részletek...

#include <stdlib.h>
#include "utvonalkereso.h"
#include "egyeb.h"
#include "debugmalloc.h"

Függvények
bool **	legrovidebb (Szintek meretek, int *idealis)
	Megkeresi a legrövidebb útat az aktív szinten a rajt és a cél között (a fájl többi függvényének segítségével). Részletek...

static void	graf_epit (Csucs cs, Csucs *vizsgalt, Szintek meretek, int meret)
	Rekurzív függvény, ami felépíti a gráf adatstruktúrát. Részletek...

static void	graf_kilapit (Csucs cs, Csucs *lista, int n, bool **vizsgalt, int hossz)
	Rekurzív függvény, ami csinál egy egydimneziós tömböt a gráfhoz, aminek minden eleme egy csúcsra mutat. Részletek...

static void	dijkstra (Csucs **lista, int meret)
	Függvény, ami megvalósítja a Dijkstra algoritmust a rajt és cél között. Részletek...

static void	laposgraf_szabadit (Csucs ***lista, int meret)
	Felszabadítja a gráf minden csúcsát, majd a tömböt amiben tároltuk őket. Részletek...

static bool	utca_teszt (Pozicio p, Szintek meretek)
	Függvény, ami megvizsálja hogy az adott koordináta a pályán belül van-e és a mező utca-e. Részletek...

static int	utak_szama (Pozicio p, Szintek meretek)
	Függvény, ami meghatározza, hogy az adott koordináták által meghatározott mezőnek hány szomszédja utca. Részletek...

static void	kovi_utca (Pozicio regi, Pozicio uj, Szintek meretek)
	Ha egy mezőnek két szomszédja utca, akkor ez a függvény meghatározza, hogy melyik irányba kell tovább menni, hogy az utcán maradjunk. Részletek...

static Irany	irany_hataroz (Pozicio p)
	Függvény, ami meghatározza, hogy az adott x-y elmozdulással melyik irányba haladunk. Részletek...

static void	csucs_init (Csucs *cs, Pozicio p, Szintek meretek)
	Kezdeti állapotba állít egy csúcsot. Részletek...

static bool	van_nem_latogatott (Csucs **lista, int meret)
	Függvény, ami meghatározza, hogy van-e még meg nem látogatott csúcs a gráfban. Részletek...

static int	legkozelebbi (Csucs **lista, int meret)
	Függvény, ami meghatározza azt a csúcsot, ami még nem volt vizsgálva, és a távolsága a legkisebb a kezdő csúcstól. Részletek...

static bool **	matrix_letrehoz (Csucs *lista, int meret, Szintek meretek, int idealis)
	Létrehoz egy dinamikusan foglalt kétdimenziós tömböt, aminek mérete megegyezik a pálya méretével, és mezői pontosan akkor igazak, ha a gráfban az ideális útvonal a rajt és a cél között átmegy az adott mezőn. Részletek...

Részletes leírás

Ez a modul tartalmazza a legrövidebb útvonal megtalálásához szükséges függvényeket.

Többek között olyan függvények, amik gráfot építenek, alkalmazzák a Dijkstra-algoritmust, és az eredményt egy kétdimenziós tömbbé alakítják, hogy könnyebben lehessen a képernyőre nyomtatni. A főbb függvények algoritmusairól az első fejezetben részletesen is írok.

Függvények dokumentációja

◆ csucs_init()

static void csucs_init	(	Csucs *	cs,
		Pozicio	p,
		Szintek	meretek
	)

static

Kezdeti állapotba állít egy csúcsot.

Pointereit lenullázza, megvizsgálja hogy a rajt vagy esetleg a cél-e. Ha a csúcs nem a rajt, akkor a távolságot egy olyan nagy értékre állítja, amilyen távolságok a gráfban biztos nem lesznek. (A Dijkstra-algoritmus szerint végtelenre kellene állítani, de ilyen lehetőség nincs C-ben)

Paraméterek

cs	A beállítani kíívánt csúcs pointere
p	A csúcs x és y koordinátája Pozíció struktúrában
meretek	Betöltött szintek méretei és tömbje

◆ dijkstra()

static void dijkstra	(	Csucs **	lista,
		int	meret
	)

static

Függvény, ami megvalósítja a Dijkstra algoritmust a rajt és cél között.

(Azaz meghatározza a legrövidebb útat a két pont között.)

Paraméterek

lista	Tömb, aminek minden elem a gráf egyik csúcsára mutat.
meret	Csúcsok száma a gráfba, azaz a tömb mérete.

◆ graf_epit()

static void graf_epit	(	Csucs *	cs,
		Csucs ***	vizsgalt,
		Szintek	meretek,
		int *	meret
	)

static

Rekurzív függvény, ami felépíti a gráf adatstruktúrát.

Az elágazások lesznek a gráf csúcsai, az őket összekötő utcák pedig az élek. Egy futása egy adott csúcsot köt össze szomszédjaival, majd mindegyik szomszédjára meghívja magát. Közben szémolja, hogy összesen hány csúcsot talál.

Paraméterek

cs	Annak a csúcsnak a pointere, amelyiket össze szeretnénk kötni a szomszédaival.
vizsgalt	Kétdimenziós tömb (méretei megegyeznek a szint méreteivel), aminek minden mezője NULL, ha ahhoz a mezőhöz még nem csináltunk csúcsot. Amikor egy új csúcsot készítünk, ebben a tömbben a megfelelő mezőt a csúcs pointerére állítjuk.
meretek	Betöltött szintek méretei és tömbje Az irányok sorrendje megegyezik enum Irany-nyal.
meret	Ebbe a változóba menti a csúcsok számát.

◆ graf_kilapit()

static void graf_kilapit	(	Csucs *	cs,
		Csucs ***	lista,
		int *	n,
		bool **	vizsgalt,
		int	hossz
	)

static

Rekurzív függvény, ami csinál egy egydimneziós tömböt a gráfhoz, aminek minden eleme egy csúcsra mutat.

Ez később segíteni fogja az eligazodást a gráfban.

Paraméterek

cs	Kiinduló csúcs
lista	Az épülő tömb
n	Index, amit a rekurzív függvények mindegyike elér. Számlálja, hogy eddig hány csúcsot tettünk a tömbbe.
vizsgalt	Kétdimenziós tömb, aminek minden mezője pontosan akkor igaz, ha az ahhoz a mezőhöz tartozó csúcs már vizsgálva volt.
hossz	Csúcsok száma a gráfban

◆ irany_hataroz()

static Irany irany_hataroz ( Pozicio p )

static

Függvény, ami meghatározza, hogy az adott x-y elmozdulással melyik irányba haladunk.

A két koordináta közül pontosan egynek 0-nak, egynek pedig 1-nek vagy -1-nek kell lennie. Más x-y párra nem feltétlenül ad helyes eredményt.

Paraméterek

p	Az x és y koordináta Pozíció struktúrában

Visszatérési érték: Az irány enum-ja

◆ kovi_utca()

static void kovi_utca	(	Pozicio *	regi,
		Pozicio *	uj,
		Szintek	meretek
	)

static

Ha egy mezőnek két szomszédja utca, akkor ez a függvény meghatározza, hogy melyik irányba kell tovább menni, hogy az utcán maradjunk.

Paraméterek

regi	Az előző pozíció x és y koordinátája Pozíció struktúrában (erre nem szeretnénk visszamenni)
uj	Meghíváskor a jelenlegi pozíció koordinátái, ami frissítve lesz a következő koordinátákra, úgy hogy az utca maradjon, de ne abba az irányba lépjünk, ahonnan jöttünk.
meretek	Betöltött szintek méretei és tömbje Az irányok sorrendje megegyezik enum Irany-nyal.

◆ laposgraf_szabadit()

static void laposgraf_szabadit	(	Csucs ***	lista,
		int	meret
	)

static

Felszabadítja a gráf minden csúcsát, majd a tömböt amiben tároltuk őket.

Paraméterek

lista	A csúcsok tömbje
meret	A tömb mérete

◆ legkozelebbi()

static int legkozelebbi	(	Csucs **	lista,
		int	meret
	)

static

Függvény, ami meghatározza azt a csúcsot, ami még nem volt vizsgálva, és a távolsága a legkisebb a kezdő csúcstól.

Paraméterek

lista	A gráf csúcsait tartalmazó tömb.
meret	A tömb mérete, azaz csúcsok száma

Visszatérési érték: A megfelelő csúcs indexe a tömbben

◆ legrovidebb()

bool** legrovidebb	(	Szintek	meretek,
		int *	idealis
	)

Megkeresi a legrövidebb útat az aktív szinten a rajt és a cél között (a fájl többi függvényének segítségével).

Minden ilyen segédfüggvényhez elkészíti a szükséges segédtömböket, majd azokat felszabadítja.

Paraméterek

meretek	Betöltött szintek méretei és tömbje
idealis	Ebbe a változó menti a függvény az ideális útvonal hosszát Az irányok sorrendje megegyezik enum Irany-nyal.

Visszatérési érték: Egy olyan kétdimenziós tömb, aminek azon mezői igazak, amin átmegy az ideális útvonal, a többi hamis.

◆ matrix_letrehoz()

static bool** matrix_letrehoz	(	Csucs **	lista,
		int	meret,
		Szintek	meretek,
		int *	idealis
	)

static

Létrehoz egy dinamikusan foglalt kétdimenziós tömböt, aminek mérete megegyezik a pálya méretével, és mezői pontosan akkor igazak, ha a gráfban az ideális útvonal a rajt és a cél között átmegy az adott mezőn.

Paraméterek

lista	A gráf csúcsait tartalmazó tömb.
meret	A tömb mérete, azaz csúcsok száma
meretek	Betöltött szintek méretei és tömbje
idealis	Pointer, ahova a függvény elmenti az ideális útvonal hosszát

Visszatérési érték: A dinamikusan foglalt kétdimenziós bool tömb, amit a hívónak fel kell szabadítania.

◆ utak_szama()

static int utak_szama	(	Pozicio	p,
		Szintek	meretek
	)

static

Függvény, ami meghatározza, hogy az adott koordináták által meghatározott mezőnek hány szomszédja utca.

(Akkor fogunk egy mezőt csúcsnak tekinteni, ha legalább 3 utca szomszédja van). Mivel a rajtot és a célt is csúcsnak szeretnénk tekinteni (hiszen közöttük keressük a legrövidebb utat), náluk automatikusan 3-at fog visszaadni a függvény.

Paraméterek

p	A pont x és y koordinátja Pozíció struktúrában
meretek	Betöltött szintek méretei és tömbje

Visszatérési érték: Szomszédos utca mezők száma

◆ utca_teszt()

static bool utca_teszt	(	Pozicio	p,
		Szintek	meretek
	)

static

Függvény, ami megvizsálja hogy az adott koordináta a pályán belül van-e és a mező utca-e.

Paraméterek

p	A pont x és y koordinátja Pozíció struktúrában
meretek	Betöltött szintek méretei és tömbje

Visszatérési érték: Igaz, ha a koordináták által mutatott mező utca

◆ van_nem_latogatott()

static bool van_nem_latogatott	(	Csucs **	lista,
		int	meret
	)

static

Függvény, ami meghatározza, hogy van-e még meg nem látogatott csúcs a gráfban.

Paraméterek

lista	A gráf csúcsait tartalmazó tömb.
meret	A tömb mérete, azaz csúcsok száma

Visszatérési érték: Igaz, ha van még meg nem látogatott csúcs, egyébként hamis