Algorithmus gesucht!

Computer: Software & Programmierung C/C++
#1

Hallo erstmal.

Ich habe folgendes Problem: Ich versuche zur Übung ein kleines textbasiertes Rollenspiel (im Stile von Pen&amp:stuck_out_tongue_winking_eye:aper-Rollenspielen wie Dungeons&Dragons) auf die Beine zu stellen. Soweit klappt das schon ganz gut, Kampfsystem und diverse Gegenstände habe ich bereits erfolgreich implementiert, nur das Würfeln bereitet mir noch sorgen (mit dem aktuellen Algorithmus ist es anscheinend nicht möglich, mit 2 6-seitigen Würfeln eine 12 zu würfeln, sehr wohl aber mit einem 6-seitigen Würfel eine 6, aber ich denke, das kriege ich noch geregelt). Nun habe ich aber ein Problem mit den Dungeons. Als „Karte“ der Dungeons soll mir dabei eine zufällige Matrix dienen. Die einträge der Matrix geben dabei vor, wo ich hin kann und wo nicht. Als Beispiel eine kleine 3x3-Matrix:

0 8 0
7 F 7
0 1 0

Die 7 bedeutet hier, dass ich nach Westen und nach Osten kann, die 1 bedeutet, ich kann nur nach Norden, die 8, dass ich nur nach Süden kann. F bedeutet, ich kann in alle Richtungen, 0 bedeutet, ich kann das Feld weder verlassen, noch betreten. Wie ihr seht, sollen die Wwerte der Matrix also voneinander abhängen, es soll aber gelten, dass über und unter einer 7 nur eine 0 stehen darf. Ebenso dürfen in Nachbarschaft bestimmter Werte nur Werte stehen, die einen Rückweg auf das ursprüngliche Feld erlauben. Z.B. soll unter einem F keine 8 stehen dürfen, da ich von der 8 aus nicht nach Norden kann. Die werte sehen folgendermaßen aus (die Richtungsangaben beziehen sich auf die Bewegungsmöglichkeiten, wenn man auf dem Feld steht):

0 = nicht verlassbar
1 = nach Norden
2 = nach Norden und Osten
3 = nach Norden und Süden
4 = nach Norden und Westen
5 = nach Osten
6 = nach Osten und Süden
7 = nach Osten und Westen
8 = nach Süden
9 = nach Süden und Westen
A = nach Westen
B = nach Norden, Osten und Westen
C = nach Norden, Osten und Süden
D = nach Osten, Süden und Westen
E = nach Norden, Süden und Osten
F = alle Richtungen

Über einen Lösungsansatz würde ich mich sehr freuen. Bisher funktioniert das Spiel ganz gut, ich habe aber bisher nur vorgefertigte Matrizen als Karten benutzen können und es liegt nahe, die Dungeons zufällig mit einem Algorithmus entwickeln zu lassen, falls das möglich ist, statt den Code, bzw. Datenbanken, künstlich mit vielen „handgemachten“ Matrizen aufzublähen.

MfG,

TheSedated

#2

Hallo TheSedated,

0 = nicht verlassbar
1 = nach Norden
2 = nach Norden und Osten
3 = nach Norden und Süden
4 = nach Norden und Westen
5 = nach Osten
6 = nach Osten und Süden
7 = nach Osten und Westen
8 = nach Süden
9 = nach Süden und Westen
A = nach Westen
B = nach Norden, Osten und Westen
C = nach Norden, Osten und Süden
D = nach Osten, Süden und Westen
E = nach Norden, Süden und Osten
F = alle Richtungen

Zuerst würde ich diese Tabelle Binär aufbauen.
1D = 0001B = nach Norden
2D = 0010B = nach Osten
4D = 0100B = nach Süden
8D = 1000B = nach Westen

z.B. 1+2 = 3 bedeutet dann nach Norden und Osten.
Du kannst dann einfacher mit Bit-Operatoren abfragen, z.B. darf in der ersten Zeile nirgends Bit 1 gesetzt sein, da man mit „nach Norden“ vom Spielbrett fallen würde.

MfG Peter(TOO)

#3

Hmm… sowas in der Richtung habe ich mir schon gedacht. Also eventuell die Zahlen etwas anders auf die möglichen Richtungen anordnen, um da Additionen usw. zu ermöglichen. Mein Ansatz war jetzt auch, das Ganze zeilenweise aufzubauen, also eine Zeile nach der anderen entwickeln, oder gegebenenfalls nach Zeilen oder Spalten aufzubauen (immer nur von Norden nach Süden da durchzulatschen ist ja auch doof). Aber damit beschäftige ich mich später wohl, hauptsache ich krieg mal einen Algorithmus zusammengebastelt, der mir überhaupt mal einen funktionierenden Dungeon ausgibt. Aber danke schonmal!

#4

Narf, jetzt habe ich geantwortet und habe was vergessen… 1 in der obersten Zeile ist erlaubt, ich muss den Dungeon ja auch verlassen können. ^^ Wenn ich die Dungeonmatrix in eine größere F-Matrix (also quasi freie Fläche) einbaue, kann ich den Dungeon verlassen und die Gebiete zwischen den Dungeons auffüllen, u.a. mit Händlern und Städten (Händler als Random-Ereignisse, Städte als feste Punkte innerhalb der großen F-Matrix).

#5

Hallo Fragewurm,

Narf, jetzt habe ich geantwortet und habe was vergessen… 1

Am besten suchst du dir mal ein warmes Plätzchen, Papier und einen Bleistift.

Dort schreibst du dir mal alle Bedingungen und die Wenn und Abers auf. Wenn du damit fertig bist hast du eigentlich deinen Algorithmus und musst den nur noch so umformulieren, dass ihn auch dein Computer versteht :wink:

MfG Peter(TOO)

#6

Hallo TheSedated,

du benötigst einen Algorithmus, der nur gültige Dungeons erzeugt. Lies Dir mal Breitensuche durch, http://de.wikipedia.org/wiki/Breitensuche

Würde folgenden Ansatz vorschlagen, nenne ihn Maulwurf-Algorithmus:

Starte am Eingang, bewege den Maulwurf in eine zufällige Richtung.
Auf dem nächsten Feld wird folgende Entscheidung ausgewürfelt:

  1. Gleiche Richtung weitergehen, mit Wahrscheinlichkeit 12/16
  2. Nach Links abbiegen, mit W’keit 1/16
  3. Nach Rechts abbiegen, mit W’keit 1/16
  4. Eine T-Kreuzung einfügen, Maulwurf teilt sich in 2 zwei unabhängige Maulwürfe auf, mit W’keit 1/16
  5. 4er Kreuzung einbauen -> 3 Maulwürfe, mit W’keit 1/16
    Falls der Maulwurf auf ein bereits gegrabenes Feld trifft,
    wird entsprechend eine Kreuzung eingebaut, oder eine Sackgasse gebildet, evt. Würfeln. Der Maulwurf wird dann entfernt.

Je nachdem, wie die Wahrscheinkeiten gewählt werden, düften die Dungeons anders aussehen. Da hab ich jetzt keine Erfahrungswerte :smile:

Zusätzlich könnte man noch eine Bewertungsfunktions einbauen (Jeder Dungeon soll mind. zwei Kreuzungen enthalten, oder ähnlich). Falls Dungeon durchfällt, einfach nochmal erzeugen.

Hoffe, dass Hilft Dir weiter …

Grüße
McGee