rewind a écrit 3429 commentaires

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 ?

Hum j'ai l'impression qu'il y a une mésentante. Tu met des cases dans ta file, lui te propose de mettre des couples case + direction (un angle), donc le tris prendrait 2 paramètres.

Effectivement, je crois qu'il y a du flou. Parce qu'il parle de mettre une case potentiellement deux fois, ou de mettre à jour son potentiel. Dans les deux cas, je ne vois pas bien comment on fait.

Et alors ? Tu génère ta carte 60 fois par seconde ?

Dans ce genre d'algo de parcours de graphe, il faut faire très attention parce que tu peux très très vite exploser le temps de calcul (un algorithme exponentiel est si vite arrivé). Mes étudiants qui ont dû expérimenter sur ce genre de chose s'en sont très vite rendu compte. Entre l'algo que je décris qui met quelques millisecondes et les premiers algos qu'ils m'avaient pondu qui mettaient plusieurs minutes (quand ils s'arrêtaient), il y a un gouffre. L'important n'est pas la vitesse mais la complexité. Même si on ne le fait pas 60 fois par secondes, on souhaite quand même que ça aille vite pour expérimenter au maximum avant de trouver une carte convenable.

Mais quand tu insères ta case dans ta file, tu sais d'où tu viens, non ? donc tu peux utiliser une altitude absolue "ajustée" pour le tri à ce moment là.
Et si tu retombes sur la même case en venant d'ailleurs, rien ne t'empêche de l'insérer une seconde fois avec une autre altitude ajustée !

Dans une file de priorité, il n'y a qu'une seule fonction de tri (en plus déterminée à la compilation en C++). On ne trie pas la file plusieurs fois, ce n'est pas possible. Si on voulait faire comme tu le suggères, il faudrait une autre structure de données, je pense, et ça serait plus lent. Pour un gain pas forcément important.

et tant qu'on y est, si cette solution marche, on pourrait même imaginer favoriser les lignes droites de la même façon, en ajoutant un petit aléa dans les altitudes des cases adjacentes.

Oui, ça c'est une idée. Utiliser du bruit (plutôt que de l'aléa) pour éviter les formes trop géométriques. Maintenant, ça va se jouer à pas grand chose, est-ce que ça vaut vraiment le coup de le faire ? Je ne sais pas trop.

Par exemple si tu as une rivière qui longe une falaise si tu élargies tu auras un bout de rivière qui montera sur la falaise (un peu cheulou comme résultat non ?).

Les altitudes, c'est pour avoir un truc de base, mais après, cette information disparaît complètement dans la carte finale, donc il n'y a pas de truc chelou. Ou ça ne se voit pas trop.

Sinon j'ai une autre question comment gère tu la profondeur de l'eau (et donc la hauteur de la surface)?

Très simple : je ne la gère pas ;) Sur un jeu en vue de haut, ça ne sert pas à grand chose. Dans mon cas, il va y avoir des rivières que tu ne peux pas traverser et tu en seras empêché physiquement. Et des gués par lesquels tu pourras passer. Donc, ça ne sert à rien de gérer une profondeur.

http://www.akagoria.org/ voilà ;)

Et du coup, il y a moyen de mettre à jour le lien permanent pour qu'il y ait un 11 à la place du 10 ?

Je m'aperçois que je n'ai pas incrémenté le numéro d'épisode. Est-ce qu'un gentil modo pourrait corriger cette erreur ? Merci !

Non, pour l'instant, je ne pondère rien. Et ça me paraît même compliqué de pondérer. Parce que la pondération, elle est relative à une position. Or, pour ma file de priorité, j'ai besoin d'avoir des informations absolues, pas relative. Il faudrait revoir complètement l'algorithme ou alors ne plus considérer les déplacements diagonaux (mais dans mon souvenir des premiers essais, ça ne rendait pas très bien).

Bonnes questions. J'ai quelques réponses.

J'ai une question sur tes rivières, a l’œil on a impression qu'elle vont principalement en diagonale est-ce un biais au niveau de l'algo de rivière ou de celui le l'altitude ou un pur hasard ?

C'est un biais assumé au niveau de l'algorithme. J'ai fait divers essais et c'est ce qui donnait les meilleurs résultats. Il faudra que je regarde ça à nouveau parce qu'avec une file de priorité, ça ne devrait pas changer quelque chose (en fait, je me dis que ce biais datait de l'époque où j'utilisais une simple file). C'est sans doute aussi un biais au niveau des données, parce qu'en allant en diagonale, tu as plus de chance d'avoir une différence d'altitude plus élevée qu'avec la case à côté.

Autre question j'ai pas vue de notion de débit ou de largeur de rivière qui augmente au fur et a mesure de la distance, de l'arrivée d'un affluant ou même lorsque le terrain s’aplanit?

Dans les versions préliminaires, j'élargissais la rivière au fur et à mesure. En fait, elle était générée de la même manière mais au moment de l'afficher, j'affichais soit le point tout seul, soit le point et les quatre points adjacents (horizontaux et verticaux) à partir de la moitié, soit le point et les huit points adjacents (horizontaux, verticaux diagonaux) à partir des 3/4. Je pense que je vais le réintroduire parce que ça marchait plutôt pas mal. Et maintenant, avec les améliorations des biseaux, ça peut rendre vraiment bien. Surtout que les rivières sont assez peu larges comparées au personnage.

J'ai également fait une petite mise à jour du site web pour le rendre moins austère. Vous me direz ce que vous en pensez ;)

J'ai regardé un peu le protocole et ça m'a l'air assez clean. Tu penses que ça vient de l'implémentation ? D'après le bug tracker, il y a pas mal de problèmes.

mode Zenitram ON

Donc tu voudrais qu'il bosse gratuitement pour toi ? Ha ben non, il faut payer, aucune raison qu'ils bossent pour toi gratuitement. C'est ça le libre, tu comprends rien au libre, tu crois que les autres vont faire des choses pour toi gratuitement ?

mode Zenitram OFF

Je l'ai bien fait ?

proposer quelque chose d'unique avec une vraie personnalité

Tu veux dire que le but de GNOME est d'arriver à un seul utilisateur ?

on est justement dans deux cas où je trouve qu'il y a énormément de place perdue en haut de la fenêtre. Que ce soit sur celle intitulée "Test" ou sur la calculatrice, il n'y a quasiment aucune information pour une occupation vraiment importante.

En fait, on a fusionné deux barres avec beaucoup d'informations en une seule, en perdant beaucoup d'informations, mais finalement, cette barre est aussi imposante que les deux anciennes réunies, sans les informations… Moi, les designers de GNOME, je les brûlerais de suite en place publique :P

Il y a une news en attente qui était en tribune de rédaction ces jours derniers, je trouve ça un peu limite de faire cette annonce en concurrence, surtout vu la qualité de l'annonce…

Après, on peut lutter contre ça ou au contraire jouer avec. Finalement, c'est aussi ça le libre, ça peut permettre de revoir le game design. Certes, ce n'est plus le même jeu après, mais au moins, des gens y jouent.

Il est probable que d'ici une dizaine d'années, les latences réseaux ne seront plus un problème pour le jeu vidéo. Mais en 2014, si on souhaite avoir un jeu accessible par Mme Michu, ou son gosse, on ne peut pas l'oublier.

Évidemment que tout le monde, à l'heure actuelle, n'a pas une super latence qui permet de jouer à tout et n'importe quoi. Mais après, si on se met à vendre qqch, il faut raisonner en terme de marché. Est-ce que mon marché, c'est l'ensemble des gens connectés à Internet ? Non, c'est ceux qui ont une bonne latence, ça représente déjà pas mal de monde et ça ne va faire que grossir.

Surtout si on veut faire du libre et qu'on est une petite structure, on ne va pas viser un gros marché, ce n'est pas cohérent. Ma stratégie, ça serait plutôt de faire simple et clair, et comme c'est libre, si qqn veut proposer des améliorations pour réduire la latence, il est le bienvenu.

Il faut simplement une procédure pour exclure les gens qui ne comprennent pas que tricher, c'est s'enlever le plaisir du jeu.

Le problème vient du fait que si tu commences à faire payer tes joueurs, tu vas aussi exclure des gens qui paient. Et rien ne dit que ça va faire venir des non-tricheurs qui paieront. Je connais au moins un jeu qui souffrent de ce problème : plein de moyen de tricher, aucune volonté apparente des équipes de dev de changer ça, des grandes déclarations mais finalement, on laisse les tricheurs en place parce qu'ils paient bien (sauf s'ils trichent pour ça aussi, mais ça, ça sera corrigé vite).

Dans un jeu vidéo, une telle resynchronisation nuit souvent à l'immersion (syndrome du joueur téléporter à cause d'un pic de latence), et on laisse donc au client une certaine marche de manoeuvre, le serveur acceptera, jusqu'à une certaine mesure, la position d'un client même si elle est différente de celle qu'il a lui même calculé.

Tu vois, tu pointes toi-même le problème de conception qui facilite la triche. Donc, tu valides quelque part ce que je dis. Après, la solution, elle va venir d'une part de la rapidité des réseaux (qui font qu'on aura moins de latence) et de l'architecture (logicielle) des serveurs qui sauront exploiter les les multi-processeurs ou tout autre technique qui permet de traiter les données plus rapidement. Sans doute aussi par un changement des règles dans les cas critiques (moins de joueurs par carte, etc).

Tu tiens vraiment à ce que tes commentaires descendent encore plus vite dans les négatifs ?

Mais en même temps, je pense que ça doit être une misère pour qui s'occupe de la triche en ligne d'avoir aussi facilement accès à tous les paramètres…

Pas vraiment. Pour tous les jeux où les paramètres sont importants, même quand ils sont propriétaires, les formules sont retrouvées en deux temps trois mouvements. Les avoir directement ne changera rien. Après, pour le reste de la triche, c'est plus la manière de coder et de concevoir qui va permettre d'éviter la triche ou pas.

Ce que tu pointes est juste mais je pense que tu ne vas pas assez loin dans la réflexion. Le libre fonctionne parce qu'il est gratuit, mais aussi parce qu'on peut avoir la main sur le code et pour tout l'écosystème autour (je fais vite). Actuellement, les jeux libres ne se différencient pas de leurs homologues propriétaires, ils sont juste libres (et gratuits pour l'immense majorité).

De la même manière que les jeux FaceBook ne sont pas les mêmes que les jeux traditionnels sur PC, qui ne sont pas les mêmes que les jeux console, je crois qu'il faut trouver ce que peut apporter comme plus un jeu libre. Je n'ai pas de réponse pour l'instant, mais à un moment, il va falloir se poser la question : qu'est-ce qu'on pourrait faire avec un jeu libre qu'on ne pourrait pas faire avec un jeu propriétaire ? Libre et gratuit ne suffiront pas, c'est clair.

Je pense surtout qu'il faut du temps avant de trouver un modèle économique adapté aux jeux libres. Déjà pour le libre, il a fallu bien 10-15 ans avant qu'une boîte arrive à survivre en faisant du libre. Avec les jeux libres, on n'est qu'aux balbutiements, ça commence à monter en puissance, on peut avoir quelques toute petites boîtes qui arrivent à survivre, mais pas encore des moyennes entreprises. Ça viendra, mais il faut laisser du temps.

Pour moi, tous les indicateurs passent au vert ces derniers temps. On a des pilotes (libres) qui commencent à ressembler à quelque chose et qui progressent vite. On a une infrastructure graphique qui prend de la maturité (et Wayland en est la meilleure preuve). On a des bibliothèques et des frameworks éprouvés qui permettent de faire de bons jeux dans quasiment tous les genres. On a des entreprises qui investissent dans tout ça, même si elles continuent à faire du propriétaire geôlier. Si on compare avec 5 ou 10 ans en arrière, on a sacrément évolué dans le bon sens. Attendons et ça arrivera.

Généralement, la «forme normale de Coplien» (première fois que j'entends ce terme) est utilisé dans le cadre de ce qu'on appelle le Rule of Three : si on implémente un des trois suivants, on implémente les deux autres : constructeur par copie, affectation, destructeur. Et depuis C++11, on a presque le Rule of Five avec le constructeur par déplacement et l'affectation par déplacement. Mais en fait, vu qu'on a maintenant des classes qui gèrent ce genre de cas très bien (shared_ptr, unique_ptr), on a un Rule of Zero (parce que les méthodes par défaut feront exactement ce qu'il faut).

Du coup, je pense que le livre s'est arrêté avant C++11.

Ce n'est pas la question. reno fait semblant que C++ est un langage récent mais se traîne des headers. C'est complètement à côté de la plaque de comparer C++ avec des langages conçus récemment. On peut affirmer qu'on aimerait bien une notion de module, sans oublier que les headers de C++, ça ne date pas d'hier non plus.