bildung von abgeschlossenen räumen verhindern? (labyrinth)

[pixartist]

hiermit baue ich eine art labyrinth:

for(int j = 0; j<20; j++)
			{
				for(int k = 0; k<32; k++)
				{
					if((k == 0 || j == 0 || j == 19 || k == 31) && fieldArray[k][j] == 0)
					{
						fieldArray[k][j] = 1;
					}
				}
			}

			while(i<100)
			{
				int r1 = rand()%32;
				int r2 = rand()%20;
				if(fieldArray[r1][r2] == 0 && (r1 != 1 || r2 != 1) && (r1 != 30 || r2 != 18))
				{
					i++;
					fieldArray[r1][r2] = 1;
				}
			}

umringt von steinen und innen drin 100 stck zufällig verteilt...wie kann ich nun die bildung von abgeschlossenen räumen bei der zufälligen plazierung verhindern?

[TGGC]

Für jedes Feld teste: befindet es sich in abgeschlossenen Raum?
Ja, dann lösche ein Teil der Umrandung.
Zurück zum Start.

Bye, TGGC

[Windalf]

Du kannst dir auch überlegen deinen algorithmus so zu basteln das gar nicht erst entstehen... z.b. indem du dein lab immer mit einer mauer aufteilst (zufällig senkrechte oder waagerechte mauer mit einem durchgang) und dann mit den unterlaubs die dabei entsehen weitermachst so lange bis du keine mauern mehr ziehen kannst...

[pixartist]

TGGC schrieb:

Für jedes Feld teste: befindet es sich in abgeschlossenen Raum?
Ja, dann lösche ein Teil der Umrandung.
Zurück zum Start.

Bye, TGGC

ja ne ich meine nicht ein feld von 4 umrandet, sondern auch grössere räume...
sprich...der spieler muss jedes freie feld auf dem spielfeld erreichen können

[dali]

pixartist schrieb:

ja ne ich meine nicht ein feld von 4 umrandet, sondern auch grössere räume...
sprich...der spieler muss jedes freie feld auf dem spielfeld erreichen können

Wie kommst du denn auf 4???

[pixartist]

dali schrieb:

pixartist schrieb:

ja ne ich meine nicht ein feld von 4 umrandet, sondern auch grössere räume...
sprich...der spieler muss jedes freie feld auf dem spielfeld erreichen können

Wie kommst du denn auf 4???

naja wenn ein feld auf einer gerasterten fläche ganz umschlossen wird, dann sind dazu mind. 4 steine notwendig, oben, unten, links und rechts einer

[TGGC]

Und?

Bye, TGGC

[Apollon]

Man kann jetzt natuerlich mit Kanonen auf Spatzen schiessen und daraus ein Graphen bauen.
Dann musst Du nur noch dafuer sorgen, dass dein Graph keine Zyklen hat.

[pixartist]

Windalf schrieb:

Du kannst dir auch überlegen deinen algorithmus so zu basteln das gar nicht erst entstehen... z.b. indem du dein lab immer mit einer mauer aufteilst (zufällig senkrechte oder waagerechte mauer mit einem durchgang) und dann mit den unterlaubs die dabei entsehen weitermachst so lange bis du keine mauern mehr ziehen kannst...

oh deinen post hab ich übersehen, danke das is ne gute idee

[Cpp_Junky]

Ich würde einen Füllalgorithmus ausführen und auf dem (hoffentlich ) freien Startfeld anfangen. Wenn der Algo fertig ist gehst du alle Felder durch und prüfst, ob sie "gefüllt" sind. In den ungefüllten Bereichen musst du dich dann nur noch irgendwie am "Rand" entlanghangeln (Ok, das ist vielleicht der schwierigste Part) und löscht hier und da eine Begrenzung und führst den Füllalgo nochmal aus. Könnte funktionieren. Aber schneller ist es wohl, das Labyrinth so zu erzeugen das gar keine geschlossenen Räume entstehen können.
Vielleicht findest du auf www.aiguru.com was dazu.

[DocJunioR]

nimm doch einfach nen Feld voller Wände und setz irgendwo ein Stück freies Feld.
Dann setzt zufällig die 4 Richtungen (N,S,E,W) auch frei , oder eben nicht. Eventuell kannst du hier auch zufällig ne Wandlänge (ergo zwischen 0=Kein Gang und 5=langer Gang) angeben. Am Ende eines solchen Ganges führst du das Ganze dann erneut durch.

Die Wahrscheinlichkeit und die Anzahl der Schritte muss dann halt so gewählt werden, daß ein schönes Labyrinth entsteht. Das muß man dann ausprobieren.

Den Zielpunkt setzt du dann zufällig an einer Wand.