/*
  hero_quest
  12.12.2021
*/

// Labyrinth ---------------------------------------------------------------------------------------

labyrinTh::labyrinTh(int B,int H,koordinateN SP,koordinateN EP)//(breite, hoehe, startpos, endpos)
{
	breite=B;
	hoehe=H;
	startpos=SP;
	endpos=EP;

	lab_feldliste=NULL;
	lab_feldmenge=breite*hoehe;

	gelaufener_weg=NULL;
	lifo=new weg_liFo;


	Labyrinth_erzeugen(breite,hoehe,startpos,endpos);

#if DEBUG
	printf("Labyrinth gestartet.\n");
#endif
}








#if DEBUG
void labyrinTh::Testausgabe_ascii()
{
	if(lab_feldliste==NULL)
	{
		fprintf(stderr,"\a\nKein Labyrinth vorhanden!\n");
		return;
	}


	for(int y=0;y<hoehe;y++)
	{
		for(int x=0;x<breite;x++)
		{
			char text[L_ASCI_LAENGE]={""};
			switch(lab_feldliste[y*breite+x]->art)
			{
				case L_WAND:
					sprintf(text,"%s",L_ASCI_WAND);
				break;
				case L_WEG:
					sprintf(text,"%s",L_ASCI_WEG);
				break;
				case L_TUER_OFFEN:
					sprintf(text,"%s",L_ASCI_TUER_OFFEN);
				break;
				case L_TUER_ZU:
					sprintf(text,"%s",L_ASCI_TUER_ZU);
				break;
				case L_EINGANG:
					sprintf(text,"%s",L_ASCI_EINGANG);
				break;
				case L_AUSGANG:
					sprintf(text,"%s",L_ASCI_AUSGANG);
				break;
				case L_SCHATZ_GOLD:
					sprintf(text,"%s",L_ASCI_SCHATZ_GOLD);
				break;
				case L_SCHATZ_ITEM:
					sprintf(text,"%s",L_ASCI_SCHATZ_ITEM);
				break;
				case L_SCHLUESSEL:
					sprintf(text,"%s",L_ASCI_SCHLUESSEL);
				break;
				case L_GEGNER:
					sprintf(text,"%s",L_ASCI_GEGNER);
				break;
			}
			printf("%s",text);
		}
		printf("\n");
	}
	printf("\n");
}









void labyrinTh::Testausgabe_sdl(bool MIT_WEG)// (mit Weg)
{
	if(lab_feldliste==NULL)
	{
		fprintf(stderr,"\a\nKein Labyrinth vorhanden!\n");
		return;
	}

	bool weg_zeichnen=false;
	if(gelaufener_weg!=NULL&&MIT_WEG)
	{
		weg_zeichnen=true;
	}


	for(int y=0;y<hoehe;y++)
	{
		for(int x=0;x<breite;x++)
		{
			int kachelnummer=0;
			int feldart=lab_feldliste[y*breite+x]->art;
			int code=lab_feldliste[y*breite+x]->code;
			if(feldart==L_WAND)
				{kachelnummer=0;}
			if(feldart==L_WEG)
				{kachelnummer=1;}
			if(feldart==L_TUER_OFFEN)
				{kachelnummer=2;}
			if(feldart==L_TUER_ZU)
				{kachelnummer=3;}
			if(feldart==L_EINGANG)
				{kachelnummer=4;}
			if(feldart==L_AUSGANG)
				{kachelnummer=5;}
			if(feldart==L_SCHATZ_GOLD)
				{kachelnummer=6;}
			if(feldart==L_SCHATZ_ITEM)
				{kachelnummer=7;}
			if(feldart==L_SCHLUESSEL)
				{kachelnummer=8;}
			if(feldart==L_GEGNER)
				{kachelnummer=9;}

			sge_Blit(kachelbilder_klein[kachelnummer],display,0,0,x*KLEINE_KACHELGROESSE,y*KLEINE_KACHELGROESSE,KLEINE_KACHELGROESSE,KLEINE_KACHELGROESSE);

			if(weg_zeichnen)
			{
				if(*gelaufener_weg[y*breite+x])
				{
					boxColor(display,x*KLEINE_KACHELGROESSE,y*KLEINE_KACHELGROESSE,x*KLEINE_KACHELGROESSE+KLEINE_KACHELGROESSE,y*KLEINE_KACHELGROESSE+KLEINE_KACHELGROESSE,0x00ff0050);
				}
			}

//			if(feldart==L_TUER_ZU||feldart==L_SCHLUESSEL)
			if(code>=0)
			{
				char text[20]={""};
				sprintf(text,"%i",code);
				stringColor(display,x*KLEINE_KACHELGROESSE+5,y*KLEINE_KACHELGROESSE+5,text,0xffffffff);
			}
		}
	}

#if DEBUG
	lifo->Zeichnen();
#endif

	SDL_Flip(display);
}
#endif








/*
void labyrinTh::Zeichnen()
{
	if(lab_feldliste==NULL)
	{
		fprintf(stderr,"\a\nKein Labyrinth vorhanden!\n");
		return;
	}

	for(int y=0;y<hoehe;y++)
	{
		for(int x=0;x<breite;x++)
		{
			int kachelnummer=0;
			int feldart=lab_feldliste[y*breite+x]->art;
			int code=lab_feldliste[y*breite+x]->code;
			if(feldart==L_WAND)
				{kachelnummer=0;}
			if(feldart==L_WEG)
				{kachelnummer=1;}
			if(feldart==L_TUER_OFFEN)
				{kachelnummer=2;}
			if(feldart==L_TUER_ZU)
				{kachelnummer=3;}
			if(feldart==L_EINGANG)
				{kachelnummer=4;}
			if(feldart==L_AUSGANG)
				{kachelnummer=5;}
			if(feldart==L_SCHATZ_GOLD)
				{kachelnummer=6;}
			if(feldart==L_SCHATZ_ITEM)
				{kachelnummer=7;}
			if(feldart==L_SCHLUESSEL)
				{kachelnummer=8;}
			if(feldart==L_GEGNER)
				{kachelnummer=9;}

			sge_Blit(kachelbilder_klein[kachelnummer],display,0,0,x*KLEINE_KACHELGROESSE,y*KLEINE_KACHELGROESSE,KLEINE_KACHELGROESSE,KLEINE_KACHELGROESSE);
		}
	}
}
*/








void labyrinTh::Labyrinth_erzeugen(int B,int H,koordinateN SP,koordinateN EP)//(breite, hoehe, startpos, endpos)
{
	breite=B;
	hoehe=H;
	startpos=SP;
	endpos=EP;

#if DEBUG
	printf("Labyrinth erzeugen gestartet. (Breite=%i, Hoehe=%i, Eing.=%ix%i, Ausg.=%ix%i)\n",breite,hoehe,startpos.x,startpos.y,endpos.x,endpos.y);
#endif

// Wenn bereits ein Labyrinth existiert, dann erst loeschen.
	if(lab_feldliste!=NULL){Labyrinth_loeschen();}

// Array erzeugen --------------------------------------------------------------
	lab_feldmenge=breite*hoehe;

	lab_feldliste=(lab_felD**)calloc(lab_feldmenge,sizeof(lab_felD*));
	if(lab_feldliste==NULL)
	{
		fprintf(stderr,"\a\nKonnte keinen Speicher fuer das Array bekommen!\n");
		return;
	}

	for(int z=0;z<lab_feldmenge;z++)
	{
		lab_feldliste[z]=new lab_felD;
		lab_feldliste[z]->art=L_WEG;
		lab_feldliste[z]->code=-1;
	}


// Labyrinth erzeugen ----------------------------------------------------------
// Erzeuge Aussenwand
	for(int x=0;x<breite;x++)
	{
		lab_feldliste[x]->art=L_WAND;
		lab_feldliste[(hoehe-1)*breite+x]->art=L_WAND;
	}
	for(int y=0;y<hoehe;y++)
	{
		lab_feldliste[y*breite]->art=L_WAND;
		lab_feldliste[y*breite+(breite-1)]->art=L_WAND;
	}

// Ein-/Ausgang hinzufuegen ----------------------------------------------------
// Sind Ein-/Ausgaenge korrekt?
	bool sok=false;
	bool eok=false;
	if(startpos.x==0||startpos.x==breite-1)
	{
		if(startpos.y>0&&startpos.y<hoehe)
		{sok=true;}
	}
	else if(startpos.y==0||startpos.y==hoehe-1)
	{
		if(startpos.x>0&&startpos.x<breite)
		{sok=true;}
	}

	if(endpos.x==0||endpos.x==breite-1)
	{
		if(endpos.y>0&&endpos.y<hoehe)
		{eok=true;}
	}
	else if(endpos.y==0||endpos.y==hoehe-1)
	{
		if(endpos.x>0&&endpos.x<breite)
		{eok=true;}
	}

	if(!sok)
	{fprintf(stderr,"\a\nStartpos (%ix%i) ist fehlerhaft!\n",startpos.x,startpos.y);return;}
	if(!eok)
	{fprintf(stderr,"\a\nEndpos (%ix%i) ist fehlerhaft!\n",endpos.x,endpos.y);return;}


	lab_feldliste[startpos.y*breite+startpos.x]->art=L_EINGANG;
	lab_feldliste[endpos.y*breite+endpos.x]->art=L_AUSGANG;


// Raeume hinzufuegen 1 ("Raumsamen" setzen) -----------------------------------
	int anzahl_raumsamen=rand()%6+2;
	for(int rs=0;rs<anzahl_raumsamen;rs++)
	{
		int zx=rand()%(breite-6)+3;
		int zy=rand()%(hoehe-6)+3;
		lab_feldliste[zy*breite+zx]->art=L_WAND;
		lab_feldliste[zy*breite+zx]->code=0;
	}


// Startwaende hinzufuegen -----------------------------------------------------
	int startwaende=rand()%10+4;
	for(int sw=0;sw<startwaende;sw++)
	{
		bool ok=false;
		while(!ok)
		{
// Zufallsposition
			int zx=rand()%(breite-2)+1;
			int zy=rand()%(hoehe-2)+1;

// Ist Position am Rand?
			if(zy==1||zy==hoehe-2)
			{
				ok=true;
			}
			else if(zx==1||zx==breite-2)
			{
				ok=true;
			}

// Ist Position vor einem Ein-/Ausgang?
			if(ok)
			{
				if(lab_feldliste[(zy-1)*breite+zx]->art==L_EINGANG||
					 lab_feldliste[(zy+1)*breite+zx]->art==L_EINGANG||
					 lab_feldliste[zy*breite+zx-1]->art==L_EINGANG||
					 lab_feldliste[zy*breite+zx+1]->art==L_EINGANG||
					 lab_feldliste[(zy-1)*breite+zx]->art==L_AUSGANG||
					 lab_feldliste[(zy+1)*breite+zx]->art==L_AUSGANG||
					 lab_feldliste[zy*breite+zx-1]->art==L_AUSGANG||
					 lab_feldliste[zy*breite+zx+1]->art==L_AUSGANG)
				{
					ok=false;
				}
			}

// Ist hier noch keine Startwand? Dann Wand setzen
			if(ok)
			{
				if(lab_feldliste[zy*breite+zx]->art!=L_WAND)
				{
					lab_feldliste[zy*breite+zx]->art=L_WAND;
				}
				else
				{
					ok=false;
				}
			}
		}
	}



// Zufaellig Waende hinzufuegen, die eine Wand beruehren -----------------------
	int testmenge=0;
	int durchlaeufe=0;
	int gesetzte_waende=breite*2+hoehe*2-4;
	while(testmenge<1000000)
	{
		durchlaeufe++;

// Zufallsposition
		int zx=rand()%(breite-1)+1;
		int zy=rand()%(hoehe-1)+1;

// Auf gueltigkeit pruefen
		if(zy*breite+zx<lab_feldmenge)
		{
			if(lab_feldliste[zy*breite+zx]->art!=L_WAND)
			{
				testmenge++;

				int angrenzungen=0;
				bool raumsamen=false;
				for(int y=-1;y<2;y++)
				{
					for(int x=-1;x<2;x++)
					{
						int pos=(zy+y)*breite+zx+x;
						if(pos>0&&pos<lab_feldmenge-1)
						{
							if(lab_feldliste[pos]->art==L_WAND)
								{angrenzungen++;}
							if(lab_feldliste[pos]->code!=-1)
								{raumsamen=true;}
						}
					}
				}

// Wand setzen
//				if(angrenzungen<=2&&angrenzungen>=1)
				if(angrenzungen==1&&!raumsamen)
				{
					lab_feldliste[zy*breite+zx]->art=L_WAND;
					gesetzte_waende++;
				}
			}
		}

//		printf("\e[%iA",hoehe+2);
//		Testausgabe_ascii();
//		Testausgabe_sdl();
//		printf("z=%3ix%3i, TM=%i, GW=%i, DL=%i, SW=%i \n",zx,zy,testmenge,gesetzte_waende,durchlaeufe,startwaende);
//		if(Auf_tastendruck_warten(5)){printf("Abbruch!\n");break;}// (millisekunden) Gibt "Taste gedrueckt" zurueck
	}



// Raeume hinzufuegen 2 ("Raumsamen" entfernen) --------------------------------
	for(int z=0;z<lab_feldmenge;z++)
	{
		if(lab_feldliste[z]->code==0)
		{
			lab_feldliste[z]->code=-1;
			lab_feldliste[z]->art=L_WEG;
//			lab_feldliste[z]->art=L_GEGNER;
		}
	}




// Tueren verteilen ------------------------------------------------------------
	int tuermenge=rand()%6+4;
	int tatsaechlich_gesetzte_tueren=0;
	int tatsaechlich_gesetzte_schluessel=0;
	for(int tm=0;tm<tuermenge;tm++)
	{
// Tuere setzen
#if DEBUG
		printf("Suche Platz fuer Tuere #%i...\n",tm);
#endif
// Leere Stellen mit 2 gegenueberliegenden Waenden suchen
		bool tuerplatz_gefunden=false;
		int sicherheitsbegrenzer=1000000;
		while(sicherheitsbegrenzer>0)
		{
// Zufallsposition
			int zx=rand()%(breite-1)+1;
			int zy=rand()%(hoehe-1)+1;
// Gueltiges Feld?
			int feld=zy*breite+zx;
			if(feld>=0&&feld<lab_feldmenge-1)
			{
// Leere Stelle?
				if(lab_feldliste[feld]->art==L_WEG)
				{
// Links und rechts eine Wand?
					if(zx+1<breite-2&&zx-1>=1)
					{
						if(lab_feldliste[feld+1]->art==L_WAND&&lab_feldliste[feld-1]->art==L_WAND)
						{
// Oben und unten frei?
							if(zy+1<hoehe-2&&zy-1>=1)
							{
								if(lab_feldliste[feld+breite]->art==L_WEG&&lab_feldliste[feld-breite]->art==L_WEG)
								{
// Platz fuer Tuere gefunden. Tuere einbauen
#if DEBUG
									printf("Platz fuer Tuere #%i gefunden. (%ix%i)\n",tm,zx,zy);
#endif
									lab_feldliste[feld]->art=L_TUER_ZU;
									lab_feldliste[feld]->code=tm;
									tuerplatz_gefunden=true;
								}
							}
						}
					}
				}
			}

			if(tuerplatz_gefunden){break;}

			sicherheitsbegrenzer--;
		}

// Schluessel verstecken -------------------------------------------------------
		if(tuerplatz_gefunden)
		{
			tatsaechlich_gesetzte_tueren++;

// Schluessel plazieren
#if DEBUG
			printf("Suche Platz fuer Schluessel #%i...\n",tm);
#endif

			Weg_ablaeufer();

			bool schluesselplatz_gefunden=false;
			int notabschaltung=1000000;
			while(notabschaltung>0)
			{
// Zufallsposition
				int zx=rand()%(breite-1)+1;
				int zy=rand()%(hoehe-1)+1;
				int feld=zy*breite+zx;

				if(*gelaufener_weg[feld])
				{
#if DEBUG
					printf("Platz fuer Schluessel #%i gefunden. (%ix%i)\n",tm,zx,zy);
#endif
					lab_feldliste[feld]->art=L_SCHLUESSEL;
					lab_feldliste[feld]->code=tm;
					schluesselplatz_gefunden=true;
					tatsaechlich_gesetzte_schluessel++;
					break;
				}

				notabschaltung--;
			}

			if(!schluesselplatz_gefunden)
			{
#if DEBUG
				printf("\a\nPlatz fuer Schluessel %i nicht gefunden!",tm);
#endif
				return;
			}


		}
		else
		{
#if DEBUG
			printf("\a\nPlatz fuer Tuere %i nicht gefunden!",tm);
#endif
			return;
		}
	}






// Fertig ----------------------------------------------------------------------
	if(tatsaechlich_gesetzte_tueren!=tatsaechlich_gesetzte_schluessel)
	{
		fprintf(stderr,"\a\nAchtung! Labyrinth ist fehlerhaft! (#%i Tueren und #%i Schloesser)\n",tatsaechlich_gesetzte_tueren,tatsaechlich_gesetzte_schluessel);
	}


#if DEBUG
	printf("Labyrinth erzeugen beendet.\n");
	printf("Gesetzte Waende=%i, Startwaende=%i, Raeume=%i, Tueren=%i, Schluessel=%i\n",gesetzte_waende,startwaende,anzahl_raumsamen,tatsaechlich_gesetzte_tueren,tatsaechlich_gesetzte_schluessel);
//	Testausgabe_ascii();
	Testausgabe_sdl(false);
#endif
}









void labyrinTh::Weg_ablaeufer()
{
	if(gelaufener_weg!=NULL)
	{
		for(int z=0;z<lab_feldmenge;z++)
		{
			delete(gelaufener_weg[z]);
		}
		free(gelaufener_weg);
		gelaufener_weg=NULL;
	}


// Weglisten anlegen
	gelaufener_weg=(bool**)calloc(lab_feldmenge,sizeof(bool*));
	if(gelaufener_weg==NULL)
	{
		fprintf(stderr,"\a\nKonnte keinen Speicher fuer das Array >gelaufener_weg< bekommen!\n");
		return;
	}

	for(int z=0;z<lab_feldmenge;z++)
	{
		gelaufener_weg[z]=new bool;
		*gelaufener_weg[z]=false;
	}


// Loslaufen
	koordinateN pos=startpos;

	bool erledigt=false;
	*gelaufener_weg[pos.y*breite+pos.x]=true;
	lifo->Ablegen(pos);

#if WEG_DEBUG
	printf("Suche Weg... Startpos=%ix%i\n",pos.x,pos.y);
#endif

	while(!erledigt)
	{
// Weiterlaufen
		int neupos=0;
		bool gelaufen=false;

		for(int richtung=0;richtung<4;richtung++)
		{
// Richtung festlegen
			switch(richtung)
			{
				case 0:// nach oben
					neupos=(pos.y-1)*breite+pos.x;
#if WEG_DEBUG
					printf("Nach oben...\n");
#endif
				break;
				case 1:// nach rechts
					neupos=pos.y*breite+pos.x+1;
#if WEG_DEBUG
					printf("Nach rechts...\n");
#endif
				break;
				case 2:// nach unten
					neupos=(pos.y+1)*breite+pos.x;
#if WEG_DEBUG
					printf("Nach unten...\n");
#endif
				break;
				case 3:// nach links
					neupos=pos.y*breite+pos.x-1;
#if WEG_DEBUG
					printf("Nach links...\n");
#endif
				break;
			}

// Ist die Position gueltig?
			if(neupos>=0&&neupos<lab_feldmenge)
			{
// Ist das Feld frei und wurde noch nicht betreten?
				if((lab_feldliste[neupos]->art==L_WEG||lab_feldliste[neupos]->art==L_SCHLUESSEL)&&!*gelaufener_weg[neupos])
				{
// Neues Feld Feld betreten
					lifo->Ablegen(pos);
					pos.y=neupos/breite;
					pos.x=neupos-pos.y*breite;
					*gelaufener_weg[neupos]=true;
					lifo->Ablegen(pos);
					gelaufen=true;
#if WEG_DEBUG
					printf("OK. Neue Position=%ix%i\n",pos.x,pos.y);
#endif
					break;
				}
			}
#if WEG_DEBUG
			else
			{
				printf("Position ist ungueltig! (%ix%i)\n",pos.x,pos.y);
			}
#endif
		}

// Weg zuruecklaufen
		if(!gelaufen)
		{
#if WEG_DEBUG
			printf("Sackgasse. (%ix%i) Zurueck gehen.\n",pos.x,pos.y);
#endif
			pos=lifo->Abfragen(&erledigt);
		}


#if WEG_DEBUG
		Testausgabe_sdl(true);
#endif
	}


#if DEBUG
	printf("Weg vor Tuere gefunden.\n");
#endif
}









void labyrinTh::Labyrinth_loeschen()
{
	for(int z=0;z<lab_feldmenge;z++)
	{
		delete(lab_feldliste[z]);
	}
	lab_feldliste=NULL;

#if DEBUG
	printf("Vorhandenes Labyrinth geloescht.\n");
#endif
}









void labyrinTh::Ende()
{
	Labyrinth_loeschen();

	if(gelaufener_weg!=NULL)
	{
		for(int z=0;z<lab_feldmenge;z++)
		{
			delete(gelaufener_weg[z]);
		}
		free(gelaufener_weg);
	}

	delete(lifo);

#if DEBUG
	printf("Labyrinth beendet.\n");
#endif
}









// Weg-LIFO ----------------------------------------------------------------------------------------

weg_liFo::weg_liFo()
{
	stapel=NULL;
	stapellaenge=0;

#if DEBUG
	printf("Weg-LIFO gestartet...\n");
#endif
}









void weg_liFo::Ablegen(koordinateN K)// (betretenes Feld)
{
	if(stapel!=NULL)
	{
		if(stapel[stapellaenge-1]->x==K.x&&stapel[stapellaenge-1]->y==K.y)
		{
#if LIFO_DEBUG
			printf("Koordinaten (%i,%i) sind schon abgelegt bei #%i.\n",stapel[stapellaenge-1]->x,stapel[stapellaenge-1]->y,stapellaenge);
#endif
			return;
		}
	}

	stapel=(koordinateN**)realloc(stapel,(stapellaenge+1)*sizeof(koordinateN*));
	stapel[stapellaenge]=new koordinateN;
	*stapel[stapellaenge]=K;
	stapellaenge++;

#if LIFO_DEBUG
	printf("#%i Koordinaten (%i,%i) in Weg-LIFO abgelegt.\n",stapellaenge,stapel[stapellaenge-1]->x,stapel[stapellaenge-1]->y);
#endif
}









koordinateN weg_liFo::Abfragen(bool* SL)// (Wird auf true gesetzt, wenn Stapel leer.) Gibt zuletzt abgelegte Koordinaten zurueck.
{
	koordinateN merker={-1,-1};

	if(stapellaenge<1)
	{
		*SL=true;

#if LIFO_DEBUG
		printf("Weg-LIFO ist leer!\n");
#endif
		return(merker);
	}

	stapellaenge--;
	merker=*stapel[stapellaenge];
	delete(stapel[stapellaenge]);
	stapel=(koordinateN**)realloc(stapel,(stapellaenge)*sizeof(koordinateN*));

#if LIFO_DEBUG
	printf("#%i Koordinaten (%i,%i) aus Weg-LIFO abgefragt. Stapellaenge=",stapellaenge+1,merker.x,merker.y);
#endif

	*SL=false;
	if(stapellaenge==0)
	{
		*SL=true;
		stapel=NULL;

#if LIFO_DEBUG
		printf("leer!\n");
#endif
	}
#if LIFO_DEBUG
	else
	{
		printf("%i.\n",stapellaenge);
	}
#endif

	return(merker);
}









#if DEBUG
void weg_liFo::Zeichnen()
{
	if(stapel!=NULL)
	{
		for(int p=0;p<stapellaenge;p++)
		{
			boxColor(display,stapel[p]->x*KLEINE_KACHELGROESSE,stapel[p]->y*KLEINE_KACHELGROESSE,stapel[p]->x*KLEINE_KACHELGROESSE+KLEINE_KACHELGROESSE,stapel[p]->y*KLEINE_KACHELGROESSE+KLEINE_KACHELGROESSE,0x0000ff50);
		}
	}
}
#endif










void weg_liFo::Ende()
{
	for(int z=0;z<stapellaenge;z++)
	{
		delete(stapel[z]);
	}
	free(stapel);

#if LIFO_DEBUG
	printf("Weg-LIFO beendet.\n");
#endif
}