Differences

This shows you the differences between two versions of the page.

Link to this comparison view

en_map_generator [2008/09/30 11:54]
hadrien
en_map_generator [2008/09/30 12:21] (current)
hadrien
Line 13: Line 13:
 === Extension === === Extension ===
  
-Lorsque le "pointeur" ​est sur un morceau de carteet souhaite se déplacer au delà de ce morceau sur la droite ​(par exemple), la première chose à faire est de regarder si ce morceau existeOn considère que la carte est consistancec'est à dire que si le morceau existe, il est rattaché au morceau courant, même si ce n'est pas à partir de ce morceau que la carte été crééIl faut éviter par exemple la situation suivante ​:+When a "cursor" ​is on a map chunkand wishes to move beyond this chunk (e.g. on the right), first thing to do is check whether this chunk exists alreadyTo achieve thisone need consistent map, meaning that every neighbor chunk is connected to each otherFor example, this case must be avoided:
  
 <​code>​ <​code>​
-x : morceau alloué; X: nouveau morceau ​ +x : allocated chunk; X: new chunk 
-- : liaison entre morceaux de carte+- : link between map chunks
  
-Etape 1:                  ​Etape 2:+Step 1:                  ​Step 2:
 . . . . . . . . .         . . . . . . . . . . . . . . . . . .         . . . . . . . . .
  
Line 29: Line 29:
  
  
-Etape 3:                  ​Etape 4:+Step 3:                  ​Step 4:
 . . . . . . . . .         . . . . . . . . . . . . . . . . . .         . . . . . . . . .
  
Line 39: Line 39:
 </​code>​ </​code>​
  
-On voit dans l'​étape ​que le dernier morceau de cartecréé par la droiten'est pas relié au morceau du dessusLa carte n'est donc pas cohérente, car depuis le morceau d'​origine, on ne pourra pas savoir que le morceau du dessous existe; il y a un risque pour qu'il soit recréé sans contenir les informations correctes. Pour résoudre cette situationil faut s'assurer qu'à la création d'un morceauce morceau soit immédiatement rattaché à tous ses voisins. Dans le cas simple exposé ci-dessusun algorithme simple controllant l'​existence de voisins pourrait faire l'​affaireMais que ce passe-t-il si la carte est plus compliqué?​ +When the last chunk is created in step 4, the way it has been created makes it separated from above chunkwhich leads to a non-consistent mapIndeedwhen on top-left chunkwe don't know that a chunk exists belowand there is a risk for creating again this chunkbreaking the whole mapTo solve thiswe must ensure that a chunk is immediately linked to all its existing neighbors. With complex map (such as in the following scenario) you cannot do that in an acceptable timeso we need to find way.
- +
-En effet si l'on créé les morceaux un par unau moment où l'on en besoinon n'pas de moyen aisé de relier les morceaux nouvellement créés à leur voisins : il faut parcourir tous les chemins possibles menant au nouveau morceauPar exemple, la situation suivante est problèmatique :+
  
 <​code>​ <​code>​
-x : morceau alloué; X: nouveau morceau ​ +x : allocated chunk; X: new chunk 
-- : liaison entre morceaux de carte+- : links between map chunks
  
-Dernière étape de parcours          Carte finale voulue:+last step of a                        Expected map: 
 +given discovery:
 . . . . x-x-x-x-x ​                    . . . . x-x-x-x-x . . . . x-x-x-x-x ​                    . . . . x-x-x-x-x
         | | |   ​| ​                            | | |   |         | | |   ​| ​                            | | |   |
Line 57: Line 56:
 </​code>​ </​code>​
  
-Dans la figure ​ci-dessuson parcours un genre de couloir circulaire en partant d'en bas à gaucheet en tournant dans le sens des aiguilles d'une montreUn algorithme relativement simple permettra de créer les liaisons multiples de la salle en haut de la carte. Par contre pour obtenir la carte voulue il faut créer la dernière liaison en bas à gauche de la carteet pour cela il faut parcourir la totalité de la carte. +In the above figure, ​some kind of circular path is realizedand in the last step we arrive to our starting pointBut without a (too) complex algorithmyou cannot tell that you're on the starting point again.
- +
-Pour éviter l'utilisation d'un tel algorithme, ​on va simplifier le problème, en créant des morceaux inutiles, mais qui permettront à chaque moment d'​avoir une carte rectangulaire "​pleine"​. Reprenons notre premier exemple, en faisant en sorte de toujours former un rectangle avec nos morceaux, quitte à créer des morceaux inutilisés.+
  
 +To avoid such complexity, we can keep a map structure "​full",​ by creating empty chunks. Let's watch our first example with such an algorithm:
  
 <​code>​ <​code>​
-x : morceau alloué; X: nouveau morceau; Y: nouveau morceau inutile pour l'​instant +x : allocated chunk; X: new chunk; Y: new chunk, useless for the moment 
-- : liaison entre morceaux de carte+- : links between map chunks
  
-Etape 1:                  ​Etape ​2:+Step 1:                   Step 2:
 . . . . . . . . .         . . . . . . . . . . . . . . . . . .         . . . . . . . . .
  
Line 76: Line 74:
  
  
-Etape 3:                  ​résultat voulu (idem étape ​3):+Step 3:                   expected map (same than step 3):
 . . . . . . . . .         . . . . . . . . . . . . . . . . . .         . . . . . . . . .
  
Line 86: Line 84:
 </​code>​ </​code>​
  
-Icidans notre algorithme, une extension vers la droite est simple, et ne nécessite que la création d'un morceauPar contrel'​extension vers le bas, pour suivre le principe consistant à toujours avoir un rectangle, nécessite la création d'une rangée complète de morceauxDans notre cas, deux morceaux sont créés. Le morceau en bas à gauche est inutile à l'​étape ​3, mais devient utile dès l'​étape 4. A l'​étape 4, aucune création n'est nécessaire,​ on évite donc le risque d'​incohérence. On gagne en complexité algorithmique,​ on perd en complexité spatiale.+Hereextending map to the right does not involve creation of useless chunksBut going downward in step 3 implies creating two chunksone that will be used at once (X) and another one (Y) which is here only to keep map consistence and avoid missing chunk links laterWhen you go left after step 3, the chunk already exists and is already linked to very first chunk.
  
 === Optimisations === === Optimisations ===
  
-Si l'on voulait améliorer la complexité algorithmiqueil faudrait entièrement revoir le processus d'​extension de la carteCe n'est pas à l'​ordre du jour pour l'​instant. +We improved algorithmic complexityat the price of memory complexityYet it is easy to have a small impact by allocating data matrix only when you need itCreation of a useless chunk would only use some bytes in memoryWhen accessedthis chunk will always return "CELL_UNKNOWN", which is the initial ​state of every cell in the matrixWhen first filledchunk matrix would be allocated
-La complexité spatiale est légèrement sous-optimale,​ car certains morceaux sont créés inutilementLa structure même en morceaux fait que cette perte n'est pas trop importante. On peut cependant limiter cette perte en créant des morceaux sans allouer la mémoire pour la matrice. La matrice serait allouée au premier remplissage;​ tant qu'​elle n'est pas crééetoute lecture sur ce morceau renverrait ​CELL_UNKNOWN ​(état ​initial ​des cellules de la matrice)Nous aurions une structure de carte "​creuse"​les morceaux créés mais inutilisés ne contenant que les pointeurs des morceaux voisins (ce qui occupe une place négligeable par rapport à la matrice de données).+
  
 ==== Parcours ==== ==== Parcours ====
 
en_map_generator.txt · Last modified: 2008/09/30 12:21 by hadrien
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS La rache Driven by DokuWiki