Jeu vidéo de course de voitures: conception des circuits

Bonjour,

Dans mes temps libres, j’essaie aussi de concevoir un jeu vidéo. Aujourd’hui j’essaie de faire un jeu de course de voitures, et je bloque dans la conception et l’organisation du circuit.

Pour le moment je fais simple: le jeu est en 2D, et idéalement j’aimerais que le joueur puisse voir l’ensemble du circuit en permanence avec la position de ses concurrents. On verra pour faire de la 3D plus tard; de toute façon je suis intimement persuadé qu’il faut commencer par imaginer le truc en 2D avant de penser à la 3D, et dans la plupart des jeux 3D on peut avoir une miniature qui affiche tout le circuit donc ça ne sera sûrement pas perdu.

La question de base à laquelle j’essaie de répondre est celle-ci: étant donné la position du joueur (x,y), quel est son avancement sur le circuit ? Est-il à 0%, 10%, 50%, 95% de l’arrivée ? J’aimerais aussi pouvoir le faire dans l’autre sens: si le joueur se crash alors qu’il en était à 45% (sort de la piste ou se fait dégommer par l’adversaire), le replacer au centre de la piste pour repartir au dernier checkpoint à 40%.

J’ai plusieurs questions importantes qui dépendent plus ou moins directement de celle-ci :

• Déterminer à l’instant T quel est le classement (qui est premier, qui est second…)
• Savoir si le joueur est ou non toujours sur la piste et où se trouve le centre de la piste
• concevoir l’IA parfaite, c’est-à-dire celle qui avance toujours exactement au centre de la piste (ça sera notamment utile parce que j’aimerais bien ajouter des missiles autoguidés genre carapace bleue)
• … et le missile qui peut rebomdir sur les bords de la piste (carapace verte)

Au début, j’ai pensé décomposer un circuit en sections: chaque section ayant une longueur et une direction. Par exemple pour un circuit qui représente un hexagone régulier (on verra pour arrondir les angles et faire des jolies courbes plus tard) ça donnerait ceci :

• 150m pi/2 (0° plein nord)
• 300m pi/6 (60° nord-est)
• 300m -pi/6 (120° sud-est)
• 300m -pi/2 (180° plein sud)
• 300m -5pi/6 (-120° sud-ouest)
• 300m 5pi/6 (-60° nord-ouest)
• 150m pi/2 (0° plein nord)

Si on fixe le début du circuit à la position (0;0), alors la fin de la première section / début de la deuxième se trouve en (0;150), qu’on obtient en faisant (0;0) + 150 * (cos(pi/2); sin(pi/2)). De même la fin de la deuxième section sera en (0;150) + 300 * (cos(pi/6); sin(pi/6)) = (260;300).

Ca me paraît drôlement lourd comme calcul; il doit y avoir plus simple…

Le problème c’est surtout dans l’autre sens. Si par exemple je prends le point (138;230), alors je dois voir que je suis au milieu de la deuxième section, latéralement décâlé de 10m à droite par rapport au centre de la piste (on va dire qu’elle est large, la piste). Le centre de la piste à cette position étant (130;225) (obtenu par interpolation linéaire pour l’exemple, pour le moment j’oublie les jolies courbes j’ai dit). JE dois aussi voir que mon avancement global est de 16.67%, car j’ai parcouru 300m utiles sur les 3.6km du circuit.

Pour le moment, la seule façon que je vois de résoudre ça est de calculer des intersections de segment et des normales aux dits segments. Puis ensuite essayer de quantifier entre 0% et 100% où je me trouve par rapport aux extrêmités du segment calculé (0%=première extrêmité, 100%=seconde extrêmité).

Pour mon hexagone bidon, pour chaque objet du jeu (voiture, missile ou autre), j’ai déjà 7 segments à tester. C’est la mort assurée le jour où je construis un vrai circuit qui risque d’avoir 100 sections non ? ET là je n’ai que des sections rectilignes… ça va encore se corser quand j’aurai des arcs de cercle, et encore mieux si on envisage des courbes de Bézier ou autres…

ça m’a l’air bien compliqué tout ça. Je doute que les jeux vidéo procèdent réellement de cette façon. Il doit y avoir beaucoup, beaucoup, beaucoup plus simple. ON se demande bien comment ils faisaient avec la mémoire et le CPU ridicules de la game boy ou des bornes arcade des années 90.

Comment les vrais jeux vidéo procèdent-ils ? Mon idée de découpage du circuit en sections, dans un premier temps rectilignes, est-elle totalement idiote ?

ET la question bonus: et si je décide de faire un circuit en forme de 8 ? JE trouverais marrant qu’il puisse y avoir des carembolages latéraux.

Merci pour vos réponses !

Y’a probablement d’autres trucs, mais tu peux déjà approximer ton morceau de circuit par un rectangle et vérifier si t’es dedans ou pas, ce qui te permet assez rapidement d’éliminer des morceaux de circuit.

Je n’ai pas la réponse quant aux anciens jeux vidéo, mais la question est passionnante. Je vais donc suivre ce sujet car les réponses m’intéressent également.

Perso j’aurais tendance à penser à un système de checkpoints ordonnés et invisibles. Disséminés à intervalle régulier sur la piste.

Salut,

Question très intéressante et bien détaillée en effet (ça manque juste d’un petit schéma). Je n’ai pas de réponse à tes questions mais peut être des pistes de réflexion ? Pourquoi le choix de l’origine du repère à cet endroit de la piste ? Pourquoi pas au centre ? J’aurais plutôt tendance à utiliser des coordonnées polaires pour ce genre de problème. Ton circuit se rapproche vachement d’un cercle non ?

Cas facile : Maintenant, imaginons que le circuit est un cercle (parfait) et que tu utilise un repère polaire centré par rapport au cercle. Si tu connais la position de ton joueur tu peux facilement connaitre répondre à tes questions.

Je pense qu’un des problèmes est dans la modélisation du circuit. Tu modélises ton circuit comme une succession de sommets. Je stockerais plutôt une succession de segments. Avec pour chaque segment un peu plus d’informations que ce que tu as actuellement

Structure Segment = { x_origine, y_origine, direction_du_segment (un angle entre -PI et PI), longueur_du_segment, Distance_deja_parcourue }

Distance_deja_parcourue, c’est le cumul des longueurs des segments qui précèdent ce segment.

Bien sûr, certaines informations sont redondantes. En particulier, la fin du segment n doit coïncider avec le début du segment n+1, mais ça permet de faire une fois pour toutes, à la préparation du circuit, un certain nombre de calculs.

Et Idem, pour stocker la position du véhicule, je stockerais

vehicule = { numéro_du_segment, longueur_parcourue_dans_ce_segment, décalage_droite_ou_gauche }

Decalage_droite_ou_gauche = un nombre en mètres, disons entre -5 et +5, pour avoir la position ""axiale"" du véhicule

Avec cette structure, on peut recalculer facilement le x et y ’classiques’, ainsi que tous les indicateurs dont tu as besoin.

Pour le véhicule, tu as aussi besoin de stocker la vitesse (vitesse + direction) , et pour ça aussi, je stockerais la vitesse, non pas dans le repère x,y, mais dans un repère lié au segment où se trouve le véhicule. Donc, si le véhicule suit bien la ligne blanche, sa vitesse est toujours (V,0) :

• V = la Vitesse du véhicule, que la route soit orientée Nord/sud , ou Est/ouest ou autre

• 0 parce qu’on considère que le véhicule reste bien sûr la même voie.

C’est en combinant ces informations sur la vitesse + la description du segment en cours qu’on va pouvoir calculer la vitesse dans le repère (x,y)

Ca ne résout pas tous les problèmes ; en particulier, il y a des traitements à faire quand le véhicule passe du segment n au segment n+1, mais ça me paraît une bonne base.

À moitié HS pour signaler que ceci :

concevoir l’IA parfaite, c’est-à-dire celle qui avance toujours exactement au centre de la piste

est faux dès qu’il y a un virage dans ton circuit (en supposant une piste de largeur supérieure à 0, ce qui est normalement le cas), parce que la trajectoire optimale coupe les virages pour minimiser la distance et/ou le rayon de courbure.

Je pense qu’il voyait plus ça comme une IA "Bête", c’est à dire qui respecte totalement le circuit. Car évidemment en allant au centre de la piste ce n’est pas la solution optimal.

Personnellement, j’aurais pensé à employer un "navigation mesh". Qui permet de déterminer où se trouve un point (sur la piste ou non), dans quel triangle et de pouvoir gérer des obstacles dynamiques. Le "chemin" sera alors l’ensemble des centres de ces triangles. Il est alors facile de déterminer le pourcentage d’avancement ou de remettre le véhicule sur la piste.

Je ne peux que conseiller le site de Reynolds, qui est certes un peu vieux, mais qui fournit plein de pointeurs très intéressants. Ou en plus "moderne", ce site qui contient plein de codes.

est faux dès qu’il y a un virage dans ton circuit (en supposant une piste de largeur supérieure à 0, ce qui est normalement le cas), parce que la trajectoire optimale coupe les virages pour minimiser la distance et/ou le rayon de courbure.

Bien vu, je n’avais pas du tout pensé à ça. Du coup ça donne deux questions distinctes en réalité:

• l’IA qui reste toujours au milieu de la piste, utile pour les missiles à tête chercheuse par exemple
• l’IA optimale en distance parcourue, utile pour que ça ne soit pas trop facile de semer les adversaires contrôlés par la machine quand on joue en solo.

Et Idem, pour stocker la position du véhicule, je stockerais

vehicule = { numéro_du_segment, longueur_parcourue_dans_ce_segment, décalage_droite_ou_gauche }

Decalage_droite_ou_gauche = un nombre en mètres, disons entre -5 et +5, pour avoir la position ""axiale"" du véhicule

Avec cette structure, on peut recalculer facilement le x et y ’classiques’, ainsi que tous les indicateurs dont tu as besoin.

Hum…effectivement, vu comme ça, ça paraît beaucoup plus simple à gérer. Ca me donnerait directement:

Avec P=Position cherchée, d=distance parcourue sur le segment, D=direction du segment, s = décalage (shift) et N = normale de D. Avec un petit gag, la normale, c’est (-y;x) ou bien (x;-y) ?

Pour le véhicule, tu as aussi besoin de stocker la vitesse (vitesse + direction) , et pour ça aussi, je stockerais la vitesse, non pas dans le repère x,y, mais dans un repère lié au segment où se trouve le véhicule. Donc, si le véhicule suit bien la ligne blanche, sa vitesse est toujours (V,0) : C’est en combinant ces informations sur la vitesse + la description du segment en cours qu’on va pouvoir calculer la vitesse dans le repère (x,y)

Là aussi ça a l’air à priori de pas mal simplifier. Si on pose alpha=angle d’orientation du segment, theta=angle du véhicule, V = vitesse cherchée et v0 = vitesse du véhicule (scalaire), sauf erreur ça donnerait:

Ca ne résout pas tous les problèmes ; en particulier, il y a des traitements à faire quand le véhicule passe du segment n au segment n+1

C’est là que ton système me paraît un peu coincer. S’il suffit de vérifier si d>l pour savoir quand on est arrivé à la fin du segment, je vois mal comment on peut transformer alpha et s. Ca risque aussi d’être compliqué pour les épingles (différence d’angle >= 90°). Parce que dans ce cas, comme vous l’avez bien fait remarquer, on a peut-être la possibilité de couper le virage et d’entamer le segment suivant sans jamais atteindre la fin du précédent.... et on a des zones qui peuvent se recouper j’ai l’impression.

Il doit sûrement y avoir un moyen simple, c’est juste une translation et une rotation.

A part ça, sinon, ça m’a l’air d’être une excellente solution. Merci.

Personnellement, j’aurais pensé à employer un "navigation mesh".

Je n’ai encore jamais fait de 3D, pour l’instant j’ai dit que j’en restais à la 2D. Je n’ai aucune idée de ce que c’est un mesh.

Par contre le deuxième lien a l’air intéressant, merci.

pour la question de savoir qui est en tête et où en est chaque véhicule sur la piste, voici comment c’est fait sur Micromachine 64.

Les carrés permettent de connaître l’avancement, et les groupes de carrés rouges sont les checkpoints.

Les carrés permettent de connaître l’avancement, et les groupes de carrés rouges sont les checkpoints.

Donc en réalité c’est des sortes de checkpoints invisibles par lesquels on est obligé de passer.

J’ai avancé en partant sur l’idée d’Elegance.

Quand on arrive à la fin d’un segment, on peut calculer où on atterrit sur le suivant en repartant du point (x;y). Je n’ai pas encore tout trouvé mais voici le début du raisonnement:

IL me faut la distance parcourue sur le nouveau segment et le décalage. La distance parcourue s’obtient en projetant la position du joueur sur la ligne. En d’autres termes en trouvant le point d’intersection entre la ligne et la normale de la ligne passant par la position du joueur. Si je note P la position du joueur, O l’origine du segment, D sa direction, N la direction de la normale et I le point d’intersection, on veut donc I l’intersection des droites OD et PN. De là, la distance parcourue d = length(I-O) et le décalage = length(I-P).

Il reste encore deux choses que je n’ai pas encore tout à fait trouvées :

• Comment obtenir le vecteur vitesse $(V_D; V_N)$ relatif au nouveau segment, ou alternativement, l’angle par rapport au nouveau segment
• J’ai le décalage, mais je ne sais pas s’il est à gauche ou à droite

L’angle, ce serait cool de pouvoir le calculer à partir du vecteur vitesse précédent plutôt qu’en repartant de la vitesse selon (x;y). A partir de (x;y) c’est possible avec la formule cos(angle) = produit scalaire / produit des longueurs, mais il doit y avoir mieux. JE ne pense pas qu’on n’a le droit d’additionner bêtmeent nouvel angle = ancien angle + différence d’angle entre les deux segments…

Une bricole (que j’ai pas lue) : pour déterminer le classement ce n’est pas l’avancement qui compte (celui qui a parcouru le plus de cases) mais bien l’inverse (le nombre de cases qu’il reste à parcourir).

Evidemment pour un circuit ça doit revenir peu ou prou à la même chose, mais pour un jeu type simulation de "tour du monde à la voile" ça serait très, très différent.