Spielproblem...

[sirbender]

Hi,

ich programmiere gerade ein Spiel und muss dafuer folgendes Problem am effizientesten Loesen. Ein grosser Teil der Effizienz ist Zeit das Ergebnis zu bekommen ein weiterer Teil ist die Qualitaet des Ergebnisses.

Ich erklaere mal das Problem und nicht das Spiel selbst.

Ich habe ein Spielfeld mit 1000x1000 Quadraten gleicher Groesse.
Nun habe ich Objekte unterschiedlichster Form, die jedoch auch als Quadrate beschrieben werden koennen.

Das erste Objekte wird in der Mitte des Spielfelds platziert. Das zweite und alle darauffolgenden Objekte sollen nun so platziert werden dass sie
1. moeglichst Nahe am Mittelpunkt sind und
2. sie duerfen kein Quadrat bedecken das bereits von einem anderen Objekt bedeckt ist.

Bisher habe ich recht dumm die Objekte ein bischen weitergeschoben und geschaut ob sie mit einem anderen Objekt ueberlappen. Wenn nicht kommt das Objekt zum liegen und das naechste Objekt wird getestet.

Ich habe mich gefragt ob das nicht effizienter geht. Im Grunde genommen kennt man das ganze Spielfeld. Man weiss welches Quadrat belegt ist und welches frei ist. Gibt es eine Methode um direkt (ohne Ausprobieren) zu sagen, wo sich die dem Mittelpunkt am naehesten freie Flaeche befindet in die, ein ObjektX (5430 Quadraten mit bekannter Form), passt?


Danke,
sb

 

[diggaa1984]

zeig mal den code dazu ... mehr als rumrechnen und zaehlen bleibt dir net übrig, test auf Schnitt muss meiner meinung nach nicht sein, wenn die quadrate alle gleich gross sind

 

[Marco13]

Solche Fragen wie z.B. ob die Objekte immer konvex sind könnten da nicht ganz unwichtig sein.

 

[Michael...]

Ich weiss zwar nicht, ob ich das Problem richtig verstanden habe.

Man könnte die Quadrate als eigenes Objekte definieren, die u.a. ein Attribut besitzen, das den Abstand zur Mitte angibt. Diese Objekte steckt man in eine Liste und sortiert sie nach ihrem Abstand. Wird ein Quadrat belegt, entfernt man es aus der Liste.
- damit würde man den Berechnungsaufwand (Abstand bestimmen und sortieren) in die Initialisierung verlagern
- durch die Liste weiss man genau welche Quadrate noch frei sind und erspart sich die ständige Suche und Überprüfung
- die Quadrate, die frei und der Mitte am nächsten sind, stehen in der Liste an erster Stelle

 

[sirbender]

Ich weiss jetzt nicht was du mit konvex meinst. Also ich versuche mal mit ASCII ein Objekt darzustellen:

####   ###
##     #####
 ########
##### ###
### #######
         #######
         #####

Also, jedes '#' ist ein Quadrat. Das Spielfeld besteht aus 1000x1000 Quadraten. Am Anfang ist das Spielfeld leer. Dann wird nacheinander ein Objekt platziert und zwar so, dass es sich moeglichst nahe am Mittelpunkt befindet (ungefaehr, muss nicht die global optimale Loesung sein) und dass es nicht mit einem bereits gesetzen Objekt ueberlappt.

Ein ungefahere Loesung reicht mir aus. Bisher mach ich es halt iterativ. Ich setze jedes Objekt auf den Mittelpunkt und teste ob es mit einem bereits geetzten Objekt ueberlappt. Wenn ja, schiebe ich es zufaellig in eine Richtung und teste nochmal auf Ueberlappung. Irgendwann ueberlappt es nicht mehr und hat somit seine Position. Durch diese Methode suche ich praktisch durch ausprobieren wo eine freie Stelle moeglichst nahe dem Mittelpunkt ist die gross genug ist, damit mein Objekt passt.

Wie finde ich eine solche dem Mittelpunkt nahe, freie Stelle effizienter? Ohne die ganze Ausprobiererei ob es ueberlappt? Eigentlich weiss ich ja, welche Quadrate des Spielfelds belegt sind und welche nicht.
Als Mensch wuerde man sich das Spielfeld anschauen und automatisch durch direktes 'Setzen' des Objekte eine recht gute freie Stelle waehlen koennen die nahe dem Mittelpunkt ist.

Danke,
sb

 

[Sotsch]

Deine Methode ist die Nadel im Heuhaufen suchen
Mein erster Gedanke war ein 2dimensionales Array, das nach dem setzen eines Steins seine Koordinaten speichert und
anhand einer abfrage den nächsten stein NICHT auf diese setzt.

so wie du das machst würde dein programm irgendwann 10 -20 minuten damit verbringen ne leere stelle zu finden, was es auch noch random macht^^

stein mittig setzen -> koordinate speichern -> nächsten stein mittig setzen außer an schon definierten Array - Einträgen -> usw.

 

[sirbender]

so wie du das machst würde dein programm irgendwann 10 -20 minuten damit verbringen ne leere stelle zu finden, was es auch noch random macht^^

Nein. 10-20 min. dauert es nicht. Auch mach ich es nicht Random. Ich bewege ein Objekt entlang eines zufaellig gewaehlten Vektors (d.h. Richtung). Ueberlappt es mit einem anderen Objekt, bewege ich es weiter in diese Richtung bis es auf einer freien Stelle liegt.

Deine Loesung versteh ich nicht.

 

[Marco13]

Also, das was du beschrieben hast klingt schon vernünftig. Als Mensch könnte man sowas vielleicht schneller, aber wenn du dir mal ein Puzzle nimmst, und es mit der Bildseite nach unten zusammensetzen willst, wirst du merken, dass du auch NUR rumprobieren kannst: Man sieht nicht unbedingt, ob's passt.

Man könnte das mit der "zufälligen" Richtung ggf. noch verbessern - z.B. in eine Richtung schieben, in der nahe dem Mittelpunkt viele freie Felder sind (an deinem Bild: Wenn das in Zeile 6 am weitesten rechts stehende Quadrat der Mittelpunkt ist, sollte man das nächste Teil nicht nach oben links, sondern eher nach unten rechts verschieben: Da ist nämlich noch nichts).

Ansonsten müßte man wissen, ob man die Teile "sammeln" kann, und wenn man alle kennt einen Algorithmus drauf loslassen, irgendeine Art Masse-Feder Modell oder gleich sowas wie Simulated Annealing ... das kann aber eben beliebig aufwändig werden....

 

[sirbender]

Man könnte das mit der "zufälligen" Richtung ggf. noch verbessern - z.B. in eine Richtung schieben, in der nahe dem Mittelpunkt viele freie Felder sind (an deinem Bild: Wenn das in Zeile 6 am weitesten rechts stehende Quadrat der Mittelpunkt ist, sollte man das nächste Teil nicht nach oben links, sondern eher nach unten rechts verschieben: Da ist nämlich noch nichts).

Ups, kleines Missverstaengnis. Wie ich oben geschrieben habe stellt die Abbildung ein Objekt dar. Ein Vorposter hatte etwas geschrieben dass mich zweifeln liess was ich mit Objekt meine. Aber eigentlich aendert auch das Missverstaendnis nichts an deiner Antwort.

Danke,
sb

 

[Cola_Colin]

Man könnte jeweils vom Mittelpunkt aus "kreisförmig" alle Quadrate durchgehen und schauen, ob sie frei sind oder nicht.
Sollte eines frei sein, könnte man zählen wie groß die freie Fläche ist, zu der es gehört. Sobald man so eine Fläche gefunden hat, die groß genug für das Objekt ist, muss man auf die Form vergleichen, passt diese ist die gesuchte Position gefunden.

Nur so mein erster Gedanke dazu, sicherlich reichlich Möglichkeiten das zu optimieren.
z.B. durch zwischenspeichern der freien Flächen in ner Liste.
d.h. zuerst hat man genau eine solche Fläche, jeweils nach dem einfügen eines Objektes wird dann getestet ob es die bisherigen Flächen in mehrere aufteilt, wenn ja wird die Liste aktualisiert.
Um nun ein Objekt hinzuzufügen geht man die Flächen durch, sucht die "beste" und gut ist.

Hab das jetzt aber nicht so weiter durchdacht