¿Cómo determino el orden de dibujo en un juego flash de vista isométrica?

Esto es para un juego flash, con vista isométrica. Necesito saber cómo ordenar el objeto para que no haya necesidad de verificar el z-buffer al dibujar. Esto puede parecer fácil, pero hay otra restricción, una escena puede tener más de 10,000 objetos, por lo que el algoritmo debe ejecutarse en menos de O (n ^ 2). Todos los objetos son cajas rectangulares, y hay 3-4 objetos moviéndose en la escena. ¿Cuál es la mejor manera de hacer esto?

ACTUALIZAR

en cada mosaico solo hay un objeto (quiero decir que los objetos no pueden apilarse uno encima del otro). y accedemos tanto al mapa de Objetos como a los Objetos que tienen su propia posición.

ACTUALIZACIÓN2

ver estas figuras:

en el primer objeto azul primero debe dibujarse luego verde y luego rojo. mientras que en el segundo tienes que dibujarlos en orden inverso. primero debe dibujar el objeto rojo y luego el verde y finalmente el azul. Como puede ver, no hay diferencia en la posición de los objetos azules y rojos, ambos tienen una distancia diferente de la cámara, etc. pero debido a su posición relativa al cuadro verde, debe cambiar su orden de dibujo entre dos imágenes. eso es lo que hace que este problema sea un desastre.

Nota al margen: dado que todos los objetos son prismas rectangulares, es matemáticamente comprobable que hay al menos un orden de dibujo para satisfacer las necesidades del problema.

Esto es realmente muy simple si tus objetos coinciden con tus mosaicos isométricos. Mira esta imagen:

Primero debe dibujar el objeto en la posición roja, luego los objetos en azul, luego en verde, luego en amarillo, luego en magenta, y así sucesivamente ... Debería ser bastante obvio cómo implementar esto si su tablero tiene objetos en él en lugar de objetos teniendo posición como un atributo. Si ese no es su caso, debe mantener una estructura de datos separada, actualizándola cada vez que se mueva un objeto (que también debería ser bastante fácil).

Esto tiene un nuevo problema: puede ver fácilmente cómo ahora su complejidad es O (N) donde N es el tamaño de su placa ( N=W*H). Para superar este problema, simplemente cree una nueva estructura de datos lineales donde cada índice de su estructura coincida con una profundidad dada, actualizándola cada vez que un objeto cambie de profundidad.

El caso en el que un objeto no coincide con un solo mosaico es un poco más difícil, por lo que lo publicaré si lo necesita tan pronto como actualice su pregunta.

No tengo ningún conocimiento especial sobre este tema, pero aquí hay un pensamiento.

Comience marcando cada celda como "no dibujada". (O, de manera equivalente, use una matriz para representar la ubicación de la cosa "dibujada" más cercana en cada "línea cercana-lejana" de celdas, o un conjunto, etc.) Luego, para cada celda (probablemente las revisaría en el orden kaoD descrito): verifique si esa celda ha sido dibujada; si no se ha dibujado y contiene un objeto, verifique si cada celda que estaría oscurecida por ese objeto se ha dibujado, y si no se dibuja de forma recursiva; dibuje el objeto contenido por esa celda si es necesario; y marque esa celda y cualquier celda ocupada por su objeto como "dibujada".

Supongo que puede asignar rápidamente una celda al objeto dentro de ella, si corresponde. Creo que este es el momento O (n), aunque podría terminar construyendo una gran pila (que es posible que desee convertir en una lista vinculada si le preocupa quedarse sin espacio de pila).

Si realmente necesita una lista, puede agregarla a una lista en lugar de dibujar. Sospecho que comenzar con una lista ordenada en su mayoría no ayuda.

Usaría el algoritmo del pintor con una distancia en taxi desde la celda más alejada de la cámara, dibujando primero las más cercanas a la cámara y luego moviéndome hacia afuera.

Editar: esto no funciona a menos que pueda dibujar el contenido de cada celda individualmente.

¿Qué le hace creer que es "demostrable matemáticamente que hay al menos un orden de sorteo para satisfacer las necesidades del problema"? Aquí hay un contraejemplo trivial en el que no puede confiar en los objetos de clasificación z: