Discussion :

[Deaf]

Bonjour,

je ne suis pas un habitué de cette partie du forum, donc si ma question n'est pas à sa place, d'avance: désolé, et merci de la déplacer

Je souhaite faire un mini-jeu qui se déroule en deux temps:
- on planifie le comportement de quelques personnes (~10, 25 au max si je pousse le truc plus loin),
- on regarde ce que ça donne avec très peu d'interactions.

Le comportement peut être constitué d'actions "statiques" (va là puis attend) ou d'ordres "dynamiques" (suis untel, va vers le premier qui se rapproche trop de toi).

Etant plus habitué à faire des mini-jeux en tour par tour plutôt qu'en "temps réel" (pas celui de l'embarqué, hein), de nouvelles problématiques se présentent à moi:
- gestion des collisions
- anticipation des trajectoires
- recalcul fréquent des actions en fonction des autres (notion d'évènements?)

Ma première idée, peut-être un peu naïve, consiste à faire une boucle de mise à jour des états (vitesse, position) qui serait brève et interviendrait toutes les X ms (je partirai sur du 50 ou 100). En arrière-plan, je ne prend en compte que les personnes qui n'ont pas réagi récemment (temps de réaction) et je vois s'ils changent leur action courante. Ensuite je prend tous les personnages et je calcule le résultat de leur action courante pour le prochain passage de la boucle (et peut-être les suivants).
Toute critique est bonne à prendre, même si c'est pour dire de jeter

Existe-t-il des lib/framework qui m'aideraient pour un ou plusieurs de ces points?
Avez-vous des conseils quelconques pour aborder ces problématiques?
Voyez-vous un point important que j'aurais raté?

PS: Je ne souhaites pas forcément tout faire par moi-même, ce n'est pas le but du projet, mais je ne souhaites pas spécialement utiliser des usines à gaz énormes car cela reste quelquechose de très modeste.

[Kannagi]

Etant plus habitué à faire des mini-jeux en tour par tour plutôt qu'en "temps réel" (pas celui de l'embarqué, hein), de nouvelles problématiques se présentent à moi:
- gestion des collisions
- anticipation des trajectoires
- recalcul fréquent des actions en fonction des autres (notion d'évènements?)

Ma première idée, peut-être un peu naïve, consiste à faire une boucle de mise à jour des états (vitesse, position) qui serait brève et interviendrait toutes les X ms (je partirai sur du 50 ou 100). En arrière-plan, je ne prend en compte que les personnes qui n'ont pas réagi récemment (temps de réaction) et je vois s'ils changent leur action courante. Ensuite je prend tous les personnages et je calcule le résultat de leur action courante pour le prochain passage de la boucle (et peut-être les suivants).
Toute critique est bonne à prendre, même si c'est pour dire de jeter

Existe-t-il des lib/framework qui m'aideraient pour un ou plusieurs de ces points?
Avez-vous des conseils quelconques pour aborder ces problématiques?
Voyez-vous un point important que j'aurais raté?

PS: Je ne souhaites pas forcément tout faire par moi-même, ce n'est pas le but du projet, mais je ne souhaites pas spécialement utiliser des usines à gaz énormes car cela reste quelquechose de très modeste.

Alors je comprend ta problématique est effectivement je te conseil de jeter ce que tu es en train de faire

Donc voila mon conseil et ce qui résoudra ton probleme , utiliser des vecteurs vitesses cela réglera ton souci
Si tu le fais de manière naïve j’imagine que tu modifie la position directement , alors que justement pour faire les bon calcul il faut connaitre sa Trajectoires et anticipation.
Et si tu fais un vecteur vitesse ben tu connais sa trajectoire et tu peux anticipé donc tu modifie ce vecteur et quand ce vecteur est modifier et testé toutes les collisions ben tu pourra modifier la position.

[Deaf]

Merci pour ce retour, par contre, serait-il possible d'avoir une réponse un peu plus détaillée?
Dans mes données, j'ai déjà l'équivalent d'un vecteur vitesse. Ce n'est juste pas un objet à part entière, mais je manipule déjà ses deux données: direction & norme. Du coup, je ne vois pas en quoi cela remplace ma solution actuelle.

Dans ta réponse, tu me dis de tout jeter, mais pas par quoi remplacer!

[Kannagi]

Merci pour ce retour, par contre, serait-il possible d'avoir une réponse un peu plus détaillée?
Dans mes données, j'ai déjà l'équivalent d'un vecteur vitesse. Ce n'est juste pas un objet à part entière, mais je manipule déjà ses deux données: direction & norme. Du coup, je ne vois pas en quoi cela remplace ma solution actuelle.

Ah tu utilise déjà un vecteur vitesse hmm , sinon un vecteur vitesse est chez moi une simple structure (x,y +z si c'est en 3D), bon je vais détaillé ça éclairera j’espère ta lanterne

Admettons que tu veux faire un Mario c'est un ensemble de carré/rectangle.
Ton mario a une vitesse admettons qu'il se déplace de 5 en x.
Ton mario a une box 2D pour les collisions.
Donc si ton mario et sa box 2D + vecteur vitesse (donc + 5 en x) et en collision avec ta map , ben il faudra faire un calcul pour changer la valeur de ton vecteur pour qu'il n'y est pas cette collision , tu peux mettre naïvement 0 mais il risque t'y avoir un vide.

PS: Pour la pièce jointe les vert les box de collision , le rouge le vecteur vitesse , le bleu le vecteur modifiée.
Je peux faire du pseudo code au pire , hésite pas a dire quel collision tu veux faire , 2D , 3D , comment ? un exemple de jeu qui implémente ?

[Deaf]

Tout d'abord, merci de t'intéresser à mon problème.

Je pense que je vais préciser un peu, car à la vue de ta dernière réponse, on a pas tout à fait la même chose en tête, mais tu ne peux pas être dans la mienne

Sur ma map, il n'y a pas d'obstacles fixes, il n'y a que des personnages.
Ce que tu expliques sur les collisions va me servir mais doit être complété car dans l'exemple mario/mur, le mur devrait être mobile pour se rapprocher de mon cas.

Mon problème est en fait un mélange de gestion des collisions et d'IA/Pathfinding.
Je dois effectivement adapter mon vecteur vitesse, mais pas pour arrêter le personnage (réduction de la vitesse), plutôt pour le dévier afin d'éviter l'autre personnage (changement de direction et éventuellement de vitesse).

Je pense modéliser les personnages comme étant des ronds ayant tous le même diamètre. Du coup, pour les collisions, je comptais juste calculer la distance entre chacun des personnages (position = centre). Cette solution me semble simple à mettre en oeuvre et suffit largement à mon cas.
Ai-je là aussi une mauvaise approche?

A ce problème s'ajoute également une incompétence complète de ma part sur ce domaine qui fait que je ne suis pas certain de la validité de mon algo principal.
Est-ce que je conserve le fonctionnement suivant (pseudo code)?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
loop
  Time prochaineLoop = heureCourante() + PERIODE;
 
  for each Personnage P
    P.position = P.position + P.vecteurVitesse;
  end for
 
  rafraichitIHM();
 
  for each Personnage P
    P.vecteurVitesse = calculeNouveauVecteurVitesse(P);
  end for
 
  attente(prochaineLoop - heureCourante());
end loop

[Kannagi]

Sur ma map, il n'y a pas d'obstacles fixes, il n'y a que des personnages.
Ce que tu expliques sur les collisions va me servir mais doit être complété car dans l'exemple mario/mur, le mur devrait être mobile pour se rapprocher de mon cas.

L'exemple que je t'ai donné marche aussi avec un mur mobile ,sauf que dans ce cas le mur aussi aura un vecteur vitesse.

Pour ton code ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
  Time prochaineLoop = heureCourante() + PERIODE;
  //code
  attente(prochaineLoop - heureCourante());

C'est pour le FPS non ?
Donc tu peux le mettre dans une fonction/méthode.


Sinon la logique m’échappe un peu a vrai dire voila en pseudo code je que je ferais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
Personnage P
loop
  //on connait pas la valeur du vecteur donc par défaut je le met a zero , en y en peut mettre une valeur pour la gravité par exemple
  P.vecteurVitesse.x = 0;
  P.vecteurVitesse.y = 0;
 
  evenemnt(); //tri des evenements
 
  if(evenement.touche_flechedroite == TRUE) P.vecteurVitesse.x = 5;
 
  collision(P.position,P.vecteurVitesse); // on modifie ici le vecteur vitesse
 
  P.position = P.position + P.vecteurVitesse;
 
  rendu();
  fps();
end loop

[Deaf]

Pour le FPS, laissons de côté, je l'avais signalé histoire de...

Ce qui me gène dans l'exemple que tu fournis, c'est que si aucun évènement (souris/clavier je suppose) ne survient, il ne se passe rien.
Ce n'est pas tout à fait ce que je souhaites. Les personnages ont des directives à effectuer et essaient de les effectuer en prenant en compte les autres personnages, afin de les éviter ou de les suivre par exemple.
Les évènements extérieurs sont très rares, on peut même considérer qu'ils n'existent pas: je compte les intégrer après coup par un changement de la directive.

J'ai l'impression de ne pas être très clair

[Kannagi]

Ce qui me gène dans l'exemple que tu fournis, c'est que si aucun évènement (souris/clavier je suppose) ne survient, il ne se passe rien.
Ce n'est pas tout à fait ce que je souhaites. Les personnages ont des directives à effectuer et essaient de les effectuer en prenant en compte les autres personnages, afin de les éviter ou de les suivre par exemple.

Je donne un exemple de base il suffit de l'adapter.

En gros si c'est IA qui décide au lieu que ça soit les événements , donc très peu de changement , ça donne un truc comme cela :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Personnage P
loop
  //on connait pas la valeur du vecteur donc par défaut je le met a zero , en y en peut mettre une valeur pour la gravité par exemple
  P.vecteurVitesse.x = 0;
  P.vecteurVitesse.y = 0;
 
  IA(); //IA qui gère ce que fait un perso
 
  if(IA.deplacement_droite == TRUE) P.vecteurVitesse.x = 5;
 
  collision(P.position,P.vecteurVitesse); // on modifie ici le vecteur vitesse
 
  P.position = P.position + P.vecteurVitesse;
 
  rendu();
  fps();
end loop

Et donc si IA ne décide rien ben il y a aucun déplacement ce qui me semble logique

[Deaf]

Donc dans l'ensemble, ma boucle principale n'était pas si bancale que ça.

Il reste à voir deux points qui me posent problème:
1 - le premier calcul du vecteur vitesse
2 - le calcul des collisions


1) Pour le calcul du vecteur vitesse, je verrai bien une solution du style:
je calcule les positions théoriques de tous les personnages sur les 2 prochaines secondes (par exemple) et ce en fonction de la position et de la vitesse actuelle. Cela me permet de faire une anticipation.
Ensuite, pour chaque personnage, je regarde si sa trajectoire entre en collision avec un des autres. Dans ce cas, je modifie son vecteur vitesse courant pour préparer l'évitement. Comme c'est pour la prochaine action, cela ne modifie pas l'anticipation et donc l'ordre de traitement des personnages n'a aucune importance.

2) Pour résoudre les collisions, je vois bien le principe théorique avec un élément fixe, mais comment gérer cela avec 2 (voire N) éléments en mouvement? Dois-je prendre en compte uniquement la position de départ, uniquement la destination, les deux? Tout ceci étant nouveau pour moi, cela me paraît un peu flou. J'ai peur d'arriver à des cas où deux personnages se croisent là où ils devraient se gêner ou inversement, ils se gênent alors qu'ils pourraient se contourner.

[Kannagi]

Bon deja il faut être d'accord que les collision et IA sont deux chose complétement indépendantes , alors que j'ai impression que tu veux mélanger les deux.

1 - le premier calcul du vecteur vitesse

Alors inutile de prédire avenir dans 2 secondes (ce qui peut etre énorme et chaud niveau codage) sur 30 fps c'est deviner ce qui se passera dans les 60 prochaine frames.

2 - le calcul des collisions

Tu dois prendre en compte le déplacement+collision , mais je vais expliquer ça en détails.

Alors déjà je parle uniquement des collisions , IA c'est juste d’après je que j'ai compris dans ton cas une histoire de pathfinding qui sera géré dans mon exemple par la fonction IA(); donc j'entrerais pas en détails sur cela.

Pour les calcul de collision déjà par étape :
La première créer une fonction de collision cercle/cercle (pas complexe).
Pour les collisions tu aura N élément avec chaqu'une une position et un vecteur vitesse.
Pour faire le test et la modification de vecteur , effectivement tu dois faire le test avec la position + vecteur vitesse , sans ce vecteur vitesse cela veut dire qu'il bougerait pas
Donc ton cercle + vecteur_vitesse qu'on appelle A a une collision avec une autre cercle+vecteur_vitesse quand appelle B, alors que doit t'on faire ?
Ben ton A tu modifie son vecteur vitesse pour qu'il n'y est plus cette collision.
Après tu fait pareil pour B si il a encore une collision (normalement pas avec A , mais peut être avec un autre cercle C ou D ).

Donc pour résumer si on a 4 certcle quand nomme A,B,C,D en pseudo code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
Si collision cercle/cercle A B
    modification du vecteur A
 
Si collision cercle/cercle A C
    modification du vecteur A
 
Si collision cercle/cercle A D
    modification du vecteur A
 
//pareil pour B
Si collision cercle/cercle B A
    modification du vecteur B
 
Si collision cercle/cercle B C
    modification du vecteur B
 
Si collision cercle/cercle B D
    modification du vecteur B
 
//ainsi de suite avec C et D , le mieux c'est une boucle mais pour explication je prefere etre explicite la

Pour IA c'est un pathfinding , le mieux c'est de quadriller ta map et de faire la pathfinding par rapport a cela , ça ne pas être très précis (par rapport a la taille de ta grille) et donc contourner un peu trop , mais pour le pathfinding oui , tu devras faire fairte le pathfinding avec position+vecteur vitesse mais j'ai peur que il reste coincé en cas d collision donc peut etre avoir une position old pour voir si cela bouge pas pendant plus une seconde , faire le pathfinding sans les vecteur vitesse.

[Deaf]

Merci encore de ton intérêt, j'espère ne pas t'épuiser trop vite

Alors inutile de prédire avenir dans 2 secondes (ce qui peut etre énorme et chaud niveau codage)

Je me doit de prédire un minimum, sinon, je ne vois pas comment faire une poursuite anticipée: A doit aller là où B va, et non la où B est.
Cette poursuite anticipée doit être possible. J'ai parlé de 2 sec, ça peut être 1 sec. De même, tu parles de 30fps, mais le but n'est pas de recalculer la direction (=appel à IA()) de tous les personnages à chaque frame, c'est pour cela que je parlais de temps de réaction. En effet, ce ne sont pas des robots, entre le moment où un personnage change de direction et où les autres réagissent en conséquence, il y aura un délai (perception + réflexion). Ce délai devra cependant être supérieur au temps de calcul, sinon, ça ressemblera à rien...

A mon sens, les collisions ne doivent arriver que très rarement car les IAs auront toutes pour but de les éviter. Après, il peut toujours il avoir des couacs (les deux décident de faire un écart par le même endroit), mais cela restera accidentel.
Il reste ceci dit un point qui me chagrine sur le modèle que tu proposes: il y a un sens de traitement qui favorise les derniers testés.
Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
  A
  |
<-V------------B

A va vers le bas pas vite et B va vers la gauche très vite.
Il a collision, donc A "laisse passer" B et s'arrête une "case" en dessous et B fait son chemin tranquillement.
Dans la dynamique, j'ai dans l'esprit que A aura empiété sur la "case" commune avant B et que ça devrait être ce dernier qui devrait s'arrêter.
Est-ce que je cherche les ennuis là où il n'y en a pas?

Tu vas peut-être clarifier quelque chose car j'utilise peut-être le terme "collision" abusivement. Pour moi, c'est le fait de savoir si deux éléments vont entrer en collision, se chevaucher. J'ai l'impression que pour toi, c'est plus la résolution des déplacements "en conflits".
Si c'est bien ça, cela expliquerait une certaine incompréhension.

Donc pour reprendre le gros de mon problème, je pense arriver à 2 niveaux de calculs:
- IA pour le vecteur vitesse initial (initial=en début de calcul de la prochaine frame) : ce calcul n'est pas systématique, il peut même s'étaler sur plusieurs frames sans influencer celles-ci.
- Calcul des collisions basé sur la position et le dernier vecteur fourni par l'IA

Du coup, cela laisse envisager du multi-threading et donc une certaine complexité. D'où mon appel à l'aide pour savoir si je ne me lance pas dans une solution désastreuse.

[Kannagi]

Au moins ça a le mérite d’être clair , je suis parti sur un postulat de base erroné donc j'ai déduit des envie sur cela (et les probleme de collisions resoulu ici sont en général des cas généraux).
Le tien est un cas un peu a part mais reste a mon avis avec des principe de base.

Bon donc a toi de voir pour anticipation mais de mon point et dans ma tête , y a rien qui empêcherait le bon fonctionnement sans anticipation , admettons perso 1 et perso 2.
Perso 1 doit aller a A et Perso 2 a B.

D’après je que j'ai dit donc admettons que Perso 1 et Perso 2 font avoir un collision soit A va changer de direction ( y a plusieurs chemins possible dans un pathfinding) soit il bouge pas (admettons que il y a un perso 3 et 4 qui l'empêche) donc le perso bougera pas et faudra attendre que perso 2,3,4 et bougé cas particulier.
sinon oui faudra déterminer un ordre de priorité dans mon exemple B a priorité sur A mais c'est a toi de voir qui a la priorité.

Et je pense que ça peut marcher si perso 1 suit perso 2 ect.

Oui je parle des collision seulement en terme "la résolution des déplacements "en conflits"" , disons que savoir s'il se touche se sont seulement en général des test de collision avec des forme géométriques.
Effectivement pour ton pathfinding tu peux déterminer une chemin si il y a dans son chemin une collision avec un autre élément alors choisir un autre chemin mais inutile de le faire pour tous son chemin je pense, il fait le chemin numero 1 tant qu'il y a pas de conflit , si y a un conflit il change de chemin.

Et donc d’évité le multi-threading et la complexité qui va avec et la complexité de tous testé.

Ma première approche me semble pas mauvaise aussi , effectivement B aura avantage sur A , je sais pas si c'est très grave dans je que tu veux faire , tu peux faire inverse aussi , on plus de faire moins de test et plus simple a coder.

[Djakisback]

Salut,
Mettons que tu précalclules un pas ou plusieurs pas (par exemple : t + 2 secs), et tu vois que A et B entrent en collision, pour ce qui est de l'avantage tu peux choisir ce que tu veux, par exemple "le plus rapide ne change pas de trajectoire" ou "le plus petit change de trajectoire", etc.
Ça risque d'être assez chaud de gérer ça sur x solides.
Sinon est-ce que tu penses mettre des solides statiques dans la scène ?

[Deaf]

Je ne compte pas mettre de solides statiques, les seuls éléments sont les 10 personnages.

Pour le pré-calcul, il peut paraître énorme, j'en ai conscience, mais il faut savoir que:
- comme il se fait sur la position et la vitesse à un instant T, il n'est nécessaire de recalculer que lorsqu'un des personnages change sa vitesse/direction
- les personnages ne sont pas constamment en train de changer de vitesse/direction
- une phase de jeu ne durera pas plus de 10 à 12 secondes.

Je suis en train d'envisager un ordre de priorité sur les personnages. Ainsi, à chaque fois qu'un changement arrive, je traite les personnages par ordre de priorité et le problème évoqué plus haut disparait.
Cette priorité aura un sens dans le jeu, le cas de A et B qui se croisent était surtout théorique. J'aime bien creuser et bien comprendre les principes avant de les simplifier.

[Djakisback]

Si tu as 10 solides, aucun problème a priori.

"- comme il se fait sur la position et la vitesse à un instant T, il n'est nécessaire de recalculer que lorsqu'un des personnages change sa vitesse/direction"

A moins que tu ne pré-calcules tous les pas jusqu'à la fin du jeu, ce qui semble peu faisable, car les comportements des solides peuvent changer, tu seras obligé de pré-calculer les pas de simulation de tous les objets à t + x secondes au fur et à mesure du déroulement mais avec 10 solides aucun problème.

Pour l'anticipation des collisions il faut voir cela je pense comme un fonctionnement classique, sauf que tu anticipes les calculs, il font donc prévoir un rollback des positions.

Pour la gestion des collisions en général il y a 2 méthodes :
discrete :
- tu computes les positions à t + x, si des solides sont entrés en collision, tu les "dépénètres", c'est-à-dire, ramener leurs positions à l'instant où ils n'étaient pas en collision mais "tangents"
continuous :
- tu découpes le temps écoulé en micro segment, et tu computes chaque partie du temps écoulé jusqu'à ce qu'il y ait collision.


Tu pourrais t'orienter vers Box2D ou Bullet si tu ne veux pas redévelopper la gestion des collisions et dépénétration + kinematic.