Comment déterminer l'amplitude des mouvements possibles dans un jeu de stratégie au tour par tour et basé sur la distance?

11

Je crée un jeu de stratégie au tour par tour en 2 dimensions en utilisant c ++ et SFML-2.0. Le mouvement est basé sur la distance plutôt que sur la grille, avec plusieurs pièces différentes en forme de triangle qui, à un tour donné, chacune peut soit tourner en place, soit avancer.

Le mouvement fonctionnera de telle manière que le joueur sélectionne un emplacement vers lequel la pièce doit se déplacer, ce qui génère un chemin potentiel pour la pièce à prendre. Une fois que le joueur a confirmé sa décision, la pièce se déplacera le long de ce chemin jusqu'à l'emplacement souhaité. Les chemins sont limités par deux facteurs: la distance, jusqu'où une pièce peut aller, en tenant compte des virages (donc s'il y a une courbe, ce sera la longueur le long de la courbe, et non directement d'un point à un autre); et l'angle de braquage, jusqu'où la pièce peut pivoter à n'importe quel point (et jusqu'à chaque point) tout en se déplaçant (par exemple, de -30 à 30 degrés).

Ma question est la suivante: comment dois-je procéder pour déterminer la plage d'emplacements potentiels que le joueur peut sélectionner pour déplacer la pièce?

Je ne sais pas exactement quelles équations et / ou algorithme utiliser ici. Mon plan d'origine était extrêmement trop compliqué, au point qu'il était presque impossible à mettre en œuvre, encore moins à expliquer, et je suis à ce stade totalement perdu avec le projet au point mort.

Comment puis-je déterminer la portée qu'une unité peut déplacer, en tenant compte de son rayon de braquage?

Par exemple, dans l'image ci-dessous. Les lignes rouges, bleues et vertes auraient toutes la même longueur. Le cercle violet indique la plage de mouvement que l'unité peut déplacer. (La forme est probablement inexacte et les lignes ne sont probablement pas réellement de la même longueur, mais vous avez l'idée)

entrez la description de l'image ici

sfphilli
la source
Il ne pourra toujours parcourir que la même distance (totale). Donc, la question est vraiment de savoir "jusqu'où va-t-elle?" / "Combien doit-elle tourner?" / " doit-elle tourner?". Vous devrez probablement commencer par déterminer la trajectoire régulière, puis reculer d'un début de virage pour les angles supérieurs à une certaine valeur; notez que la distance finale sera plus longue en ligne droite (tournant le plus tard) qu'avec les courbes.
Clockwork-Muse
Oui, la distance parcourue est le principal facteur limitant. Mon plus gros obstacle ici est que je dois tenir compte du fait que la pièce peut tourner, et continuer à tourner, à tout moment qu'elle peut atteindre, tant qu'il reste de la distance disponible.
sfphilli
Que voulez-vous dire, la plage qu'une unité peut déplacer? Vous voulez dire les points vers lesquels il peut se déplacer? Connaissez-vous l'algèbre linéaire (vecteurs)?
BlueRaja - Danny Pflughoeft
1
Quel scénario réel essayez-vous de modéliser? Votre problème est trop vague sur les exigences, ce qui entraîne trop de solutions proposées. Il existe des approches bien connues pour (virtuellement) chaque problème spécifique dans ce domaine, mais tout le monde devine lequel de ces nombreux problèmes vous affrontez réellement.
Pieter Geerkens
1
@PieterGeerkens Je suppose que parce que OP ne demande pas de code, ils demandent un algorithme. Et ont fourni suffisamment de détails sur le scénario pour qu'un algorithme puisse raisonnablement être conçu. Ceci est courant et acceptable.
MichaelHouse

Réponses:

4

Générez un champ d'écoulement ou de distance à l'aide de Dijsktra.

Essentiellement, remplissez une grille en utilisant l'algorithme Dijkstra sans destination (probablement un nom différent pour cela; je ne le sais pas). Prenez simplement chaque nœud ouvert, calculez les voisins accessibles, poussez-les sur la liste ouverte, définissez-les sur la liste fermée, mettez à jour le chemin "suivant" du nœud parent selon le cas, etc. Lorsque vous déterminez le coût pour atteindre un nouveau nœud, tenez compte des limitations de rotation.

Le résultat sera maintenant que vous avez un réseau de tous vos nœuds sur la façon de revenir au début. Les nœuds qui ne peuvent pas être atteints n'auront pas été touchés par la première étape. Les nœuds qui peuvent être atteints auront un élément "nœud suivant le long du meilleur chemin possible vers le parent" calculé afin que vous puissiez à la fois mettre en surbrillance tous les nœuds et ensuite utiliser ces informations pour afficher ou exécuter le chemin de déplacement lorsque l'utilisateur survole ou clique sur les zones en surbrillance.

Sean Middleditch
la source
Pas tout à fait comment j'expliquerais le concept, ou comment je le mettrais en œuvre, mais certainement la bonne approche.
Pieter Geerkens
Ma compréhension de l'algorithme, en l'état, est que la traversée de nœud doit être indépendante du chemin. Ainsi, pour ce faire, vous devez ajouter un autre degré de liberté (un autre axe sur lequel créer vos nœuds) dédié au parement. En d'autres termes, vous auriez un nœud pour chaque combinaison de différents X, Y, potentiellement Z et face. Sinon, trouver le chemin le plus court pour entrer dans un nœud ne fait pas de distinction entre les différentes facettes en le quittant. Est-ce exact? Si tel est le cas, cette méthode est-elle peut-être trop intensive?
TASagent
@TASagent: bon point, je ne l'ai pas entièrement pensé. L'algorithme est alors peut-être un peu décalé mais l'approche devrait fonctionner.
Sean Middleditch
@PieterGeerkens: Je suis d'accord, c'est une mauvaise explication. Vous devriez faire votre propre réponse qui explique tout mieux.
Sean Middleditch
Cela semble être assez proche de ce dont j'ai besoin, mais je dois admettre que je n'ai jamais entendu parler de cet algorithme, et donc je ne sais pas comment le généraliser à ce dont j'ai besoin. Avez-vous un lien vers de bonnes informations ou des tutoriels à ce sujet?
sfphilli
4

Une solution de force brute serait:

  1. Créez un cercle de sommets autour de l'unité, avec l'unité au centre. Le rayon du cercle est la distance de déplacement maximale. La densité des sommets peut changer en fonction du niveau de détail souhaité pour le résultat final.
  2. Pour chaque position de sommet, simulez le mouvement de l'unité se dirigeant vers cette position. Cela se fait en boucle serrée sans rendu.
  3. Lorsque la distance maximale est atteinte dans la simulation de direction, déplacez le sommet jusqu'au point de l'unité simulée. Ce point est le plus proche que l'unité puisse atteindre ce sommet avant la fin du tour en cours. Cela a pour effet de réduire le cercle à la taille du mouvement réel.
  4. Utilisez ces sommets, ainsi qu'un sommet centré sur l'unité pour créer un cercle rendu pour tracer les distances de mouvement possibles.

entrez la description de l'image ici

Donc, en commençant par le cercle bleu, vous traitez vos chemins, pour finir avec le cercle violet. Ensuite, vous pouvez utiliser ces points avec un point central sur l'unité pour créer les triangles rouges nécessaires à l'affichage de la forme. (Faire juste cette image me fait réaliser que cette forme n'est pas correcte, mais ce sera intéressant de voir ce qui est réellement correct)

MichaelHouse
la source
3

Je vais développer la solution de Sean dans une réponse séparée, car elle représente une approche différente de ce que je proposais initialement.

Cette solution représente probablement la méthode la plus accessible. Cela nécessite de partitionner votre environnement en nœuds. Oui, cela réintroduit une approche basée sur la grille, mais elle peut être rendue relativement fine, ou utilisée pour une détection de chemin large avec un positionnement plus fin géré dans le nœud. Plus la structure du nœud est grossière, plus la recherche de chemin est rapide.

Le gros problème ici est que vous avez en fait affaire avec le vaisseau, donc de nombreuses solutions traditionnelles d'orientation ne peuvent pas être utilisées sans modification. Ceux-ci sont généralement indépendants du chemin, en ce sens qu'ils ne se soucient pas de la façon dont vous êtes arrivé au nœud dans lequel vous vous trouvez. Cela fonctionne bien lorsque l'accélération, la décélération et le virage sont instantanés et libres. Malheureusement pour vous, tourner n'est pas gratuit. Cependant, comme il y a vraiment une information supplémentaire qui est supprimée dans cette simplification, nous pouvons la coder comme une autre variable. En physique, cela serait connu sous le nom d'espace de phase.

En supposant que 2 dimensions pour l'instant, vous pouvez extrapoler pour 3:

Normalement, vous auriez besoin d'un nœud pour chaque position de coordonnées discrète autorisée. Par exemple:

(0,0) - (1,0) - (2,0)
  | \  /  |  \  / |
(0,1) - (1,1) - (2,1)

Etc. Vous construisez un diagramme de nœuds de points adjacents et les connectez par adjacence spatiale. Ensuite, vous utiliseriez l'algorithme de Dijkstra, tuant les nœuds qui dépassent la valeur de mouvement autorisée pour le tour, jusqu'à ce qu'il n'y ait plus de nœuds vivants inexplorés restant connectés aux nœuds explorés. Chaque nœud garde une trace de la plus petite distance nécessaire pour l'atteindre.

Pour étendre cette méthode afin qu'elle soit utilisable avec Rotation, imaginez ce même nodegraph en 3 dimensions. La direction Z correspond à la rotation / face et est cyclique, ce qui signifie que si vous continuez à voyager dans la direction + Z, vous revenez à votre point de départ. Maintenant, les nœuds correspondant à des positions adjacentes ne sont connectés qu'à travers la face qui correspond à cette direction. Vous parcourez les nœuds connectés aux nœuds déjà explorés comme d'habitude. Je recommanderais de limiter à N, NE, E, SE, S, SW, W, NW dans ce schéma.

Cette solution peut vous indiquer toutes les régions accessibles de l'espace, ainsi que le meilleur chemin pour y arriver, la rotation que vous avez lorsque vous y arrivez et toutes les orientations que vous pourriez avoir lorsque vous y arrivez.

Ensuite, lors de l'exécution du cheminement, vous êtes libre d'interpoler / de spline cubique pour le rendre plus authentique.

TASagent
la source
1
C'est excellent. Je vais devoir faire un peu de recherche sur l'algorithme et l'expérimenter dans mon jeu, mais cela me semble vraiment être la solution idéale, d'autant plus que je peux le généraliser à d'autres parties importantes du jeu.
sfphilli
1

Il semble que vous deviez d'abord décider de la manière exacte dont vous souhaitez que la mise en route fonctionne. Des options comme:

  • S'ils se déplacent à l'intérieur du cône, tournez-les d'abord, puis commencez à bouger. Il s'agit de la solution la plus facile à mettre en œuvre et à rechercher. C'est aussi moins intéressant donc je ne voudrais pas l'utiliser.

  • Rotation continue tout en se déplaçant, jusqu'à un total de 45 degrés. Celui-ci est beaucoup plus délicat et, espérons-le, celui que vous recherchez. L'intégration numérique sur le chemin à l'aide d'un pas de temps fixe est probablement la façon la plus simple d'aborder celui-ci. Votre cône sera limité par la rotation maximale (+ X degrés à chaque étape) et minimale (-X degrés à chaque étape).

La meilleure façon de traverser l'espace avec la seconde de ces exigences dépend en grande partie de l'environnement dans lequel ils se déplaceront. S'il y a beaucoup d'obstacles que vous devez traverser, alors les choses peuvent devenir vraiment délicates et très coûteuses. Cependant, s'il n'y en a pas, vous pouvez charger à l'avant (et même réduire progressivement) la rotation pour finir à l'emplacement souhaité.

J'ai le sentiment que je n'ai peut-être couvert que partiellement les sujets sur lesquels vous aviez une question, alors n'hésitez pas à ajouter plus dans les commentaires et je peux étendre la discussion.

TASagent
la source
Je veux très certainement utiliser la deuxième option, de tourner jusqu'à (par exemple) 45 degrés à n'importe quel point, et potentiellement à chaque point, le long d'un chemin. Il y aura également des obstacles, chacun plus grand que les pièces (pensez aux roches géantes). La façon dont je pensais à l'origine à ce sujet était de générer un cône de points d'extrémité possibles, puis de générer pour chacun de ces points d'extrémité un nouveau cône, et ainsi de suite pour chaque emplacement possible jusqu'à ce qu'il atteigne la distance maximale parcourue. Cela dit, je ne suis pas tout à fait sûr de savoir comment procéder sans implication excessive.
sfphilli
Hmmm, il semble que j'étais / suis un peu flou sur certains détails. En repensant à la question, je vois que vous avez spécifié «au tour par tour» et que les unités peuvent «tourner ou se déplacer» à leur tour. Cela signifie-t-il alors que le joueur trace ses actions plusieurs tours à l'avance et que vous voulez faire le chemin pendant qu'il se déplace? Des précisions supplémentaires sur la façon dont le mouvement est censé fonctionner seraient utiles.
TASagent
Non, ce que je voulais dire, c'est qu'à un tour donné, le joueur peut soit faire pivoter sa pièce en place, aussi loin qu'il le souhaite, soit se déplacer dans la direction qu'il regarde déjà. S'ils se déplacent, ils peuvent parcourir une distance particulière le long d'un chemin, et ils peuvent tourner ou se diriger vers un angle particulier (donc n'importe où de -45 à 45 degrés par exemple) tout en se déplaçant. Imaginez donc qu'un chemin choisi impliquerait une courbe afin de se déplacer vers la gauche ou la droite. Le chemin serait déterminé par le joueur qui choisit un point vers lequel il veut se déplacer, dans la plage de points possibles que j'ai du mal à déterminer.
sfphilli
Ok, donc il semble que vos caractéristiques souhaitées soient malheureusement trop restrictives pour l'algorithme de Dijkstra dont nous parlons ci-dessus: - \. Peut-être. Je vais esquisser certaines choses pour cela plus tard quand je rentrerai.
TASagent
Vous souhaiterez peut-être modifier certaines des informations que vous avez recueillies pour clarifier le problème dans la question d'origine, afin que les personnes qui viennent plus tard puissent commencer avec plus d'informations.
TASagent