Affichage de la plage sur une grille hexagonale

10

Voici la situation.

J'ai un plateau hexagonal et une unité dessus, avec une valeur de vitesse ou de déplacement 4. Le terrain différent a un coût différent. Quand je clique sur l'unité, le jeu devrait me montrer une plage de déplacement.

Ma solution était de vérifier chaque hex dans la gamme de 4, avec A * pathfinding, et si le coût du chemin était inférieur à 4, alors cet hex était dans la gamme. Enfin, le jeu me montre bien la portée de cette unité.

Ma question est: existe-t-il une autre solution pour rechercher une plage sur des grilles hexagonales ou une grille carrée, car même si je suis vraiment fier de ce que j'ai fait dans ma solution, je pense que c'est un peu exagéré? :))

Qu'est-ce qui me fait poser cette question? J'ai remarqué que lorsque la vitesse unitaire est de 4 ou 6 ou même 8, le temps de calcul de la portée de mon ordinateur était vraiment bon, mais lorsque la vitesse était de 10 et plus, j'ai remarqué que je devais attendre quelques secondes pour calculer .Bien dans les vrais jeux, je ne vois pas quelque chose comme ça et mon A * pathfinding est plutôt bien optimisé, donc je pense que ma solution est mauvaise.

Merci pour toutes les réponses.

user23673
la source
1
Je suis d'accord avec Byte56 qu'un premier algorithme de recherche étendu est une bonne solution. Cela ne veut pas dire que vous ne devriez pas essayer d'être créatif, mais en ce qui concerne les algorithmes bien connus, c'est un bon qui s'applique bien.
theJollySin

Réponses:

11

Vous avez raison: A * est un peu exagéré, mais pas beaucoup. Vous ne devriez pas voir des retards comme vous. Un * n'est vraiment qu'un algorithme de Dijikstra modifié . Puisque vous n'utilisez pas de position finale (car votre position finale est juste "aussi loin que vous pouvez aller"), l'utilisation de A * avec son heuristique supplémentaire n'est pas nécessaire. Utiliser simplement Dijikstra ou une première recherche simple sera suffisant.

Par exemple, Dikikstra s'étalera uniformément dans toutes les directions:

entrez la description de l'image ici

(Une première recherche de largeur simple ressemblera à ceci)

Gardez une trace du coût pour se rendre à chaque nœud. Une fois qu'un nœud est au coût de déplacement maximum, ne traitez plus ses nœuds connectés. (Similaire à l'endroit où les nœuds se heurtent au mur ci-dessous).

Si vous rencontrez des problèmes de performances à seulement 10 nœuds, vous voudrez voir comment vous accédez aux nœuds. Une première recherche étendue devrait être en mesure de parcourir des centaines de nœuds sans délai notable (certainement pas quelques secondes). Pensez à stocker une version simple de votre monde dans un format graphique, pour une traversée rapide.

MichaelHouse
la source
pouvez-vous trouver la distance entre deux nœuds en utilisant BFS et en tenant compte des obstacles / poids différents?
Luke B.
Le coût du déplacement entre les nœuds doit être pré-calculé pour la plupart. Le coût n'est pas calculé en utilisant BFS, BFS est un algorithme pour traverser les nœuds. La façon dont vous déterminez le coût de déplacement d'un nœud à un autre est indépendante de la façon dont vous traversez les nœuds.
MichaelHouse
Merci, maintenant je vois pourquoi ma pensée était fausse, la clé pour cela était cette déclaration "Puisque vous n'utilisez pas une position finale (car votre position finale est juste" aussi loin que vous pouvez aller ")". Dans ma solution, je avait une position de fin, c'était l'unité.J'ai juste résolu le problème dans la mauvaise direction.Premièrement, j'ai déterminé la frontière, puis à partir de là, je suis retourné à mon unité, de cette façon, j'ai probablement parcouru plusieurs fois les mêmes nœuds. lorsque ma vitesse augmente, le nombre de calculs augmente également beaucoup. La façon dont vous me le montrez, je visiterai toujours le nœud une fois. J'ai juste eu un mauvais point de vue, vraiment merci, cela simplifie beaucoup.
user23673
4

Amit Patel a fourni une excellente ressource pour obtenir des gammes sur son site . Dans l'article, il utilise l'algorithme suivant pour collecter des tuiles hexadécimales dans une plage:

for each -N  Δx  N:
    for each max(-N, x-N)  Δy  min(N, x+N):
        Δz = xy
        results.append(H.add(Cubex, Δy, Δz)))

Cela crée des limites alignées avec la grille hexadécimale:

entrez la description de l'image ici

Cela trouvera tous les hexagones à une certaine distance de l'hexagone central, si vous voulez considérer les obstacles, utilisez d'abord la recherche étendue de mon autre réponse.

MichaelHouse
la source
1

Si quelqu'un en a besoin, voici l'implémentation C # de l'algorithme de Patel:

IEnumerable<Hex> GetRange(Hex center, int range)
    {
        var inRange = new List<Hex>();
        for (int q = -range; q <= range; q++)
        {
            int r1 = Math.Max(-range, -q - range);
            int r2 = Math.Min(range, -q + range);
            for (int r = r1; r <= r2; r++)
            {
                inRange.Add(center.Add(new Hex(q, r, -q - r)));
            }
        }

        return inRange;
    }
Allan Haugsted
la source