Path finding du plus droits chemin

Bonjour,

Je viens de finir une version préliminaire du path finding pour le plus droits chemin.
Mais pourquoi le plus droits et non pas le plus court?
  • Car cela permet de minimiser le volume réseau
  • Minimiser le changement de contexte coté OS à cause de multiple trame réseau
  • Minimiser le changement de contexte coté application car il doit géré un client, puis un autre, puis revenir sur le 1er
C’est loin d’être optimal coté implémentation (ont ne peu pas changer de map, intérragir avec les objets, …), mais c’est fait. C’est assez complexe car il y as 4 informations par tile, au lieux de une dans un path finding avec le plus cour chemin.
Cela permettra de reduire les couts de fonctionnement du projet.
1er post fait avec blogilo car chrome bug pour les accents depuis quelques versions.
Bye,

 

Technologie utilisé dans CatchCallenger

Manipulation du buffer réseau

0 copy

La technologie 0 copy technologie est un moyen pour ne jamais copier un buffer dans un autre (bien sur qu’en interne ont ne peu y échapper, par exemple pour transférer le buffer de la carte réseau jusqu’au programme). Vous déplacez seulement le curseur sur les données et vous controlez les données. Aprés vous pouvez:

  • Isolez le code principal et retournez les données comme une structure
  • Directement tout passer comme une structure

La structure de donnée est exclusivement de taille fixe car les tailles dynamique exige pointer et copie mémoire. (Et vous ne pouvez pas envoyé un pointeur au travers du réseau)

Si une donnée est supérieur à 8Bits, alors vous devez corrigez l’endianness, cela coute principalement des petites transactions mémoire.
Cela est pour envoyer des commandes avec des arguments temporaires. Les données persistantes ont besoin d’être stocker et donc n’autorise pas le 0 copy. Vous devez les garder quelque part car le buffer vas être purger.

SIMD

Sur Arm c’est neon, sur x86 c’est SSE-X, AVX-X. Pour en savoir plus, voir: http://en.wikipedia.org/wiki/SIMD
Ils permettent de copier un block mémoire avec une seuls instruction, c’est plus puissant qu’une boucle car cela exploite mieux le hardware sans avoir besoin d’utiliser les capacités de Vectorization du compilateur, voir: http://en.wikipedia.org/wiki/Vectorization_(parallel_computing)
Si une plage d’octet est valide, vous pouvez avoir un structure similaire as: 99x8Bits dans le buffer,  »’vous pouvez utiliser memcpy() pour transférer une plage d’octet directement depuis le buffer sur la structure »’.
Si une donnée est supérieur à 8Bits, alors vous devez corriger l’endianness, cela coute principalement des petites transactions mémoire. Voir le déserialiseur.
Cela est plus orienté pour le stockages des données mais peu être utilisé avec des données temporaire dans certains circonstances..

Déserialiseur

Cela est plus lent que le SIMD, mais cela est adapté pour les stockages d’informations qui doit être traités. Par exemple en chaine qui doit être transformer en pointeur + taille (mix avec les SIMD arrive souvent), vous devez changer l’Endianness pour la plus part des entiers, …
Priviligez de démarrer avec les adresses basses (buffer[0]) jusqu’au adresses haute (buffer[99]) pour améliorer les performances.

0 Allocation mémoire

La plus par du temps, n’ayez pas d’allocation mémoire, ou dans le pire des cas sur la stack. Grace à un protocole binaire, une taille fixe, un buffer permanent pour déserialiser les données est une bonne solution.
Toutes les opérations réseau lourdes comme le chargement du datapack peuvent être externalisé. Sur des serveurs hautes performances seul le trafic utile est envoyé et reçu, il y as donc de meilleur latences et un serveur plus légé, …

Binaire

Le texte peu être utile pour débugger, mais il utilise beaucoup de réseau et ressources.
Moins d’un accès sur un millards sur http est lu directement depuis le dump réseau (par des hackers, admin réseau, développeur -> vous devez avoir le niveau pour travailler avec, au même titre que manipuler des images/videos), cela veux dire que le reste du temps les ressources sont consommés sans raison, un protocole http binaire serai afficher de la même manière que le protocole http text dans un navigateur.
Pour utiliser les données « Data: 654654″‘ vous devez extraire « 654654 » (vérifier la longueur, faire une allocation dynamique) puis  »’le convertir en nombre »’. En binaire faite juste une copie (a=b;) et corriger l’endianness si besoin. ce qui est beaucoup plus puissant en binaire. La negociation du protocol en binaire été de 66 octets, en binaire elle est seulement de 5, avec un gain de 50x d’utilisation du cpu sur les opérations de lecture et comparaison.

Anti DDOS et cout de l’infrastructure

Toutes ces technologies et un bon usage du compilateur comme -march=XXX, permette d’être anti-DDOS par nature car cela permet de supporter un grand nombre de requêtes par seconde. Cela minimise le cout de l’infrastructure, autorise un jeu moins chère, plus de serveur pour les joueurs. Cela est donc plus dur à DDOS, C’est aussi plus facile à administré.

Epoll

Epoll est utilisé pour résoudre le problème C10K. Le serveur peu facilement supporter beaucoup de joueur sur un ordinateur de 25ans. Il ne saute pas la couche tcp du noyau pour fonctionner correctement en para-visualization, mais un bonne optimisation permet de résoudre le problème C10M sur un bon hardware.

Plugin

La plus par des parties standard comme la visibilité sur la map, base de données sont dans des classes et géré comme des plugin pour être changé, testé et benchmarké facilement.
Les plugins des bases de données en mode texte demande beaucoup de conversion du text vers des entiers (utilisation du cpu sur le serveur), la manipulation des chaines due à SQL prends aussi beaucoup de cpu/memoire/allocation mémoire aussi, et finalement la base de données sur le même serveur consomme aussi des ressources.
Inclut avec index et optimisé, la base de données est largement la partie la plus lente du serveur (tant coté cpu, memoire que IO disk), c’est pourquoi les requêtes sont asynchronisés.

Traduit de: http://catchchallenger.first-world.info/wiki/Technologies_used

Note: le protocole ftp en plus d’être text oblige de supprimer le contenu des dossiers pour supprimer ces dossiers. Vous passez donc de l’envoie de quelque octet et quelque ms 0 des Mo et des minutes heures pour supprimer les gros dossiers… Et vous contourner toutes les optimisations des FS sur la suppression des dossiers…

Ssl et serveur de MMORPG

Bonjour,

Je suis en train de mettre en place l’infrastructure pour commencer dans la prochaine version le supports des clusters.

L’overhead (qui est assez couteux sur http1) de la couche Ssl est peu important sur un serveur de type MMORPG car il garde la connexion ouverte. Par contre, à cause des petits packets envoyé à intervalle éloigné (ont de peu donc pas les grouper), la couche Ssl deviens extrêmement lourde. Le ralentissement vis à vis d’une connexion en claire est de 24x sur un Intel haswell (avec prise en charge matériel).

Les syscall pour les events des trames réseaux sont trés correcte et ont un coût minimum car il sont multipléxé sur epoll avec linux. Ca semble un peu du bricolage pour les timers, … je veux même pas voir d’autre syscall… Par contre une lecture/écriture sur un socket = un syscall, ce qui peu devenir très lourd rapidement. Une suggestion sur le problème C10M est de by-passer le noyau, cela oblige de ré-implémenté TCP, c’est trop dangereux et dur pour être fait (hors mit cas spéciaux). Par contre un syscall pour multipléxé les entrées/sorties sur socket peu être utile.

Comment bien découper votre serveur pour avoir un cluster de serveur? Déjà il faut l’avoir bien optimisé pour maximiser le ratio utilisateur par serveur/nombre de serveur. Car le mode cluster à un cout. Ensuite balancer via un round-robin dns sur plusieurs frontaux (cela permet de s’affranchir de HAPROXY, ou tout autre système qui serai à notre charge et moins fiable). Hors mit les clients, les frontaux doivent avoir le minimum de connexion, alors n’utilisez pas de maillage, mais une structure de serveur en arbre. Dans le cas de CatchChallenger cela vas être une connexion pour la base de données, et une connexion pour un serveur racine (chargé de broadcast, ou de passé le client sur un autre serveur via reconnexion pour séparer les serveurs: une groupe de serveurs = un groupe de maps dans la même zone). La découpe vas influer fortement sur votre cluster, spamer des threads dans tout les sens et n’importe comment vas ralentir votre serveur (apache worker vs nginx/lighttpd). Je vous conseiller d’attaquer votre db en asynchrone, et qu’elle ai plusieurs frontaux. Vous pouvez coder la communication inter-serveurs en claire, et faire des tunnels de communications crypté via openssl pour sécurisé l’échange. Cela permet un maximum de performance sur un réseau de confiance, et de la sécurité sur internet.

Ssl fourni une compression activé par défaut. Je trouve cela assez mauvais, car la compression devrai être séparé de la cryptographie. Pour une question de sécurité, mais aussi de fléxibilité: toutes les formes de compression ne sont pas disponible (xz), et certain protocole comme CatchChallenger à sa propre compression adaptative interne qui est bien plus efficace. La compression devrai être donc si disponible, désactivé par défaut (bien que mon opinion n’est pas tranché sur ce point). La compression, même gzip/zlib doit avoir au moins 100 octets pour être efficace, hors la grosse majorité des packets de CatchChallenger fait moins de 6 octets. Et le reste est compressé…

J’espère vous avoir aidé.

Optimisation dans CatchChallenger

Salut,

J’ai fait de grosse optimisation dans CatchChallenger. J’ai composé le packet pour ensuite l’envoyer sur chaque client au lieu d’envoyer les variables et que chaque client compose le même packet. Cela donne un gros coup de boost sur les fonctions de type broadcast.

Ensuite j’ai fait une boucle ou j’appelle tout les clients, et j’ai connecté un QTimer dessus. Cela est bien plus efficace que de connecté ce timer sur chaque client (8x de performance).

Moins vous allez accéder à de grosse quantité de mémoire, plus il vont tenir dans un cache CPU performant, et donc vous allez gagner en performance (évitez d’allouer la mémoire aussi, si non RTT), sur mon haswell (pris grace à memtest86+):

  • 64Ko L1 202 427Mo/s
  • 256Ko L2 52 675Mo/s
  • 6144Ko L3 37 592Mo/s (répartie entre tout les cpus)
  • 8239Mo Mémoire 9 375Mo/s
Autant vous dire tout de suite, les performances pour un serveur MMORPG même bien fait, c’est:
  • à vide (<20 joueurs) utilisation du L1 trés performant
  • charge moyenne (<100 joueurs) utilisation du L2/L3
  • à forte charge (>2000 joueurs) utilisation de votre mémoire bien lente même si vous avec GDDR5/DDR4 avec un grosse fréquence en comparaison des caches interne (surement dans ce cas que votre config tirerai partie d’un mémoire rapide)
Et pourtant je fait passé sans problème le serveur de MMORPG sur un Intel Atom ou un Cortex-A9 à 1Ghz avec 6000 joueurs (charge simulé en les répartisant sur map map, avec les pires réglages, en débug, et avec génération de chat, déplacement, …). Hors mit les hash qui peuvent être consommateur de CPU, le reste de mon code utilise des variables/tableaux de variable avec presque aucun calcule dessus, donc le temps est passé à attendre la mémoire.
Pour finir, je constate même à l’heure actuelle, 99% du temps pris pas la gestion des events de Qt. Je ne sais pas encore si il y as un truc à faire pour mon cas (pas mal d’objet connecté entre eux pour un même client), ou si je vais devoir m’orienter vers un autre système d’event et donc réseau (boost?).
Limiter la fragementation mémoire aide à avoir des création d’objet et allocation mémoire plus rapide.
Bye,

CatchChallenger et son datapack/db

Bonjour,

C’est quoi un datapack? C’est le pack de donnée contenant les données du jeux, les ressources si vous préférez. Pour CatchChallenger, c’est les monstres, les attaques, les images, les items et leurs utilisations, les maps, …

En comparant avec certains datapacks (PWO, PokeNet, Pokemium) pour faire des outils d’importation automatique, pour faciliter le passage sur mon jeu, je me suis rendu compte des problèmes des autres datapack:

http://catchchallenger.first-world.info/wiki/CatchChallenger_vs_other

Les traductions sont dans tout les coins (en plus de pouvoir avoir des choses sans traduction et des traductions qui ne sont relié à rien). Plein d’informations sont sortie de leur contexte, soit j’ai eu du mal à comprends ce que c’été, soit j’ai simplement pas compris. C’est souvent une simple liste d’éléments dans un fichier texte (par exemple ont sais même pas à quel map c’est relié, quel monstre, bot, …). Ça veux dire que si ont supprime un ligne, ça décale tout et tout deviens faux. Pour trouver certaines info sur les map, je doit résoudre la map avec son nom, puis de sont nom vers l’info, et donc si le nom change l’info n’est plus trouvable…

Vous aller me demander, mais quel format utilise t’il? Des fois des fichiers binaires, mais bien souvent un mix de fichiers textes de différents types: texte brute avec de simple retour à la ligne, des fichiers ini et des fichiers xml. Le tout en même temps, cela oblige de lire et de programmer de différente manière, cela est typique quand les développeurs ont beaucoup changé sur un même projet. La perte de performance lié au fichiers texte n’est pas important car tout datapack devrai (coté client et serveur) être chargé en mémoire et pas analysé en temps réel.

Avec CatchChallenger, c’est que du xml. Les traductions sont juste au dessous du texte en anglais (avec un lang= »fr » dans la définition de la balise), les attaques à apprendre pour les monstres sont dans la balise du même montres. Les ids sont la pour garder en base de données des nombres simple, minimiser l’espace en db, ne pas changer les références en cas de changement de nom, faire une indexation plus efficace. J’ai vu dans les autres datapack, qu’il y avais pas mal d’info que je n’utilisais pas, comme la classe, l’habitat, … informations que j’ai rajouter dans le xml car le format le permet. Et plus tard pris en compte dans l’application. Le faite d’avoir du xml permet d’organiser les items sous formes de liste mais aussi sous forme d’arbre, ce qui est trés pratique pour les données lié.

Le format des images est assez anarchique dans les autres datapack, elle n’ont pas le même centrage (raison?), certaines avec un fond transparent, d’autre avec un fond noir ou rose, … CatchChallenger supporte le gif, png et jpeg pour s’adapter aux images les plus diverses (jpeg pour les fonds d’écran, png pour les monstres en grands et miniatures, gif pour les miniatures et attaque animé), au choix de celui qui fait le datapack. Le datapack officiel à des images sur font transparent.

L’avantage lié à ces formats comme le xml, png/jpeg/gif (même si ce n’été pas recherché), c’est qu’il sont utilisable dans un navigateur, par exemple pour afficher comme je le fait actuellement sur le site officiel, les images des items/joureurs dans les pages web. Vous pouvez donc voir la partie statique du datapack, comme les informations en temps réél de la base de donnée.

Les données que j’ai vu sont buggées dans la plus part des datapack, même les liens entre les maps. Souvent car il sont à 2 endroits et qu’il ont été mise à jour des fois d’un coté, des fois d’un autre coté. Donc j’ai du coder un minimum de contrôle pour l’importation. Par exemple les attaques, il y as juste l’information power, et pas le changements de status si besoin, cela à cause du format ini pas adapté pour ça. Le xml permet des éléments optionnel, donc pour les bot de combats, ont peu spécifier ou non les attaques des monstres, pour les montres sauvage, ont peu soit ecrire le niveau min/max avec levelMin/levelMax ou un niveau unique avec level.

Dans la db, il stocke des données statique, statiquement, je m’explique… La maximum de vie est stocker sous forme de hp, donc si le datapack change le nombre de hp, il faut adapter toutes la base de données. En plus garder quelque chose en base de donnée alors qu’on l’as dans le datapack c’est bête, ça bouffe de la place en base de données. Dans ce cas, pour minimiser la base de donnée, j’aurai fait un type text, avec comme contenu: « HP:+50;SP:-10 ». Cela permet de ne pas prendre de place quand il n’y as pas de bonus (90% du temps), et de s’adapter au contenu du datapack. Bien sur si un objet est tenu, il est mieux de calculer les bonus directement depuis l’objet, au lieux de stocker l’effet en db. Cela permet d’adapté l’effet, et de limité le nombre d’effet possible. Ensuite une bonne utilisation des types, tant coté C++ que coté db est important pour limiter la taille mémoire et disque, et les index pour obtenir rapidement les infos en gardant à l’espris qu’une db sera toujours lente (et donc avec un temps d’accès).

Le datapack de CatchChallenger est commun entre le client et le serveur. C’est le même. Cela veux dire que si des personnes essayent de m’attaquer juste pour me faire fermer ou pour essayer de me faire cracher du fric, chaque personne s’étant connecté sur un serveur précis, peu facilement remonté le même serveur avec le même contenu lui même, depuis chez lui avec se petit connexion adsl de campagne. Hors fichiers lourd (image, musique), 80% en balise, et 60% en volume sont commun entre le serveur et le client. Le serveur doit avoir la partie client pour que le client puisse télécharger le datapack pour jouer. Et la partie spécifique au serveur qui se retrouve sur le client est minime (<1%). Une grosse partie la pour pouvoir faire les calcules coté client et coté serveur. Car si c’est fait juste coté serveur, cela oblige d’avoir de RTT (round-trip delay time (RTD) or round-trip time (RTT)).

Grace à cela, je me prémuni aussi des fermetures arbitraire de mon serveur. Imaginons que X essaye de faire fermer mon serveur entier par ovh (donc avec Ultracopier, …). Juste parce-que cette personne dit que mon jeu est trop proche d’un autre. Pas grave, je peu l’héberger chez moi, chaque personne peu le reprendre en plus si besoin. Et donc mon serveur se retrouve avec juste des sites, pas le serveur de jeu, et ont peu donc rien lui reprochez. Cela permet aussi que chaqu’un dispose du datapack pour faire sont propre contenu, et donc cela ne limite pas la créativité.

Apparemment PWO, PokeNet, Pokemium, ont été codé par des amateurs (comme beaucoup de petit jeux et de jeux de fan). Sur l’implémentation c’est pas grave car ça peu facilement être changer. Par contre sur le protocole et le datapack cela est fortement handicapant. Le protocole permet une bonne réactivité, sécurité et communication. Et le datapack, d’être repris, modifié, …

Le projet avance, petit à petit. Vu que je le fait sur mon temps libre, il avance pas aussi rapidement que je le voudrai. Pour la version 0.2 beaucoup de changements ont déjà été fait. Mais le changement de moteur n’as pas toujours été fait (Qt -> Qt Quick 2 pour accélération matériel, scripting, …). La roadmap est défini, et sera surement publié pour la sortie de la version 0.4. Avec la 1.0 prévu pour fin 2014 au pire.

Compression de données pour l’envoi en ligne

Bonjour,

Je vais vous parler de la compression de données pour avoir sur la destination une arborescence. Cela peut être mis en parallèle avec l’html (page web), qui elle aussi a besoin d’avoir une arborescence de fichiers chargé coté client pour fonctionner. La compression de données est là pour que les données mettent moins de temps à télécharger. Mais le temps n’est pas que le temps de téléchargement, c’est temps de téléchargement + temps de compression + temps de décompression (que j’oublie car coté client, et donc par fait une une machine avec concurrence des ressources).

La compression ajoute une taille fixe (un entête) aux données. La grosse majorité des compressions ne commence à être efficace qu’à partir de 100 octets, mais n’est vraiment intéressante qu’après 15Ko. Pour on choisira une compression lourde, plus les tailles de début de compression, et compression optimal seront grosse (avec xz par exemple). De ce fait, compresser un fichier non compressible, ne fera que lui rajouter de la taille. Vous devez donc filtrer ce qui doit être compressé ou pas.

En fonction de votre protocole, les fichiers non compressés peuvent être envoyés à la queue ou dans un block. Dans mon cas, les fichiers sont assez petits <100octets, mais très répétitifs. La mise dans un block (suite binaire des données des différents fichiers), permet de tirer avantage de la compression sur ce genre de fichier. Mais la où l’on pouvait faire simplement un cache par fichier (pré-compresser le fichier, et renvoyer ceux-ci sur demande), c’est plus difficile car la compression et sur plusieurs fichiers. Certains choisiront de compresser dynamiquement à chaque fois. D’autres mettront un cache, car comme moi, le téléchargement du datapack ce fait soit depuis le début, soit depuis la mise à jour, donc la majorité des fichiers envoyés seront contenu dans les mêmes listes. La gestion du cache, ou même de la compression dynamique doit être bien faite car cela rend sensible votre serveur aux attaques DDOS.

Comme dans une page html, les fichiers de mon datapack sont liés entre eux. Les compresser ensemble permet de compresser la référence « toto » dans tout les fichiers d’un coup, ce qui rend la compression encore plus efficace. Or le protocole http actuel (le 1), ne fait pas ça (en plus de compresser en gzip), ce qui fait perdre beaucoup de bande passante.

Pour éviter le transfert et la compression de données inutiles sur le datapack, les ressources sont préalablement bien compressées (ogg en mono dans mon cas, quantization des fichiers png /!\ trés important, …). Je peux aussi virer tout les caractères utiles que pour la compréhension humaine des xml (indentation, retours à la ligne, …), mais qui peux être inversé.

J’ai aussi passé de la définition d’action sur fichiers de 8Bits à 1Bits pour avoir un minimum de compression naturelle, efficace sans compression, ou avec compression légère (gzip/zlib). Cela est applicable à tout. Par exemple pour l’envoi des déplacements des joueurs, il n’y a pas de compression car les données sont censées être toutes aléatoires. Et le reste compressé par le protocole: pas de nom de map, mais un id (de 8 ou 16Bits).

Au final, cela me permet de reduire la taille du datapack original de 4Mo à 200Ko transféré max sans les musiques.

Voila pour la compression des données pour la transmission dans vos applications.

Fichier ogg et Qt

Bonjour,

Pour le support de l’audio dans catchchallenger, j’ai choisi de supporté qu’un format unique (le .ogg), avec le codec inclut dans le programme. Pour évité les merdes de codec absents, l’installeur du codec à mettre dans mon codec, embarquer un player lourd type vlc, …

1) J’ai du installé msys2 par dessus mingw, ensuite faut compilé libogg puis libvorbis (./configure –prefix=mingw, make, make install + copie à la main des .dll/.a/.exe fait), j’avais déjà Qt5 compilé avec ce mingw (webkit désactivé et supprimé, configure -nomake demos -nomake webkit -nomake examples -nomake tests -opensource -confirm-license -debug-and-release -no-dbus -no-rtti -no-qml-debug -no-cetest -no-angle -opengl desktop, make -j5)

2) J’ai du faire un wrapper Qt pour libvorbis pour lire facilement les fichiers audio via Qt mais sans QFile (trop long à codé). Le lui balance le chemin du fichier, puis je fait play/pause. Correcte pour une utilisation basic (ambiance, bruitage, …)

3) Passé mon projet en Qt5 pour pouvoir compilé libvorbis/libogg sur un env récent, puis passé libtiled en 0.9 git pour passé sur Qt5, puis catchchallenger sur Qt5 et la nouvelle libtiled.

Mon 1er essaie été pourri (ça planté au lancement à cause de libvorbis), 2éme essaie ça planté à la fermeture…. peu étre que sur mon 3éme essaie ça vas marché. En tout cas sous linux c’été super simple, j’ajoute ma lib dans qt, mon wrapper et fini.

Bye