en fait, j'avais plutôt cru comprendre que c'est une insersion triée que tu fais et pas un tri global à chaque fois
En fait, ce n'est ni l'un ni l'autre. C'est une file de priorité. C'est une structure de données qu'on appelle aussi un tas, ça permet d'insérer en O(log n) et d'avoir accès au plus petit élément en O(1). En revanche, les autres éléments ne sont pas triés globalement mais grossièrement on va dire. En fait, un tas, c'est un arbre binaire pour lequel tu as deux propriétés : un nœud est plus petit que tous ses fils, et l'arbre est presque complet (c'est-à-dire qu'il manque uniquement des nœuds sur la dernière ligne). En pratique, ça s'implémente très efficacement avec un tableau. Avec une liste triée, tu insères en O(n), tu ne peux pas faire autrement, et du coup, c'est moins efficace.
La complexité est ajoutée au moment d'ajouter un élément dans ta liste triée. Il faut pondérer son altitude absolue par un facteur "judicieusement" choisi.
Et ça, je conçois tout à fait que ça n'est pas trivial.
Surtout, le problème que je vois, c'est que les cases sont en plusieurs exemplaires dans la file. Comment tu gères ça ?
[^] # Re: Rivière en diagonale, et taille des rivière?
Posté par rewind (Mastodon) . En réponse à la dépêche Je crée mon jeu vidéo E11 : génération procédurale de carte (partie 2). Évalué à 2.
En fait, ce n'est ni l'un ni l'autre. C'est une file de priorité. C'est une structure de données qu'on appelle aussi un tas, ça permet d'insérer en O(log n) et d'avoir accès au plus petit élément en O(1). En revanche, les autres éléments ne sont pas triés globalement mais grossièrement on va dire. En fait, un tas, c'est un arbre binaire pour lequel tu as deux propriétés : un nœud est plus petit que tous ses fils, et l'arbre est presque complet (c'est-à-dire qu'il manque uniquement des nœuds sur la dernière ligne). En pratique, ça s'implémente très efficacement avec un tableau. Avec une liste triée, tu insères en O(n), tu ne peux pas faire autrement, et du coup, c'est moins efficace.
Surtout, le problème que je vois, c'est que les cases sont en plusieurs exemplaires dans la file. Comment tu gères ça ?