Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (475)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (530)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Rectangle packing...  (Read 1681 times)
0 Members and 1 Guest are viewing this topic.
Offline Anon666

Junior Member




aka Abuse/AbU5e/TehJumpingJawa


« Posted 2006-04-05 16:50:39 »

Has anybody written or found an algorithm for performing this operation?

I'm totally amazed there are no resources on the web offering an open source solution to this problem, even poor implementations seem to not exist =/

While I understand the complexity of the problem, a generalized solution should be totally reusable - afterall, a rectangle is a rectangle!
The only problem specific aspects are specializations in the type of rectangles that are present in the input dataset.

I would expect every single game developer has at one time or another come across this problem, as it is fundamental to optimal texture-page arrangement.
My instance of this problem is in the domain of J2ME development, where memory is at a premium - so optimal use of textures is critical.
That said, scalability is also paramount, so *automated* packing of texture data is of critical importance also. (doing it by hand is simply not an option)
Offline kevglass

JGO Kernel


Medals: 120
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #1 - Posted 2006-04-05 17:00:29 »

SPGL has a tool that does it I believe. Cas is your man for this one,

Kev

Offline Anon666

Junior Member




aka Abuse/AbU5e/TehJumpingJawa


« Reply #2 - Posted 2006-04-05 17:28:31 »

ahhh! cheers, having a look now.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Catharsis

Junior Member


Exp: 18 years


EGR Software rocks!


« Reply #3 - Posted 2006-04-05 21:33:56 »

Has anybody written or found an algorithm for performing this operation?

Check out a "bin packing". There are variations, but 2D bin packing should get you on the right track I'd imagine.  I haven't played around with something like this for optimizing textures, but I wrote such a program for my 1st quarter CS class way back in the day.. Sounds tough for a 1st quarter class, but it was an accelerated class combining the intro 101, 102, 103 series (3 courses into 1). Heh, the extra credit project that would get you an A in the class and not have to take the final was to create a chess program that could beat the professors.  ;P

Founder & Principal Architect; EGR Software LLC
http://www.typhonrt.org/
http://www.egrsoftware.com/
Offline Kova

Senior Member





« Reply #4 - Posted 2006-04-06 01:17:17 »

sorry for offtopic Tongue

Quote from: Catharsis
Heh, the extra credit project that would get you an A in the class and not have to take the final was to create a chess program that could beat the professors.  ;P
doable.... with some research how best chess programs work and such stuff Smiley ... did anybody did it? Smiley
Offline Anon666

Junior Member




aka Abuse/AbU5e/TehJumpingJawa


« Reply #5 - Posted 2006-04-07 12:40:19 »

Ended up writing my own implementation, as the problem solved in the SPGL code is subtlely different to my requirements.
(Cas is packing a set number of images into a variable number of 256x256 textures,
I on the other hand need to pack a set number of images into the smallest possible area.)
There was also a minor complication that in my datasets, the input rectangles could be super-imposed. (several sprites sharing the same pixels)

Ended up with an acceptable solution that given a random dataset of rectangles with dimensions [1<=x<=26, 1<=y<=26]  it on average attains a 91% fitness efficiency.
With a real-life dataset the variance is alot larger (typicaly between 80-100%) which is acceptable for the time constraints I had to write it in....1 day Roll Eyes

Most importantly - it generates better texture pages than the artists usually manage (One step closer to making the artists redundant Grin)

The modularity of the problem does leave the algorithm open to future improvements too - so i'm happy.
Offline Catharsis

Junior Member


Exp: 18 years


EGR Software rocks!


« Reply #6 - Posted 2006-04-07 23:53:09 »

sorry for offtopic Tongue
Quote from: Catharsis
Heh, the extra credit project that would get you an A in the class and not have to take the final was to create a chess program that could beat the professors.  ;P
doable.... with some research how best chess programs work and such stuff Smiley ... did anybody did it? Smiley

Continued off topic.. ;P

Certainly doable; max/min type stuff; This was a 1st quarter .freshman. class though, so it was a little on the hardcore side when everyone else that didn't have a clue taking just 101 was lucky to be writing for loops by the end of their 1st quarter. The bin packing problem was just before the chess extra credit as well in assignments and to reasonably get the chess program done you'd have to skip that one and take a gamble.. I played it safe, but a couple of folks did do it... About 5-6 people actually failed the course (12 units in major!) because they shared their work amongst each other which was forbidden by signed contract.  You know college was going to be fun when you walk into your 1st class and the prof says this is the hardest class you will take; almost was..  I went on to do the computer architecture classes and more freshman year and finished my senior project that summer..   Then slacked like a mofo after one more year of hard effort.. I was trying to get out in 3 years, but just didn't care at some point. ;P

Founder & Principal Architect; EGR Software LLC
http://www.typhonrt.org/
http://www.egrsoftware.com/
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

pw (8 views)
2014-07-24 01:59:36

Riven (9 views)
2014-07-23 21:16:32

Riven (11 views)
2014-07-23 21:07:15

Riven (11 views)
2014-07-23 20:56:16

ctomni231 (42 views)
2014-07-18 06:55:21

Zero Volt (38 views)
2014-07-17 23:47:54

danieldean (32 views)
2014-07-17 23:41:23

MustardPeter (34 views)
2014-07-16 23:30:00

Cero (49 views)
2014-07-16 00:42:17

Riven (50 views)
2014-07-14 18:02:53
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!