Recherche de chemin 2D - recherche de chemins lisses

10

J'essayais d'implémenter un cheminement simple, mais le résultat est moins satisfaisant que ce que j'avais l'intention de réaliser. Le truc, c'est que les unités dans des jeux comme Starcraft 2 se déplacent dans toutes les directions alors que les unités dans mon cas ne se déplacent que dans au plus 8 directions (style Warcraft 1) car ces 8 directions dirigent vers les prochains nœuds disponibles (elles se déplacent d'une tuile à la tuile voisine suivante) . Que dois-je faire pour obtenir le résultat comme dans Starcraft 2? Réduire la taille des carreaux?

http://i.stack.imgur.com/lr19c.jpg

Sur l'image, vous pouvez voir une ligne horizontale de carreaux de roche constituant des obstacles et le chemin trouvé marqué comme des carreaux verts. La ligne rouge est le chemin que je veux atteindre.

game-design game-mechanics path-finding Kooi Nam Ng
la source
Je suis un grand fan de la recherche de points de saut même si je n'ai pas encore trouvé le temps de l'implémenter. Mais la documentation était intéressante et a de bonnes performances.
2
Êtes-vous sûr que c'est le chemin que vous souhaitez? Les unités l'utilisant traverseront partiellement les murs. Je l'ai rendu plus visible dans un autre exemple: i.imgur.com/eh4ZR.png Et voici ce que vous voulez probablement vraiment réaliser: i.imgur.com/vFQg4.png
Markus von Broady
Vous avez raison.Mon chemin était défectueux, mais c'était plus à des fins d'illustration.Merci d'avoir indiqué la meilleure façon d'examiner.
Kooi Nam Ng
Vous devrez avoir des coordonnées fractionnaires dans une tuile pour obtenir ce que vous voulez. Aucun chemin possible sans cela ne fonctionnerait - le fait de transporter les fractions mais de ne pas les afficher ferait bouger votre unité tout droit / diagonale / droite / diagonale.
Loren Pechtel
@LorenPechtel vous vous trompez, vous pouvez lisser le chemin après en avoir trouvé un. C'est assez simple car vous créez deux lignes en fonction des dimensions de l'unité et vérifiez si elles se croisent avec des tuiles entre tuile0 et tuileN, où tuile1-tuile (N-1) sont des tuiles que vous souhaitez supprimer du chemin.
Markus von Broady

Réponses:

8

Pour un bon algorithme de recherche de chemin, l'utilisation de A * serait probablement une bonne idée, cependant, pour un jeu simple qui ne nécessite pas de recherche de chemin sophistiquée, efficace ou efficace, simplement en faisant avancer les personnages vers une cible en trouvant la direction de l'objectif devrait être suffisant.

Vous pouvez faire est de générer un «graphique de visibilité» (quels autres points sont visibles à partir de chaque point) à partir des sommets, puis effectuez A * sur le graphique. Cela fonctionne car le chemin le plus court se trouvera toujours sur le graphique de visibilité.

Réduire la taille des carreaux peut vous aider.

Ressources

Lectures complémentaires

EDIT: J'aime le commentaire de @ MarkusvonBroady.

"il s'agit en fait de lisser le chemin, pas de le trouver. Le chemin trouvé sur l'image semble OK."

Ressources

De @MarkusvonBroady

J'ai fait une recherche, trouvez les éléments suivants (ceux-ci peuvent vous aider)

Md Mahbubur Rahman
la source
1
excellents liens, +1 de ma part
lhk
2
@MarkusvonBroady, merci pour -1. J'ai appris de toi. Je ne veux pas de point, je suis plutôt disposé à apprendre et à partager le bon. Je crois qu'en discutant, nous pouvons trouver la bonne. :)
Md Mahbubur Rahman
@MarkusvonBroady, voudriez-vous s'il vous plaît partager plusieurs ressources d'algorithme de lissage de chemin?
Md Mahbubur Rahman
En fait, je pense que cette réponse aide le PO. Je ne pense pas que l'OP demandait un lissage réel (interpolation spline ou similaire) mais plutôt que son algorithme trouve actuellement un chemin horriblement non optimal et doit être "lissé" en une ligne plus droite. Ce qu'A * lui aurait naturellement trouvé sans aucun lissage supplémentaire.
Sean Middleditch
J'utilisais A * et je pense avoir trouvé le chemin optimal.
Kooi Nam Ng
0

À partir d'une extrémité du chemin brut, par exemple path[0], vous pouvez supprimer path[1]si le segment formé en joignant les points de path[0]et path[2]ne coupe aucun mur. Aller plus loin jusqu'au dernier segment fournira un chemin plus simple.

Cela permettra non seulement de lisser le chemin mais aussi de supprimer certains points inutiles, comme un exemple de tir, 3 segments consécutifs d'une ligne droite.

arainone
la source