problème d'emballage revisité

Question

Je développe un jeu et je l'ai trouvé un problème que je dois résoudre pour gérer la mise en page d'un composant qui me ressemble à un problème d'emballage.

Pour résumer ce que je dois faire suppose que j'ai un espace similaire à la suivante:

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

dans laquelle chaque cellule de coin est une 4x4 tandis que le centre est 3x3 (de sorte que les restants sont 3x4 et 4x3). Ensuite, j'ai un ensemble d'éléments à placer dans ces blocs qui peuvent varier de 1x1 à 3x3 (je ne pense pas que 4x4 est nécessaire encore, mais il ne faut rien changer). Bien sûr, ces éléments ne peuvent pas franchir les lignes et doivent mettre entièrement à l'intérieur d'un seul bloc.

Ce qui pourrait être la meilleure façon de les attribuer? En supposant que je préfère ne pas les avoir tous ensemble si stickied n'est pas nécessaire (par exemple. Ne pas placer deux éléments s'il y a assez de place autour de les placer en dehors). Je suis à la recherche d'un algorithme simple, aussi parce que la situation est tout à fait limitée ..

Question bonus: en supposant que d'autres blocs en plus de ces 9 (peut-être d'autres 3-4) comment pourrais-je hiérarchiser par rapport aux nouveaux? (Je veux dire juste ne pas utiliser le bloc supplémentaire jusqu'à ce qu'un seuil de remplissage a été atteint) ..

Bien sûr, je suis à la recherche de l'idée générale, aucune mise en œuvre:)

Answer 1

Bin emballage ressemble problème comme il NP dur .

Voici quelques options:

• La force brute ou mieux encore la branche et lié. Ne fonctionne pas échelle (du tout!), Mais vous trouverez la solution optimale (pas dans notre vie peut-être).

• algorithme déterministes: trier les blocs sur la plus grande taille ou le plus grand côté et passer par cette liste, un par un et lui attribuer le meilleur endroit restant. Qui terminera très rapide, mais la solution peut être loin d'être optimale (ou possible). Voici une image agréable montrant un exemple de ce qui peut aller mal. Mais si vous voulez garder les choses simples, c'est la voie à suivre.

• méta-heuristiques, à partir du résultat d'un algorithme déterministe. Cela vous donnera un très bon résultat dans un délai raisonnable, mieux que ce que les humains viennent avec. Selon combien de temps vous donnez et la difficulté du problème, il pourrait ou pourrait ne pas être la solution optimale. Il y a quelques bibliothèques là-bas, comme Drools Planner (java open source).