problema di imballaggio rivisitato

Question

Sto sviluppando un gioco e ho trovato un problema che devo risolvere per gestire il layout di un componente che mi assomiglia ad un problema di imballaggio.

Per riassumere quello che devo fare supporre che ho uno spazio simile a quello seguente:

+------------+---------+------------+
| 0          | 1       | 2          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 3          | 4       | 5          |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 6          | 7       | 8          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+

in cui ogni cella d'angolo è 4x4, mentre quella centrale è 3x3 (in modo che i rimanenti sono 3x4 e 4x3). Poi Ho una serie di elementi a posto all'interno di questi blocchi che possono variare da 1x1 a 3x3 (non 4x4 che qualsiasi momento è necessaria ma non dovrebbe cambiare nulla). Naturalmente questi elementi non possono attraversare le linee e devono fissare interamente all'interno di un unico blocco.

Il che potrebbe essere il modo migliore per allocare loro? Partendo dal presupposto che io non preferisco averli tutti stickied insieme, se non è necessario (ad es. Non posizionare due elementi insieme, se c'è abbastanza spazio intorno a metterli a parte). Sto cercando un semplice algoritmo, anche perché la situazione è abbastanza limitata ..

Domanda bonus: assumendo altri blocchi in aggiunta a questi 9 (forse altri 3-4) come ho potuto dare la priorità rispetto a questi quelli nuovi? (Intendo semplicemente non utilizzare il blocco addizionale fino al raggiungimento di una soglia di riempimento) ..

Naturalmente sto cercando l'idea generale, nessuna implementazione:)

Answer 1

Questa 2D Bin Packing sguardi problema come se fosse di NP difficile .

Qui ci sono un paio di opzioni:

• La forza bruta o meglio ancora ramo e rilegato. Non scala (a tutti!), Ma sarà trovare la soluzione ottimale (non durante la nostra vita forse).

• deterministico algoritmo: ordinare i blocchi sul più grande dimensione o laterale più grande e passare attraverso quella lista uno per uno e assegnare il posto migliore rimanente. Che finirà molto veloce, ma la soluzione può essere tutt'altro che ottimale (o fattibile). Ecco una bella foto che mostra un esempio cosa può andare storto. Ma se si vuole mantenere le cose semplici, questa è la strada da percorrere.

• meta-euristica, partendo dal risultato di un algoritmo deterministico. Questo vi darà un ottimo risultato in un tempo ragionevole, migliore di quello che gli esseri umani venire con. A seconda di quanto tempo si dà e la difficoltà del problema che potrebbe o non potrebbe essere la soluzione ottimale. Ci sono un paio di librerie là fuori, come ad esempio Drools Planner (java open source).