Je lance une discussion sur ce sujet : non pas que je veuille faire un jeu qui s´appuie la dessus mais juste pour en causer, car les idées m´intéressent !

Prenez un Mario Bros, un jeu RPG Maker, etc : ils utilisent du TileMapping : algorithmiquement parlant, c´est un tableau 2D de "blocs"
Pour etre compact, on peut dire qu´un "bloc", c´est 1 octet : partant du principe qu´il n´y aura pas plus de 256 tiles différents dans le monde.
Un monde de Mario par exemple, qui fait 20 tiles de haut, et 1000 tiles de long, coutera donc 20*1000 = 20 000 octets (~ 20 Ko)
L´avantage d´un tel codage pour un "level", c´est qu´on calcule, depuis la position d´un perso, sur quel tile il évolue en 2 divisions (immédiat donc !)

Prenons maintenant Tomb Raider, premier du nom :
C´est le meme codage, mais en 3D. Ainsi, un monde qui fait 100 tiles de long, 100 de large, 100 de haut, fait déja 1 million de tiles, donc 1 Mo si on dit toujours qu´il ne peut y avoir que 256 tiles différents dans les monde.
Pour Tomb Raider, je pense qu´ils se sont débrouillé pour que les mondes ne soient pas trop grand ! (ou alors pas trop haut) pour ne pas consommer trop de mémoire.

Mais maintenant, imaginons que je veuille faire un monde tres tres grand (aussi bien en hauteur qu´en largeur qu´en prodondeur), la je suis coincé !
En effet, 1000 * 1000 * 1000 = 1 Go -> c´est déja beaucoup trop.

Alors sachant qu´il y aura de grannndes zones de vide, on pense tout de suite a la compression. Mais comment compresser cela ? J´avais pensé a un RLE, mais un RLE, c´est en une seule dimension !
De plus, avec un RLE, il devient apres bien difficile de trouver rapidement, pour une position x,y,z (de personnage) donné, sur quel tile il est !

Oui, je sais, c´est pour ça qu´on a inventé le heightmap, l´octree, le BSP, mais ça m´amuse de savoir comment on pourrait s´en sortir avec un codage en Tiles 3D !

Quelques idées ?

Que veut tu dire par "s´en sortir avec un codage en Tiles 3D", tu veux conserver case (x,y,z) en O(1) ?

Sinon une premiere idée au pif.
tu décris z a x,y fixe. et tu fais de l´indexation par la dessus. tu peux donc avoir nbtileparligne tiles par ligne et plus dans le monde entier. ca te coute la description de la table d´indexation soit log(nbtileparligne)*log(nbtiletotal) par ligne. c´est donc a multiplier par 1000*1000...

pas forcément en O(1), disons qu´il soit toujours relativement rapide de récupérer le tile a la position x,y,z.

typiquement un jeu comme tomb raiser aura des mondes beaucoup moins haut que long ou large.
Mais à supposer qu´il y a par endroit des tours très très hautes, tu commence par une table de type tableau 2D qui donne l´offset ou lire la "colonne" (x,y), puis à cet offset, tu donne la colonne elle même (la hauteur de la colonne est obtenue en lisant par exemple l´offset du début de la colonne suivante).

c´est peut-être ce qu´à dit godrik, mais je n´en suis pas sûr.

Bon le mieux ça serait quand même de compresser le tout. (surtout que dans une colonne, tu doit probablement avoir peu de tiles différentes de "vide").

Oui, je vois le principe : un tableau 2D de pointeurs, finalement, vers d´autres tableaux 1D : et chaque tableau 1D peut avoir une taille différente, cela me parait etre une bonne idée !

Je me rappelle que Lara Croft, un moment, devait descendre treees bas dans un lac souterrain, dans lequel étaient enfouies des statues géantes, en faisant fi des 10 bars de pression d´eau qu´elle devait se prendre sur la tete bien sur C´était amusant !

tiles ou pas tiles, en 3D j´aurais tendance a sortir un classique BSP (solid de preference) + portals + PVS.

Les "tiles" sont p-e pratique pour le level designer, mais c´est loin d´etre optimal comme SD runtime pour le type de requetes qu´on peut vouloir faire dans un monde 3d.
Ici, un solid BSP te file un encodage efficace de la geometry, des raychecks "gratuits", et tu peux meme cumuler avec un "offset BSP" facon "MDK" si tes entites ont les meme volumes englobants.
Des portals te donnent naturellement des cells que tu peux streamer, enlevant la contrainte de memoire.
Quant a la visibilite, avec des tiles c´est pas gagne..
Tu peux aussi facilement utiliser un hitcheck different de la geometrie de rendue ; le seul potentiel endroit ou ca complique un peu, c´est pour les navgraphs.

En regle generale, essayer d´avoir des formats compiles aussi proche du format runtime de la machine que possible ; compresser la ou ca peut l´etre mais sans affecter les perfs. S´ils faut decompresser des formats complexes a la volee, ca n´aide pas. Si ca ne rentre pas en memoire sans enlever du contenu, et qu´on ne veut pas augmenter la charge CPU, le mieux reste de streamer proprement les ressources.

hop, mon idée de la nuit.

Plus fort que l´indexation des lignes, on peut multi-indexer les lignes. Il suffit de faire des blocs indexé de tailles variable. Quand on y réfléchit, c´est l´idée sous jacente de la compression par bloc de gzip ou de bzip2.
On peut alors raisonablement penser que le nombre de bloc est petit devant la taille de la ligne. ce qui fait que retrouver la bonne valeur se fait facilement.
La compression optimale reste un probleme long a faire, mais on ne la fait qu´a la compilation du niveau...

Deplus, il est facil de faire les compressions sur les trois axes et de prendre le plus petit.
Ou alors de faire de l´indexation par plan plutot que par ligne, la encore on peut facilement tous les calculer et prendre le plus petit.