rewind a écrit 3434 commentaires

A l'heure où les DRM enferment les utilisateurs, Mozilla négocie le poids des chaînes

ça dépend, tu es dans l'armée américaine ou pas ?

Je pense que tu as raison. D'après ce que j'ai pu voir dans la libcxx, c'est bien le cas.

Merci ! Je ne savais pas si c'était possible, j'ai demandé au cas où. Mais ça me perturbait de voir un 10 à la place du 11. Du coup, c'est mieux comme ça, je suis soulagé ;)

c'est donc unse insertion triée ;) ce que tu décris, c'est une std::map (implémenté par un red/black tree au moins dans la lib c++ livrée avec gcc)

Non, c'est une std::priority_queue et ça n'a rien à voir avec un arbre binaire de recherche, mais vraiment. Dans un arbre binaire de recherche, tu n'as pas accès au plus petit élément en O(1) mais en O(log n) parce que c'est l'élément le plus à gauche dans l'arbre et donc tu dois descendre sur une branche.

C'est bien un tas dont on se sert pour implémenter cette file de priorité.

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 ?