Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

2D Mustererkennung

Werbeanzeige

neido

Treue Seele

  • »neido« ist der Autor dieses Themas

Beiträge: 225

Wohnort: Wien

  • Private Nachricht senden

1

02.06.2015, 08:52

2D Mustererkennung

Hallo!
Ich programmiere gerade ein Spiel, in dem es unter Anderem darum geht, auf einem m*n Schachbrettartigen Feld Steine zu setzen und damit bestimmte Muster zu bilden. Ein Muster könnte zB ein "+" aus 5 Steinen sein (4 außen, eins in der Mitte).
Eine Naive Methode könnte jetzt sein, eine Instanz dieses Musters zu erstellen und damit über alle Positionen des Spielbretts zu "wandern" und zu sehen, ob es ein Match gibt. Da ich aber das ganze erstens gerne schön machen würde und zweitens etwas daraus lernen möchte frage ich mich, was es denn da für anerkannte, bewährte Methoden gibt.

Hier jetzt das Beispielmuster mit dem "+"

Quellcode

 
1
2
3

.#.
###
.#.

Und hier eine Beispiel-Spielsituation in der ein Match auftreten sollte

Quellcode

 
1
2
3
4
5

.......
#....#.
.#..###
##...#.
...##..


Natürlich habe ich bereits gegoogelt, aber die gefundenen Mustererkennungs-Algorithmen sind alle viel zu kompliziert, Ich habe ja kein Foto vor mir sondern einfach ein simples Schwarz-Weiß Spielfeld

anti-freak

Alter Hase

Beiträge: 635

  • Private Nachricht senden

2

02.06.2015, 09:26

Setzt du die Steine nacheinander?
An sich könnte man das dann ganz gut TicTacToe mäßig lösen. Du nimmst den zuletzt gesetzten Stein und prüfst die umliegenden Felder solange, bis du auf ein nicht gesetztes Feld stößt. Das dann eben für alle Richtungen.
Damit kannst du dir ganz gut dein momentanes Muster generieren. Für die Erkennung kämen mehrere Methoden in Frage. Kommt halt auch drauf an, wie komplex die Muster sind und wie einfach du das erweitern möchtest.

neido

Treue Seele

  • »neido« ist der Autor dieses Themas

Beiträge: 225

Wohnort: Wien

  • Private Nachricht senden

3

02.06.2015, 09:30

@anti-freak: Ich möchte mir gerne die Möglichkeit vorbehalten, beliebig große und beliebig viele Muster zu machen. In Komplexität und Menge halt maximal so groß, dass ein durchschnittlicher Spieler sich noch alle merken kann ;)
Die Steine werden nacheinander gesetzt ja. Allerdings soll es ja zB auch eine KI geben (bzw möglich sein), die tausende an möglichen Zügen durchrechnet und dabei alle Muster erkennen muss.

//Edit: Für ein "Pixel" des Musters gibt es übrigens 3 states: Belegt; Frei; Transparent(Belegt oder Frei)

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

4

02.06.2015, 10:08

Ich denke, hier spricht nichts gegen den "naiven" Ansatz, das Spielfeld Pixel für Pixel abzusuchen. Den Ansatz kannst du etwas verbessern, indem du so wie beim Knuth-Morris-Pratt-Algorithmus für String-Matching vorgehst. Dieser Algorithmus erlaubt es dir, das Suchfenster nicht immer nur um 1 zu verschieben, sondern ggf. über größere Strecken, was unnötige Tests einspart und somit die Suche beschleunigt. Diesen Algorithmus auf den 2D-Fall zu erweitern dürfte interessant sein.

Hier fragt jemand genau danach und wird auf den Rabin-Karp-Algorithmus verwiesen.

Hier noch ein Paper über das Thema: http://citeseerx.ist.psu.edu/viewdoc/dow…p=rep1&type=pdf
David Scherfgens Website | Konzentrationstest Polizei

neido

Treue Seele

  • »neido« ist der Autor dieses Themas

Beiträge: 225

Wohnort: Wien

  • Private Nachricht senden

5

02.06.2015, 10:51

Vielen Dank, David und [Anonymer Benutzer]!
@David: Das war genau das was ich gesucht habe, ich denke ich kann den Algorithmus aus dem Paper quasi direkt verwenden
@[Anonymer Benutzer]: Auch sehr interessant, das könnte in meinem Fall sogar noch effizienter sein, da meine Muster ja alle im vornherein hardcodiert sind

Werbeanzeige

Zur Zeit ist neben dir 1 Benutzer in diesem Thema unterwegs:

1 Besucher

Ähnliche Themen