Hi,

hier liegt noch ein altes Spiel von mir rum, dass Ihr noch sehen werdet, sobald es fertig ist (ich bin ein Feind von toten Projekten in der Projektsektion, erstelle daher in der Regel erst ein Thema wenn das Projekt so gut wie fertig ist). Einziger "kleiner" Punkt der noch zu tun ist: Das Spiel ist ein Brettspiel und ich benötige mehrere Spielbretter. Je mehr desto besser, am besten ist die Möglichkeit, dass jeder Spieler selbst auf Knopfdruck ein Brett - oder wie im Folgenden nun gesagt - ein Spielfeld generieren kann. Wenn ich 50 reguläre Levels habe, wäre das ein großer Aufwand, diese manuell zu erstellen. Außerdem ist es doch schön, wenn der Spieler auf Knopfdruck ein neues Spielfeld generieren kann.

Bei Spielfeld denkt jeder gleich an was Großes, doch hier geht es im Prinzip um die zufällige Befüllung einer Matrix, welche schwieriger ist als man denken mag. Ein Spielfeld besteht aus einer Matrix. Alle nicht beschriebenen Teile der Matrix sind mit Spielfiguren logischerweise nicht begehbar. Alle anderen schon. Das klingt so, als würde man einfach wild in einer Matrix Felder befüllen - das dürfte einfach sein. Beispiel:
0 0 x 0
x 0 0 x
0 x x 0
x x 0 0
Und genau das soll es nicht sein. So ein Level wäre gewünscht:
0 0 x 0
x x x 0
x 0 0 0
x x x 0
Der Unterschied ist offensichtlich: Das x repräsentiert ein begehbares Feld. Es ergibt sich ein Pfad. Dieser Leveltyp wird von mir persönlich Streckenlevel genannt. Das Level hat einen Start- und Endpunkt. Wenn ein Spieler das Ende erreicht, endet das Spiel und es werden Punkte aufsummiert etc. Dieses Level konnte ich zufällig sogar schon halbwegs brauchbar generieren.
Das Hauptproblem sind die Punktelevels, bei denen das Level beim Erreichen eines Spielers einer festen Punktzahl endet. Diese Levels müssen im Kreis laufen. Start- und Endpunkt müssen entweder direkt nebeneinander liegen oder sogar das gleiche Feld sein. Der wohl einfachste Fall der mir einfällt (jedes Feld kann Start- und Endpunkt zugleich sein):
x x x x
x 0 0 x
x 0 0 x
x x x x

Zur Generierung:
Das Streckenlevel generiere ich einfach: Ich bin auf einem Feld und setze zufällig eins in die drei verbleibenden Richtungen (Norden, Süden, Weste, Osten - die Richtung aus der ich komme fällt weg, daher nur drei), wenn kein Feld mehr gesetzt werden kann (bspw. am Rand des Spielfelds angelangt), bricht der Algorithmus ab. Danach schaut er, ob es genügend Felder sind und generiert ggf. brachial ein neues Zufallslevel. Nach ein paar Durchläufen und einer Wartezeit die nicht auffällt, ist das Level dann generiert.
Die Punktelevels könnte man genauso generieren, wenn man bei jedem Feld das man setzt prüfen würde, ob ein Weg zurück existiert. Das hatte ich auch in verschiedenen Umsetzungsformen versucht, allerdings endete es grundsätzlich in einer Exception, welche laut Debugger (und Logsystem, welches ich einfach an gewissen Stellen Statusposts ausgeben lassen habe) immer woanders auftrat. Der Algorithmus für die Streckenlevels hat ohnehin schon einige Schleifen und er ruft sich gerne mal selbst auf, falls nötig. Nun nimmt man diesen Strecken-Algorithmus - der ein Klotz ist - und baut noch pro gesetztes Feld eine Prüfung ein, die ebenso am besten noch rekursiv einen Rückweg von dem Feld sucht. Der Code enthält keine sichtbaren Fehler, der Debugger zeigt auftretende Exceptions immer an anderen Stellen, ein try..except um alle Stellen herum hilft nicht. Die einzige Erklärung dafür wäre, dass er Algorithmus sich selbst zu oft aufruft und irgendwie für einen Überlauf sorgt. Ansonsten habe ich keinen blassen Schimmer, wieso der Algorithmus immer an einer ganz anderen Stelle beim xten Durchlauf (er ruft sich mehrfach selbst auf) abbricht. Da die Felder zufällig gesetzt werden, ruft er sich wohl zu oft selbst auf. Auffällig fand ich, dass ich einzelne Teile des Algos einfach rausnehmen konnte und sie liefen ohne Ende durch. Es ist die Kombination des Streckenalgorithmus' und des "Existiert ein Weg zurück"-Algorithmus'. Kombiniert man diese scheint sich die Laufzeit zu potenzieren. Aber ich muss sie dummerweise kombinieren.

Außerdem: So dürfen Felder gesetzt werden:
x x x 0
0 0 x 0
x x x 0
0 0 0 0
So nicht:
x x x 0
x x x 0
0 0 0 0
0 0 0 0
Im zweiten Fall ist nicht mehr erkennbar, wie der Pfad genau läuft. Das darf nicht sein. Ich könnte die Ränder der Felder in jeweilige Richtungen abdunkeln, aber am Übersichtlichsten bleibt es, wenn man einen gewissen Freiraum, wie im ersten Beispiel gezeigt, zwischen den Feldern generiert.

Der Algorithmus ist eigentlich nur eins: Schrott. Sowohl der Strecken- als auch der davon abgeleitete Punktealgorithmus sind äußerst brachial programmiert. Das ist einfach nur Müll. Das Problem ist, dass das Level zufällig sein muss. Außerdem darf der Pfad nicht hintereinander dreimal Aussetzenfelder haben. Die Verteilungen, welche Felder aufeinander folgen, muss unbedingt gleichmäßig verteilt sein. Ich habe also einen vollen Pool aus Feldtypen, wähle immer ein Feld raus, setze es an den Pfad dran. Dann das nächste usw., bis kein Feld mehr im Pool ist. Dann wird der Pool einfach neu befüllt. Das wäre in meinen Augen die sicherste Methode, für eine gleichmäßige Verteilung zu sorgen.

An dem Problem hänge ich schon ewig. Habt Ihr irgendeine Idee, wie man das stabil kriegen könnte ? Der Algorithmus macht Mist und ist in meinen Augen so zwar die einzige Idee, die ich habe, aber dennoch einfach nicht gut. Wer den Algorithmus sehen will (er ist riesig, dafür benötigt man viel Zeit um das zu verstehen denke ich), gerne, ich würde ihn dann kompilierbar machen etc., aber darauf kommt es mir nicht an. Mir geht es erstmal darum, die Laufzeit des Algorithmus' in den Griff zu kriegen, ihn mit einer besseren Idee neu zu programmieren. Daher wäre die Analyse des Algorithmus' eventuell Zeitverschwendung.

Gruß,
Nils

_________________
Meine Musik: spiker-music.net

Da die Pfadlänge vorgegeben ist, ist dies in der Tat keine einfache Aufgabe.

Meine spontane Idee für deine Punktelevels wäre ein Pattern-Ersetzer. D.h. du startest mit einem ganz einfachen Pfad:
x x x x
x 0 0 x
x 0 0 x
x x x x

Nun könnte man etwa nach dem folgenden Pattern suchen:
0 ? 0 0
? x 0 0
0 x 0 0
? x 0 0
0 ? 0 0
Dabei ist das "?" ein Joker, d.h. an der entsprechenden Stelle darf alles sein. Wenn das Pattern irgendwo gefunden wurde, wird es z.B. durch das folgende neue Pattern ersetzt:
0 ? 0 0
? x x 0
0 0 x 0
? x x 0
0 ? 0 0
An Stelle der Joker bleibt einfach das was vorher da war. In diesem Fall hat sich durch Anwendung der Regel die Länge der Strecke um zwei erhöht. Der Punkt ist das eine gültige Strecke durch Anwendung einer Regel in eine neue längere gültige Strecke überführt wird.

Ich denke wenn du dir 5-10 derartige Pattern ausdenkst (jeweils in allen 4 möglichen Rotationen) kriegst du brauchbare Strecken raus. Also der Basis-Algorithmus wäre etwa so:
1. Wähle zufällig ein Pattern aus.
2. Finde alle Stellen der aktuellen Strecke auf die dieses Pattern passt.
3. Wähle zufällig eine Stelle aus und ersetzte das Pattern durch das neue Pattern.
4. Wenn benötigte Streckenlänge noch nicht erreicht, weiter bei 1.

Neben dem Joker ("?") wäre wahrscheinlich ein Inverse-Joker hilfreich. Damit könnte man dann ein X auf der Strecke zu einer 0 machen und umgekehrt.

_________________
Yeah!

Die Erklärung zu den Punktelevels habe ich nicht verstanden und du könntest nochmal deutlicher schreiben, welche Bedingungen es für den Pfad alle gibt.
Er soll von einer Seite zu einer der drei anderen gehen?
Er soll eine Mindestlänge haben?
das Spielfeld ist exakt 4x4 Felder groß?

Ich denke, es handelt sich um ein graphentheoretisches Problem.

Vielleicht geht es ja so:

Man markiert alle Felder als begehbar und sucht sich zufällig einen Startpunkt.
Dann ändert man zufällig ein Feld in "nicht begehbar". Per Tiefensuche testet man dann ob noch ein Weg/Kreis mit einer Länge größergleich deiner minimalen Streckenlänge existiert. Falls nicht macht man die Änderung rückgängig und wählt zufällig ein anderes Feld (am besten nicht das selbe ).
Das wiederholt man solange bis man keine Felder mehr ändern kann, ohne das die Bedingung von oben erfüllt ist.