Breitensuche

  • Hi,
    ich hab jetzt auch mal wieder ein Problem.
    Vor einiger Zeit wollte ich das mal in Delphi lösen, habe es damals aber genauso wenig hinbekommen wie heute :P.

    Also, ich habe ein Spielfeld (in einem Array).
    (Blaue Felder = Spielfeld = 0 ; Komplett gelbes Feld = Ziel = 2 ; Violett = Blockade = 1 [kann man nur "knacken" wenn man genau drauf kommt])

    [Blockierte Grafik: http://img523.imageshack.us/img523/8743/bild2ap8.jpg]

    Mein Würfel hat für mich die Zahl 5 gewürfelt.
    Die Spielfigur (schwarzer Punkt) steht auf einem Punkt im Spielfeld. Es gibt bei der Augenzahl 5 4 Möglichkeiten die Figur zu bewegen.

    So, jetzt brauche ich einen Algorithmus, der mir die möglichen Positionen ausgibt.

    Man hat mir gesagt Breitensuche würde hier helfen. Ich verstehe auch den Sinn des Algorithmus, aber eigentlich ist der doch dafür gedacht um die kürzesten Wege zu finden.
    Wie soll ich den jetzt aber anwenden, dass er mir die möglichen Wege zurückgibt?

    Ich kann leider auch keinen Anfangscode liefern, weil ich einfach nicht weiß wie ich es umsetzen soll.
    Ein Pseudocode oder eine kleine Erklärung würde mir schon voll und ganz reichen für den Anfang :).

    Dankeschön ;)

  • Hi,
    Also mit Spielstein meinst du einfach meine Spielfigur?

    Ja, die darf sich nach allen Richtigen bewegen, solange sie auf dem Weg bleibt.

    Die Violetten Felder sind Blockaden. Man darf die Blockaden nicht überschreiten. Wenn man mit der Würfelzahl genau auf die Blockade kommt, dann darf man die Blockade verschieben.
    Andere Spieler könne wie bei Mensche-ärgere-dich-nicht "gefressen" werden. Ansonsten kann man sie ganz einfach überspringen. Man kann sich auf dem ganzen Spielfeld bewegen, sowohl vorwärts wie auch rückwärts, nur die Richtung, die beim ersten rücken genommen wurde muss logischerweise beibehalten werden.

    Aber die Blockaden und Spielerabfrage usw. kann ich auch selber einbauen, mir geht es eher um die Möglichkeit des Algorithmus. Denkt euch die Blockaden einfach weg.

    Falls es doch noch jemanden interessiert, es handelt sich um das Spiel Malefiz

    Danke!

  • Malefiz liegt hier als Holzspielzeug mit farbigen Holzdübeln :D Früher ewig gespielt :rolleyes:
    Es fehlt in dem Bild der Startbereich wo die Spieler reinwürfeln aber bekannt kam es mir schon irgendwie vor.

    Achtung Anfänger! :whistling:

    Betrachten des Quellcodes auf eigene Gefahr, bei Übelkeit,Erbrechen,Kopfschmerzen übernehme ich keine Haftung. 8o

    • Offizieller Beitrag

    Ich würde so herangehen, dass jedes Feld Statuswerte bekommt, die Auskunft geben über Belegung und mögliche Bewegungsrichtungen. Sinnvollerweise jeden Parameter als Dualwert, sodass ganz simpel per BitAnd() abgefragt werden kann.

    Code
    Felder erhalten Werte, z.B.
    1   - Spielfeld
    2   - Eigener Spieler
    4   - Gegenspieler
    8   - Blockade
    16  - Ziel
    32  - Richtungsvektor  3 Uhr
    64  - Richtungsvektor  6 Uhr
    128 - Richtungsvektor  9 Uhr
    256 - Richtungsvektor 12 Uhr
  • Ja,
    ok, das wäre schon mal eine Super Möglichkeit die Möglichen Richtungen zu speichern.
    Damit wäre ein 1. Schritt schon mal getan.

    Nur mein Algorithmus muss ja alle Möglichkeiten ausprobieren.

    Das ist ja Praktisch nur Brute Force. Ich weis nur nicht, wie ich auf die anderen Lösungen kommen soll.

    1. Wenn nach oben möglich, dann prüfe Feld oben drüber.
    2. Wenn von dort aus nach oben nicht möglich, dann prüfe Feld rechts.
    usw. ...

    Jetzt muss ich ja aber irgendwie die Felder speichern, die ich gar nicht ausprobiert habe und in einem neuen Schritt auch diese Prüfen, bis ich wirklich alle Möglichkeiten durchgeackert habe.
    Nur da hängts leider :(.

    Kannst du oder irgendjemand auch hier eine Anstupser geben :D ?

  • na also ich würde vllt ein 2dimensionales array nehmen

    und dann ist 0 0 halt links oben und 16 16 rechts unten

    und dann immer so:
    sagen wir mal die erste dimension ist X die 2. Y
    spielstein auf 1 2
    wenn 0 2 = wahr
    wenn 2 2 = wahr
    wenn 1 1 = falsch
    wenn 1 3 = wahr...

    ;0 2 = wahr
    wenn 1 2 = wahr
    wenn 0 1 = wahr
    wenn 0 3 = wahr

    usw usw...

    und dann muss man halt in einer rekursiven funktion, bzw. einer schleife alle möglichkeiten ausprobieren

    was besseres fällt mir net ein aber ich bin in solchen sachen (algos) nicht grade geübt^^... ist halt eine aufgabe für die cracks :D

    MFG FireFlyer

    *Paradox ist, wenn man sich im Handumdrehen den Fuss bricht* :D

  • Hi,
    ja, dass das so ablaufen muss, ist mir auch klar, dafür hab ich das Array ja auch erstellt ;).

    Ich hatte nur gehofft jemand würde sich damit ein bisschen auskennen, deshalb seht das mal als ganz leichten *push* an :).

    Falls wirklich niemand sonst ne Ahnung hab, muss ich das wohl aufgeben und noch ein bisschen lernen, bis ich sowas auch alleine auf die Reihe bekomme.

    Aber danke für die bisherige Hilfe, wo ja schon gut Ansätze dabei waren :).

  • Hi :),

    Ich habe mich heute mal wieder mit meiner Frage, die ich letztens gestellt habe beschäftigt.
    Das ist meine erste rekursive Funktion, bei der ich sagen würde, Iterativ wäre es zu kompliziert (ich wüsste jedenfalls nicht wie :P) und ich auch den Sinn erkenne.

    Spoiler anzeigen
    [autoit]

    #include <Array.au3>

    [/autoit] [autoit][/autoit] [autoit]

    Dim $ergebnisarray[1][2]

    [/autoit] [autoit][/autoit] [autoit]

    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ; Spielfeld ;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    Dim $spielarray[14][17]
    Global $string = StringSplit("xxxxxxxx1xxxxxxxx111111111111111111xxxxxxxxxxxxxxx111111111111111111xxxxxxxx1xxxxxxxxxxxxxx11111xxxxxxxxxxxx1xxx1xxxxxxxxxx111111111xxxxxxxx1xxxxxxx1xxxxxx1111111111111xxxx1xxxxxxxxxxx1xx111111111111111111xxx1xxx1xxx1xxx111111111111111111", "")
    Global $counter = 1, $counter2 = 0

    [/autoit] [autoit][/autoit] [autoit]

    For $j = 0 To 13
    For $i = 0 To 16
    $spielarray[$j][$i] = $string[$counter]
    $counter += 1
    Next
    Next
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ; ;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    _ArrayDisplay($spielarray, "Spielfeld")
    _getpos(5, 13, 13)
    _ArrayDisplay($ergebnisarray, "Feld:13-13 ; Wuerfel:5")

    [/autoit] [autoit][/autoit] [autoit]

    Func _getpos($dice, $posx, $posy, $direction = 0)
    If ($posx <= 13) And ($posy <= 16) And ($dice <= 6) Then
    If $dice = 0 Then
    ReDim $ergebnisarray[$counter2 + 1][2]
    $ergebnisarray[$counter2][0] = $posx
    $ergebnisarray[$counter2][1] = $posy
    $counter2 += 1
    Return
    Else
    Switch $direction
    Case 0
    If (($posx + 1) <= 13) And ($posy <= 16) And $spielarray[$posx + 1][$posy] <> 'x' Then _getpos($dice - 1, $posx + 1, $posy, 1)
    If (($posx - 1) <= 13) And ($posy <= 16) And $spielarray[$posx - 1][$posy] <> 'x' Then _getpos($dice - 1, $posx - 1, $posy, 2)
    If (($posx) <= 13) And ($posy + 1 <= 16) And $spielarray[$posx][$posy + 1] <> 'x' Then _getpos($dice - 1, $posx, $posy + 1, 3)
    If (($posx) <= 13) And ($posy - 1 <= 16) And $spielarray[$posx][$posy - 1] <> 'x' Then _getpos($dice - 1, $posx, $posy - 1, 4)
    Case 1
    If (($posx + 1) <= 13) And ($posy <= 16) And $spielarray[$posx + 1][$posy] <> 'x' Then _getpos($dice - 1, $posx + 1, $posy, 1)
    If (($posx) <= 13) And ($posy + 1 <= 16) And $spielarray[$posx][$posy + 1] <> 'x' Then _getpos($dice - 1, $posx, $posy + 1, 3)
    If (($posx) <= 13) And ($posy - 1 <= 16) And $spielarray[$posx][$posy - 1] <> 'x' Then _getpos($dice - 1, $posx, $posy - 1, 4)
    Case 2
    If (($posx - 1) <= 13) And ($posy <= 16) And $spielarray[$posx - 1][$posy] <> 'x' Then _getpos($dice - 1, $posx - 1, $posy, 2)
    If (($posx) <= 13) And ($posy + 1 <= 16) And $spielarray[$posx][$posy + 1] <> 'x' Then _getpos($dice - 1, $posx, $posy + 1, 3)
    If (($posx + 1) <= 13) And ($posy - 1 <= 16) And $spielarray[$posx][$posy - 1] <> 'x' Then _getpos($dice - 1, $posx, $posy - 1, 4)
    Case 3
    If (($posx + 1) <= 13) And ($posy <= 16) And $spielarray[$posx + 1][$posy] <> 'x' Then _getpos($dice - 1, $posx + 1, $posy, 1)
    If (($posx - 1) <= 13) And ($posy <= 16) And $spielarray[$posx - 1][$posy] <> 'x' Then _getpos($dice - 1, $posx - 1, $posy, 2)
    If (($posx) <= 13) And ($posy + 1 <= 16) And $spielarray[$posx][$posy + 1] <> 'x' Then _getpos($dice - 1, $posx, $posy + 1, 3)
    Case 4
    If (($posx + 1) <= 13) And ($posy <= 16) And $spielarray[$posx + 1][$posy] <> 'x' Then _getpos($dice - 1, $posx + 1, $posy, 1)
    If (($posx - 1) <= 13) And ($posy <= 16) And $spielarray[$posx - 1][$posy] <> 'x' Then _getpos($dice - 1, $posx - 1, $posy, 2)
    If (($posx) <= 13) And ($posy - 1 <= 16) And $spielarray[$posx][$posy - 1] <> 'x' Then _getpos($dice - 1, $posx, $posy - 1, 4)
    EndSwitch
    EndIf
    EndIf
    EndFunc ;==>_getpos

    [/autoit]

    Das ist meine Lösung, ohne mir weiter über irgendwelche Suchalgorithmen Gedanken zu machen ;).
    Aber dann will ich mich zum Schluss noch bei allen bedanken die mit geholfen haben...
    Ich werde auf jeden Fall noch BugFix's Vorschlag mit BitAND einbauen :thumbup: .
    Bei der Abfrage von Links/Rechts/Oben/Unten kann ich BitAND allerdings nicht benutzen, da man die Blockaden verschieben kann und dann die angaben nicht mehr stimmen würden.

    Aber ansonsten gut zu gebrauchen.

    Falls noch jemand was besser machen würde, dann kann er das ruhig schreiben 8) .

    Danke nochmal
    anno2008 :)