• Hallo liebe Userinnen und User,

    nach bereits längeren Planungen und Vorbereitungen sind wir nun von vBulletin auf Xenforo umgestiegen. Die Umstellung musste leider aufgrund der Serverprobleme der letzten Tage notgedrungen vorverlegt werden. Das neue Forum ist soweit voll funktionsfähig, allerdings sind noch nicht alle der gewohnten Funktionen vorhanden. Nach Möglichkeit werden wir sie in den nächsten Wochen nachrüsten. Dafür sollte es nun einige der Probleme lösen, die wir in den letzten Tagen, Wochen und Monaten hatten. Auch der Server ist nun potenter als bei unserem alten Hoster, wodurch wir nun langfristig den Tank mit Bytes vollgetankt haben.

    Anfangs mag die neue Boardsoftware etwas ungewohnt sein, aber man findet sich recht schnell ein. Wir wissen, dass ihr alle Gewohnheitstiere seid, aber gebt dem neuen Board eine Chance.
    Sollte etwas der neuen oder auch gewohnten Funktionen unklar sein, könnt ihr den "Wo issn da der Button zu"-Thread im Feedback nutzen. Bugs meldet ihr bitte im Bugtracker, es wird sicher welche geben die uns noch nicht aufgefallen sind. Ich werde das dann versuchen, halbwegs im Startbeitrag übersichtlich zu halten, was an Arbeit noch aussteht.

    Neu ist, dass die Boardsoftware deutlich besser für Mobiltelefone und diverse Endgeräte geeignet ist und nun auch im mobilen Style alle Funktionen verfügbar sind. Am Desktop findet ihr oben rechts sowohl den Umschalter zwischen hellem und dunklem Style. Am Handy ist der Hell-/Dunkelschalter am Ende der Seite. Damit sollte zukünftig jeder sein Board so konfigurieren können, wie es ihm am liebsten ist.


    Die restlichen Funktionen sollten eigentlich soweit wie gewohnt funktionieren. Einfach mal ein wenig damit spielen oder bei Unklarheiten im Thread nachfragen. Viel Spaß im ngb 2.0.

[Aufgabenstellung] Programmierwettbewerb Nr. 5

Brother John

(schein)heilig
Veteran

Registriert
1 Aug. 2013
Beiträge
235
@KaPiTN
Danke für den Einblick! Du bist definitv in die Richtung der effizienteren Standardalgorithmen marschiert. Ich habs noch nicht wirklich verstanden, wann genau du Wege zwischen den Zellen gräbst. Gäbst du überhaupt? Oder baust du Wände? Das Ergebnis schaut jedenfalls echt gut aus. Vom Bauchgefühl her müssten deine Labyrinthe perfect sein. Ich bin jedenfalls nach ein bisschen Rumprobieren mit zwei beliebigen Punkten aus deinem letzten Bild nie steckengeblieben. :T


Ich hab auch weitergebastelt und kann jetzt den Algo über die GUI konfigurieren, das Labyrinth lösen und die Lösung malen.

Bild zur Sicherheit im Spoiler, weil man die Algo-Konfig-GUI sieht. Ohne den Algo gut zu kennen sollte das aber nichts Wichtiges verraten.

Und wer genauer spicken will:
Repo: https://gitlab.com/be-sc/maze
Doku: https://here-be-braces.com/maze/

Mit der Konfig kann man ziemlich wilde Effekte erzeugen, wenn man sie wild einstellt. Sehr fein! Ich bin dann mal weg, Spielzeug ausleben! :p
 

KaPiTN

♪♪♫ wild at heart ♪♫♫♪

Registriert
14 Juli 2013
Beiträge
29.138
@Brother John:

Alle Wände haben am Anfang 4 Wände. Immer dann, wenn ich zufällig eine Zelle aus der Liste der umliegenden ausgesucht habe, füge ich sie in die Liste der Labyrinthzellen hinzu und lösche die Wand.
 

Rakorium-M

NGBler

Registriert
14 Juli 2013
Beiträge
413
Urlaub ist vorbei, hiermit reiche ich meine Lösung ein.

Maze Generator by Rakorium



Source Code: Anhang anzeigen maze-generator-source.zip
Download Konsolen-Version: Anhang anzeigen maze-cli.windows.zip | Anhang anzeigen maze-cli.linux.tar.xz | Anhang anzeigen maze-cli.darwin.tar.xz
Download GUI-Version: maze-gui-linux.tar.xz | maze-gui-windows.zip

Geschrieben in 600 Zeilen Go, mit QT5 als GUI-Framework. Die generierten Labyrinthe sind garantiert eindeutig lösbar, und alle Felder sind erreichbar. Optional kann das Labyrinth gelöst werden, und in gelöster oder ungelöster Form als Bild exportiert werden.

Mein Algorithmus:
Die Grundidee für meinen Algorithmus ist eine Graph-Repräsentation eines Labyrinths. Die Felder sind Knoten, die Kanten dazwischen repräsentieren einen Gang / eine Mauer dazwischen. Eine Kante kann also entweder gesetzt sein (man kann von einem Knoten zum anderen gehen) oder nicht (eine Mauer ist dazwischen). Initial hab ich ein Feld ohne Mauern, das heißt jeder Knoten hat Kanten zu seinen 4 direkten Nachbar-Knoten. Die Anforderungen ans Labyrinth kann man jetzt als Anforderungen an den Graph formulieren:
  1. Ein gutes Labyrinth sollte lösbar sein => es muss einen Pfad durchs Labyrinth vom Eingangs-Knoten zum Ausgangs-Knoten geben
  2. In einem guten Labyrinth sollten alle Felder erreichbar sein => zwischen zwei beliebigen Knoten muss es immer einen Pfad geben. Das impliziert die vorherige Anforderung.
  3. Das Labyrinth sollte nicht unnötig leicht sein, es soll nur eine Lösung geben => zwischen zwei Knoten darf es nur genau einen Pfad geben.

Ich baue mein Labyrinth jetzt, in dem ich nach und nach zufällig gewählte Mauern errichte (Kanten aus dem Graph herausnehme). Das kann ich mit jeder Kante machen, solange Bedingung 2 nicht verletzt wird. Ich wähle zufällig eine Kante A->B, und prüfe, ob durch Entfernen dieser Kante zwei Punkte nicht mehr erreichbar werden. Dazu reicht es zu prüfen, ob die beiden Enden der Kanten (A und B / die beiden Felder die durch die Mauer getrennt werden sollen) eine alternative Verbindung zueinander haben (denn dann könnte jeder Pfad, der die gewählte Kante benutzt stattdessen diese alternative Verbindung nutzen, nichts wird unerreichbar). Ich werfe also meinen Solver (Details unten) auf das Labyrinth, und weise ihn an einen Pfad A==>B zu finden der nicht die Kante A->B benutzt. Findet er eine, kann ich die Kante entfernen (die Mauer errichten), findet er keinen, ist die Kante essenziell und die Mauer wird auch in Zukunft nicht errichtbar sein. Das wiederhole ich so lange, bis alle Kanten entweder entfernt oder essenziell sind.
Das so generierte Labyrinth erfüllt Bedingung 2 (da ich in jedem Schritt genau das prüfe) und auch Bedingung 3 (angenommen es gäbe zwei Pfade zwischen zwei Knoten, dann hätte der Graph irgendwo einen Kreis, in diesem Kreis wären alle Kanten optional und damit würde zumindest eine vom Algorithmus entfernt werden).
Zur Auswahl der Kante erfolgt immer gleichmäßig zufällig, mit gewichtetem Zufall könnte man hier noch Parameter in die Generierung einbringen.

Der Solver ist im Prinzip standardmäßiges A*, Heuristik-Funktion ist die Hamming-Distanz (also |x1-x2| + |y1-y2|), der sich auch die benutzten Knoten merkt.

Fazit: Hatte vor diesem Projekt nur ein paar Zeilen Go geschrieben (und das war länger her) - aber Go schreibt sich echt leicht und ist generell relativ angenehm zu handhaben (für den Entwickler). Und dazu noch getypt und deutlich flotter als Python (das sonst so meine Standard-Sprache ist). QT war ok, aber von den Bindings (Go<->QT) bin ich noch nicht überzeugt. Andere GUI-Frameworks gibt's in der Sprache aber anscheinend nicht (bzw die sind alle web-basiert). Das heißt die nächste Desktop-GUI-Anwendung wird wohl wieder irgendwas Java-basiertes. Oder ich bleib einfach bei Webseiten.
 

Kenobi van Gin

Brillenschlange

Registriert
14 Juli 2013
Beiträge
3.620
Ort
.\
Ich möchte an dieser Stelle einwerfen, dass ich mich am Wettbewerb zwar nicht beteilige (weil mir a) im Moment die Zeit fehlt und ich mich b) für die Lösung der Aufgabe noch nicht bereit gefühlt habe), eure Lösungsideen aber mit Interesse lese. Macht wirklich Spaß, euch über die Schulter zu schauen und auch dabei etwas zu lernen :T
 

Roin

Freier Denker

Registriert
22 Juli 2013
Beiträge
581
Da ich keine weitere Anpassung mehr machen werde, reiche ich meine Lösung mal auch ein.

ngbLabyrinth by Roin:
ngbLabyrinth.jpg

SourceCode:Anhang anzeigen ngbLabyrinth.zip
Zum Ausführen muss nur eine Python 3.x-Installation auf dem Computer vorhanden sein. Dann kann die main.py ausgeführt werden und das Programm startet.

In Summe ungefähr 400 Zeilen Python Code, vollständig mit Standard-Bibliotheken umgesetzt. Zum Zeichnen meiner Ausgabe verwende ich nun TKinter für Python und sonst nur ganz einfache Schleifen usw. Es werden mehrere kleine Threads erzeugt, da sonst die eigentliche Erzeugung usw. nicht funktioniert.

An sich ist das Skript nicht sonderlich ressourcenhungrig. Es lässt sich ein "Spieler" durch das Labyrinth steuern. Sofern dies gelungen ist, wird die benötigte Schrittzahl angezeigt und ein neues Labyrinth generiert. Ich bin zeitlich leider nicht dazu gekommen zu ermitteln, wie viele Schritte minimal möglich sind.

Etwas Info zum Vorgehen:
Ich starte mit einem Feld aus Wänden und wähle ein zufälliges Feld als Startpunkt aus. Von diesem gehe ich in beliebiger Richtung zwei Schritte und füge dieses neue Feld zu meinen "Wegen" hinzu. Das Wandfeld dazwischen wandle ich schlichtweg ebenfalls in einen Weg um.
Sobald ich von dem neuen Feld kein neues Wandfeld mehr mit genau zwei Schritten erreichen kann, wähle ich ein zufälliges der bisherigen Wegfelder aus und laufe erneut wild drauf los. Sobald es kein Wandfeld mehr auf dem entsprechenden Grid gibt, ist die Erzeugung gestoppt.
Wenn ich es richtig sehe ist damit jeder Weg eindeutig und es dürfte zwischen zwei Feldern immer nur genau einen Weg geben.
Das ganze passiert in einer recht simplen 2D Array-Struktur.
Ich habe keinen anerkannten Labyrinth-Generier-Algorithmus verwendet und einfach drauf losprogrammiert.
Mein erster Ansatz "zufällig überall Wege generieren und dann stoppen, wenn alles "voll" ist, war etwas zu kurz gedacht. Den habe ich dann zu Beginn doch bald fallen lassen.

Zwar nicht umgesetzt aber relativ einfach möglich in den Code einzubauen:
  • Items, die der Spieler für beispielsweise Punkte aufsammeln kann
  • Gegner, die durch das Labyrinth laufen und der Spieler gegen sie für Punkte kämpfen kann
  • Einen Lösungsweg einzeichnen
  • Nur einen gewissen Sichtbereich einblenden, um die Schwierigkeit zu erhöhen.
 

Brother John

(schein)heilig
Veteran

Registriert
1 Aug. 2013
Beiträge
235
Hier ist mein Einreichungspaket:
»Fertig« würde ichs zwar noch nicht nennen, aber für eine 1.0 ist es ein guter Stand.

Was mir noch vorschwebt sind mehr Statistiken. Das treibt mich gerade um: Wie kann man halbwegs objektiv den Schweregrad eines Labyrinths messen? Je nach Algokonfig sieht das nämlich ganz anders aus, wie oft, wie weit und wohin man sich verlaufen kann. Etwas simples wie »Anzahl der irreführenden Abzweigungen vom Lösungsweg« oder »Anzahl der Sackgassen« reicht jedenfalls nicht aus. Aber noch fehlt mir dafür die zündende Idee.
 

X-Coder

Aktiver NGBler

Registriert
14 Juli 2013
Beiträge
149
Mir war es heute langweilig und habe auch ein bisschen gebastelt und dies in Expression2 (einer Script-Sprache eines mods) geschrieben.
Wer es nicht kennt, dies ist eine Scriptsprache innerhalb von einem Spielemod für das Spiel "Garry's Mod".

Habe sozusagen einen Mod für einen Mod von einem Mod gemacht (Halflife 2>Garry's Mod>Wiremod>Expression2>Mein Expression2 Script) um damit dann die Objekte zu spawnen und das Labyrinth zu generieren.

Dazu habe ich einen Backtrace-Algorythmus verwendet:
  1. Grid/Zellen und Wände spawnen (Größe ist einstellbar)
  2. Start und Exit per Zufall auswählen und Außenwände entfernen (Zell-Abstand ist einstellbar, damit Start und Exit nicht zufällig direkt nebeneinander liegen)
  3. Per Zufall, nächste, bisher noch nicht besuchte Nachbarzelle auswählen
  4. Wand dazwischen entfernen
  5. Falls auf eine Sackgasse gestoßen wird, geht es auf dem gleichen Weg zurück, bis wieder ein freie, bisher nicht besuchte Nachbarzelle gefunden werden kann. Das ganze solange bis möglichst alle Zellen besucht worden sind.

Falls jemand Garry's Mod hat, und es selbst testen möchte, so kann der Code vom Spoiler einfach in den Expression2-Chip des Wiremod-Addons geladen werden. Dann noch einen Button damit verbinden, und einen Hebel zum Einstellen der Maze-Größe anschließen, falls jemand Hilfe dabei braucht einfach fragen, oder alternativ das unten angehängte Savefile für Advanced-Duplicator 2 verwenden.

20210109154235_1.jpg 20210109154248_1.jpg 20210109154324_1.jpg Expression2-ngb-mazegenerator.jpg

Google-Drive Video-Upload: [video]https://drive.google.com/file/d/1FbgNNJLMhmgeJsjWlfRfJzLI8im2IbyC/view?usp=sharing[/video]

Expression2-Code
[src=text]
@name ngb-mazegenerator
@inputs Start Reset MazeSize
@persist [PosX PosY PC MazeSize FloorCount]:number [VisitedFloors Way Walls OuterWalls Floors OuterFloors]:array CurrentFloorEntity:entity
@trigger

################################################################################################################
#Configuration
#
# MazeSize of maze grid
# MazeSize = 10 (uses Input connection value of this chip)
#
# Minimium cells between start and exit cell
ExitDistanceCells = 5
#
# Wall model
Wall = "models/props_phx/construct/metal_plate2x2.mdl"
#
# Wall color
Color1 = vec4(255,0,0,255)
#
# Floor color
Color2 = vec4(255,0,0,255)
#
# Enable debug
Debug = 1
#
# spawning interval in ms (if props dont spawn, try increasing the value)
SpawningInterval = 100
#
# at which rate should the maze generate new cells
MazeGenerationInterval = 1000
################################################################################################################


#Main entry points
################################################################################################################
# Input "Start" changed to 1
if(~Start && Start == 1) {
# start generation process
hint("spawning north walls", 1000)
timer("spawnNorthWallsTimer", 1000)
}

# Input "Reset" changed to 1
if(~Reset && Reset == 1) {
propDeleteAll()
reset()
}
################################################################################################################}


# function definitions
################################################################################################################
function entity getClosestOuterWall(E:entity){
findClearBlackList()
findClearWhiteList()
FindCount = findByModel(Wall)
findClipToEntities(OuterWalls)
ClosestEntity = findClosest(E:pos())
ClosestEntity:setColor(vec4(0,0,255,255))
return ClosestEntity
}

# removes a wall between two floors
function void removeWall(){
findClearBlackList()
findClearWhiteList()
FindCount = findByModel(Wall)
findExcludeEntities(OuterWalls)
findClipToEntities(Walls)

Pos = (Way[Way:count(),entity]:pos() + CurrentFloorEntity:pos()) / 2
ClosestEntity = findClosest(Pos)
ClosestEntity:propDelete()

if(Debug==1) {
holoCreate(5, ClosestEntity:pos())
holoColor(5, vec4(255,0,0,255))
}
}

# get direct neighbour floors of unvisited cells
function array getClosestNeighbourFloors(E:entity){
Dimensions = E:boxSize()
Neighbours = array()

findIncludeEntities(Floors)
FindCount = findByModel(Wall)
findClipToBox(E:pos()-vec(Dimensions:x(), 0, 0), E:pos()+vec(Dimensions:x(), 0, 0))
Number = findClipFromEntities(VisitedFloors)

for(Index = 1, Number){
EI = findResult(Index)
EI:setColor(vec4(0,255,0,255))
Neighbours:pushEntity(EI)
}

FindCount = findByModel(Wall)
findClipToBox(E:pos()-vec(0,Dimensions:y(), 0), E:pos()+vec(0,Dimensions:y(), 0))
Number = findClipFromEntities(VisitedFloors)

for(Index = 1, Number){
EI = findResult(Index)
EI:setColor(vec4(0,255,0,255))
Neighbours:pushEntity(EI)
}

# draw holos for debuging
if(Debug==1){
holoCreate(1, E:pos()-vec(Dimensions:x(),0,0))
holoCreate(2, E:pos()+vec(Dimensions:x(),0,0))
holoCreate(3, E:pos()-vec(0,Dimensions:y(),0))
holoCreate(4, E:pos()+vec(0,Dimensions:y(),0))
}

return Neighbours
}

# trace back until a unvisited neighbour is found
function void backtrace(){
CurrentFloorEntity = Way:popEntity()
Neighbours = getClosestNeighbourFloors(CurrentFloorEntity)
NeighbourCount = Neighbours:count()
if(NeighbourCount>0){
hint("found unvisited neighbour - resuming from here", 500)
timer("generateMazeTimer", MazeGenerationInterval)
}
else{
if(Way:count()>0){
timer("backtraceTimer", 100)
}
else{
hint("reached start - no more unvisted cells available", 1000)
hint("maze generation finished", 1000)
}
}
}

# main maze generation
function void generateMaze() {
# mark cell as visited
VisitedFloors:pushEntity(CurrentFloorEntity)

# push last visited cell to stack
Way:pushEntity(CurrentFloorEntity)

# get unvisited neighbours
Neighbours = getClosestNeighbourFloors(CurrentFloorEntity)


NeighbourCount = Neighbours:count()
# if it has neighbours...
if(NeighbourCount>0){
# ...select random neighbour cell
RandomNeighbourIndex = randint(NeighbourCount)
RandomNeighbour = Neighbours[RandomNeighbourIndex, entity]

RandomNeighbour:setColor(vec4(0,0,255,255))

#remember for next iteration
CurrentFloorEntity = RandomNeighbour

# remove Wall between cells
removeWall()

# start next iteration timer
timer("generateMazeTimer", 300)
}
else{
# ... no direct neighbour available?
# go back to last visited cell and trace back until a unvisited cell can be found again
CurrentFloorEntity = Way:popEntity()
hint("reached end - starting backtrace", 500)
timer("backtraceTimer", 100)
}
}

# mazeGenerator init function
function void mazeGenerator() {
# Select random start floor in the outer border
FloorCount = OuterFloors:count()
StartFloorIndex = randint(FloorCount)
StartFloorEntity = OuterFloors[StartFloorIndex, entity]
StartFloorEntity:setColor(vec4(0,0,255,255))
CurrentFloorEntity = StartFloorEntity

# Select random exit floor in the outer border
ExitFloorIndex = StartFloorIndex
ExitFloorEntity = StartFloorEntity
while(ExitFloorIndex==StartFloorIndex || StartFloorEntity:pos():distance(ExitFloorEntity:pos()) < (ExitDistanceCells*StartFloorEntity:boxSize():x())) {
ExitFloorIndex = randint(FloorCount)
ExitFloorEntity = OuterFloors[ExitFloorIndex, entity]
}
ExitFloorEntity:setColor(vec4(0,0,255,255))

# determine and remove outer walls
hint("creating random start and exit", 1000)
StartWall = getClosestOuterWall(StartFloorEntity)
StartWall:propDelete()

ExitWall = getClosestOuterWall(ExitFloorEntity)
ExitWall:propDelete()

# Start maze generator
timer("generateMazeTimer", MazeGenerationInterval)
}

# grid generation
################################################################################################################
function void spawnNorthWalls(){
EN = propSpawn(Wall, entity():pos() + vec(0, 0, 50) + vec((PosY-1) * 95, (PosX ) * 95, 0), ang(90,0,0), 1)

if(PosY == 0 || PosY == MazeSize){
EN:setColor(Color1)
OuterWalls:pushEntity(EN)
}

PosY = PosY + 1
if(PosY>MazeSize) {
PosX = PosX + 1
PosY = 0
}
entity():weld(EN)
Walls:pushEntity(EN)
timer("spawnNorthWallsTimer", SpawningInterval)
}

function void spawnWestWalls(){
EW = propSpawn(Wall, entity():pos() + vec(50, 50, 50) + vec((PosY-1) * 95, (PosX - 1) * 95, 0), ang(90,90,0), 1)

if(PosX == 0 || PosX == MazeSize){
EW:setColor(Color1)
OuterWalls:pushEntity(EW)
}

PosY = PosY + 1
if(PosY>(MazeSize - 1)) {
PosX = PosX + 1
PosY = 0
}

entity():weld(EW)
Walls:pushEntity(EW)
timer("spawnWestWallsTimer", SpawningInterval)
}

function void spawnFloor(){
EF = propSpawn(Wall, entity():pos() + vec(50, 0, 0) + vec((PosY-1) * 95, (PosX ) * 95, 0), ang(0,0,0), 1)

if(PosY == 0 || PosY == (MazeSize - 1) || PosX==0 || PosX==(MazeSize - 1)){
EF:setColor(Color2)
OuterFloors:pushEntity(EF)
}

PosY = PosY + 1
if(PosY>(MazeSize - 1)) {
PosX = PosX + 1
PosY = 0
}
Floors:pushEntity(EF)
entity():weld(EF)
timer("spawnFloorTimer", SpawningInterval)
}
################################################################################################################


#Timer listeners
################################################################################################################
if(clk("spawnNorthWallsTimer")) {
PC = PC + 1
if(PC - MazeSize<= MazeSize * MazeSize){
spawnNorthWalls()
}
else{
# reset position once the row has finished spawning
PosX = 0
PosY = 0
PC = 0
hint("spawning west walls", 1000)
timer("spawnWestWallsTimer", SpawningInterval)
}
}

if(clk("spawnWestWallsTimer")) {
PC = PC + 1
if(PC - MazeSize <= MazeSize * MazeSize){
spawnWestWalls()
}
else{
# reset position once the row has finished spawning
PosX = 0
PosY = 0
PC = 0
hint("spawning floors", 1000)
timer("spawnFloorTimer", SpawningInterval)
}
}

if(clk("spawnFloorTimer")) {
PC = PC + 1
if(PC - MazeSize <= MazeSize * MazeSize && PosX<MazeSize){
spawnFloor()
}
else{
# start maze generation process once all walls and floors has been spawned
hint("starting maze generation", 1000)
mazeGenerator()
}
}

if(clk("generateMazeTimer")) {
generateMaze()
}

if(clk("backtraceTimer")){
backtrace()
}
################################################################################################################
[/src]
Aufgrund des alten Garrysmod/Source bzw. Multiplayer-Engine und Spawnrate-Limits des Wiremods, musste ich das ganze mit Timern lösen, deswegen sieht der Code etwas komplexer aus, als er sein müsste.

Savefile für Advanced-Duplicator2 (damit kann alles was im Video sichtbar ist, direkt gespawnt werden):
https://drive.google.com/file/d/1QK5Z9zP1ChXvFoPOTTTsUqIS1XWZhK5T/view?usp=sharing
 
Zuletzt bearbeitet:

Der3Geist

always feed the fish

Registriert
14 Juli 2013
Beiträge
2.702
Ort
Hessen
Ich werde meinen Beitrag leider nicht Fertig bekommen.
Da ich durch meinen neuen Job letzte woche (Blöde Spätschicht) nicht dazu gekommen bin irgendwie daran zu Programmieren.

Das Labyrinth erstellen und Anzeigen Funktioniert zwar, aber ich hatte ursprünglich vor, noch ein kleines Spiel drumrum zu basteln.

Zur Labyrinth erstellung,

Das Prinzip war ganz einfach.
Ich lege ein Array an mit der größe des Labyrinths und fülle es Anfangs mit Wänden.

Ich suche mir eine Zufällige Startposition im Labyrinth welche /2 Teilbar ist.
Nun Prüfe ich per Zufall in eine Richtung (N/O/S/W) ob das Übernächste Feld eine Wand ist.

Ist dieses Feld eine Wand, wird es zum Weg gemacht und das Feld dazwischen ebenso.
Dannach wird das Feld als neuer ausgangspunkt für die Bewegung genommen.

Dadurch wird zwar ohne System einfach Zufällig über die Karte gezeichnet und ich habe Keine überprüfung ob die Karte nun Komplett oder nur Halb mit Gängen überzogen ist.
Das hat zwar den nachteil, das ich eine Ziemlich Große schleife brauche, um wirklich zu wissen, ob die Karte Komplett ausgefüllt ist.
Aber ein kleiner Vorteil ist dabei auch, das ich eben schnell mal ein kleines Labyrinth erstellen kann, was die Karte nicht Komplett Abdeckt.

Falls Gewünscht kann ich den VB6 Quellcode hier einstellen.
 

Roin

Freier Denker

Registriert
22 Juli 2013
Beiträge
581
@Der3Geist:
Das ist ja so ähnlich wie meine Lösung. Aber klar, die Hauptaufgabe war ein Labyrinth erstellen. Das hast du ja umgesetzt. Also zeig her dein Ergebnis :)
 

Der3Geist

always feed the fish

Registriert
14 Juli 2013
Beiträge
2.702
Ort
Hessen
Quellcode VB6

Ich habe 1 Combobox (cmbSize) auf der Form welche die Labyrinth größe als Drop Down Menü zur auswahl vorgib.
20x20 , 50x50 , 100x100 , 200x200 und 500x500

Die Größe wird innerhalb der Generierung in SizeX und SizeY eingelesen.

Eine weitere Combobox gibt die Leveltiefe zur auswahl (cmbDeep) in 3 Varianten.
Dies gibt nurbu an, wie lange die Zufällige "Gehen" Funktion ausgeführt wird.
Je Höher die Tiefe, desto Öfter / länger wie im Level Gelaufen und Wege gezeichnet.
Dadurch wird der Zähler (Deep) Festgelegt.

Die Karte selbst wird in Maze(x,y) Geschrieben, welche ichzu Begin pauschal auf 1000x1000 Festlege.

Das erstellen einer einfachen 100x100 Matrix mit "Minimal" Tiefe dauert ~100ms, dabei ist etwa 50% der Karte mit einem Labyrinth belegt.
Eine 100x100 Matrix auf "Maximal" Tiefe hingegen 2 1/2 Sekunden, wobei dann die Komplette Matrix belegt wird.

Im Unterschied zu den anderen Einseungen hier, belegen meine Wände immer 1 ganzes Feld.
Was ich früher schon so in Spielen Verwendet habe, da es bei der darstellung für mich einfacher Anzuzeigen war und die Levels durch diesen Aufbau immer Rechteckig waren.


Code:
'   Level Generieren
Private Sub cmdCreate_Click()
    Randomize Timer()
    '   Variablen zur Levelgeneration
    Dim x1 As Integer, y1 As Integer, x2 As Integer, y2 As Integer, n As Long, Deep As Long
    '   Variablen für Fortschrittsbalken
    Dim skip As Integer, tmp1 As Long, tmp2 As Long
    
    '   Gewünschte Labyrinth Größe aus dem Drop Down Menü auslesen
    SizeX = Val(Mid$(cmbSize.List(cmbSize.ListIndex), 1, 3))
    SizeY = Val(Mid$(cmbSize.List(cmbSize.ListIndex), 5, 3))
    
    '   Labyrinth mit Wänden füllen
    For x1 = 1 To SizeX
        For y1 = 1 To SizeY
            Maze(x1, y1) = 1
        Next y1
    Next x1
        
    '   Fortschrittsbalnken Anzeigen
    picProgress.Cls
    frmCreate.Top = Label1.Top
    frmCreate.Left = Label1.Left
    frmCreate.Visible = True
        
    '   Startposition Festlegen
    x1 = 2: y1 = 2
    
    '   Labyrinth Tiefe Festlegen
    '   (je größer der wert / die Auswahl, je Umfangreicher wird auf die Karte geschrieben
    '   braucht aber entsprechend auch mehr zeit
    Select Case cmbDeep.ListIndex
        Case 0: Deep = (SizeX * SizeY) / 2
        Case 1: Deep = (SizeX * SizeY)
        Case 2: Deep = (SizeX * SizeY) * 12
    End Select
    
    '   Schleife für den Wegzähler um durch das Labyrinth zu gehen und den weg zu zeichnen
    For n = 1 To Deep
        '   Fortschrittsbalken (jeden 2. durchlauf anzeigen)
        skip = 1 - skip
        If skip = 0 Then
            'picProgress.Cls
            '   Levelgeneration in %
            tmp1 = (n * 100) / Deep
            '   Levelgeneration in % auf Picturebox in % umrechnen
            tmp2 = (tmp1 * picProgress.Width) / 100
            '   Anzeigen
            picProgress.Line (1, 1)-(tmp2, picProgress.Height), RGB(255 - (tmp1 * 2), tmp1 * 2, 128), BF
            DoEvents
        End If
    
        '   Labyrinth Erstellen
        x2 = x1: y2 = y1
        '   Zufällige Richtung Auswählen
        Select Case Int(Rnd * 4)
            Case 0
                x1 = x1 + 2: If x1 >= SizeX Then x1 = x1 - 4
            Case 1
                x1 = x1 - 2: If x1 < 1 Then x1 = x1 + 4
            Case 2
                y1 = y1 + 2: If y1 >= SizeY Then y1 = y1 - 4
            Case 3
                y1 = y1 - 2: If y1 < 1 Then y1 = y1 + 4
        End Select
        '   Ist in dieser richtung eine Wand, dann Wand Löschen und weg einzeichnen
        '   Und das Generieren zu beschleunigen das XDELAY Entfernen
        If Maze(x1, y1) = 1 Then Maze(x1, y1) = 0: Maze((x1 + x2) / 2, (y1 + y2) / 2) = 0
        DoEvents
    Next n
    
    '   Fortschrittsbalken Verstecken
    frmCreate.Visible = False
    '   Karte Anzeigen
    frmShow.Show vbModal
    cmdPlay.Enabled = True
End Sub

Und so sieht das dan bei einem 100x100 Level aus

maze.png
(Das Schwarze sind die Wege ;) )
 

MingsPing

NGBler

Registriert
15 Juli 2013
Beiträge
346
  • Thread Starter Thread Starter
  • #52
Ich hab wenig Zeit gehabt die Woche leider, konnte auch gar nicht mit Beiträgen glänzen. Mir haben eure Beiträge aber sehr gefallen, auch die verschiedenartigen Mazes und Optionen, richtig toll.

Muss den Abgabetermin leider etwas reißen, aber es kommt noch was! (Meine Graphenimplementierung hat dann doch mehr Zeit gekostet, als ich dachte).

Aber war ne tolle Challenge, so viele Beiträge und Leute die mitgemacht haben, klasse!
 

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
Ich kann auch leider erst in den nächsten Tagen (vermutlich WE) abgeben und dann außerhalb der Wertung fahren.
 

drfuture

Zeitreisender
Teammitglied

Registriert
14 Juli 2013
Beiträge
8.728
Ort
in der Zukunft
Jo Respekt wie das manche gelöst haben.
Ich habe das ganze "nur" im Kopf durchgespielt und hatte hatte mir vorgestellt das ich ein festes Koordinaten-System verwende und dort aus einer Anzahl an möglichen Puzzle-Teilen (also ein Baustein gerade, kurve rechts, kurve links etc.) zufällig einen Weg bauen lasse der auf einer anderen Wand raus kommt.
So hätte ich dann schon mal eine garantierte Lösbarkeit.

Die Schwierigkeit könnte man über die Anzahl der dazu verwendeten Schritte bis zum Ausgang im Verhältnis zu unnützen Wegen festlegen / feststellen. Wenn die passende Stufe nicht erreicht ist, lösche ich k.a 10% des Weges und lasse den Zufall erneut entscheiden.

im Anschluss würde ich dann beliebige Positionen auf der restlichen Karte wählen und den gleichen Prozess laufen lassen und jedes mal wenn ich auf einen bestehenden Weg oder eine Wand treffe von neuem beginnen.

Jedes der Baustein-Elemente ist ein CustomObject mit einigen Meta-Daten wie eben das "Bild (Aussehen), vorgänger-Objekt, nachfolge-Objekt, mögliche Züge von diesem Feld (berechnet anhand der angrenzenden Objekte).
Die Metadaten zu jeder Zelle des Grids machen es dann möglich das ganze nach Generierung zu dynamisieren:
z.B. wenn man mit einer Figur durch das Labyrinth läuft Wände erscheinen lassen / löschen | für eine Figur mögliche Züge zu bestimmen / verwehren.

Das ganze wollte ich in Powerhell umsetzen. ... vielleicht wird es ja "irgendwann" was :D
 

Roin

Freier Denker

Registriert
22 Juli 2013
Beiträge
581
@Der3Geist: Meine Einsendung verwendet ebenfalls ein ganzes Feld als Wand. In der Array Form ist das vermutlich auch das einfachste. Andernfalls muss man ja Verknüpfungen schaffen, wo Wände sind und wo keine sind.

Ich bin positiv überrascht, wie viele Abgaben und Ankündigungen für Nachreichungen es schlussendlich doch gibt. Auch finde ich die Lösungen ganz spannend.
Wenn ich es richtig sehe hat jede Abgabe einen eindeutig lösbaren Weg, die meisten haben "tote Enden" in den Labyrinthen und zwei Versionen sind sogar "spielbar".
Einige haben Lösungswege direkt mitberechnen lassen und Brother John hat sich sogar die Gedanken gemacht, wie er Bestagons verwenden kann.

Ich habe mir bisher nur die Ausgaben angeguckt, jedoch keinen Quellcode außer meinen, bisher.
Wie schaut es bei euch anderen aus?
 
Zuletzt bearbeitet:

Der3Geist

always feed the fish

Registriert
14 Juli 2013
Beiträge
2.702
Ort
Hessen
@Der3Geist: Meine Einsendung verwendet ebenfalls ein ganzes Feld als Wand. In der Array Form ist das vermutlich auch das einfachste. Andernfalls muss man ja Verknüpfungen schaffen, wo Wände sind und wo keine sind.

Ich habe dieses System früher schon verwendet, als ich noch in DarkBasic pro programmiert habe, um 3D Spiele zu Programmieren.
Dadurch war es ziemlich schnell und einfach möglich Dungeon Crawler spiele aus der Ego Perspektive zu Programmieren.
Quasi gab es mehrere 3D Objekte als Tile alle mit gleicher größe, und man konnte so einfach ein Level Generieren mit 2 Schleifen und einer Hand voll 3D Objekten.
 
Oben