He tenido algunos problemas para determinar de manera eficiente si las salas grandes están selladas en salas 3D basadas en voxel. Estoy en un punto en el que he hecho todo lo posible para resolver el problema sin pedir ayuda, pero no he intentado lo suficiente como para rendirme, así que estoy pidiendo ayuda.
Para aclarar, sellado siendo que no hay agujeros en la habitación. Hay selladores de oxígeno, que verifican si la habitación está sellada y sellan según el nivel de entrada de oxígeno.
En este momento, así es como lo estoy haciendo:
- Comenzando en el bloque sobre la loseta de sellador (el respiradero está en la cara superior del sellador), haga un bucle recursivo en las 6 direcciones adyacentes
- Si el mosaico adyacente es un mosaico completo sin vacío, continúe a través del bucle
- Si el mosaico adyacente no está lleno, o es un mosaico de vacío, verifique si sus bloques adyacentes lo están, recursivamente.
- Cada vez que se marca un mosaico, disminuya un contador
- Si el recuento llega a cero, si el último bloque está adyacente a una loseta de vacío, devuelva que el área no está sellada
- Si el conteo llega a cero y el último bloque no es un mosaico de vacío, o el ciclo recursivo termina (no quedan mosaicos de vacío) antes de que el contador sea cero, el área está sellada
Si el área no está sellada, ejecute el ciclo nuevamente con algunos cambios:
- Verificación de bloques adyacentes para la loseta de "aire respirable" en lugar de una loseta de vacío
- En lugar de usar un contador decreciente, continúe hasta que no se encuentren fichas adyacentes de "aire respirable".
- Una vez que finalice el ciclo, configure cada bloque marcado en un mosaico de vacío.
Aquí está el código que estoy usando: http://pastebin.com/NimyKncC
El problema:
Estoy ejecutando esta comprobación cada 3 segundos, a veces un sellador tendrá que recorrer cientos de bloques, y en un mundo grande con muchos selladores de oxígeno, estos múltiples bucles recursivos cada pocos segundos pueden ser muy difíciles para la CPU.
Me preguntaba si alguien con más experiencia en optimización puede echarme una mano, o al menos señalarme en la dirección correcta. Gracias un montón.
Respuestas:
La mejor solución dependerá de múltiples factores, como el tamaño esperado de la habitación.
Enfoque 1:
Puede usar un A * para encontrar una ruta desde el respiradero hasta el mosaico sobre el respiradero / el respiradero mismo o hacia un mosaico que se conoce como vacío. Si se encuentra el camino, la habitación está abierta. Esto no es muy diferente de su enfoque actual, pero debería ser más rápido. Una vez encontrado, haga un "relleno de inundación" para configurar los azulejos como vacío.
Enfoque 2:
Tal vez su estructura externa sea menos compleja: teniendo en cuenta que hay una superficie donde están las habitaciones, no necesita moverse en las 6 direcciones, por lo que debe viajar a lo largo de la superficie, marque cada baldosa como vacío que viaja.
fuente
Cuando haces tu búsqueda recursiva, ¿te aseguras de no estar revisando el mismo vóxel varias veces? No pude distinguir por la forma en que describió su algoritmo, pero debería tener algún tipo de indicador para indicar si ya ha expandido recursivamente un vóxel, por lo que no lo hace más de una vez.
Y como dijo Byte56, también debe verificar si hay fugas cuando las cosas cambian. Eso podría minimizar en gran medida la cantidad de trabajo que realiza, dependiendo de la frecuencia con que ocurran los cambios. Incluso puede almacenar en caché la información entre llamadas sucesivas al algoritmo, lo que puede trivializar la cantidad de cálculo que realiza después de la primera llamada.
Editar:
Miré algunos de tus códigos. Parece que está usando un LinkedList para indicar si un vóxel ya se ha verificado, como en mi primer párrafo. Es posible que tenga mejores resultados si utiliza algo diferente a LinkedList para esto. ¿Quizás prueba un HashSet o algo así? Esto debería reducir la complejidad de su método de verificación de O (n) a O (1).
fuente