Discussion :

[Guntha]

J'avoue, je ne voyais pas toutes les implications, d'autant plus que ton moteur se veut généraliste. Je crois que j'ai été perturbé par l'énergie qu'il a fallu dépenser pour uploader sur Youtube 2 vidéos qui montrent un cas "simple"

[wtAngat]

Du très bon boulot ! Un grand bravo !

[jwar0]

Beau travail sur la physique, sur la dernière vidéo le résultat est plutôt réaliste.
Une question concernant un précédent message ou tu parlais de 'sweep and prune' et 'AABB'
As-tu fait es bench sur plusieurs milliers d'objets pour la détection de collision et voir le nombre réel de calcul effectué ?

Je pose la question car en implémentant un Octree et en optimisant certains phase (réassignement d'objet en mouvement dans les nodes, différentiation objet statique/mobile, etc) on arrive à réduire drastiquement le nombre de calcul.

[zenux]

Encore merci pour vos messages

As-tu fait es bench sur plusieurs milliers d'objets pour la détection de collision et voir le nombre réel de calcul effectué ?

Non, je n'ai pas encore fait de benchmark. J'ai surtout fait l'implémentation de AABB Tree pour le 'ray test' qui était forcément plus performant que dans le sweep and prune.
Pour info: il y a un benchmark sur Bullet Physics: http://www.bulletphysics.org/mediawi...DTestFramework

[zenux]

Je viens de terminer le développement du Continuous Collission Detection (CCD).

Voici une nouvelle mini démo avec une 'compound shape':

J'ai aussi essayé de faire une collision de type CCD entre deux corps dynamiques comme me l'a suggéré Guntha. J'ai fait plusieurs tests et le résultat semble acceptable. Comme expliqué plus haut, le résultat n'est pas à 100% correcte mais comme tout va très vite, on ne le remarque pas vraiment. Voici une démo où j'applique une force opposée aux 2 cubes. Malheureusement, c'est difficile de bien voir le résultat vu que tout est très rapide.

[NevilClavain]

J'ai aussi essayé de faire une collision de type CCD entre deux corps dynamiques comme me l'a suggéré Guntha. J'ai fait plusieurs tests et le résultat semble acceptable. Comme expliqué plus haut, le résultat n'est pas à 100% correcte mais comme tout va très vite, on ne le remarque pas vraiment. Voici une démo où j'applique une force opposée aux 2 cubes. Malheureusement, c'est difficile de bien voir le résultat vu que tout est très rapide.
]

J'avais la même problématique autrefois. Il te faudrait insérer dans ta chaîne une classe de "gestion du temps reel" (je sais pas décrire autrement), qui permet de ralentir l'écoulement du temps dans le moteur physique, en positionnant un facteur : X 0.5, X 0.1, etc..., voire même de mettre l'execution sur "pause", ou de faire du "pas à pas" avec appui sur une touche clavier

-Nev-

[Bousk]

J'avais la même problématique autrefois. Il te faudrait insérer dans ta chaîne une classe de "gestion du temps reel" (je sais pas décrire autrement), qui permet de ralentir l'écoulement du temps dans le moteur physique, en positionnant un facteur : X 0.5, X 0.1, etc..., voire même de mettre l'execution sur "pause", ou de faire du "pas à pas" avec appui sur une touche clavier

C'est un des B.A.-BA du dév de jeu et simulation au sens large : http://alexandre-laurent.developpez....e-de-jeu/#LIII
En général j'ai toujours vu ça sous le terme "delta time" ou DT qui l'incrémente, c'est le temps de la simulation.

[Guntha]

Oui, mais pour tester la CCD entre 2 objets qui se déplacent à grande vitesse, on est obligé d'avoir un grand déplacement entre 2 frames. Ou bien de tricher en updatant la physique moins souvent que le rendu, mais en extrapolant les vitesses/forces de la frame physique précédente pendant les frames de rendu où il n'y a pas d'update physique, pour avoir le temps de voir le déplacement

[Bousk]

Programmer un jeu, c'est tricher.
Si le déplacement est grand entre 2 frames, tu ne détecteras pas leur collision mais peux détecter si l'un a traversé l'autre ou non au cours de la frame. Ca peut être juste un objet.position.isBetween(objet2.position.before, objet2.position.after)

[zenux]

En général j'ai toujours vu ça sous le terme "delta time" ou DT qui l'incrémente, c'est le temps de la simulation.

Effectivement, c'est le base dont je me sers pour mes calculs. Je pourrais changer cette valeur pour ralentir mon moteur physique.

voire même de mettre l'execution sur "pause", ou de faire du "pas à pas" avec appui sur une touche clavier

C'est vrai que l'éxecution "pas à pas" pourrait m'être très utile pour débugger. Je peux déjà faire "pause": quand je retourne dans le menu de mon "jeu", je mets le moteur physique, 3D et son en pause.

mais en extrapolant les vitesses/forces de la frame physique précédente pendant les frames de rendu où il n'y a pas d'update physique, pour avoir le temps de voir le déplacement

Ca donnerait un résultat assez étrange. Pendant l'interpolation, on verrait des objets faire du tunneling et lorsque qu'on arrivera à la prochaine frame du moteur physique: on verrait un retour arrière vu qu'il aura résolu le problème de tunneling.
Ca peut quand même être utile pour savoir où les objets sont sensés entrer en collision.

Si le déplacement est grand entre 2 frames, tu ne détecteras pas leur collision mais peux détecter si l'un a traversé l'autre ou non au cours de la frame. Ca peut être juste un objet.position.isBetween(objet2.position.before, objet2.position.after)

C'est en gros la solution pour résoudre le tunneling. Avec toutes les difficultées:
- Comment déterminer le 'after'. Une simple interpolation n'est pas toujours suffisante si l'objet va entrer en collision avec un autre objet au sein d'une même frame.
- L'algorithme pour détecter: le point de collision + normal + temps avant l'impact sur des objets convexes ou composés n'est pas super simple.
- Si l'objet 1 bouge aussi, c'est juste l'enfer.
- Déterminer l'impulsion correcte dans le solver de contraintes.
Bref, je m'en sors dans tous les cas avec une marge d'erreur plus ou moins acceptable suivant la situation.

[zenux]

Bonjour,

Je travaille toujours sur mon projet à un rythme très lent mais constant. Voici quelques news:

- Je m'améliore un peu à Blender et je commence à réussir quelques modèles en low poly sans trop de difficulté. Mais je ne me fais pas d'illusion: je serais toujours mauvais en modélisation.
- Je suis capable d'exporter un modèle Blender composé de plusieurs 'objects Blender' et d'en faire le rendu (voir screenshot: le tronc de l'arbre et son feuillage sont deux objects différents dans Blender).
- Je gère une nouvelle forme pour les collisions dans le moteur physique: le cone. Très pratique pour les sapins


- Je commence tout doucement le moteur d'IA. Je crée ce qu'on appel un 'navigation mesh' qui pourra être utilisé par la suite pour faire du pathfinding (A*). Malheureusement, il y a vraiment très peu de bonne documentation sur le sujet et ce n'est vraiment pas une chose facile quand on fait tout de zéro (triangulation de polygones, gestion des trous dans les polygones, déterminer le 'footprint' d'un object...). Il me reste encore énormément de travail pour arriver à un navigation mesh correct qui peut être regénéré en temps réel pour un monde dynamique. Je dois encore gérer:
* les sols à surface non plate
* la taille du personnage pour bloquer certain accès dans les zones trop étroites
* les sauts d'un sol à un autre
* les échelles
* le partionnement pour regénérer que les parties où un object dynamique à bougé
* etc.
Je devrais avoir fini dans 5-6 ans Un exemple de navigation mesh (en vert) que je suis capable de générer actuellement:

[yildiz-online]

histoire de gagner 5 ou 6 ans tu as recast / detour qui fait la navigation:

https://github.com/recastnavigation/recastnavigation

[zenux]

histoire de gagner 5 ou 6 ans tu as recast / detour qui fait la navigation

Oui, je connais très bien. J'avais regardé le code source de Recast avant de commencer le moteur d'IA.
Deux grandes techniques semblent exister pour générer un navigation mesh:

• La technique Recast: voxeliser tout l'espace et déterminer ce qui est 'walkable' (c'est mieux expliqué dans le lien GitHub). Ca semble être utilisé par Unity, Unreal Engine, etc. J'ai quand même des doutes sur cette technique pour générer le navigation mesh en temps réel dans un monde très dynamique. D'ailleurs, j'ai testé quelques jeux AAA (sans savoir si ils utilisent Recast) et j'ai remarqué que le pathfinding/navMesh n'est généralement pas parfait (voire catastrophique) quand il y a des objects dynamiques.
• L'autre technique se base sur les objects physiques et détermine par différents calculs de géométrie les surfaces qui sont walkable. C'est cette technique que j'ai choisi vu qu'elle semblait plus adapté aux mondes dynamiques. Malheureusement, après des heures de dev. je me suis rendu compte que c'est vraiment très complexe et peu expérimenté/documenté. J'ai des doutes si au final (si j'y arrive) ça sera mieux en terme de performance que Recast.

Je fais tout ça par passion et je verrai bien si j'y arrive. Mon but n'est pas de reprendre l'existant mais plutot d'expérimenter et apprendre.

[yildiz-online]

Et pourquoi pas un mix des 2? un precalcul de la zone uniquement pour établir les routes possibles, puis un recalcul dynamique par collision d'objet dummy entourant le personnage (ou raycast si les chemins sont étroits) pour établir le meilleur chemin par rapport aux routes possibles.

[Matt_Houston]

Oui un mélange est un peu ce qui me viendrait à l'esprit aussi. Un navmesh est relativement statique par définition. Que penserais-tu d'y ajouter du steering ? On aurait en gros une passe de calcul de chemin via le navmesh qui ne prendrait en compte aucun objet dynamique, puis l'agent se chargerait lui-même de la gestion de ces obstacles (contournement, demi-tour..) en se rendant au prochain waypoint.

[zenux]

Mon idée est de générer/charger le nav mesh au chargement du jeu. Ce nav mesh serait diviser en régions et quand un événement se produit (un objet dynamique qui bouge) dans une région, je régénère le nav mesh de cette région.
Faire du ray cast (je ne sais pas si il existe d'autres techniques) pour contourner un objet fonctionne pour le plupart des jeux mais en cas d'un chemin complètement bloqué par des objets dynamiques, j'ai du mal à voir comment je peux recalculer un autre chemin facilement.
Il y a plein de cas plus ou moins complexe à gérer:
- Imaginons deux objets dynamiques qui se rapprochent (deux bateaux par exemple) et où le nav mesh devrait créer des liens de 'jump' dynamiquement quand les objets sont assez proche l'un de l'autre.
- Un joueur qui déplace un caisse, ce qui permet à un PNJ de marcher sur cet objet et d'accéder à un endroit qui ne lui était pas accessible avant.
- Un PNJ n'a pas sensé savoir qu'un chemin a été bloqué par un joueur tant qu'il ne l'a pas vu de ses propres yeux. Mais si il fait demi-tour, il doit être au courant de ce chemin bloqué. J'avoue, c'est un cas extrême

J'expérimente et je verrai bien si je dois me tourner vers d'autres solutions. Je pense que c'est de tout façon très difficile d'avoir une navigation parfaite, performante et générique qui fonctionne pour tout type de jeux.

[Matt_Houston]

c'est de tout façon très difficile impossible d'avoir une navigation parfaite, performante et générique qui fonctionne pour tout type de jeux.

FYP

Tu te fixes à mon humble avis des objectifs irréalisables. Les cas d'utilisation de tous les jeux possibles sont incommensurables et incompatibles. C'est très rare d'utiliser une fonctionnalité d'un moteur telle quelle, sans l'adapter au problème en question.

[zenux]

Je suis d'accord, c'est impossible. Je ne compte pas non plus résoudre toutes les situations que j'ai décrite dans mon précédent message. Je me rends bien compte que ça demanderait trop de temps.
Je continue le dev. tant que je m'amuse et je verrai bien où ça me mène. Je vous tient au courant dès que j'ai fait des progrès.

[stopviolence]

Bonjour,

Intéressant de voir qu'il y'a encore des petits génies qui codent tout de A à Z comme à l'époque où y'avait pas les moteurs pour nous mâcher 90% du boulot.

[zenux]

Voici quelques news:

• J'ai changé d'éditeur. Je suis passé de Eclipse à CLion. L'éditeur n'est pas parfait mais je le trouve bien mieux que Eclipse.
• J'utilise enfin les makefiles (via CMake) pour builder. C'est beaucoup plus pratique et rapide pour générer une release.
• J'essaye toujours de générer un navigation mesh en temps réel. Je commence à avoir de bon résultats mais il me reste encore énormément de boulot. Actuellement, j'arrive à générer un navigation mesh triangularisé en environ 1ms (vidéo). Il me reste encore:
  
  1. Quelques bugs à corriger. Même après plus de 60 unit tests, j'ai encore des erreurs d'arrondis/float dans les calculs
  2. Quelques improvements: ignorer les objects qui bougent trop vite et les objects trop petits
  3. J'ai encore des idées pour améliorer la performance
  4. Créer des liens de sauts pour les personnages (dur dur)
  5. Finalement faire la pathfinding sur base des triangles
     
     Voici la vidéo avec en bleu le navigation mesh généré en temps réel. Je n'ai pas affiché les triangles mais ils sont calculés: