Algorytm sortowania klockow tetrisa

[TO_mek]

Witam!

Każdy pewnie kojarzy klocki jakie występują w tetrisie. Zresztą dla przypomnienia:

 

oraz wszelkie możliwe położenia (19):

 

Nie robię tetrisa, interesuje mnie zupełnie coś innego.

Poszukuję algorytmu który by pozwalał na upakowanie klocków o takich kształtach w dowolnej tablicy dwuwymiarowej tak aby zniwelować straty wolnego niewykorzystanego miejsce. Rodzaje klocków mogą się powtarzać oraz nie występować wcale. Interesują mnie 2 opcje - gdy klocki mogą być dowolnie obracane podczas sortowania oraz gdy obrót jest zakazany (ale "na wejściu" oczywiście klocki dowolnie obrócone czyli 19 możliwych kombinacji).

Znalazłem "algorytm plecakowy" ale tam zupełnie pomija się kształt obiektów a jedynie wagę (objętość) a mnie interesuje konkretne posortowanie elementów tak by upakować ich jak najwięcej lub aby zostało jak najwięcej miejsca w jednym dużym kawałku.

[Tymon]

Przez upakowanie rozumiesz upchanie w każdą wolną komórkę kawałka klocka? Czy mają być jakieś wolne przestrzenie między nimi?

[TO_mek]

Przez upakowanie rozumiesz upchanie w każdą wolną komórkę kawałka klocka? Czy mają być jakieś wolne przestrzenie między nimi?

Upchanie w każdą wolną komorkę ale bez dzielenia klocków na mniejsze kawałeczki. Im mniej wolnej przestrzeni tym lepiej. Coś jak upakowanie w prostokąt jak najwiekszej ilości klocków o kształtach tetrisopodobnych. Czytałem też trochę o "problemie optymalnego rozkroju" ale nie znalazłem implementacji algorytmu który by ten problem rozwiązywał.

[Platyna]

Zdefiniuj relację porządkującą na układach klocków, bo ja nie wiem, który jest dla Ciebie optymalniejszy. Czy należy zredukować liczbę wolnych pól czy też ich rozkład ma znaczenie, czy może chodzi o zminimalizowanie wysokości wieży. Możliwości jest cała masa.

Poza tym czy ja dostaję zestaw klocków i mogę dowolnie wybierać kolejność w jakiej je układam?

Chodzi po prostu o upakowanie jak największej liczby klockół z pewnego zbioru do tablicy n x n?

[TO_mek]

Chodzi po prostu o upakowanie jak największej liczby klockół z pewnego zbioru do tablicy n x n?

Dokładnie o to czyli mam jakiś zbiór klocków o kształtach jak w tetrisie. Interesuje mnie upakowanie jak największej liczby klocków do tablicy n x n w taki sposób aby zostało jak najwięcej miejsca. Dochodzi jakiś następny klocek (niech to będzie "T") i następuje przesortowanie tablicy tak by znowu było jak naj mniej straconego "materiału".

 

Najlepiej wyobrazić sobie drewnianą płytę w której mamy wyciąć określony zbiór desek w kształcie figur tetrisa tak aby było jak najmniej odpadów i pozostał jak największy kawałek płyty w całości. I teraz jeszcze 2 warianty czyli jeden gdy te klocki można dowolnie obracać (reguły jak na drugim obrazku) oraz drugi wariant gdy klocki nie mogą być obracane (bo załóżmy ta drewniana płyta ma jakiś wzór i jest istotne czy wycinamy figurę w pionie czy poziomie).

[Platyna]

Wszystkie klocki mają taki sam rozmiar w polach więc niezależnie od rozkładu to ilosć wolnych miejsc jest niezmienna także chyba nie rozumiem. Sprowadza się to tylko i wyłącznie do upchnięcia maksymalnej liczby klocków bez zważania na puste pola?

I czy te klocki przychodzą w ustalonej kolejności czy mogę dowolnie wybierać?

[TO_mek]

Wszystkie klocki mają taki sam rozmiar w polach więc niezależnie od rozkładu to ilosć wolnych miejsc jest niezmienna także chyba nie rozumiem. Sprowadza się to tylko i wyłącznie do upchnięcia maksymalnej liczby klocków bez zważania na puste pola?

I czy te klocki przychodzą w ustalonej kolejności czy mogę dowolnie wybierać?

 

 

Nie, no jak taki sam rozmiar? Po pierwsze rysunek drugi obrazuje tylko jak można dany klocek obracać ale każdy z klocków składa się zawsze z 4 malutkich kwadracików a nie z matrycy 4x4. Po drugie klocków nie można dzielić na kawałeczki (pojedyncze kwadraciki).

Jednym słowem zależy mi na jakby takim układaniu klocków w siatce n x n jak to robi człowiek w tetrisie czyli tak dobiera poszczególne klocki aby nie zostawiać wolnych miejsc ale tak jak zaznaczyłem wcześniej, nie robię tetrisa.

[Platyna]

Każdy klocek ma taką samą powierzchnię równą 4 jednostki. Także niezależnie od tego jak je poukładam, jeśli zmieszczę tyle samo klocków to wolnych miejsc zostanie dokłądnie tyle samo. Nie zdefiniowałeś porządku na układach więc przyjąłem, że tylko liczba, a nie rozmieszczenie ma znaczenie.

[TO_mek]

Każdy klocek ma taką samą powierzchnię równą 4 jednostki. Także niezależnie od tego jak je poukładam, jeśli zmieszczę tyle samo klocków to wolnych miejsc zostanie dokłądnie tyle samo. Nie zdefiniowałeś porządku na układach więc przyjąłem, że tylko liczba, a nie rozmieszczenie ma znaczenie.

Ok zgadza się, powierzchnia to zawsze 4 jednostki. Zostaje więc tylko je poukładać. I właśnie tego algorytmu "poukładania" szukam :)

[gnysek]

Znaczy sie, jak dochodzi nowe tetramino, to pozostałe można ponownie przestawić? Chodzi tylko o ułożenie ich na planszy tak, żeby najmniej miejsca zajęły? Coś jak u stolarza, że ma program który mu układa jak pociąć dużą płytę na małe deski, aby było najmniej ścinków?

[I am Lord]

Znaczy sie, jak dochodzi nowe tetramino, to pozostałe można ponownie przestawić? Chodzi tylko o ułożenie ich na planszy tak, żeby najmniej miejsca zajęły? Coś jak u stolarza, że ma program który mu układa jak pociąć dużą płytę na małe deski, aby było najmniej ścinków?

Najlepiej wyobrazić sobie drewnianą płytę w której mamy wyciąć określony zbiór desek w kształcie figur tetrisa tak aby było jak najmniej odpadów i pozostał jak największy kawałek płyty w całości.

[gnysek]

Tak, ale nadal są dwie możliwości: można przekładać kolcki gdy dochodzi nowy i nie można ich przekładać.

[TO_mek]

Tak, ale nadal są dwie możliwości: można przekładać kolcki gdy dochodzi nowy i nie można ich przekładać.

 

Można przekładać jak dochodzi nowy. To jakby poszukiwanie optymalnego wykorzystanie "drewnianej płyty" jeszcze PRZED rozpoczęciem wycinania :)

[Muuuuczek567]

Operuj tylko na klockach w kształcie kwadratu i prostokąta. Jeśli iloczyn wymiarów jest podzielny przez 4, zawsze można znaleźć takie ułożenie, dzięki któremu nie zostanie żadne wolne miejsce na płycie. W innych przypadkach zawsze ilość wolnego miejsca nie będzie większa niż 3.

 

Chyba, że masz już ustalone, jakie klocki masz wykorzystać, to w takim razie za wiele nie pomogłem.

[pamparampa]

A może spróbuj sobie na kartce ułożyć jak najbardziej optymalny układ i na podstawie tego zrobić kod, który będzie układał klocki w odpowiednie miejsca

[TO_mek]

Operuj tylko na klockach w kształcie kwadratu i prostokąta.

 

To byłoby zbyt proste :)

Równie dobrze możnaby się ograniczyć do samych kwadratów i matrycy o bokach parzystych.

 

EDIT: DO Pamparampa -> Zbiór klocków nie jest stały tzn. jest określona liczba możliwych kształtów ale generowanie klocków może być np. losowe. Można przyjąć, że matryca 20x20 teoretycznie powinna zmieścić 100 klocków (bo każdy klocek zajmuje 4 kwadraciki), i albo losujemy na dzień dobry 100 klocków, albo po jednym (czyli za każdym razem układać należy od nowa) a algorytm ma tak kombinować aby zmieścić jak największą liczbę z tej setki.