Division spatiale alignée sur l'axe: diviser l'espace en rectangles aléatoires?

J'ai besoin d'une méthode pour diviser l'espace 3D en formes de boîtes alignées sur des axes aléatoires. Pour l'instant, je divise actuellement l'espace 2D à des fins de test. L'approche la plus immédiate que j'ai trouvée était de définir un rectangle de taille (1, 1), puis de diviser récursivement tous les rectangles existants en deux rectangles inégaux alternant entre les axes X et Y.

Le problème ici est évident. Cette approche entraîne de longues lignes d'étirement (marquées en rouge)

Ce que je voudrais, c'est quelque chose de plus organique (j'ai inclus un exemple)

Vous voyez, pas de longues lignes droites de haut en bas ou de gauche à droite.

La seule contrainte est que je puisse souhaiter limiter la taille minimale du rectangle sans affecter la granularité des tailles. c'est-à-dire si le plus petit rect est de 1 centimètre carré que la seconde plus petite pièce ne doit pas être de 2 unités carrées.

Donc, idéalement, l'algorithme devrait répondre aux trois contraintes suivantes:

1. Les rectangles ne sont pas infiniment petits.
2. Les tailles rect ne sont pas une multiplication discrète de la plus petite taille rect. c'est-à-dire que si le plus petit rect est de 3 unités carrées, les plus grands rectes ne sont pas limités à 6, 9, 12 et ainsi de suite, et peuvent donc être de 3,2 ou 4,7, d'ailleurs).
3. L'algorithme s'exécute en temps polynomial (doit être calculé rapidement).

L'approche que vous décrivez est simple et utile, mais souffre de terribles artefacts comme indiqué. L'éviter. Vous avez besoin d'un algorithme de croissance parallèle; pour un modèle monothread, une approche à tour de rôle suit:

1. Placez au hasard divers points dans votre espace de carte. Normaliser leur distribution (évite les regroupements laids) en utilisant la distribution gaussienne ou en appliquant un algorithme de relaxation itératif pour éloigner les points placés au hasard les uns des autres, conformément à la relaxation de Lloyd pour les diagrammes de Voronoi . Ces points représentent les centres de gravité de vos futures pièces.
2. (Round-robin parallèle / répété pour toutes les pièces) À partir de chaque point, développez 4 sommets vers l'extérieur (une pièce rectangulaire), en vous déplaçant du point central par itération globale (vous pouvez agrandir différentes pièces à des taux différents dans chaque axe plutôt que les mêmes pour tous, et voyez comment cela se passe - peut-être pour un résultat plus organique / varié). À un moment donné, certains de vos rectangles commenceront à se presser. À ce stade, limitez la croissance dans cet axe, assurez-vous que les bords adjacents des deux pièces se touchent exactement et continuez.
3. Répétez l'étape 2, en augmentant progressivement chaque pièce, jusqu'à ce que toute croissance soit limitée par les pièces adjacentes ou les limites de la carte.
4. Cela laissera toujours des espaces vides. Le problème devient maintenant celui de localiser et de créer des pièces à partir d'espaces non occupés. En fait, si votre espace sous-jacent est une grille (indexée sur un nombre entier) (et chaque itération de croissance s'aligne sur cette grille), cela est beaucoup plus facile à gérer, car vous pouvez maintenir des listes de cellules de grille occupées et inoccupées: une fois que vous '' ve placé et agrandi toutes vos chambres, recherchez dans la liste inoccupée des espaces discrets constitués de groupes de cellules adjacentes. Comme de nombreux espaces inutilisés auront des formes non rectangulaires, vous devrez choisir une cellule au hasard dans cet espace non rectangulaire et la développer à sa taille maximale comme vous l'avez fait avec des pièces à l'étape 2. Répétez dans ledit non -espace rectangulaire, jusqu'à ce qu'il soit complètement rempli.
5. Répétez l'étape 4 jusqu'à ce que votre carte soit occupée à 100%.

Comme vous pouvez le voir, j'ai réussi à débarrasser le monde de ces artefacts. L'idée est très similaire.

1. Divisez l'espace 2D en une grille non uniforme. Si deux lignes sont trop proches, supprimez-en une.
2. Choisissez un rectangle au hasard, vérifiez s'il a été modifié sur l'axe-y (en hauteur) et si son voisin direct a été modifié sur l'axe-y. Je n'ai pas été modifié tous les deux, demandez-leur de renégocier le segment entre eux (l'un donnera de l'espace à l'autre).
3. Faites la même chose qu'à l'étape 2 mais cette fois sur l'autre axe.
4. Répétez le processus jusqu'à ce que vous en ayez modifié autant que possible.

Grille non uniforme (1):

Négociation sur l'axe x (2):

Négociation sur l'axe y (3):

Résultat (4):