"Tangled"-Spiel Lösbare Level Automatisch erstelle

Übersicht

BlitzMax, BlitzMax NG

Allgemein

	M0rgenstern Betreff: "Tangled"-Spiel Lösbare Level Automatisch erstelle	Sa, Jun 09, 2012 11:40 Antworten mit Zitat
Hallo Leute. Ich bin gerade dabei ein "Tangled" Spiel zu programmieren. Damit meine ich sowas: http://www.addictinggames.com/...tangle.jsp Ich habe zwar schon einen Editor geschrieben, würde aber gerne die Möglichkeit haben einen Endlosspielmodus anzubieten, in welchem einfach immer schwierigere Level generiert werden. Meine momentaner Ansatz sieht so aus: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Function RandomLevel:TLevel(piDifficulty:Int) Local level:TLevel = TLevel.Create() If(piDifficulty <= 1) Then piDifficulty = 2 'Anzahl der Ecken und Verbindungen per Zufall bestimmen. Die Anzahl der Verbindungen ist Abhängig 'von der Anzahl der Ecken. Local iAmountCorners:Int = 1 + Rand(piDifficulty - piDifficulty / 2, piDifficulty + piDifficulty / 2) Local iAmountConnections:Int = Rand(iAmountCorners - iAmountCorners / 2, iAmountCorners + iAmountCorners / 2) 'Ecken erstellen. Dafür eine zufällige Position wählen. For Local index:Int = 0 Until iAmountCorners level.AllCorners().AddLast(TCorner.Create(TVector2D.Create(Rand(20, TGlobalValues.GraphicsVector.X() - 20), Rand(20, TGlobalValues.GraphicsVector.Y() - 20)))) Next 'Verbindungen erstellen. 'Dafür für jede Verbindung zwei Ecken zufällig auswählen. For Local index:Int = 0 Until iAmountConnections Local iCorn1:Int, iCorn2:Int, tcCorn1:TCorner, tcCorn2:TCorner Repeat iCorn1 = Rand(0, level.AllCorners().Count() - 1) iCorn2 = Rand(0, level.AllCorners().Count() - 1) Until iCorn1 <> iCorn2 tcCorn1 = TCorner(level.AllCorners().ValueAtIndex(iCorn1)) tcCorn2 = TCorner(level.AllCorners().ValueAtIndex(iCorn2)) level.AllConnections().AddLast(TConnection.Create(tcCorn1, tcCorn2)) Next 'Ecken, die in keiner Verbindung enthalten sind werden entfernt. level.RemoveUnconnectedCorners() Return level End Function Das Problem ist nur: So werden, gerade in höheren Schwierigkeitsgraden, die Level gerne mal unlösbar. Den PC das Level vorher lösen zu lassen mag zwar verlockend klingen, aber dann kommt man ungefähr bei dem n-Damen Problem heraus. Das heißt, dass, wenn der PC eine Lösung errechnet, es ziemlich lange dauern wird, bis er eine hat, falls es eine gibt. Deshalb wollte ich mal hier nachfragen ob jemand vielleicht nen Ansatz für mich hätte, wie man das ganze veranstalten könnte, dass es nur lösbare Level produziert, bzw. ob es überhaupt möglich ist, das so zu programmieren. Lg, M0rgenstern

M0rgenstern

Betreff: "Tangled"-Spiel Lösbare Level Automatisch erstelle

Sa, Jun 09, 2012 11:40
Antworten mit Zitat

Hallo Leute.
Ich bin gerade dabei ein "Tangled" Spiel zu programmieren.
Damit meine ich sowas: http://www.addictinggames.com/...tangle.jsp

Ich habe zwar schon einen Editor geschrieben, würde aber gerne die Möglichkeit haben einen Endlosspielmodus anzubieten, in welchem einfach immer schwierigere Level generiert werden.

Meine momentaner Ansatz sieht so aus:
BlitzMax: [AUSKLAPPEN]

Function RandomLevel:TLevel(piDifficulty:Int)
		Local level:TLevel = TLevel.Create()
		
		If(piDifficulty <= 1) Then piDifficulty = 2
		
                'Anzahl der Ecken und Verbindungen per Zufall bestimmen. Die Anzahl der Verbindungen ist Abhängig
                'von der Anzahl der Ecken.
		Local iAmountCorners:Int = 1 + Rand(piDifficulty - piDifficulty / 2, piDifficulty + piDifficulty / 2)
		Local iAmountConnections:Int = Rand(iAmountCorners - iAmountCorners / 2, iAmountCorners + iAmountCorners / 2)
		
                'Ecken erstellen. Dafür eine zufällige Position wählen.
		For Local index:Int = 0 Until iAmountCorners
			level.AllCorners().AddLast(TCorner.Create(TVector2D.Create(Rand(20, TGlobalValues.GraphicsVector.X() - 20), Rand(20, TGlobalValues.GraphicsVector.Y() - 20))))
		Next
		
                'Verbindungen erstellen.
                'Dafür für jede Verbindung zwei Ecken zufällig auswählen.
		For Local index:Int = 0 Until iAmountConnections
			Local iCorn1:Int, iCorn2:Int, tcCorn1:TCorner, tcCorn2:TCorner
			
			Repeat
				iCorn1 = Rand(0, level.AllCorners().Count() - 1)
				iCorn2 = Rand(0, level.AllCorners().Count() - 1)
			Until iCorn1 <> iCorn2
			
			tcCorn1 = TCorner(level.AllCorners().ValueAtIndex(iCorn1))
			tcCorn2 = TCorner(level.AllCorners().ValueAtIndex(iCorn2))
			
			level.AllConnections().AddLast(TConnection.Create(tcCorn1, tcCorn2))
		Next
		
                'Ecken, die in keiner Verbindung enthalten sind werden entfernt.
		level.RemoveUnconnectedCorners()
		
		Return level
	End Function

Das Problem ist nur: So werden, gerade in höheren Schwierigkeitsgraden, die Level gerne mal unlösbar.
Den PC das Level vorher lösen zu lassen mag zwar verlockend klingen, aber dann kommt man ungefähr bei dem n-Damen Problem heraus. Das heißt, dass, wenn der PC eine Lösung errechnet, es ziemlich lange dauern wird, bis er eine hat, falls es eine gibt.

Deshalb wollte ich mal hier nachfragen ob jemand vielleicht nen Ansatz für mich hätte, wie man das ganze veranstalten könnte, dass es nur lösbare Level produziert, bzw. ob es überhaupt möglich ist, das so zu programmieren.

Lg, M0rgenstern

	Xeres Moderator	Sa, Jun 09, 2012 11:53 Antworten mit Zitat
Ich habe keine direkte Ahnung wie, aber das sieht mir sehr nach einem Graphentheoretischem Problem aus, das sich womöglich lösen lässt. Aber ich würde erst Geometrisch einwandfreie Formen generieren und wenn die Verbindungen klar sind die Punkte zufällig positionieren. Dann gibt es keine unlösbaren Formen. Unregelmäßige Netze sollten dann nicht all zu schwer zu generieren sein.
Win10 Prof.(x64)/Ubuntu 16.04\|CPU 4x3Ghz (Intel i5-4590S)\|RAM 8 GB\|GeForce GTX 960 Wie man Fragen richtig stellt \|\| "Es geht nicht" \|\| Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

Sa, Jun 09, 2012 11:53
Antworten mit Zitat

Ich habe keine direkte Ahnung wie, aber das sieht mir sehr nach einem Graphentheoretischem Problem aus, das sich womöglich lösen lässt.
Aber ich würde erst Geometrisch einwandfreie Formen generieren und wenn die Verbindungen klar sind die Punkte zufällig positionieren. Dann gibt es keine unlösbaren Formen. Unregelmäßige Netze sollten dann nicht all zu schwer zu generieren sein.

Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

	Noobody	Sa, Jun 09, 2012 11:58 Antworten mit Zitat
Achso, du meinst Untangle - bei Tangled fiel mir nur der Disney-Film ein Im Prinzip kannst du ja einfach einen bereits gelösten Levels generieren (d.h. keine Linien schneiden sich) und dann die Punkte in irgendeiner coolen Kurve anordnen, um den zu lösenden Level zu erhalten. Um einen gelösten Level zu generieren, gibt es viele Möglichkeiten - z.B. kannst du Dreiecke als Grundform nehmen, indem du zuerst drei Punkte generierst, um ein Dreieck zu formen, und dann einen Punkt in die Mitte setzt und mit einer zufälligen Anzahl der Eckpunkte verbindest (also 2 oder 3 - 1 wäre ein wenig langweilig...). Dann gehst du rekursiv vor, indem du die jetzt neu geformten Dreiecke bearbeitest, dort einen Mittelpunkt setzt etc. etc., bis du genug Punkte hast Das gibt dann zwar sehr regelmässige Konstrukte, aber da du die Punkte nachher eh wieder neu anordnest, spielt das keine Rolle.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Noobody

Sa, Jun 09, 2012 11:58
Antworten mit Zitat

Achso, du meinst Untangle - bei Tangled fiel mir nur der Disney-Film ein Razz

Im Prinzip kannst du ja einfach einen bereits gelösten Levels generieren (d.h. keine Linien schneiden sich) und dann die Punkte in irgendeiner coolen Kurve anordnen, um den zu lösenden Level zu erhalten.

Um einen gelösten Level zu generieren, gibt es viele Möglichkeiten - z.B. kannst du Dreiecke als Grundform nehmen, indem du zuerst drei Punkte generierst, um ein Dreieck zu formen, und dann einen Punkt in die Mitte setzt und mit einer zufälligen Anzahl der Eckpunkte verbindest (also 2 oder 3 - 1 wäre ein wenig langweilig...). Dann gehst du rekursiv vor, indem du die jetzt neu geformten Dreiecke bearbeitest, dort einen Mittelpunkt setzt etc. etc., bis du genug Punkte hast
Das gibt dann zwar sehr regelmässige Konstrukte, aber da du die Punkte nachher eh wieder neu anordnest, spielt das keine Rolle.

Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

	M0rgenstern	Sa, Jun 09, 2012 15:53 Antworten mit Zitat
Ha. Vielen Dank ihr Beiden. Genau nach soner Lösung habe ich gesucht. Funktioniert auch super. Lg, M0rgenstern

M0rgenstern

Sa, Jun 09, 2012 15:53
Antworten mit Zitat

Ha.

Vielen Dank ihr Beiden.
Genau nach soner Lösung habe ich gesucht.
Funktioniert auch super.

Lg, M0rgenstern

Übersicht

BlitzMax, BlitzMax NG

Allgemein

Nach Oben

BlitzBasic Portal

"Tangled"-Spiel Lösbare Level Automatisch erstelle

M0rgenstern

Betreff: "Tangled"-Spiel Lösbare Level Automatisch erstelle

Xeres

Noobody

M0rgenstern