1024x1024 Singlesurface für Sprites optimal ausnutzen

Übersicht

BlitzBasic

Blitz3D

	Iguan Betreff: 1024x1024 Singlesurface für Sprites optimal ausnutzen	Mi, Jan 04, 2012 13:47 Antworten mit Zitat
Hallöchen allerseits! Ich wollte mich mal erkundigen, ob ihr vielleicht eine Lösung/Lösungsansatz für mein Problem habt: Ich benutze "Sprite Candy" und muss nun die einzelnen Tiles einer Map optimal (mit möglichst wenig Platzverschwendung) auf den 1024x1024 Resource-Images (Texturen) verteilen. Mit dem mitgelieferten Image-Packer muss man das mühselig von Hand erledigen. Ich möchte daher gerne ein Programm schreiben, welches anhand einzelner BMP-Dateien (in einem bestimmten Ordner) diese Resource-Images automatisch erstellt. Die einzelnen Dateien haben immer eine Seitengrössen von 2er Potenzen (z.B 16x16, 16x32, 256x16, 32x512, 256x256 etc.... 16x16 ist dabei das Minimum). Gibt es einen Algorithmus für sowas... oder wie würdet ihr das machen? Mfg und vielen Dank! Iguan

Iguan

Betreff: 1024x1024 Singlesurface für Sprites optimal ausnutzen

Mi, Jan 04, 2012 13:47
Antworten mit Zitat

Hallöchen allerseits!

Ich wollte mich mal erkundigen, ob ihr vielleicht eine Lösung/Lösungsansatz für mein Problem habt:

Ich benutze "Sprite Candy" und muss nun die einzelnen Tiles einer Map optimal (mit möglichst wenig Platzverschwendung) auf den 1024x1024 Resource-Images (Texturen) verteilen. Mit dem mitgelieferten Image-Packer muss man das mühselig von Hand erledigen. Ich möchte daher gerne ein Programm schreiben, welches anhand einzelner BMP-Dateien (in einem bestimmten Ordner) diese Resource-Images automatisch erstellt. Die einzelnen Dateien haben immer eine Seitengrössen von 2er Potenzen (z.B 16x16, 16x32, 256x16, 32x512, 256x256 etc.... 16x16 ist dabei das Minimum).

Gibt es einen Algorithmus für sowas... oder wie würdet ihr das machen?

Mfg und vielen Dank!

Iguan

	Eingeproggt	Mi, Jan 04, 2012 14:09 Antworten mit Zitat
Wenn ich das richtig verstanden hab, willst du viele kleine Bilder zusammen in einem großen reinpacken? Geht es darum, das große Bild "möglichst gut zu nutzen", sprich möglichst viele Bilder rein zu packen? Weil dann hättest du ein Problem. mfG, Christoph.
Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9

Eingeproggt

Mi, Jan 04, 2012 14:09
Antworten mit Zitat

Wenn ich das richtig verstanden hab, willst du viele kleine Bilder zusammen in einem großen reinpacken?
Geht es darum, das große Bild "möglichst gut zu nutzen", sprich möglichst viele Bilder rein zu packen? Weil dann hättest du ein Problem.

mfG, Christoph.

Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9

	Iguan	Mi, Jan 04, 2012 14:32 Antworten mit Zitat
Ja, du hast das richtig verstanden! Dein Link verstehe ich leider nicht.. ist mir zu mathematisch es müsste etwas wie folgendes sein, nur mit Seitenlängen im 16er Rastermass: http://incise.org/2d-bin-packi...anvas.html http://pollinimini.net/demos/RectanglePacker.html Ich hab inzwischen herausgefunden, dass der Algorithmus den ich brauche 2D-Packing heissen könnte... nur hab ich keine Ahnung wie ich den in Blitz3D implementieren soll..

Iguan

Mi, Jan 04, 2012 14:32
Antworten mit Zitat

Ja, du hast das richtig verstanden! Dein Link verstehe ich leider nicht.. ist mir zu mathematisch Rolling Eyes

es müsste etwas wie folgendes sein, nur mit Seitenlängen im 16er Rastermass:

http://incise.org/2d-bin-packi...anvas.html

http://pollinimini.net/demos/RectanglePacker.html

Ich hab inzwischen herausgefunden, dass der Algorithmus den ich brauche 2D-Packing heissen könnte... nur hab ich keine Ahnung wie ich den in Blitz3D implementieren soll.. Rolling Eyes

	DerHase	Mi, Jan 04, 2012 14:37 Antworten mit Zitat
Ich würde so eine Art Tetris Algo schreiben, dabei zuerst die großen Teile "runterfallen" lassen und dann eine kleine KI die die Lücken füllt. Nicht 100% optimal, aber sollte doch gehen, glaub ich
Play Satyr!

DerHase

Mi, Jan 04, 2012 14:37
Antworten mit Zitat

Ich würde so eine Art Tetris Algo schreiben, dabei zuerst die großen Teile "runterfallen" lassen und dann eine kleine KI die die Lücken füllt. Nicht 100% optimal, aber sollte doch gehen, glaub ich Wink

Play Satyr!

	Eingeproggt	Mi, Jan 04, 2012 16:59 Antworten mit Zitat
Worauf ich hinaus wollte ist, dass ein "perfekter" Algorithmus mehr oder weniger unmöglich ist. Man braucht so "grobe" Ansätze wie sie der Hase soeben vorgeschlagen hat. Dabei sind der Phantasie mehr oder weniger keine Grenzen gesetzt wenn denn am Ende was brauchbares rauskommt mfG, Christoph.
Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9

Eingeproggt

Mi, Jan 04, 2012 16:59
Antworten mit Zitat

Worauf ich hinaus wollte ist, dass ein "perfekter" Algorithmus mehr oder weniger unmöglich ist.
Man braucht so "grobe" Ansätze wie sie der Hase soeben vorgeschlagen hat. Dabei sind der Phantasie mehr oder weniger keine Grenzen gesetzt wenn denn am Ende was brauchbares rauskommt Wink

mfG, Christoph.

Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9

	PhillipK	Do, Jan 05, 2012 0:40 Antworten mit Zitat
Ich glaube, das du zu verquer denkst. Erfahrungsgemäß tuts ein simples sortieren (versuche zb immer eine reihe voll auszunutzen und danach die 2te reihe füllen). Ich denke, es werden nicht viele "unterschiedliche" teile anfallen, sodass du viele gleiche teile hast, die du optimal auf eine Reihe bzw spalte sortieren kann. Zb 4 256x16ner teile, oben, darunter 8x 64x64 usw. Und selbst wenn es kleinere lücken gibt, ein grober algo dürfte ausreichen um mehr "optimalen platz" zu nutzen, als du es auf die schnelle mit menschlichen fähigkeiten schaffst. In blitzmax würde ich hier ein paar Tlist.sort() funktionen verwenden, ein vergleichbares gegenstück kenne ich in BB allerdings nicht. Danach wie folgt: Nach höhe sortieren - teile mit gleicher höhe nach breite sortieren.

PhillipK

Do, Jan 05, 2012 0:40
Antworten mit Zitat

Ich glaube, das du zu verquer denkst. Erfahrungsgemäß tuts ein simples sortieren (versuche zb immer eine reihe voll auszunutzen und danach die 2te reihe füllen).

Ich denke, es werden nicht viele "unterschiedliche" teile anfallen, sodass du viele gleiche teile hast, die du optimal auf eine Reihe bzw spalte sortieren kann.
Zb 4 256x16ner teile, oben, darunter 8x 64x64 usw. Und selbst wenn es kleinere lücken gibt, ein grober algo dürfte ausreichen um mehr "optimalen platz" zu nutzen, als du es auf die schnelle mit menschlichen fähigkeiten schaffst.

In blitzmax würde ich hier ein paar Tlist.sort() funktionen verwenden, ein vergleichbares gegenstück kenne ich in BB allerdings nicht.

Danach wie folgt: Nach höhe sortieren - teile mit gleicher höhe nach breite sortieren.

	D2006 Administrator	Do, Jan 05, 2012 12:23 Antworten mit Zitat
Gar keine verkehrte Idee. Aber sollte man glaub ich dahingehend ausweiten, dass man nicht nur gleichhohe Bilder in eine Zeile packt. Weil das wäre zu viel Platzverschwendung. Aber die Teile der Größe nach sortieren und immer versuchen soweit links oben wie möglich einzuordnen könnte funktionieren.
Intel Core i5 2500 \| 16 GB DDR3 RAM dualchannel \| ATI Radeon HD6870 (1024 MB RAM) \| Windows 7 Home Premium Intel Core 2 Duo 2.4 GHz \| 2 GB DDR3 RAM dualchannel \| Nvidia GeForce 9400M (256 MB shared RAM) \| Mac OS X Snow Leopard Intel Pentium Dual-Core 2.4 GHz \| 3 GB DDR2 RAM dualchannel \| ATI Radeon HD3850 (1024 MB RAM) \| Windows 7 Home Premium Chaos Interactive :: GoBang :: BB-Poker :: ChaosBreaker :: Hexagon :: ChaosRacer 2

D2006

Administrator

Do, Jan 05, 2012 12:23
Antworten mit Zitat

Gar keine verkehrte Idee. Aber sollte man glaub ich dahingehend ausweiten, dass man nicht nur gleichhohe Bilder in eine Zeile packt. Weil das wäre zu viel Platzverschwendung. Aber die Teile der Größe nach sortieren und immer versuchen soweit links oben wie möglich einzuordnen könnte funktionieren.

	BladeRunner Moderator	Do, Jan 05, 2012 13:02 Antworten mit Zitat
Ich würde erstmal versuchen einzelne teile zu finden die eine Richtung komplett belegen. Gibt es keine, werden Paare gesucht die das tun. Immer wenn man was passendes gefunden hat wird es eingebaut und der Restplatz neu berechnet.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Do, Jan 05, 2012 13:02
Antworten mit Zitat

Ich würde erstmal versuchen einzelne teile zu finden die eine Richtung komplett belegen. Gibt es keine, werden Paare gesucht die das tun. Immer wenn man was passendes gefunden hat wird es eingebaut und der Restplatz neu berechnet.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	PhillipK	Do, Jan 05, 2012 13:20 Antworten mit Zitat
Die idee funktioniert Es wird erst kritisch, wenn die teile wirklich willkürliche seitenverhältnisse haben. Bei exponenten von 2, welche auf 1024x1024 verteilt werden müssen, sollte es nur minimalsten schwund geben. Ich habe so ein system für meinen TD-BCC beitrag gebastelt, um die einheiten, tower und blöcke zu sortieren. Getestet hatte ich es mit vielen unterschiedlichen grafiken - der schwund war minimal und sicher 100x besser als wie ich es "per hand" hinbekommen habe. Grade bei 16x16, 16x32 etc (kleine teile) gibt es hinterher einen vorteil: Erst einmal sucht man sich die größten teile und fängt oben an, dann beginnt man in der 2ten, komplett freien zeile (immer Y + höhe eines teils mit der zuletzt gemerkten position vergleichen - ist der neue wert größer, den "zuletzt gemerkten" auf Y+höhe setzen. Ist eine reihe voll, bei eben diesem Y wert bei X=0 weitermachen.) Hinterher bilden sich zwar lücken, aber die lassen sich dann mit den kleineren teilen auffüllen. Hierfür ist zwar ein neuerer Algorythmus nötig, aber es sollte dennoch gut machbar sein. Ich glaube, dieser ansatz wurde oben allerdings bereits erwähnt Ps: Solltest du dein tileset ändern, rate ich dir, alles erneut zu sortieren. Vom Programm versteht sich =) Je mehr gleiche teile auftreten (dh breite=breite und höhe=höhe), desto einfacher wird das sortieren sein, da mehrere zeilen direkt voll ausgenutzt werden können. Ein wirklich perfektes sortieren würde wohl zu lange dauern. Ich habe zwar keien ahnung wie sowas gemacht wird, aber ich würde es wohl wie eine schach-ki aufbauen: Jede mögliche kombination durchgehen und alles hintereinander einsortieren - für jeden schritt gibts allerdings 2 neue schritte, was eine extreme rechentiefe auf vergleichsweise kleiner tile-zahl bedeuetet!

PhillipK

Do, Jan 05, 2012 13:20
Antworten mit Zitat

Die idee funktioniert Smile

Es wird erst kritisch, wenn die teile wirklich willkürliche seitenverhältnisse haben. Bei exponenten von 2, welche auf 1024x1024 verteilt werden müssen, sollte es nur minimalsten schwund geben.

Ich habe so ein system für meinen TD-BCC beitrag gebastelt, um die einheiten, tower und blöcke zu sortieren. Getestet hatte ich es mit vielen unterschiedlichen grafiken - der schwund war minimal und sicher 100x besser als wie ich es "per hand" hinbekommen habe.

Grade bei 16x16, 16x32 etc (kleine teile) gibt es hinterher einen vorteil:

Erst einmal sucht man sich die größten teile und fängt oben an, dann beginnt man in der 2ten, komplett freien zeile (immer Y + höhe eines teils mit der zuletzt gemerkten position vergleichen - ist der neue wert größer, den "zuletzt gemerkten" auf Y+höhe setzen. Ist eine reihe voll, bei eben diesem Y wert bei X=0 weitermachen.)
Hinterher bilden sich zwar lücken, aber die lassen sich dann mit den kleineren teilen auffüllen. Hierfür ist zwar ein neuerer Algorythmus nötig, aber es sollte dennoch gut machbar sein.

Ich glaube, dieser ansatz wurde oben allerdings bereits erwähnt Smile

Ps: Solltest du dein tileset ändern, rate ich dir, alles erneut zu sortieren. Vom Programm versteht sich =) Je mehr gleiche teile auftreten (dh breite=breite und höhe=höhe), desto einfacher wird das sortieren sein, da mehrere zeilen direkt voll ausgenutzt werden können.
Ein wirklich perfektes sortieren würde wohl zu lange dauern. Ich habe zwar keien ahnung wie sowas gemacht wird, aber ich würde es wohl wie eine schach-ki aufbauen: Jede mögliche kombination durchgehen und alles hintereinander einsortieren - für jeden schritt gibts allerdings 2 neue schritte, was eine extreme rechentiefe auf vergleichsweise kleiner tile-zahl bedeuetet!

Übersicht

BlitzBasic

Blitz3D

Nach Oben

BlitzBasic Portal

1024x1024 Singlesurface für Sprites optimal ausnutzen

Betreff: 1024x1024 Singlesurface für Sprites optimal ausnutzen