División espacial alineada del eje: ¿Divide el espacio en rectángulos aleatorios?

Necesito un método para dividir el espacio 3d en formas de caja alineadas con ejes aleatorios. Por ahora estoy dividiendo el espacio 2d para fines de prueba. El enfoque más inmediato que se me ocurrió fue definir un rectángulo de tamaño (1, 1) y luego dividir recursivamente todos los rectángulos existentes en dos rectángulos irregulares que alternan entre los ejes X e Y.

El problema aquí es obvio. Este enfoque da como resultado largas líneas de estiramiento (marcadas en rojo)

Lo que me gustaría es algo más orgánico (incluí un ejemplo)

Mira, no hay líneas rectas largas de arriba a abajo o de izquierda a derecha.

La única restricción es que me gustaría limitar el tamaño mínimo del rectángulo sin afectar la granularidad de los tamaños. es decir, si el rectángulo más pequeño es 1 centímetro cuadrado que el segundo, la habitación más pequeña no debe tener 2 unidades cuadradas.

Entonces, idealmente, el algoritmo debe cumplir con las tres restricciones siguientes:

1. Los rectángulos no son infinitesimalmente pequeños.
2. Los tamaños de rect no son una multiplicación discreta del tamaño rect más pequeño. es decir, si el rect más pequeño es de 3 unidades cuadradas, los rectos más grandes no están limitados a ser 6, 9, 12, etc.
3. El algoritmo se ejecuta en tiempo polinomial (necesita calcular rápido).

El enfoque que describe es simple y útil, pero sufre de artefactos terribles como se muestra. Evítalo. Necesita un algoritmo de crecimiento paralelo; para un modelo de un solo subproceso, sigue un enfoque de operación por turnos:

1. Coloca al azar varios puntos en tu espacio del mapa. Normalice su distribución (evita la agrupación fea) usando la distribución gaussiana o aplicando un algoritmo de relajación iterativo para alejar los puntos colocados aleatoriamente uno del otro, según la relajación de Lloyd para los diagramas de Voronoi . Estos puntos representan los centroides de sus futuras habitaciones.
2. (Paralelo / repetir round-robin para todas las habitaciones) Desde cada punto, crezca 4 vértices hacia afuera (una habitación rectangular), moviéndose desde el punto central por iteración global (puede hacer crecer diferentes habitaciones a diferentes velocidades en cada eje en lugar de lo mismo para todo, y vea cómo resulta esto, posiblemente para un resultado más orgánico / variado). En algún momento, algunos de tus rectángulos comenzarán a presionarse uno contra el otro. En ese punto, limite el crecimiento en ese eje, asegúrese de que los bordes adyacentes de las dos habitaciones se toquen exactamente y siga adelante.
3. Repita el paso 2, creciendo cada habitación de forma incremental, hasta que todo el crecimiento esté restringido por habitaciones adyacentes o los límites del mapa.
4. Esto todavía dejará algunos espacios vacíos. El problema ahora se convierte en ubicar y hacer habitaciones con espacios no ocupados. De hecho, si su espacio subyacente es una cuadrícula (indexada con enteros) (y cada iteración de crecimiento se ajusta a esa cuadrícula), esto es mucho más fácil de manejar, ya que puede mantener listas de celdas de cuadrícula ocupadas y desocupadas: una vez que ' Cuando haya colocado y crecido todas sus habitaciones, busque en la lista de desocupados espacios discretos que consisten en grupos de celdas adyacentes. Como muchos espacios no utilizados tendrán formas no rectangulares, deberá elegir una celda al azar dentro de ese espacio no rectangular y hacerla crecer a su tamaño máximo tal como lo hizo con las habitaciones en el paso 2. Repita dentro de dicho espacio -Espacio rectangular, hasta que esté completamente lleno.
5. Repita el paso 4 hasta que su mapa esté 100% ocupado.

Como puede ver, logré librar al mundo de estos artefactos. La idea es muy parecida.

1. Divide el espacio 2D en una cuadrícula no uniforme. Si dos líneas están demasiado cerca, quite una.
2. Elija un rectángulo al azar, verifique si se ha modificado en el eje-y (en altura) y si su vecino directo se modificó en el eje-y. Ambos no fueron modificados, pídales que renegocien el segmento entre ellos (uno donará algo de espacio al otro).
3. Haga lo mismo que en el paso 2 solo esta vez en el otro eje.
4. Repita el proceso hasta que haya modificado tantos como sea posible.

Rejilla no uniforme (1):

Negociando sobre el eje x (2):

Negociando sobre el eje y (3):

Resultado (4):