Comment implémenter un pilote automatique

Question

Je travaille sur la construction d'un jeu d'espace textuel avec .net J'ai un serveur et un client où je suis capable de "bouger" autour de la carte. La carte est décomposée par secteurs, chaque secteur ayant la possibilité de se connecter à 8 autres secteurs (un quadrillage diagonal aussi). Ceci est stocké dans la classe de secteur par un tableau répertoriant les secteurs de connexion. Actuellement, tous les secteurs sont stockés dans une liste. Lorsqu'une commande de déplacement est émise, le tableau de secteurs de connexion est vérifié et si le secteur demandé est trouvé dans le tableau, le nouveau secteur est chargé. Ce que je voudrais faire est implémenter une fonction de pilote automatique, mais pour la vie de moi ne peux pas comprendre comment le retirer avec mes structures actuelles. Chaque secteur connaît seulement ses secteurs de connexion.

Quelqu'un a-t-il des suggestions/idées?

Merci,

Ben

Answer 1

Je pense que vous voulez un algorithme de chemin le plus court. Les secteurs forment un graphique et vous voulez trouver un itinéraire à travers les secteurs.

La manière la plus simple de faire ceci est de faire deux recherches en largeur simultanées à partir de la position actuelle du vaisseau et de l'endroit que vous voulez obtenir. Lorsque vous trouvez un nœud partagé, fusionnez les chemins d'accès à ce nœud depuis chaque emplacement et vous avez un chemin.

Vous pouvez optimiser ceci avec A * si vous avez des données de proximité.

Answer 2

Il y a plusieurs façons de procéder. Est-ce que votre carte ressemble à l'espace lui-même, où vous pouvez voyager dans toutes les directions, ou est-ce plus comme un labyrinthe? En tant que jeu de l'espace, je l'aurais imaginé la carte à

XXXX 
XXXX 
XXXX 
XXXX 

Dans ce cas, vous pourriez être mieux d'utiliser un tableau 2D pour stocker la carte. Cela vous permettra de simplement piloter automatiquement en augmentant X et Y jusqu'à ce que vous trouviez votre destination. Toutefois, si votre carte est plus complexe, vous devez rechercher l'algorithme A * pour la navigation. Ce que vous faites est la force brute votre chemin vers le meilleur chemin, en calculant chaque itinéraire possible, et en choisissant le plus court. Par exemple, si votre carte est:

X 
XXX 
A B 

Et vous essayez d'aller de A à B, vous créez une carte:

(U = up, etc.)

U 
UR 
URU 
URUD 
URUDR 
URUDRD* 
URR 
URRD* 

Cela ressemblera à quelque chose comme ça. Le * signifie que l'itinéraire a trouvé son chemin vers la destination, alors il regarde tous ceux qui l'ont fait, et choisit le plus court.

Un avantage de A * est que vous pouvez appliquer une pondération pour chaque secteur. Si vous avez une nébuleuse dans un secteur qui prend trois fois plus de temps à passer, vous pouvez l'inclure dans votre algorithme en comparant l'effort total au lieu du nombre d'opérations. C'est cool dans les jeux où votre personnage navigue via le chemin parce que le chemin est beaucoup plus rapide :)

Il existe de nombreux algorithmes pour cela en ligne, il suffit de rechercher un pathfinding A *. Bonne chance!