Discussion :

[Evorlde]

Bonjour,

Je tiens à signaler que cela est mon premier poste sur developpez, j’ai lu la FAQ et j’espère donc être au bon endroit. Si tel n’est pas le cas je présente d’avance mes excuses aux modos.

CONTEXTE :
Tout d’abord voici le contexte qui m’amene à poster (Pour ceux qui veulent passer cette partie rendez-vous à la partie « Problématique »). Je suis actuellement étudiant en informatique et nous (une équipe de 4 étudiants) avons pour notre 3ème année décidé de présenter un jeu vidéo de type RTS codé en C++ pour le moteur et SFML pour la partie graphique.
Après 3 à 5 mois de travail nous avons réussi à implémenter les parties suivantes:
• Un menu d’accueil par lequel le joueur peut se connecter au serveur en renseignant l’adresse IP du serveur et le login que le joueur souhaite avoir durant la partie. Chaque serveur peut accueillir 2 joueurs (le serveur ne peut gérer qu’une seul partie à la fois pour le moment).
• Un système de salle d’attente contenant un chat, un system de sélection du peuple avec lequel le joueur jouera, un system de check Box pour indiquer que le joueur est prêt ou non.
Une fois en jeu le joueur peut :
• Sélectionner 1 ou plusieurs unité simultanément.
• Ordonner à l’unité ou au groupe d’unité de se déplacer.
• Ordonner à l’unité ou au groupe d’unité d’attaquer (si la cible est trop loin l’unité se mettra a porté de tire).
• Ordonner la création de bâtiment grâce aux ouvriers (gestion du system de construction et du multitâche  plusieurs construction à la suite).
• Ordonner de réparer un bâtiment.
• Ordonner la création d’unité (j’entends par là une unité autre que de type bâtiment).
• Récolter des ressources.
Tout cela fonctionne parfaitement. A noter que pour la partie graphique nous avons utilisé des sprites pris à starcraft (en attendant d’avoir « mieux »).
Nous avons donc réussit notre challenge (à savoir réaliser un prototype). Et nous passons donc à la partie suivante pour laquelle nous allons avoir un peu plus de 2ans (à savoir rendre un jeu parfaitement 100% finit).

PROBLEMATIQUE :
Pour la partie PathFinding (la partie la plus importante du jeu étant donner que c’est un RTS) nous utilisons le system suivant :
1. L’unité reçoit l’ordre de bouger.
2. La carte de jeu est découpée en secteur grâce à un system de Quadtree (permet d’améliorer les performances sur les longs chemins et encore plus sur les longs chemins avec beaucoup d’obstacles).
3. Un A* est utilisé pour calculer le chemin entre les cases du Quadtree (donnant ainsi des checkpoints).
4. Un A* est utilisé pour calculer le chemin entre 2 checkpoints (ce A* n’est calculé que lorsque l’unité a fini d’exécuter le précèdent chemin entre les 2 checkpoints précèdent).
Ce system est performant et permet de ne pas avoir de lag pour une partie en 1 vs 1 avec 500 unités.
Par contre le point faible de se system est que aucun comportement de groupe n’est géré. Ainsi lorsqu’un groupe doit se déplacer chaque unité calculera son propre chemin. Ce qui est un peu bête… De plus aucune formation de déplacement n’est gérée.

QUESTIONS :
J’aimerai donc savoir comment nous pourrions faire pour gérer un déplacement de groupe. J'ai deux, trois idées sur comment faire pour réaliser cela mais quelques points restes obscures.
Pour cela j’ai plusieurs questions:
• Comment mettre les unités en formation « basique » (ligne de 5 unités de front par exemple).
• Comment faire lorsque les unités n’ont pas tous la même vitesse de déplacement.
• Comment faire lorsque les unités n’ont pas tous la même taille (pour le passage dans des potentiels couloirs former par des obstacles).
• Comment faire si les unités ne démarrent pas tous du même point (par exemple une partie du groupe démarrer depuis la gauche de l’écran et l’autre depuis la droite).
A noter que je ne demande pas de code, mais le concept (le processus) afin de réaliser ce déplacement de groupe. Pour ce qui est du code je serai en mesure de le réaliser une fois que j'aurai les grandes lignes.

En vous remerciant d’avance.

P.S : D’un point de vu plus générale j’accepte tout type de conseils/documentations concernant la création de RTS.

[LittleWhite]

Bonjour,

• Comment mettre les unités en formation « basique » (ligne de 5 unités de front par exemple).

Vous pouvez construire un algorithme (à base de for), qui indique une position de destination pour chaque unité de la formation. La position de l'unité 1, sera 0, 0 par exemple, et la seconde 20, 0 et la troisième 40, 0 et ainsi de suite.
Le décalage que vous donner devra dépendre de la taille de l'unité (bounding sphère ?) et une fois que la position de destination est déterminée, vous n'avez plus qu'à faire fonctionner l'A* et elles iront là où il faut.

• Comment faire lorsque les unités n’ont pas tous la même vitesse de déplacement.

Le cas Age of Empires et/ou Empire Earth : On va à la vitesse de l'unite la plus lente
Le cas Starcraft : On s'en fout (le groupe est brisé du coup )

Comment faire lorsque les unités n’ont pas tous la même taille (pour le passage dans des potentiels couloirs former par des obstacles).

Le A* peut être calculer pour le groupe entier, afin d'optimiser en prenant une taille globale du groupe. On peut imaginer le faire pour l'unité la plus grosse et tout le monde suivra son chemin.
Sinon, il faudra le faire pour toutes les unités en partant du point de départ de la formation, ainsi, le A* résoudra logiquement les problèmes d'obstacles.

• Comment faire si les unités ne démarrent pas tous du même point (par exemple une partie du groupe démarrer depuis la gauche de l’écran et l’autre depuis la droite).

Ceci n'est pas un groupe

Pour le path finding, un groupe, c'est un ensemble d'unité qui parte d'à peu près le même point. Si c'est une sélection multiple du joueur, ce n'est pas nécessairement un groupe


On pourra jouer au RTS ?

[Evorlde]

Tout d'abord merci a toi LittleWhite.

Vous pouvez construire un algorithme (à base de for), qui indique une position de destination pour chaque unité de la formation. La position de l'unité 1, sera 0, 0 par exemple, et la seconde 20, 0 et la troisième 40, 0 et ainsi de suite.
Le décalage que vous donner devra dépendre de la taille de l'unité (bounding sphère ?) et une fois que la position de destination est déterminée, vous n'avez plus qu'à faire fonctionner l'A* et elles iront là où il faut.

Je viens de m'apercevoir que ma question n'était pas complète. J'entendais par la mise en formation de savoir comment nous devront stocker le positions X/Y. Pour le moment nous sommes en int. Au début ont était en double mais cela augmentais les temps des calcules... Du coup être en int est-ce une bonne idée ou faut'il passer en double (quitte a passer en int pour les calcules les plus couteux)? Et ensuite, 1 int est censé représenter quoi comme ordre de grandeur? Par exemple pour le moment un ouvrier de base (pour le moment nous avons pris comme sprite l'ouvrier zerg de starcraft 1) représenté comme taille 1 de hauteur et 1 de largeur. Cela me parait trop peut mais en même temps cela permet de gagner du temps dans le calcule de pathFinding.

Le cas Age of Empires et/ou Empire Earth : On va à la vitesse de l'unite la plus lente

Justement j'ai bien étudier la question et cela est un peu plus compliqué. Les unité en retard vont a une vitesse plus élevé que celle en avance. Je m'explique. Si les unités passent dans un goulot les dernière a passé seront en retard et devront donc pendant un moment avancé plus vite que celle qui ont pris de l'avance. En effet, si une ligne de 5 doit passé dans un espace de 1, la 5ème unité de la ligne a passé aura minimum 4 case de retard sur la position qu'elle devrait avoir... Du coup ici je recherche une sorte de formule pour donner la vitesse de l'unité en pourcentage (en calculant les points de pénalité == si en avance, et le point bonus == si en retard).

Le A* peut être calculer pour le groupe entier, afin d'optimiser en prenant une taille globale du groupe.

Une bonne idée en terme de coup de calcule mais en cas d'obstacle (encore notre goulot) le A* pourrait ne pas renvoyer de résultat alors qu'il y a potentiellement un chemin possible.

On peut imaginer le faire pour l'unité la plus grosse et tout le monde suivra son chemin.

Solution la "meilleur" en terme de coup de calcule/résultat du chemin mais qui casse énormément le GamePlay. Si les unité arrive fasse a un groupe ennemis en file indienne ça fait peloton d’exécution...

Sinon, il faudra le faire pour toutes les unités en partant du point de départ de la formation, ainsi, le A* résoudra logiquement les problèmes d'obstacles.

Pour le moment ont fait comme cela mais quand on aura 6 joueurs sur 1 partie ça risque de ramer.
Ont pensait plus a calculer le chemin de l'unité au centre du groupe et d'appliquer aux autres unité le chemin calculer + l’écart entre l'unité du centre et l'autre unité. Cependant j'ai du mal a voir si c'est la bonne solution et comment l'appliquer.

Ceci n'est pas un groupe

Si cela est un groupe. Dans age of empire par exemple ont peut sélectionner n'importe quelle unité qui apparait a l'écran. L'écran étant relativement grand il peut y avoir de l’écart entre les unité a gauche et a droite. Dans ce cas la j'ai l'impression que age of empire déterminé un point de rassemblement avant de rejoindre le point demandé. Mais encore une fois j'ai du mal a trouver une formule pour déterminer ce point de rassemblement.


Désolé LittleWhite je sais que je suis un peu chiant mais je suis assez perfectionniste du coup je suis a la recherche du "code absolut" qui se rapprochera le plus des RTS du genre age of empire et donc d'un gamePlay le plus appréciable pour le joueur.

On pourra jouer au RTS ?

Pour le moment ont a un prototype fonctionnel (cf. mon premier message pour savoir les fonctionnalité présente).
Après pour la suite ont a prévu de le "sortir" gratuitement dans un peu plus de 2ans.
Pour le moment ont bataille avec notre école pour avoir le droit de faire ce projet comme projet de fin d'étude, disons que l'administration est divisé quand a nous laisser faire ce projet (une partie de l'administration croit en notre potentiel et l'autre partie pense que ont a vu trop gros...).
Si vous voulez je pourrais mettre 2, 3 screen shoot de notre prototype, sachant que pour les graphismes pour le moment ont a:
__ des images empreinte a d'autre jeux pour les unité (par exemple starcraft).
__ pas de terrain.

Si vous voulez également (un peu hors sujet), vous pouvez jeter un oeil a un autre projet que nous avons réalisé (recoder un r-type en 3semaines et a 4 étudiants) ==> https://www.youtube.com/watch?v=jPABDLE8L8U (pour passer les explications allez a 21:20 min).

[LittleWhite]

Pour la première partie, je ne parlais absolument pas de comment on code les éléments du jeu ou autre (je ne remettais pas en question cela non plus). Je donnais juste des exemples pour que cela soit clair.

Si ce sont les unités les plus rapides qui sont devant et qui passe le goulot, alors elles passeront en premier dans le goulot. Si elles étaient derrière, grâce à votre algorithme, alors même en dehors du goulot, elles resteront derrière.
Après, s'il y a du retard, ce n'est pas ultra grave. Si je prend Starcraft, oui les unités sont en file indienne et cela n'a pas gêné grand monde.
Vous pouvez chercher à faire mieux, mais cela aura un coût en performances (peut-être même des bogues). Alors que actuellement, vous doutez de votre A*, qui est la base de votre IA. Vous devriez benchmarker votre IA dès maintenant en spawnant 30000 unités et en leurs donnant des objectifs aléatoires.

Solution la "meilleur" en terme de coup de calcule/résultat du chemin mais qui casse énormément le GamePlay. Si les unité arrive fasse a un groupe ennemis en file indienne ça fait peloton d’exécution...

ça fait parti même du gameplay (autant que les trous dans les murs de Counter Strike j'imagine ). Dans Starcraft, tout le monde sait qu'il faut gérer ses unités

Ont pensait plus a calculer le chemin de l'unité au centre du groupe et d'appliquer aux autres unité le chemin calculer + l’écart entre l'unité du centre et l'autre unité. Cependant j'ai du mal a voir si c'est la bonne solution et comment l'appliquer.

Sans écart, ça marche aussi, ça fait file indienne par contre.

Si cela est un groupe. Dans age of empire par exemple ont peut sélectionner n'importe quelle unité qui apparait a l'écran. L'écran étant relativement grand il peut y avoir de l’écart entre les unité a gauche et a droite. Dans ce cas la j'ai l'impression que age of empire déterminé un point de rassemblement avant de rejoindre le point demandé. Mais encore une fois j'ai du mal a trouver une formule pour déterminer ce point de rassemblement.

Pour l'IA, au début, ce n'est pas un groupe (tant qu'il n'y a pas de rassemblement) car si on prend cinq unités en haut à droite de la carte et cinq unités en bas à gauche, je doute qu'ils aient le même chemin.

Désolé LittleWhite je sais que je suis un peu chiant mais je suis assez perfectionniste du coup je suis a la recherche du "code absolut" qui se rapprochera le plus des RTS du genre age of empire et donc d'un gamePlay le plus appréciable pour le joueur.

Sauf que Age of Empires, ça a tout de même ... +10 ans.
Moi, je pensais donner des réponses, et le coup de ralentir toutes les unités à la vitesse la plus lente + votre idée des offset par rapport au centre, bah ça fait du Age of Empires à 100% ... sauf que je préfère Starcraft


Astuce : Fouillez sur aigamedev.net



Oh, un r-type avec les collisions fixes sur l'écran ...