• [Battle Snakes] Aufgetaut! 15.07.2015 - 21:50 0

    Hi Community!

    Nachdem mein Projekt Battles Snakes so lange auf Eis lag, habe ich mich entschieden, es wieder aufzutauen. Seit vorletzter Woche arbeite ich wieder daran und es hat sich auch schon "einiges" getan. Allerdings nicht direkt am Spiel selber, sondern ich habe begonnen, einen Map-Editor für Battle Snakes zu entwickeln. Nicht, dass das Spiel in der Phase dringend einen Editor benötigt, aber ich hatte gerade bock einen zu basteln und zum "wieder-rein-kommen-in-die-entwicklung" schadet es ja bekanntlich nicht, an etwas zu arbeiten, was einen gerade besonders interessiert.

    Der Editor ist in Python geschrieben und bettet ein Pygame-Fenster in eine Tk GUI ein. Da ich wenig bis gar keine Erfahrung mit Tk habe und völlig planlos vorgegangen bin, ist bei der Entwicklung einiges schief gegangen und ich fürchte, das wohl oder übel ein großes Refactoring ansteht bevor sinnvoll neue Features hinzugefügt werden können. Nichtsdestotrotz können mit dem Editor Maps erstellt werden, die in Battle Snakes funktionieren.

     

    Der Editor in Aktion

     

    Bevor ich Battle Snakes Ende Februar diesen Jahres auf Eis gelegt hatte, war ich mit der Entwicklung der KI des Bots beschäftigt. Dabei hab ich den ersten Versuch, der den Pathfinding-Algorithmus A* genutzt hat, über den Haufen geworfen und mich den sogenannten Potential Fields zugewandt.  Potential Fields kann man sich vorstellen als Felder, die entweder abstoßend oder anziehend sind, wie z.B. Magnetfelder. Im Falle von Battle Snakes generieren die Wände ein abstoßendes Feld und das "Food" bzw. die Power-Ups (oder einfach das Ziel) ein anziehendes. Für jede Zelle im Raster (Battle Snakes ist komplett rasterbasiert) wird dann ein Wert berechnet, der anzeigt, wie günstig dieses Zelle für den Bot ist. Umso näher an einer Wand umso geringer der Wert. Umso näher am Ziel, desto höher.

    Mit diesem erstaunlich einfachem Algorithmus lässt sich in der Tat eine Wegfindung realisieren, die allerdings ein gravierendes Problem hat - das sogenannte "Local Optima". Dieses entsteht, wenn sich der Bot direkt vor einer Wand und sich das Ziel direkt auf der anderen Seite der Wand befindet. Dadurch ist die günstigste Zelle direkt vor der Wand, obwohl der Weg um die Wand herumführt! Resultat: Der Bot steckt fest. Für dieses Problem gibt es verschiedenste Lösungsansätze: Z.B. könnte man mit A* einen Weg um die Wand herum suchen, wenn der Bot in einem Local Optima feststeckt.
     

    Potential Field im Einsatz - die rote Snake findet ihr Ziel (Bei den grünen Punkten handelt es sich um Food)

     

    Ein Vorteil von Potential Fields ist es, das sich damit sehr leicht ein Chase-and-Evade Verhalten basteln lässt (zumindest in der Theorie).

    Dafür dürfte es wesentlich schwerer sein, auch Portale und die torusförmige Map (oben raus, unten rein) zu nutzen. Mit A* lies sich dies im Falle der torusförmigen Map relativ einfach lösen.

    Der Bot hat sich hier nicht das nächste, sondern ein zufälliges Ziel gesucht

     

    Der Nachteil von A* ist allerdings, dass es (zumindest meine Implementation) nicht besonders performant ist. Auch Multithreading hilft hier nicht besonders viel, da der Python-Interpreter nur einen Prozessorkern nutzen kann und sich somit die Threads nur abwechseln als hätte der Prozessor nur einen Kern. Das Bild zeigt zwar 60 FPS, diese brechen aber kurzzeitig auf 30 ein, wenn der Bot einen neuen Pfad sucht. Ohne Multithreading gibt es sogar einen kleinen Ruckler. Da Battle Snakes mehrere Bots auf einmal unterstützen soll, sehe ich das mit der Performance kritisch. Aus diesem Grund werde ich als nächstes versuchen das Local Optima Problem zu lösen, um endlichen mit dem Bot weiter zu kommen.

     

    Das war's soweit zu Battle Snakes. Sobald eine neue, spielbare Version (mit hoffentlich funktionierendem Bot) fertig ist, werde ich diese auch anständig für Windows packen, so dass sich die Windows-User nicht mit irgendwelchen Installationen herumschlagen müssen.

     

    Wenn euch der Post gefallen hat und ihr in Zukunft öfter (technische) Einblicke in die Entwicklung von Battle Snakes haben wollt, so schreibt es in die Kommentare.

     

    Battle Snakes ist übrigens open source und auf Github

     

    #python #pygame #battle-snakes #opensource #ki #ai #a* #wegfindung #pathfinding #snake #potentialfields


    Kommentare: 1