Abstimmung Programmierwettbewerb #5

[theSplit]

Hallo zur Abstimmung NGB.to Programmierwettbewerb #5

Viele fleißige Hände haben sich an einer Lösung zu der aktuellen Coding Challenge bzw. dem Programmierwettbewerb herangetastet. Und es war wirklich ein Vergnügen dem Thema zu folgen. Vielen Dank an alle Teilnehmer an dieser Stelle für eure Teilnahme und die investierte Arbeit an und in diesem Thema!

Ihr seid nun dazu eingeladen für eine oder mehrere der Abgaben zu stimmen. Auch könnt ihr gerne ein paar Worte zu eurem Favoriten schreiben, warum ihr für ihn oder sie gestimmt habt um den Teilnehmer noch etwas mehr Feedback zu geben über dass sie sich sicherlich freuen würden.

Ihr habt nun 21 Tage Zeit für einen oder mehrere Favoriten. unter den Gesichtspunkten Optik, Funktionalität und Code Qualität zu stimmen.

Und nun zu der folgende Problemstellung und Anforderungen für diesen Wettbewerb (vielen Dank an @ Mingsping für die tolle Einleitung/Ankündigung!)

Dynamischer Dungeon / Dynamisches Labyrinth
EINLEITUNG

Unendlich viel Spielspaß? Kein Level gleicht dem anderen?

Das klingt zu gut, um wahr zu sein?
Das ngb machts möglich! Wir beginnen gerade noch rechtzeitig im Jahr 2020 den 5. forumsinternen Programmierwettbewerb.

ANFORDERUNGEN

Es soll ein Programm geschrieben werden, das zufällig generierte (dynamische) Labyrinthe erstellt. Welche Form diese haben (2d/3d, Quadrate/sonstige Bausteine), ist euch überlassen. Eine Grafikausgabe ist nicht zwingend, wäre aber toll. Im Prinzip reicht eine Kommandozeilenausgabe.

Mögliche Features:
- Schwierigkeitsparameter: wie "verwinkelt" soll das Labyrinth sein?
- Größe einstellbar
- mehrere Wege zum Ziel möglich? Mehrere Ziele?
- Räume im Labyrinth
- Fog of War
- Sechsecke (because Hexagons are Bestagons, danke an Brother John)

---

Folgend die Abgaben der Challenge in chronologischer Reihenfolge mit Link zum jeweiligen Abgabebeitrag, gegebenenfalls mit Bild und oder Video und Quelltexten/Bezugsquellen.

---

Maze Generator by Rakorium Lang: Go + Qt5

Abgabebeitrag

---

ngbLabyrinth by Roin Lang: Python3 + Tkinter

Abgabebeitrag

---

Maze by Brother John Lang: C++ & Qt

Abgabebeitrag

---

X-Coder Lang: Expression2 (Garry`s Mod/Wiremod)

Abgabebeitrag

---

KaPiTN Lang: C#

Abgabebeitrag

---

Der3Geist Lang: VB 6

Abgabebeitrag

[Roin]

Ich habe meine Stimme mal an Brother John gegeben.
Allein die Dokumentation ist sehr gut. Dafür muss bereits mehr Zeit investiert worden sein als ich für die ganze Aufgabe genutzt habe.
Ansonsten sind nunmal Hexagons genutzt worden, was die Abgabe eindeutig von den anderen Abgaben unterscheidet.
Auch die Code-Qualität ist gut, jedoch hätte ich mir in dem Code ein paar mehr Kommentare gewünscht.

Die anderen Abgaben finde ich auch alle sehr gut und deswegen konnte ich mich erst nicht entscheiden. Hier aber ein paar Sätze zu den restlichen Abgaben:

Rakorium:
Ich habe noch nie etwas in Go gesehen und fand es spannend das mal zu sehen.
Die Einleitung am Anfang deiner Abgabe als Kommetar fand ich sehr hilfreich, wenn auch er Gedankengang ein wenig umständlich ist. Das liegt aber durchaus daran, dass ich diesen bei mir in der Form einfach nicht verwendet habe.

Ich:
Mein eigener Code ist sowieso der Beste von allen. Ist ja immerhin meiner ;-)

X-Coder:
Die Aufgabe als Mod für ein Spiel umzusetzen finde ich eine coole Idee. Ich weiß nicht recht, ob du es in deinem Code eingestellt hast oder es einfach der Mod geschuldet ist, aber den Aufbau des Labyrinths fand ich etwas arg langsam, wenn auch schön zu sehen ist, wie dein Algorithmus funktioniert.
Sonst noch ein kleiner Hinweis: Bei vielen Ecken kann man bei dir zwischen den Wänden durchgucken, weil sozusagen der Treffpunkt der Wände nicht zwingend bündig sind. Das könnte dem Spieler wichtige Tipps geben. Kann man aber dadurch auch als Feature verkaufen
Zudem bist du der Einzige, bei dem, neben mir ein "echtes" Spiel aus dem Labyrinth entstanden ist.
Dafür gibt es aber noch einen großen Kritikpunkt an deinem Code. Ich bin gar kein Freund davon Variablen mit großen Buchstaben zu starten. Das stört mich persönlich sehr stark.

KaPiTN:
Sehr sauberer Code und sinnvoll in verschiedene Dateien gesplittet. Auch hier hätte ich mir ein paar wenige Kommentare mehr gewünscht.
Die Form des Codes, also zum Beispiel die Klammern in einer eigenen Zeile ist Geschmackssache, ich finde es streckt den Code unnötig lang und es passt einfach weniger auf den Bildschirm.

Der3Geist:
Du hast schonmal die gleiche Datenstruktur wie ich verwendet. Das gibt von mir natürlich einen Pluspunkt.
Ich habe vier Punkte, die ich bei dir ansprechen möchte...
Du hast ein relativ großes Beispielmaze gemacht, das finde ich erstmal schön. Leider gibt es allerdings keinen Ein- und Ausgang, da fehlen also wohl noch ein paar wenige Zeilen Code.
Das VB* keine hübsche Sprache ist, ist wieder komplett Geschmackssache und einfach persönliche (nicht-)Präferenz.
Du hast in deinem geposteten Code eine Variable "skip", die für mich so absolut kein Sinn ergibt. Habe ich da was übersehen oder ist in dem Code die Variable nicht initialisiert und dadurch wird bei der Variable immer zwischen 0 und 1 gewechselt? Ich hätte dafür eher eine Variable genutzt, die zwischen True und False welchselt. Hätte ich intuitiver gefunden.
Ansonsten ist der Code aber ausreichend kommentiert.

Alle zusammen:
Schön, dass ihr die Zeit gefunden habt mitzumachen.
@Brother_John: Magst du mal sagen, wie viel Zeit du am Ende für das Projekt gebraucht hast? Ganz ehrlich?

[Brother John]

@Brother_John: Magst du mal sagen, wie viel Zeit du am Ende für das Projekt gebraucht hast? Ganz ehrlich?

Da muss ich schätzen, weils mich häppchenweise den ganzen Weihnachtsurlaub begleitet hat. Das kommt davon, wenn Lockdown ist und schnelle kleine Wochenendprojekte plötzlich unerwartet viel Spaß machen … Bei dem Umfang, wenn ich mir die Githistorie so anschaue, mit Recherche und allem drum und dran: Größenordnung ne Vollzeitwoche.

[X-Coder]

Finde es super, dass viele mitgemacht haben und auch bei allen gute und umfangreiche Lösungen dabei heraus gekommen sind.


Ein bisschen Feedback zu Roin's post:

X-Coder:
Die Aufgabe als Mod für ein Spiel umzusetzen finde ich eine coole Idee. Ich weiß nicht recht, ob du es in deinem Code eingestellt hast oder es einfach der Mod geschuldet ist, aber den Aufbau des Labyrinths fand ich etwas arg langsam, wenn auch schön zu sehen ist, wie dein Algorithmus funktioniert.

Ich musste es künstlich ausbremsen, da ich nur alle x ms Objekte spawnen darf, was der Multiplayer-Engine bzw. dem Wiremod geschuldet ist. Da gibt es Hard-Limits um Lags bei anderen Spielern zu verhindern, da die Funktionen oft Missbräuchlich verwendet werden um andere Mitspieler zu trollen oder Server zu crashen und da der Mod die alte Halflife2-Engine ziemlich ausreizt, welche dafür wahrscheinlich gar nicht ausgelegt war.

Und ich wollte die Generierung absichtlich sichtbar machen, damit man auch visuell sehen kann wie der Algorythmus arbeitet, sonst hätte man natürlich auch alles Vorab generieren können, und erst zum Schluss das fertige Labyrinth spawnen.

Sonst noch ein kleiner Hinweis: Bei vielen Ecken kann man bei dir zwischen den Wänden durchgucken, weil sozusagen der Treffpunkt der Wände nicht zwingend bündig sind. Das könnte dem Spieler wichtige Tipps geben. Kann man aber dadurch auch als Feature verkaufen
Zudem bist du der Einzige, bei dem, neben mir ein "echtes" Spiel aus dem Labyrinth entstanden ist.

Das ist ein Feature

Dafür gibt es aber noch einen großen Kritikpunkt an deinem Code. Ich bin gar kein Freund davon Variablen mit großen Buchstaben zu starten. Das stört mich persönlich sehr stark.

Da bin ich auch absolut kein Freund von, ist aber leider dem Expression2-Syntax geschuldet, dieser ist sehr simpel gehalten und unterscheidet zwischen Funktionsnamen und Variablen nur durch Groß-/Kleinschreibung, da habe ich leider keinen Einfluss drauf. Wurde von den Entwicklern vermutlich so gelöst damit das Syntax-Highlighting simpel gelöst werden kann.

[Der3Geist]

Meine Stimmt geht ebenfalls an Brother John, weil die Doku wirklich sehr Umfangreich ist.
Außerdem finde ich die sache mit den Hexagons wirklich Gelungen.
Die wege sind nicht wie üblich oben/unten, Links und rechts, was ein Labyrinht somit viel Komplexer machen kann.
Das finde ich Persönlich einfach Innovativ und ich wüsste jetzt auch anhieb nicht wie das "Leicht" umzusetzen ist.

Eine weiter Stimme geht an X-Coder für die Idee die Aufgabe mit einer Scriptsprache eines Spieles zu lösen.
Der Code ist leider wenig Dokumentiert und für jemanden der Code fremd ist, ist es schwer dort durchzusteigen.


@Roin
Dadurch, das ich nur den Codeteil für die Labyrinth Generierung gepostet habe, fehlen einige dinge.
Dies hat zur folge (hab ich leider Verpeilt) die ein & ausgänge zu zeigen.
Da die Gänge alle miteinander Verbunden ist, suche ich mir einfach am oberen und unteren rand ein Feld mit "Weg" und lösche die wand für einen Aus & Eingang.

Die Variable "Skip" wird als Integer Definiert (Siehe Quellcode)
Die gibt es nur, damit bei jedem 2. durchlauf der Fortschrittsbalken Akualisiert wird.
Da es nicht nötig ist, die bei jedem durchlauf der Schleife zu machen.
In VB erlaubt es der Befehl "DoEvents" das Windows seine restlichen sachen Abarbeitet.
Wenn ich nun jeden durchlauf ein DoEvents laufen lasse, wird die Levelgenerierung Künstlich Verlangsamt, und im gegensatz dazu wenn kein DoEvents ausgeführt wird,
Aktualisiert Windows das Programmfenster Nicht und das programm wirkt wie Abgestürzt.

Mit True & False ist das so nicht möglich, da ich durch die Rechnung "skip=1-skip" erreiche, das diese immer zwischen 0 und 1 wechselt.
Wenn ich ein Boolean verwenden würde, kann ich nicht mit dieser Simplen rechnung wechseln.
Dies würde dann in VB entsprechend so aussehen "if skip=true then skip=false : else : skip=true : endif" was die sache unnötig verschachtelt und Unübersichtlicher als "skip=1-skip" macht.

[KaPiTN]

Mit True & False ist das so nicht möglich, da ich durch die Rechnung "skip=1-skip" erreiche, das diese immer zwischen 0 und 1 wechselt.
Wenn ich ein Boolean verwenden würde, kann ich nicht mit dieser Simplen rechnung wechseln.
Dies würde dann in VB entsprechend so aussehen "if skip=true then skip=false : else : skip=true : endif" was die sache unnötig verschachtelt und Unübersichtlicher als "skip=1-skip" macht.

Und was wäre mit

skip=!skip

?

[Der3Geist]

Und was wäre mit

skip=!skip

?

Private Sub Form_Load()
 Dim test As Boolean

 test=true
 test=!Test
End Sub

Ergibt

Fehler beim Kompilieren
Unzulässiger oder nicht ausreichend definierter Verweis

Nicht zu Vergessen, es Handelt sich um VB6

[KaPiTN]

Ok. Ich war mir nicht sicher, ob VB das kann.

Auslagern in eine Funktion würde mir dann noch einfallen.

(Das gibt es aber, oder? )

[Der3Geist]

Auslagern in eine Funktion würde mir dann noch einfallen.

(Das gibt es aber, oder? )

Sicher gibt es das, das macht es aber Weniger Benutzerfreundlich und Bläht die ganze sache unnötig auf.
Nur um die sache mit True & False zu machen, und ein Boolean zu Verwenden macht es nun wirklich keinen Sinn dafür noch eine Funktion zu schreiben, um von 0 und +1 (x=1-x) auf 0 und -1 zu wechseln.

[KaPiTN]

VB war case-insensitive?

Also der Fehler beim Kompilieren liegt nicht an groß/klein?

test=!Test

[Der3Geist]

VB war case-insensitive?

Also der Fehler beim Kompilieren liegt nicht an groß/klein?

VB ist nicht Case Sensitive.
Es lag auch nicht an "test=!Test", da VB6 bei mir in einer VM Läuft und ich den Code nicht per Zwischenablage Kopiert habe sondern hier neu eingetippt habe.
Die Variablen waren in VB schon richtig Geschrieben, zumal der VB Codeeditor das sowieso selber regelt, und es dieser nicht zulässt eine Variable mal klein / groß zu schreiben.

Der Editor passt das selber an, heisst so wie die Variable Deklariert wurde ( Dim test as Integer) so wird sie vom Editor im Kompletten Code Automatisch immer angepasst.
Und nach einer Änderung der Deklaration ändert sich diese im Kompletten Code.

Es liegt einfach an der Operation !

[Roin]

Ich bin mir ehrlich gesagt nicht sicher wo der Unterschied zwischen Visual Basic und VB6 ist aber statt ! gibt es zumindest in Visual Basic das NOT

Alternativ sowas wie:

' Möglichkeit 1skip = not skip' Möglichkeit 2skip = (skip == False)

Aber da wird jetzt über ein Kleinigkeit diskutiert. Ich fand die Stelle einfach auf den ersten Blick etwas irritierend.

[KaPiTN]

Jetzt wo Du es erwähnst.

Ich habe länger kein VB.Net mehr gemacht und vergessen, daß da nicht nur die Klammern durch End ersetzt werden, sondern es auch Unterschiede wie ! statt not oder auch select case statt switch case gibt.

[drfuture]

VB6 != VB.NET
Vb.Net läuft am Ende auf den gleichen Zwischencode wie c# raus...
VB6 findet in etwas angepasster Form z.b. auch in der Makro engine von Excel / wird etc. Verwendung.

[KaPiTN]

Natürlich ist es nicht das Gleiche, aber vor allem unter der Haube. Ansonsten ist VB.Net sprachlich darauf angelegt, den VB-Usern den Einstieg in .NET leicht und schmackhaft zu machen.

Und mit not läßt sich das ohne Fehler kompilieren.

Module VBModule    Sub Main()         Dim test As Boolean  test=true test= NOT testConsole.WriteLine(test)    End SubEnd Module

gibt false aus und

Module VBModule    Sub Main()         Dim test As Boolean  test=false test= NOT testConsole.WriteLine(test)    End SubEnd Module

gibt true aus.


Und aus C# und VB.Net resultiert weitestgehend gleiche CIL.

[drfuture]

Ja - c# hat auch ein wesentlich größeren Sprachumfang - wodurch sich einige dinge Eleganter lösen lassen und damit auch anderer Zwischencode entsteht
Aber ist ja gut wenn du das weißt - leider wird das nur alt so gerne in einen Topf geworfen - meist nicht aus Böswilligkeit sondern wegen blöder Namensgebung

[KaPiTN]

Ich mußte mal vor Ewigkeiten ein VB.Net Projekt eines ausgeschiedenen Kollegen nach C# portieren. Theoretisch sollte das ja von alleine gehen, wenn die CIL die Gleiche wäre.
Aber, die genauen Einzelheiten sind nicht mehr parat, da war eine Menge Handarbeit nötig.

Schon so etwas Einfaches wie ein Array unterscheidet sich in beiden Sprachen:

Ein Array mit 5 Elementen

in VB.Net wird der höchste Index angegeben:

Dim numbers(4) As Integer

in C# die Anzahl der Elemente:

int[] numbers = new int[5];

[drfuture]

Nein so meinte ich das nicht...
der Syntax ist bei VB.NET ziemlich an VB6 angelehnt; c# eher an Java... im weitersten Sinne.
der Compiler erstellt zwischencode der dann bei Ausführung von der .NET Laufzeitumgebung gelesen wird.

Dieser Zwischencode ist relativ identisch - in beiden deiner Code-Varianten oben.

[Der3Geist]

[src=vb]

Dim test As Boolean

test=true
test= NOT test
Console.WriteLine(test)

Geht nicht, weil der Consolen Befehl in VB nicht Existiert.
Aber das mit "test= NOT test" Funktioniert.

Ich hab es halt über test=1-test gelöst, weil ich mir das zu C64 zeiten halt schon so angewöhnt habe.

VB 6 und VB Net sind zwar Ähnlich, aber die Unterschiede sind doch ziemlich groß.

[drfuture]

lohnen sich aber ... so btw
Komme auch von VB6 und bin froh das ich vor vielen Jahren dann umgestiegen bin.
Vor allem da VB6 langsam aber sicher auch von der technischen Basis im OS mehr beschnitten wird und langsam ausstirbt.

[KaPiTN]

@drfuture:

Das mit dem Array war jetzt schlecht gewählt, weil das tatsächlich nur ein Unterschied in der Syntax ist und die gleichen CIL ergibt.

Aber es gibt in beiden Sprachen Features, die die andere nicht hat.


Schon ein Integer und einen String zu definieren und dann den integer dem string zu zu weisen´muß zu etwas unterschiedlichem CIL führen, weil in C# der Integer ein Wert zugewiesen werden und eine Methode aufgerufen werden muß, die den Int in ein string castet.

Spoiler: 

int s=0;
string w;
w = s.ToString();
_______________________

[0] int32 s,
[1] string w
)

IL_0000: nop
IL_0001: ldc.i4.0
IL_0002: stloc.0
IL_0003: ldloca.s s
IL_0005: call instance string [mscorlib]System.Int32::ToString()
IL_000a: stloc.1
IL_000b: ret

Spoiler: 

Dim s As Integer
Dim w As String
w = s
________________________

[0] int32 s,
[1] string w
)

IL_0000: nop
IL_0001: ldloc.0
IL_0002: call string [Microsoft.VisualBasic]Microsoft.VisualBasic.CompilerServices.Conversions::ToString(int32)
IL_0007: stloc.1
IL_0008: ret

Ein einfacheres Beispiel dürfte es nicht geben, aber bereits hier gibt es Abweichungen, weil VB automatische Initialisierung und implizite Typumwandlung hat, C# aber nicht.

Das soll jetzt kein kleinliches Korinthenkacken sein, weil es ja schließlich irgendwo noch ähnlich aussieht.
Vielmehr geht es mir darum dem Versprechen zu mißtrauen, unter .NET könne jeder die Sprache seiner Wahl wählen für das Projekt, weil letztendlich käme ja der gleiche Zwischencode heraus.
Das ist jetzt fast 15 Jahre her, ich weiß nicht mehr welche Effekte damals aufgetreten sind, aber wir haben den VB Code portiert, weil verschiedene, mal aus VB und mal aus C# heraus erzeugte Programmteile, zusammen nicht zuverlässig die erwarteten Resultate lieferten.

[Brother John]

Häckchen zu vergeben ist gar nicht so einfach. Es hat Spaß gemacht, die ganzen verschiedenen Ansätze in so vielen verschiedenen Sprachen zu sehen, und da seid ihr alle miteinander schuld dran! Sowas wie ein Codereview macht auch wenig Sinn, weil ich die meisten Sprachen höchstens oberflächlich kenne. OK, sagen wir zwei Punkte für die Algos.

Der erste Punkt geht an Rakorium, weil das am Ende der interessanteste algorithmische Ansatz war. Ein perfect Maze zu erzeugen, indem man den Solver draufschmeißt und ausrechnet, dass die Perfectness-Regeln nicht verletzt werden, auf die dumme Idee muss man erstmal kommen! Ich bin ein bisschen skeptisch in Sachen Performance, aber das tut der Idee keinen Abbruch.

Und noch ein Punkt für Roin für die komplette Implementierung von »Zelle ist Wand oder Weg«. Ich fands gut, dass du nicht in Richtung zelluläre Automaten losmarschiert bist, was man für die Art Labyrinth wohl oft macht. Sonst hätte man nicht so schön gesehen, dass sich die Ansätze für »Wand/Weg-Zellen« und »Wand zwischen den Zellen« gar nicht so sehr unterscheiden. In Zweierschritten zu gehen scheint mir der wichtige Trick zu sein. Außerdem Bonus-Daumenhoch dafür, dass das Labyrinth auch noch spielbar ist.

Nochwas zur Perfectness: Ich glaube, ich hab die wichtigen Punkte dafür verstanden. Eine garantierte Lösung stellt man sicher, indem man stecken bleibt und dann irgendwo anders am schon erzeugten Weg wieder ansetzt. So hat man immer freien Rückweg zum Eingang – und das gilt natürlich auch noch am Ausgang. Eine eindeutige Lösung kriegt man, wenn man es vermeidet, einen Weg zu einem schon besuchten Feld zu graben. Spätestens die letzte Wand bleibt immer stehen. Damit kreuzt sich der Lösungsweg nie selbst und es entstehen keine Schleifen, durch die man sich entscheiden könnte wie herum man läuft. Und das klärt auch den spanning tree, der immer wieder als Begriff auftaucht. Denn ein Pfad, der sich nur immer weiter verästelt, aber nie Äste wieder zusammenführt – das ist ein Baum.