[Index Software] Coin des développeurs :]

[Bubu]

Purée, je suis en train de mettre à jour notre appli (un jeu) et c'est un enfer.
Précédemment, leurs mises à jours ont engendré des problèmes phénoménaux.
Les applis plein écran, même si on précisait dans le manifeste, était tronqués même si on désactivait les 2 barres de navigations. (Status et Navigation).
Ils ont corrigé le bug. Maintenant c'est bon.

Le pendant, c'est qu'ils cherchent à afficher la barre de navigation à outrance.
J'ai beau bidouiller, lire des forums, mais rien n'y fait.

[Bubu]

Il y a la nouvelle version d'android. La version 10, de nom de code Q. (Sans doute que les diabétiques qui bossent pour Google en ont eu marre d'avoir des noms grand public de pâtisseries et de confiseries ).
Je n'ai pas publié de nouvelle version depuis Avril, car il y avait un bug dans leur premier jet de cette version.
Les barres d'états disparaissaient, mais l'écran ne se mettait pas en plein écran.
Et jouer à un jeu en plein écran avec des barres noires sur les cotés, c'est comme manger des patates crûes.
C'était donc un bug...
Ils l'ont corrigé. Enfin.
Seulement dans notre jeu j'utilise une fenêtre de Dialog pour demander la confirmation de quitter, qui est une Dialog Android.
Ô les enculés. La barre de navigation (d'action, son type est ActionBar) s'affichait alors que personne ne lui avait rien demandé). Et elle restait persistante, même après la fermeture de cette popup.
Il m'a fallu 2 jours pour réussir à ce qu'elle ne s'affiche pas quand la Dialog s'affiche…

Enfin, je n'ai plus de soucis. Dans la nouvelle version, on supprime la pub du jeu (il y avait une bannière de pub en haut avant. C'est pénible pour les joueurs et c'est inutile pour les développeurs. ) et on le rend compatible pour la nouvelle version d' Android.

Je posterai un petit message quand cela sera effectif.

[Bubu]

Savez-vous comment une entité (voiture, personnage dans un jeu) calcule son itinéraire pour aller de là où il est, vers une destination dans une carte ?

L'algorithme le plus exact est celui de Dijkstra. Il est même parfaitement exact tout court, car il donne le plus court chemin exactement.
On appelle cet algorithme "Algorithme du plus court chemin".
Enseigné en 2ème année dans le cours sur les graphes en cursus d'informatique.
Donc plutôt abordable. Mais le problème, c'est sa complexité algorithmique.

Il y a cependant une alternative, de complexité algorithmique moindre, et utilisant une heuristique.
Cet algorithme porte le nom A*. (A étoile ou chez les anglophones A star).
C'est un algorithme inspiré du premier bien-sûr, sauf qu'il privilégie les arcs selon leur distances par rapport à la destination.
C'est pareil, sauf que l'on va d'abord explorer les branches du graphe qui sont plus proches en vol d'oiseau de la destination.
Donc le parcours choisi n'est pas forcément optimal. On a une bifurcation entre 2 nœuds qui ont la même distance accumulée, on choisit alors celle qui est en vol d'oiseau la plus proche.
Cela parait logique car on suppose (d'où l'heuristique) que la voie la plus judicieuse est celle qui est la plus proche (en vol d'oiseau) de la destination.
En cartographie routière cela est intuitif. Mais en théorie on peut avoir le contraire : la voie la plus courte peut être celle qui s'éloigne en vol d'oiseau du puit. (La destination).

Et c'est cet algorithme qu'utilise votre GPS dans votre voiture, et dans les jeux.

Il est un peu plus compliqué à implémenter, mais dans la plupart des cas est plus efficace.

Mais les deux algos sont assez lourds. Dans les jeux, on n'utilise pas A* en entier pour une frame, on l'exécute sur plusieurs frames.
C'est pourquoi on observe souvent une latence quand une entité dans un jeu doit recalculer son parcours.

EDIT : en informatique, une heuristique est une fonction qui représente de manière approximative une autre fonction. Elle est créée via des bidouillages, et est établie de manière empirique. (Bidouillages basés sur l'observation simplifiée d'un phénomène).

Par exemple, en topologie concernant A*, on utilise généralement la distance euclidienne (vol d'oiseau). Mais on peut utiliser n'importe quelle autre heuristique, comme la distance de Manhattan (quand on ne peut qu'avancer ou tourner à 90°).

L'heuristique ici pour A* étant de répondre à la question : "En gros, comment puis-je me rapprocher de ma destination ?"
Et de répondre : "Choisis le nœud du graphe le plus proche de la destination, à vol d'oiseau."

A* date de 1968
L'algorithme de Dijkstra "du plus court chemin" date de 1959.
C'est donc très tardif dans l'histoire des mathématiques. Alors que ce sont des algorithmes plutôt simples et intuitifs. Euler le premier a théorisé les graphes. Encore aussi très tardivement ….
Pourquoi cette notion (de graphe) et ses algorithmes associés sont apparus si tardivement ? J'ignore de le savoir.
Mais ce que je n'ignore pas de le savoir, c'est qu'ils sont efficaces.


Pourquoi les algos de Dijkstra et A* sont si différents, pourtant ayant un fonctionnement similaire :
Vous voulez faire le trajet Paris-Brest :
L'algo de Dijkstra aura besoin du réseau entier du monde pour le trouver. Il aura besoin d'évaluer tous les trajets possibles du monde pour vous donner le chemin le plus court. (Vous serez mort avant d'avoir l'itinéraire ! )
Grâce à son heuristique, A* n'en aura pas besoin. Car il a une analyse locale. Si on avait un nœud à Los Angeles, A* l'ignorerait, il ne serait même pas atteint.

Après c'est propre à l'analyse combinatoire. Parfois, on ne peut pas obtenir la bonne solution. Car il faudrait des millénaires pour obtenir la solution optimale. Donc on utilise des heuristiques. Mais on assume : la solution donnée au problème combinatoire n'a aucune chance d'être optimale…. (1 sur ……). Mais elle s'en rapproche.

A* fournit un parcours approché (en général. Car parfois (et sous certaines conditions) c'est effectivement le plus court).
Mais c'est fonctionnel quand même : on peut suivre le parcours obtenu pour arriver à la destination. A 100%.
L'algo de Dijkstra fournira la solution optimale. Mais c'est impraticable pour les grandes cartes, vu sa complexité algorithmique.
Mais A* n'existerait pas si Dijkstra n'avait pas auparavant crée son algorithme le plus célèbre.

[Bubu]

Cela s'adresse plutôt aux jeunes, comment représenter de la 3D sur un écran ?
D'abord, faîtes en sorte que l'origine de votre repère 3D soit le centre de votre écran.
Vous avez 3 coordonnées (x, y, z) car vous êtes en 3D.
Mais comment transformer ces coordonnées en coordonnées sur l'écran ?
Facile.
Vous divisez tout par z, la profondeur.
Sur l'écran, le point 2D obtenu est (x/z, y/z).
C'est une perspective.
Cela s'explique facilement :
Plus un objet est profond et plus il est petit.
Plus un objet est profond et plus il se rapproche du centre.

[EDIT]
J'avais fait une appli qui faisait ce que le GPU fait…. C'était un labyrinthe de surfaces transparentes dans lequel on se baladait…. C'était champion Ah bah ouais, multithreading, (4 threads, chacun générant un quart de l'écran), avec lissage de textures.... Tout sur CPU.
Résultat ridicule, mais cela m'a beaucoup appris sur ce que faisaient les GPUs.

[Bubu]

Après, je suis angoissé concernant mon implémentation de tracé de polygone.
On s'en fout en fait, les GPU le font très bien !

C'est la rastérisation : on donne 3 points, et on se retrouve avec un triangle tracé.

Ce qui est a pain in the ass, c'est que c'est très difficile de tracer un triangle quand il sort partiellement du champ de vue et qui coupe le champ de vue.
On se retrouve à remplacer un triangle par deux autres, etc.

Je l'ai implémenté, mais je suis sûr que c'est plus compliqué que ça.
Comment on trace un triangle qui a 2 sommets hors champs !

[Bubu]

Les bonnes nouvelles, c'est que l'on ne se préoccupe que de triangles ( en 3d bien-sûr). Même les GPUs ne gèrent que les triangles.

La première : les triangles ont une propriété sympa, c'est qu'ils sont convexes. Donc faciles à rastériser (c.a.d énumérer les pixels qui le remplissent).
Si le designer veut des formes plus complexes, pas de problème, son logiciel transformera sa forme 3D complexe en liste de simples triangles. (triangularisation).

La deuxième : pour rastériser, énumérer les pixels, vu que la cible est en 2D (l'écran), on travaille en 2D. On projette les sommets du triangle sur l'écran avant de le rastériser, après on revient en 3D avec les données à interpoler (les coordonnées barycentriques servent à la pondération pour interpoler) pour que les surfaces soient remplies correctement par les pixels shaders (ou fragments shaders). On fournit les uvs, les couleurs, les normales …. interpolées. C'est totalement câblé dans les GPUs, c'est le matériel qui fait ça tout seul. Par contre au développeur de shader de les utiliser correctement dans son rendu. Rassurez-vous, mais la rastérisation est transparente pour le rendu avec GPU.

Cela amène la troisième bonne nouvelle, c'est que c'est facile de savoir si un triangle sort de l'écran partiellement (ou même totalement : dans ce cas il est ignoré). Des simples comparaisons 2D, vu que les coordonnées des sommets du triangle pour ce contexte local (de l'énumération de pixels contributeurs) sont en 2D. Et il suffit de calculer les intersections des segments du triangles avec les segments (imaginaires …) du pourtours de l'écran. Faux. On reste en 3D pour savoir cela. En calculant l'intersection entre le plan correspondant à l'écran et chaque triangle a rastériser quand il a un ou deux sommets derrière l'écran. Si les 3 points sont derrière l'écran, on ignore ce triangle. On détermine cela avant la projection. (cad La perspective (qui déforme tout ) d'ailleurs il y a des cas où on ne sait pas si on doit travailler avec les coordonnées cartésiennes d'avant la projection, ou les coordonnées homogènes d'après la projection).

La mauvaise nouvelle : c'est la difficulté de gérer ces triangles partiellement hors champ au cas par cas.
Je ne vais pas m'étaler, d'autant plus que je crois que j'ai sous-estimé la difficulté du problème dans mon implémentation.
(Dans tous les cas, on regénère des sommets avec les données réelles du triangle coupé, interpolées).
Juste des exemples :
Le cas le plus simple, c'est quand 2 points sont à l'extérieur par le même coté de l'écran. Le résultat est un triangle. Dont 2 sommets sont tronqués, et remplacés par les intersections des 2 points dehors avec le bord de ce coté de l'écran.
Maintenant, un seul point du triangle est à l'extérieur : et bien il faut afficher un trapèze (si les points sortent par le même coté de l'écran) ou un quadrilatère (si ce n'est pas le cas): le triangle est coupé en un sommet. Donc il faut remplacer (la primitive) triangle par un quadrilatère, soit 2 triangles.
Dernier exemple : les points peuvent êtres tous hors champs, et pourtant le triangle reste visible. Et même pire, il peut remplir l'écran !
[EDIT], sur cet exemple, je n'ose pas imaginer la difficulté si on a un sommet plus haut que l'écran, un autre à droite en dehors et un autre à gauche en dehors, de telle sorte que toutes les arêtes du triangles soient quand-même visibles à l'écran…. c'est plus un ou deux triangles, là …

Une illustration :

Image3.jpg

Et une solution :

Image4.jpg

Dans ce cas, il faut carrément remplacer le triangle par 4 autres ...

Si vous voulez faire du rendu 3D software rastérisé, pas le choix il faut passer par ça. (Rastérisé je répète, car en lancer de rayon on n'utilise pas la rastérisation, on raisonne dans l'autre sens).
Mais rassurez-vous, si vous utiliser un GPU, rendu 3D avec hardware, vous pouvez complètement ignorer ce post : dans les GPU, il y a des unités de rastérisation qui gèrent à la perfection ce problème depuis le début des GPU.

[EDIT] Je me suis trompé. Après c'est un projet de 15 ans, j'ai un peu perdu le fil. Pour rastériser, on reste en 3D. Surtout pour détecter les intersections entre la face (un triangle), et l'écran (un plan).
Quand cela dépasse l'écran, on utilise les fonctions min et max pour tronquer le triangle.
Mais la rastérisation se fait en 2D. C'est juste que les paramètres nécessaires pour le rendu sont des interpolations 3D.
Et il faut parfois transformer la primitive triangle en entrée, en 2 triangles en sortie.

Imaginez que vous êtes dans un couloir, avec les murs qui sont des plans.
Il arrivera un moment où l'extrémité du couloir sera derrière vous, derrière la caméra.
Vu qu'on utilise une projection avec perspective, ce mûr sera complétement à l'ouest. Et mal tracé. En nœud papillon.
Donc avant la perspective, on regarde où le point derrière l'écran est placé.
On calcule l'intersection de ce plan (un quadrilatère composé de 2 triangles tête-bêche en fait) avec l'écran. Et on génère d'autres triangles à la place. On recalcule leurs sommets pour qu'il n'y ait pas de différence avec les triangle qui posent problème. On remplace les sommets derrière l'écran par des sommets qui sont sur le plan de l'écran. Et on continue normalement.

[EDIT2] Ce qui me fait revenir à mon implémentation de l'époque qui était en fait bonne. Le problème ce n'est pas que les polygones (triangles) sortent de l'écran. (On gère facilement la rastérisation dans ces cas à grand coup de min et max, grâce à de simples comparaisons), mais quand un sommet (ou 2) est derrière l'écran car dans ce cas, la perspective donne un résultat de position faux. (Inversion des axes, enfin le bordel quoi ). Dans ce cas, on peut soit être amené à tronquer le triangle et le remplacer par un autre généré par le moteur, avec les 2 points derrière l'écran comme références, ou 2 triangles s'il n'y a qu'un point qui est derrière l'écran car à l'écran c'est devenu un trapèze. (On a guillotiné le triangle, coupé un de ses sommets).
On calcule la position d'intersection entre le plan représentant l'écran et les arêtes du triangles. On remplace les sommets derrière l'écran par d'autres calculés via interpolations qui sont sur l'écran.
Et le tour est joué.

J'aurai aimé poster l'exe et le code source, sauf que j'ai perdu le projet. (Je n'utilisais pas de Cloud à l'époque)
En même temps c'était pas ouf ... un labyrinthe translucide dans lequel on se déplaçait à la 1ème personne. Genre Wolfenstein 3D, donc bon ...
J'avais quand-même implémenté un lissage des textures (Oh le goujat), où j'interpolais les 9 texels (pixels de la texture) selon la position du point (vertex) dans le texel central. Mais ce n'était pas fameux.

[2N3055]

J'ai un peu peur qu'après avoir fait le nécessaire concernant, par exemple Gary Webb et Ian Murdoch,
Ils sont maintenant en train de s'occuper de Richard Stallman

[Bubu]

SudokuW.exe.txt

C'est une appli qui permet de jouer au Sudoku, et de créer des grilles de différentes difficultés de Sudoku.
Très simple d'accès.
(C'est une petite fenêtre de rien du tout !)
Pour Windows.

Il faut enlever l'extension .txt.
Pour que le fichier s'appelle juste SudokuW.exe. Et que vous puissiez l'exécuter. (En double-cliquant dessus)
Les modos pourraient me tuer de détourner le système de fichiers joints, mais vous avez forcément un anti-virus, donc si c'était un malware, vous seriez les premiers au courant.
Si vous avez un ordi récent, normalement, ça suffit.
Si vous avez un message comme quoi il manque des dll (ce qui est très improbable), installez les redistribuables de visual studio 2012, c'est gratuit et très léger.
Mais normalement elles devraient déjà être installées car beaucoup de programmes les utilisent.

Au lancement, la grille est vide.
Il faut aller dans Menu->Nouvelle grille. Et soit entrer une grille que vous avez déjà (Editer…), soit en générer une automatiquement selon un niveau de difficulté.
Je vous mets au défi de réussir une grille générée en mode 'Très difficile'.
Perso, je n'ai jamais réussi. (On est obligé de faire des hypothèses, et là ça se complique énormément).

Pour jouer, il suffit de cliquer sur une case et mettre un chiffre.
Si vous voulez-mettre une possibilité (des tout petits chiffres dans la case), il faut appuyer sur Maj avant, et réappuyer pour revenir à l'édition normale.
(La couleur de la sélection est bleue, mais change en vert quand on entre des possibilités).

Ce programme résout absolument tous les sudokus, et génère des grilles selon plusieurs difficultés de résolutions.
Vous pouvez sauvegarder votre partie pour la continuer plus tard.
Regardez le menu.

Le programme peut vous guider pendant la résolution.
En évitant les cas triviaux (genre 2 chiffres identiques sur une même ligne, etc …)
Et en vérifiant que le chiffre entré est le bon. (Car le programme connait toutes les valeurs, car il l'a résolu avant vous, dès l'affichage de la grille proposée).

(Ne cherchez pas à résoudre une grille vide, car je n'ai pas prévu ce cas. L'ordi va chercher à vous donner toutes les grilles de sudoku pleines possibles.
Windows vous dira que le programme ne répond pas. Normal. Fermez-le quand-même ce n'est pas grave).

Vu qu'on est sur un sujet de développeurs, j'explicite un peu le fonctionnement de ce programme.

Pour résoudre un Sudoku :
Tout est basé sur le backtracking, un algorithme de recherche qui est connu.
Algorithme qui teste toutes les possibilités en arborescence, et qui revient en arrière si une solution ne convient pas.
(Si 2 chiffres identiques sont dans la même cellule de 3x3, ou dans la même ligne, ou dans la même colonne).
J'utilise la récursivité. Mais on peut (comme pour tous les problèmes récursifs), utiliser une pile. Ce qui est souvent préférable si les contextes sont lourds en mémoire.
Mais là ce n'est pas le cas. Car on a juste un entier à stocker pour une possibilité. Et c'est plus simple !

Pour générer une grille :
Je commence par générer une grille pleine.
Pour simplifier, je résout un sudoku qui a toutes ses cases vides au début, et je choisis une grille parmi les solutions obtenues.
Bien-sûr, je ne génère pas toutes les possibilités, je prends des choix au hasard, sinon je ne serais plus là pour en parler.
Et je vide la grille au fur et à mesure. Tant que la grille est résoluble et qu'il n'y a qu'une solution. Au hasard, j'enlève un chiffre, et je vérifie cela.
Concernant la difficulté variable, je regarde la profondeur d'analyse qu'il faut pour déduire un chiffre d'une case.
Pendant le backtracking, je note la profondeur du nœud dans l'arborescence de déduction pour déduire un chiffre.
Et en fonction de la difficulté voulue par le joueur, j'essaie d'enlever un chiffre selon sa profondeur, et je résout le sudoku. S'il y a plusieurs solutions, j'essaie un autre chiffre.

Car un bon sudoku n'a qu'une seule solution.

[EDIT2]
Ce qui m'a motivé, c'est les cours de Prolog en Licence.
Et parce qu'on a eu un TP sur Prolog pour résoudre les sudoku.

Et qu'à cette époque j'étais fan de Sudoku.

Le problème, c'est qu'avec Prolog, il faut plusieurs secondes pour résoudre une grille.
Mais cela m'a servi, je ne veux pas être ingrat.

En Java, C, C++, C#, la résolution est instantanée à échelle humaine. Sauf qu'il faut implémenter soi-même le backtracking, c'est tout.
Et, à échelle humaine, on obtient la solution immédiatement.
Si j'avais utilisé Prolog pour générer les grilles très difficiles, il aura à peu près fallu une 1/2 heure.
En C++, un peu plus d'une seconde pour ce niveau de difficulté. Et ce serait pareil en C, Java ou C#.

Après on ne peut pas dire que Prolog est incompétent pour le back-tracking. C'est évident. Il a d'autres compétences et propriétés, comme le concept de contraintes, etc ...

Le code source :

SudokuW.rar

Après il n'est pas compilable tout seul, il faudrait que je rajoute des librairies.
Car j'utilisais les types List et Array que j'avais moi même crée. J'étais un peu naïf. (J'avais essayé de reproduire la même arborescence de classes collections que dans SmallTalk, cela m'avait pris 2 mois)
Et j'utilise ma librairie WindowDraw, qui permet de faire du tracé 2D dans une zone de la fenêtre.
Car il y a les std::vector et std::list, allez surtout sur le .cpp SudokuGrid.

Si quelqu'un veut vraiment le compiler, je mettrai en ligne mon dossier d'utilitaires Util.

[EDIT]
Après, j'ai fait ça comme ça. Je m'en fous. (C'est juste qu'à ce moment de ma vie j'adorais les Sudokus).
Par contre si vous avez des problèmes pour exécuter le programme, j'essaierai de donner des solutions.
Mon hobby, c'est programmer des jeux vidéos. Et j'aimerais en faire mon métier.
C'est largement plus intéressant. C'est comme souvent, un mélange artistique, entre l'Art et la technique. Comme la pratique de la Musique.

[Bubu]

Une petite anecdote pour les sprites 2D rendus en utilisant les GPUs.
Cela concerne les déformations que subissent les sprites.
Chose facilement réalisable quand on utilise un GPU pour le rendu 2D. (C'est utilisable en 3D aussi).
Cela selon le scaling : rétrécissement, agrandissement selon un axe. (En 2D c'est simple, il n'y en a que 2 : x et y).
C'est l'effet chamallow.
On applique une sinusoïde selon la hauteur et une autre sinusoïde selon la largeur sur l'échelle du sprite, le scaling. Les deux étant décalées. Mais en phase.
Pseudocode :

ScaleX = sinus (temps écoulé)
ScaleY = 1 - sinus (temps écoulé).
Et on applique ces proportions sur le sprite 2D.

Du coup, dans le temps, le sprite se déforme comme un chamallow.
Mais il garde la même surface. (aire).

C'est amusant. Et efficace. Cela évite de créer un atlas de sprites approximatif qui représenterait le phénomène.

C'est une explication approximative car en vérité, on se sert d'une sinusoïde pour calculer la mise à l'échelle, et de valeurs min et max de celle-ci.

Le vrai pseudo-code est :

Code : Tout sélectionner

( C, C++, java, ou C#)
float interpolationFactor = (1f + sinus(facteur_de_vitesse * temps_écoulé)) / 2f. // Cela permet d'avoir une sinusoïde qui varie entre 0 et 1, avec une vitesse paramétrable. (Vitesse angulaire en fait).
//Ensuite on fait les interpolations en utilisant ce facteur. En ayant des valeurs min et max de mises à l'échelle (scaling), qui sont à paramétrer au cas par cas, par animation.
scaleX = interpolationFactor * scaleMax + (1f - interpolationFactor) * scaleMin.
scaleY = (1f - interpolationFactor )* scaleMax + interpolationFactor * scaleMin.

L'équation que j'utilise est primordiale pour les développeurs. Elle permet de calculer une valeur qui se situe dans une certaine marge à définir, grâce à un facteur réel entre 0 et 1.
0 = min, 1 = max. C'est un peu comme un potentiomètre mathématique.

(En 3D, on peut faire la même chose grâce aux coordonnées barycentriques, c'est la même logique sauf qu'il y a 3 paramètres au lieu de 2.)
Et donc 2 paramètres d'interpolation. (3 en fait, mais le 3ème se déduit des 2 premiers). Car on sait que la somme des facteurs vaut 1.
(C'est un peu comme une moyenne avec coefficients). Si vous savez les coefficients appliqués sur votre bulletin scolaire, vous n'avez pas besoin du dernier coefficient, vous le déduisez par soustraction si vous avez le total.

Cela peut aller plus loin.
Bon, tout le monde joue à des jeux vidéo. Et a vu comment les personnages se contorsionnaient quand ils marchent, respirent, ou courent.
Là encore, c'est une affaire d'interpolations.
Chaque point de la surface du personnage est interpolée entre des états fixes, appelés clés d'animation.
Et on est plus à 2 valeurs ou 3. Certains de ces objets utilisent jusqu'à 8 paramètres d'interpolations, surtout pour les visages.

Après pour donner des pistes, renseignez-vous sur les barycentres.

valeur interpolée = facteur d'interpolation * valeur max + (1 - facteur d'interpolation) * valeur min.

(Le facteur d'interpolation est compris entre 0 et 1). S'il va plus loin, on ne parle plus d'interpolation mais d'extrapolation.)
L'extrapolation est parfois nécessaire, surtout pour le réseau. On va plus loin que le temps fourni, et on suppose que si un objet était dans sa lancée, il va la continuer. Ce n'est qu'une heuristique.
Et on corrige l'état de l'objet dès que le serveur envoie la solution réelle. Ce qui peut conduire à de vilains spawn ou autre dans les jeux en réseaux.

Cette équation est violée : usée et usée encore, dans bien des domaines. Gestion de la transparence, ou l'opacité (alpha) joue le rôle de facteur d'interpolation entre la couleur de premier plan et la couleur de fond, etc ….

[EDIT] Pour programmer les animations de personnages (skin-meshes), il y a pas mal de boulot.
Pour une fois, ce n'est pas le pixel (ou fragment) shader qui pose problème, c'est le vertex shader.
Dans un personnage animé, il y a un squelette. C'est une arborescence de transformations (matricielles), reliées entre elles par des points de pivot.
Qui définit les pivots acceptés de rotations entre les os. (Par exemple si je voulais plier mon genou vers l'avant, ce serait impossible).
Cela passe par le paramétrage de joints (entre les os). Je peux bouger mon omoplate dans les 3 axes selon une certaine amplitude, mais mon coude c'est juste de haut en bas.
On appelle ces blocages, ou limitations de degré de liberté, des contraintes.

Comment se passe l'animation de tels objets ?
Chaque point est lié à plusieurs os. Le point définit l'affinité avec chaque os auquel il est relié. Le logiciel avec lequel a été conçu l'objet, donne les facteurs d'interpolation.
On calcule une interpolation linéaire entre tous les os intervenants, avec comme poids les poids fournis par le point. Mais ces positions sont données en fonction d'une pose particulière de l'objet : la bind pose.
Pour annuler ce positionnement, il faut corriger en multipliant le résultat obtenu par l'inverse de la matrice en bindpose.

L'animation est conçue en utilisant des "key frames", des positions clés à interpoler. Ces positions définissent chacune une pose. Une position du squelette. Cette pose sert à calculer la position de la surface de chaque point de l'objet. En fait, on calcule la pose (ensemble des positions dans le squelette) pour cet instant t précis.
Dans ce genre d'animations (prédéfinies), les contraintes n'ont pas d'importance.
Mais si on veut animer le personnage selon les lois de la physique, si. Genre quand il meurt et que l'on veut qu'il tombe ou qu'il soit projeté, cela de manière réaliste.
On appelle ça des ragdolls. (Littéralement poupées de chiffon).
En général, tant qu'un personnage est contrôlé (via le joueur ou une IA) on le représente par une capsule verticale (cylindre avec 2 demi-sphères en haut et en bas). Et dès qu'il meurt, on le remplace par une ragdoll, et on laisse le moteur physique nous donner la pose de l'objet frame par frame.

[Bubu]

J'ai envie de parler des quaternions.
Surtout pour leur importance en 3D pour un développeur.
Car mathématiquement je ne sais pas ce que c'est.
C'est une extension des nombres complexes.
Il y a 3 unités d'imaginaires purs : i, j k.
i² = -1
j² = -1
k² = -1
i.j.k = -1

A l'instar des nombres complexes qui sont l'outil idéal pour travailler avec des rotations 2D, les quaternions sont idéaux pour travailler avec les rotations 3D.

Les nombres complexes sont utilisés en 2D, et les quaternions, en 3D. Je n'en sais pas plus.

Pourquoi sont-ils si importants en 3D ?

Une matrice utilisée dans les jeux est de taille 4x4.
Donc une rotation, exprimée comme une matrice, aussi.
(En fait il suffit d'une matrice 3x3 pour représenter une rotation en 3D, mais vu qu'on utilise les coordonnées homogènes pour les projections, et qu'on fait des translations, on utilise des matrices 4x4.)

Un quaternion ne contient que seulement 4 valeurs. (4 au lieu de 16 c'est pas mal). (une composante réelle, et 3 composantes imaginaires purs)
Et seulement 3 si on sait qu'il est normalisé.

Premier intérêt, c'est plus concis d'exprimer une rotation sous forme de quaternion plutôt que sous forme de matrice.
Deuxième intérêt et de loin le plus important et intéressant, on peut faire des interpolations de quaternions. (Amusez vous à faire des interpolations de matrices ! )

La plupart des APIs qui ont besoin de rotations comme les moteurs physiques ou graphiques, les utilisent. Mais ils permettent de les convertir en matrices, car les GPUs (pour le rendu) ont besoin de matrices et ne savent pas manipuler les quaternions.

Evidemment, toute interpolation faite, on transforme le quaternion obtenu en matrice pour pouvoir l'utiliser dans le pipeline graphique.

[Bubu]

Je me suis mis à Unity, le moteur de jeu.
Enfin c'est un grand mot. Je découvre.

J'en suis encore à assimiler l'interface.
Bien que cela ne me serve à rien, car c'est mon binôme Virgule qui est concerné.

Ce qui compte pour moi, ce sont les scripts. (En c#, qui est identique à Java à quelques mots-clés près).

J'ai survolé quelques scripts, et je ne comprends pas. Mais rien du tout. Car aucun script (vu) n'utilise le temps écoulé.
Or c'est une variable fondamentale. Car tout est basé sur le temps écoulé entre chaque frame.

Je ne comprends pas comment ces scripts arrivent à gérer des animations sans cette donné.

Peut-être parce que j'ai un raisonnement trop bas niveau.

[user6375]

Je me suis mis à Unity, le moteur de jeu.
Enfin c'est un grand mot. Je découvre.

Je l'utilise depuis quelques temps déjà, et je le maîtrise assez pour t'orienter.

J'ai survolé quelques scripts, et je ne comprends pas. Mais rien du tout. Car aucun script (vu) n'utilise le temps écoulé.
Or c'est une variable fondamentale. Car tout est basé sur le temps écoulé entre chaque frame.

Tu pense par exemple a un déplacement, en fonction du temps ?
Si c'est ça, si si les scripts l'utilise.

Prend le script StandardAsset\Vehicule\Car\Scripts\CarController.
Dedans tu trouve une ligne
m_GearFactor = Mathf.Lerp(m_GearFactor, targetGearFactor, Time.deltaTime*5f);

Ton temps est Time.deltaTime.
Et cette variable se retrouve dans beaucoup d'autre de script.

Après pour les animations ça fonctionne autrement. Typiquement une animation d'un personnage va faire appel à un plugin Animator, qui contient les infos d'animations du personnage. Tu en trouve dans StandardAsset\Vehicule\Aircraft\Animator

Unity c'est un moteur 3D. Donc pour faire une action dans Unity, tu dois utiliser le moteur et la manière dont les éléments interagissent entre eux (mesh, animation, script, audio, camera, collision, etc...). Et pour ça il faut comprendre comment unity structure les éléments du jeu. Faut pas chercher a utiliser Unity et y appliquer des recettes adhoc comme quant on doit coder tout le moteur. Là y a pas besoin. Il faut juste donner à Unity les infos pour faire les actions, mais c'est Unity qui les exécutent (ça s'applique également aux scripts, qui sont des objets que Unity instancient).

Comme tu le soupçonne, faut pas trop descendre dans la logique. On est pas à bas niveau justement.

[Bubu]

Merci pour les infos.
Je n'ai pas encore mis trop le nez dans les scripts.
Je n'en suis qu'à mettre des objets dans la scène et à faire des animations basiques sans code. (Fenêtre "animations")
Au tout début, quoi.

[Starrk]

Hors sujet pour les messages précédant

Pour ma part j'ai été développeur d'applications Android et iOs natives (java et Objective-C), depuis l'année dernière je m’intéresse aux nouveaux frameworks web : Angular / ReactJs / NodeJs. Donc en gros du typescript/javascript, ES6.

Les technos qui m' intéressent et que j'aimerais tester : Kotlin, swift, tensorflow/machine learning

Pendant mes études j'ai commencé par le C puis assembleur, vhdl, C++, Java, C#, Python... some html/css/php, etc...

[Bubu]

Hors sujet pour les messages précédant

Pour ma part j'ai été développeur d'applications Android et iOs natives (java et Objective-C), depuis l'année dernière je m’intéresse aux nouveaux frameworks web : Angular / ReactJs / NodeJs. Donc en gros du typescript/javascript, ES6.

Les technos qui m' intéressent et que j'aimerais tester : Kotlin, swift, tensorflow/machine learning

Pendant mes études j'ai commencé par le C puis assembleur, vhdl, C++, Java, C#, Python... some html/css/php, etc...

Donc tu es calé !
Le vhdl c'est plus un langage de modélisation d'architecture, plutôt qu'un langage de développement.
On avait fait un modèle de processeur 16 bits pipeliné en Licence (avec peu d'étages, en 3ème année) en l'utilisant.
Pour ma part, je ne connais rien aux langages pour le net.
Ça ne m'intéressait pas, c'est entré par une oreille et ressorti par l'autre.

Un de mes nombreux défauts, c'est que j'ai du mal à utiliser des Frameworks ou des bibliothèques faites par d'autres. J'essaie de renverser la tendance en me mettant à Unity, mais j'ai du mal à m'y faire.
Il y a quelques années, j'avais fait un moteur de jeu basé pour le graphisme sur DirectX, et pour la physique sur PhysX de Nvidia. C'est déjà utiliser des API certes, mais c'est bas niveau.
On s'en était servi pour faire un prototype de jeu de course à la Mario Kart, mais on a abandonné. Car les progrès allaient trop vite pour pouvoir être utilisés, assimilés et intégrés dans le projet par un seul developpeur.

Et pour notre jeu publié sur GoogleStore pour Android, un moteur graphique 2D utilisant OpenGL. Pas en native code, en Java.
J'ai d'ailleurs longtemps hésité, mais la puissance des GPUs des plateformes mobiles aidant, ainsi que la découverte de la puissance de Java, c'était en fait largement suffisant.
3 mois pour faire l'API de base. Avant de vraiment se mettre au programme du jeu. (l'essentiel du jeu a été programmé en 3 jours ! )

Tu parles aussi de l'assembleur. Je ne connais rien à l'assembleur PC, en plus maintenant on sait que les compilateurs C, C++ produisent en général un code assembleur plus performant que si un développeur le créait lui-même. Très jeune je me suis mis au Motorola 68000. Sur ma TI92. Je devais avoir en gros 19 ans.
J'ai fais un niveau de jeu de plateforme à la Mario2 de Gameboy. (Caméra sur deux axes qui suivait le personnage, plus une physique élémentaire supportant l'accélération, et en fonction, des sauts de hauteur variable). En 4 niveaux de gris. (Le personnage n'était qu'un rectangle). Il y avait aussi une librairie qui en permettait 7, mais je ne l'ai jamais utilisé.
On codait dans le Notepad un texte basique (ASCII), et grâce à un câble fait maison et un OS (fargo) spécifique on l'envoyait dans la calculatrice.
J'ai failli envoyer plusieurs fois ma calcu contre le mur. Sans débogueur, la calcu freezait en cas d'erreur et il fallait la réinitialiser complètement. Et réinstaller Fargo, et réinstaller le programme. Lourdingue à souhait.
Le plus compliqué, c'était l'affichage de sprites a une position quelconque. Vu que c'est un écran LCD monochrome, un octet code pour plusieurs pixels (8) (Il y avait une plage d'adresses mémoires correspondant à l'écran). Et en 4 niveaux de gris, on a deux écrans à gérer qui se superposent avec des temps d'affichage qui sont différents. Cela se fait avec les instructions de décalage. De droite à gauche ou de gauche à droite. Et il faut remplir correctement les pixels des octets voisins correctement. Et le problème du clipping, quand un sprite est partiellement en dehors de l'écran.
Ce projet, après un affichage correct des sprites au pixel près, est allé vite. Sauf que j'ai galéré pour créer le niveau. Un énorme tableau auquel il manquait toujours une valeur soit en ligne, soit en colonne, ce qui générait un désastre. Freeze.
Mais coder les collisions, et la dynamique du personnage a été un plaisir.

C'était loin d'être un programme parfait, car au lieu d'inverser les pointeurs pour le prochain rendu, je copiais ce qui avait été fait dans le buffer vers l'écran. Octet par octet. Ce qui divise le frame rate par deux au moins. Or on sait qu'il suffit de permuter les pointeurs. (Les adresses). Erreur de jeunesse !

Dernier ajout : le Motorola 68000 gère les mots de 8, 16 et 32 bits.
Mais il faut toujours s'exprimer en 16 bits pour l'adressage mémoire !
Sinon, sur la TI92, on risque d'avoir un bordereau "Adress Error" avec le système complètement bloqué !
Après il n'y a pas trop s'en faire, mais adressez vos donnés sur des multiples de 16 bits.
Après c'est un processeur primitif car il ne gère que les nombres entiers. (Mais jusqu'à 32 bits quand-même !).