Como determino a ordem do sorteio em um jogo flash com vista isométrica?

Isto é para um jogo em flash, com vista isométrica. Eu preciso saber como classificar o objeto para que não haja necessidade de verificação do z-buffer ao desenhar. Isso pode parecer fácil, mas há outra restrição: uma cena pode ter mais de 10.000 objetos; portanto, o algoritmo precisa ser executado em menos de O (n ^ 2). Todos os objetos são caixas retangulares e há 3-4 objetos em movimento na cena. Qual é a melhor forma de fazer isso?

ATUALIZAR

em cada bloco há apenas objeto (quero dizer, objetos não podem ser empilhados uns sobre os outros). e acessamos o mapa de objetos e os objetos têm sua própria posição.

UPDATE2

veja estas figuras:

no primeiro, um primeiro objeto azul deve ser desenhado, depois verde e vermelho. enquanto no segundo você precisa desenhá-los em ordem inversa. você precisa desenhar primeiro o vermelho e depois o objeto verde e finalmente azul. Como você pode ver, não há diferença na posição dos objetos azuis e vermelhos, ambos têm distâncias diferentes da câmera e assim por diante. mas devido à sua posição relativa em relação à caixa verde, é necessário alterar a ordem dos desenhos entre duas imagens. é isso que torna esse problema uma bagunça.

nota lateral: como todos os objetos são prisma retangular, é matematicamente comprovável que exista pelo menos uma ordem de desenho para atender às necessidades do problema.

Isso é realmente muito simples se seus objetos combinarem com seus blocos isométricos. Veja esta imagem:

Você deve primeiro desenhar o objeto na posição vermelha, depois objetos em azul, depois verde, depois amarelo, depois magenta e assim por diante ... Deveria ser bastante óbvio como implementar isso se o seu quadro contiver objetos em vez de objetos tendo posição como um atributo. Se esse não for o seu caso, você deve manter uma estrutura de dados separada, atualizando-a sempre que um objeto se mover (o que também deve ser bastante fácil).

Isso tem um novo problema: você pode ver facilmente como agora sua complexidade é O (N) onde N é o tamanho da sua placa ( N=W*H). Para superar esse problema, basta criar uma nova estrutura de dados linear em que cada índice em sua estrutura corresponda a uma determinada profundidade, atualizando-a sempre que um objeto alterar a profundidade.

O caso em que um objeto não corresponde a um único bloco é um pouco mais difícil, portanto, publicarei se você precisar assim que atualizar sua pergunta.

Não tenho nenhum conhecimento especial sobre esse assunto, mas aqui está um pensamento.

Comece marcando cada célula como "não desenhada". (Ou, de maneira equivalente, use uma matriz para representar a localização da coisa "desenhada" mais próxima em cada "linha mais próxima" de células, ou um conjunto etc.) Em seguida, para cada célula (eu provavelmente as examinaria em a ordem kaoD descrita): verifique se a célula foi desenhada; se não foi desenhado e contém um objeto, verifique se cada célula que seria obscurecida por esse objeto foi desenhada e, se não, desenhe-a recursivamente; desenhe o objeto contido nessa célula, se necessário; e marque essa célula e quaisquer células ocupadas por seu objeto como "desenhadas".

Suponho que você possa mapear rapidamente uma célula para o objeto dentro dela, se houver. Acredito que este é o tempo de O (n), embora possa acabar criando uma pilha grande (que você pode querer transformar em uma lista vinculada, se estiver preocupado com a falta de espaço na pilha).

Se você realmente precisa de uma lista, pode anexá-la a uma lista em vez de desenhar. Suspeito que começar com uma lista classificada principalmente não ajude.

Eu usaria o algoritmo do pintor a uma distância de táxi da célula mais distante da câmera, desenhando primeiro os mais próximos da câmera e depois movendo-os para fora.

Editar: isso não funciona, a menos que você possa desenhar o conteúdo de cada célula individualmente.

O que faz você acreditar que é "matematicamente comprovável que exista pelo menos uma ordem de empate para satisfazer as necessidades do problema"? Aqui está um contra-exemplo trivial em que você não pode confiar em objetos de classificação z: