Emballage 2D avec obstacles

Quelqu'un connaît un algorithme efficace pour déplacer des rectangles dans un carré contenant des obstacles?Emballage 2D avec obstacles

: Rectangles

peut tourner
peut se déplacer/téléportation
ne doit pas entrer en collision avec des obstacles (carrés noirs)

Obstacles:

ne peut pas être déplacé
peut être ajouté n'importe où

Objectif: lorsqu'un obstacle est ajouté, essayez de déplacer les rectangles de façon à ce qu'ils ne heurtent aucun des obstacles.

State 1 http://img440.imageshack.us/img440/6995/59737192.png

State 2 http://img87.imageshack.us/img87/2336/28560269.png

State 3 http://img406.imageshack.us/img406/5469/30594959.png

State 4 http://img683.imageshack.us/img683/81/88927554.png

State 5 http://img25.imageshack.us/img25/3657/83405570.png

Source

2010-03-26 redman

jusqu'à ce que vous pouvez quoi? –

@Henk Holterman: oui, ils peuvent TelePort. L'objectif est de les déplacer si vous le pouvez ou de retourner faux (ne peut pas les déplacer de la façon dont ils ne heurtent pas avec des obstacles). – redman

Comment? Avec téléportation/déplacement et rotation À quelle fréquence? Seulement lorsqu'un nouvel obstacle est ajouté Où? Quelque part sur le terrain, les rectagles ne doivent tout simplement pas entrer en collision avec des obstacles. Pourquoi? Un jeu de type cuirassé, quand vous déplacez vos vaisseaux jusqu'à ce que vous le puissiez - quand vous pouvez les déplacer plus vous les laissez là et dites le coup à l'adversaire. – redman

Jetez un oeil à ceci: Dynamic programming - Largest square block
En fait, compte tenu de la rec Enchevêtrement, vous ajoutez un obstacle et enlevez le carré que l'obstacle interfère.
Ensuite, exécutez l'algorithme lié (avec les "limiteurs" étant les obstacles et les carrés existants), et si un endroit a été trouvé qui peut contenir un carré de taille NxN (N est la grande partie du rectangle), et ajoutez le rectangle).
Cela peut être optimisé un peu plus loin, et je vous le confie. (Fondamentalement, les rectangles ne seront pas toujours placés à l'endroit le plus optimal, ce qui peut être corrigé, au moins dans une certaine mesure)
Cette solution vous donnera O (n) temps et espace pour chaque obstacle ajouté.
Modification possible que vous devriez également examiner: Ne reconstruisez pas le tableau pour chaque obstacle, mais construisez-le pour le tableau vide-d'obstacles, et modifiez-le au fur et à mesure. Cela permettra d'économiser aller à travers l'ensemble du tableau pour chaque obstacle.

Source

2010-03-26 11:19:01 Rubys

Répondre

Questions connexes