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!

Bejeweled Algorithmus

  • 1
  • 2

Werbeanzeige

xxendlessxx

Treue Seele

  • »xxendlessxx« ist der Autor dieses Themas

Beiträge: 230

Wohnort: Bad Schussenried

Beruf: Full Stack Developer

  • Private Nachricht senden

1

23.11.2010, 00:07

Bejeweled Algorithmus

Guten Morgen Leute,

arbeite gerade an meinem Bejeweled Klon und hab mich gefragt wie ich den Algorithmus dafür auslege. Bei meiner alten Version war es so das ich, sobald 2 Steine zum Verschieben angeklickt wurden, einfach nur die Steine Links und Rechts auf gleiche Farbe überprüft habe. Im Original wird ja das komplette Spielfeld geprüft. Horizontal sowie Vertikal ob mehr als 3 Steine in einer Reihe liegen. Wie würdet ihr daran gehen? Achja mein Spielfeld besteht aus List<List<int>> int[,] und die Elemente können Werte von 0 bis 4 haben.

gruß michi

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »xxendlessxx« (23.11.2010, 18:27)

Schrompf

Alter Hase

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

2

23.11.2010, 08:24

Ich würde einen std::vector(breite*hoehe) draus machen, denn Listen sind ganz ganz mies, wenn es um wahlfreien Zugriff anhand eines Indexes geht. Ansonsten sehe ich kein Problem darin, das ganze Feld zu prüfen - spätestens bei Kettenreaktionen musst Du das eh tun.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

3

23.11.2010, 09:00

Man muss nicht zwangsweise das ganze Spielfeld prüfen. Alle veränderten Felder (inklusive der Umgebungsprüfung, die man ja braucht) ist ausreichend. Allerdings ist der Aufwand diese Selektion zu bestimmt am Ende vermutlich auch nicht viel schneller als gleich das ganze Feld zu prüfen. Dürfte ja auch kein Problem sein das ganze Feld zu prüfen, da die Komplexität ja auch nur linear zur Anzahl der Felder ist.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

4

23.11.2010, 10:16

Auf was muss das denn laufen, damit der Algo so optimal sein muss. Und wenn der Algo so optimal sein muss, wie kannst du dir so unsinniges Zeug wie list<list<>> erlauben?

Premature optimization wohl mal wieder.

Ansonsten set machen, in dem alle geaenderten Felder gesucht werden, dann brauch man nicht alle Felder testen.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

xxendlessxx

Treue Seele

  • »xxendlessxx« ist der Autor dieses Themas

Beiträge: 230

Wohnort: Bad Schussenried

Beruf: Full Stack Developer

  • Private Nachricht senden

5

23.11.2010, 16:11

Das ganze ist in C# und XNA geschrieben. Darum List<List<int>> :D Das hab ich extra nicht dazu geschrieben da ich ja einen allgemeinen Lösungsansatz wollte. Da das Spielfeld Variabel bleiben sollte hab ich das eben in eine Liste gepackt. Sollte es bei C# ne bessere Möglichkeit geben bin ich dafür offen.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »xxendlessxx« (23.11.2010, 16:17)

NachoMan

Community-Fossil

Beiträge: 3 885

Wohnort: Berlin

Beruf: (Nachhilfe)Lehrer (Mathematik, C++, Java, C#)

  • Private Nachricht senden

6

23.11.2010, 16:26

Zitat von »xxendlessxx«

Sollte es bei C# ne bessere Möglichkeit geben bin ich dafür offen.

ein ganz normales array vielleicht?
ich kann dir gerne meinen algo (in c++) geben.
"Der erste Trunk aus dem Becher der Erkenntnis macht einem zum Atheist, doch auf dem Grund des Bechers wartet Gott." - Werner Heisenberg
Biete Privatunterricht in Berlin und Online.
Kommt jemand mit Nach oMan?

Mastermind

unregistriert

7

23.11.2010, 16:50

Zitat von »xxendlessxx«

Das ganze ist in C# und XNA geschrieben. Darum List<List<int>> :D Das hab ich extra nicht dazu geschrieben da ich ja einen allgemeinen Lösungsansatz wollte. Da das Spielfeld Variabel bleiben sollte hab ich das eben in eine Liste gepackt. Sollte es bei C# ne bessere Möglichkeit geben bin ich dafür offen.



Das was in C++ list heißt, heißt in C# LinkedList. TGGC hat Groß/Kleinschreibung missachtet und dein "List<List<int>>" als "list<list<>>" gelesen.

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

8

23.11.2010, 18:12

Zitat von »Mastermind«

Das was in C++ list heißt, heißt in C# LinkedList. TGGC hat Groß/Kleinschreibung missachtet und dein "List<List<int>>" als "list<list<>>" gelesen.
D.h. eine List ist kein Liste sondern ein Array? Die doppelte Verschachtelung waere trotzdem unnoetig, wenn man denn so einen ganz toll optimierten Algo braeuchte (Aber warum dann C#?). Die liese zu, dass alle Listen/ Arrays ungleiche Laengen haben, was die Zugriffe dann unnoetig kompliziert macht.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

xxendlessxx

Treue Seele

  • »xxendlessxx« ist der Autor dieses Themas

Beiträge: 230

Wohnort: Bad Schussenried

Beruf: Full Stack Developer

  • Private Nachricht senden

9

23.11.2010, 18:24

Ist ja jetzt nicht mehr schlimm. Ich hab nun aus dem Spielfeld ein Array gemacht was zur Initialisierung variable Werte bekommen kann. Das mit den Listen ist nun gestrichen.

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

10

23.11.2010, 20:57

Zitat von »TGGC«

D.h. eine List ist kein Liste sondern ein Array?.

Nein, das heißt eine C#-Liste ist eine List mit wahlfreiem Zugriff in O(1), also in etwa ein C++ Vektor.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Werbeanzeige

  • 1
  • 2

Ähnliche Themen