Je suis en train de développer un simple jeu de SIM basé sur la grille 2D et avoir une découverte de chemin entièrement fonctionnelle.
J'ai utilisé la réponse trouvée dans ma question précédente comme base de la mise en œuvre d'une constatation de chemin *. ( Jeu de Java 2D Pathfinding? ).
Pour vous montrer vraiment ce que je demande, j'ai besoin de vous montrer cet écran vidéo capture que j'ai fait. J'étais juste testé pour voir comment la personne se déplacerait vers un endroit et de retour à nouveau, et c'était le résultat ...
http://www.screenjelly.com/watch/bd7d7pobyfo
choix différent de chemin en fonction de la direction, un résultat inattendu. Des idées?
9 Réponses :
Les deux chemins sont de la même longueur, de sorte que l'algorithme fait son travail très bien - il trouve un chemin le plus court. Cependant, l'algorithme A * ne spécifie pas le chemin le plus court qu'il faudra. Les implémentations prennent normalement le «premier» chemin le plus court. Sans voir le vôtre, il est impossible de savoir exactement pourquoi, mais si vous voulez les mêmes résultats à chaque fois que vous devrez ajouter des règles prioritaires de quelque sorte (afin que vous soyez souhaité, le chemin apparaisse d'abord dans la recherche). < / p>
Si vous regardez le premier lien et suivez la réponse à cette question, la page contient réellement des liens vers tout le code de fiançailles que j'ai utilisé. Sous enquête, j'ai le choix de 4 heuristiques. Une * heuristique (basée sur le coût uniquement), le plus proche, le plus proche et le Manhattan. Je vais essayer les 3 autres, comme un * est la valeur par défaut.
Qu'est-ce que c'est * heuristique dont vous parlez? A * utilise courantCost + estimation_of_remainder ("huériste"). Le plus proche, le plus proche, Manhattan est la heuristique, mais je ne connais aucun nommé "A * Heuristic".
Mon erreur. Ce n'est qu'une classe d'interface! Encore beaucoup d'apprendre beaucoup! :) c'était sur le plus proche duriste. Essayé l'autre 2. La clienteQuedHeuetistic a été un peu drôle parfois, tandis que la Manhattanheunistique a évité de zigging, ce qui semble mieux. Je me demande si theres une promenade humanistic ...
Les humains n'ont pas tendance à devoir passer d'une place de grille à une autre!
Je sais, mais je veux dire dans un environnement basé sur la grille 2D. Je suppose que la randomisation est la plus proche que je puisse obtenir.
La raison est la voie que vous voulez que l'algorithme aille.
Je ne connais pas l'heuristique que vous utilisez * mais dans le premier cas, il doit d'abord aller à la fin du tunnel, puis planifie la voie de la fin du tunnel à la cible.
Dans le second cas, les mouvements les plus simples des cibles descendent jusqu'à ce qu'il frappe le mur, puis il planifie le chemin du mur à la cible.
La plupart A * Je sais travailler avec une ligne de spectacle heuristique ou un Distance Manhattan dans le cas d'un monde de bloc. Cette heuristique vous donne la voie la plus courte, mais en cas d'obstacles qui force pour aller une manière différente de la ligne de spectacle, les voies dépendent de votre point de départ.
L'algorithme ira la ligne de spectacle aussi longtemps que possible.
Si j'ai vu de droite, la sphère se déplace d'abord vers la droite dans une ligne Straigt, car elle ne peut pas être directement vers l'objectif (le chemin est bloqué). Ensuite, cela va en ligne droite vers le but. Il ne semble que diagonale.
Je pense que vous n'avez pas saisi mon argument. Désolé si je ne l'ai pas fait clairement. Je parlais de la comparaison entre le voyage vers et le retour.
Ah ok. Je n'ai pas vu la vidéo entière. Je suis sur une petite bande de connexion Internet à droite savoir ...
pas de soucis. Je vous remercie de prendre le temps d'écrire une réponse à ma question quand même :) Toujours reconnaissant!
Votre recherche examine-t-elle d'abord dans la direction "Down"? Cela pourrait expliquer l'algorithme. Essayez de le changer pour regarder 'Up' d'abord et je parie que vous verriez le comportement opposé.
La réponse la plus probable est que cela se passe en premier lieu dans le sud de son objectif. En allant de la manière opposée, ce n'est pas un choix, il optimise donc le sous-chemin morceau avec le résultat qui alternant les mouvements up / transparents sont considérés comme mieux.
Si vous voulez que ce soit le long de la diagonale, vous allez devoir identifier certains points d'intérêt le long du chemin (par exemple, la bouche du tunnel) et les prendre en compte dans votre heuristique. Alternativement, vous pouvez les prendre en compte dans votre algorithme en ré-calculant tout sous-chemin qui passe à travers un point d'intérêt.
De retour dans la journée, ils utilisaient une analyse statique pré-compilée des cartes et placées sur les marqueurs de fiches de parcours sur des points de fixation. En fonction de votre objectif final, cela pourrait être une bonne idée ici aussi.
Si vous êtes vraiment intéressé par l'apprentissage de ce qui se passe, je suggérerais de rendant les étapes de la recherche A *. Compte tenu de votre question, cela pourrait être très utile pour vous.
Merci Mike, j'adore vraiment la pile et visualisez les personnes qui posent des réponses, alors j'aurais read à quand j'ai vu la note modifiée. Merci :) Je ne suis pas sûr de comprendre complètement ce que vous voulez dire, mais je pense que je vois ce que vous dites. Comme il s'agit d'un jeu de SIM, et éventuellement tout peut changer, je ne pense pas pouvoir utiliser des marqueurs. Je comprends seulement comment cela fonctionne et se souvient d'un site Web qui montre la progression de A *, que je vais regarder. Je pourrais la mettre en œuvre dans mon jeu, même si je pense que cela peut être un peu trop pour moi à mon niveau. J'ai changé l'heuristique du Manhattan, et ça alla les deux fois.
La raison pour laquelle on est effectivement assez simple: le chemin essaiera toujours d'avoir la heuristique la plus basse possible car elle recherche de manière gourmande. Se rapprocher de l'objectif est un chemin optimal.
Si vous avez autorisé le mouvement diagonal, cela ne se produirait pas.
Vous savez que cela aurait un sens. Je ne prévois pas d'autoriser le mouvement diagonal car cela soulève des problèmes avec les coins des pièces. Ce n'est que le 2e jeu ive fabriqué à Java, le premier étant une faible interprétation du jeu d'hélicoptère classique ... Alors, apprenez, apprendre comme je vais, essayez de le garder assez simple. J'attends que je vais l'ouvrir et permettre aux autres développeurs de choisir une fois que j'ai quelque chose de bien établi.
Dans chaque cas, il préfère le chemin qui le prend plus près de son noeud d'objectif plus tôt, c'est ce que A * est conçu pour.
Si vous recherchez une solution simple-ish, puis-je suggérer un peu de randomisation?
Qu'est-ce que je veux dire, c'est ceci: Dans l'exemple de code CKKeantCode, il y a les boucles imbriquées qui génèrent le " successeur déclare "(à utiliser le terme AI). Je me réfère au point où il boucle sur le carré 3x3 autour de l'état "actuel", ajoutant de nouveaux emplacements sur la pile à prendre en compte.
Un correctif relativement simple (devrait :)) être isoler ce code A Bit, et dites-le, par exemple, a généré une liste litigieuse des nœuds avant le reste de l'étape de traitement. Ensuite, des conteneurs.shauffe (ou est-ce Generics.shauffe?) Cette liste liée et continuez le traitement là-bas. Fondamentalement, dites une routine, "Crétenaiveneighbors (noeud)" qui retourne un linkedlist = {(nœud.x-1, nœud.y), (node.x, nœud.y-1) ...} (veuillez pardonner le pidgin Java, j'essaie (et à toujours échouer) à être bref.
Une fois que vous avez construit la liste liée, vous devez simplement être capable de faire un "pour (node n: myNewLinkedlist)" au lieu de la et utilisez toujours le même code corporel! Qu'est-ce que cela ferait, idéalement, est une sorte de "secouer" l'ordre des nœuds considérés et créer des chemins plus proches de la diagonale, mais sans Devoir changer de heuristique. Les chemins seront toujours les plus efficaces, mais généralement plus près de la diagonale. L'inconvénient est, bien sûr, si vous allez de A à B Plusieurs fois, un chemin différent peut être pris. Si cela n'est pas innacceptable, vous devrez peut-être envisager une modification plus drastique. J'espère que cela vous aide!
-Agor
Wow, merci Agor. Bien que cela puisse ne pas être choisi comme "la réponse" pour ma question exacte, c'est la réponse à mon commentaire de la promenadehumanhumanistic, que j'ai fait avant de voir cela. Je ne peux pas dire que je comprends tout ce que vous avez dit, mais je reçois l'idée générale de cela. Je vais certainement regarder cela. Si vous souhaitez rejoindre mon équipe sur ce jeu (équipe, y compris de moi ...) et de la mettre en œuvre, je serais heureux de le donner!
Pas de problème, heureux d'aider. Je suis flatté à propos de l'invitation, mais je suis toujours étudiant (et travaille pendant l'été), je dois donc refuser. Bonne chance, cependant!
Je suis aussi un étudiant :) Bien que ne pas faire de maîtres, contrairement à vous-même. Ok sûr, pas de précipitation. Je cherche toujours un emploi!
Quelque chose d'autre à considérer est la pondération. Cela pourrait être aussi simple que de travailler le meilleur itinéraire en termes de coûts: marcher sur les coûts de gazon 2 alors que marcher sur les coûts de chemin 1, qui encourage la marche sur certains types de terrain, ou il pourrait être utilisé d'une autre façon de dire changer Direction des coûts 1 et des coûts en mouvement 1, pour encourager le mouvement en lignes droites. Au lieu de compter le nombre total de mouvements, vous comptez le «coût» total (qui est la même chose jusqu'à ce que vous introduisiez différents «coûts»)
Selon la mise en œuvre de votre Astar, vous verrez des résultats différents avec la même heuristique, autant de personnes ont mentionné. Ceci est dû à des liens, lorsque deux chemins ou plus, la façon dont vous commandez votre jeu ouvert déterminera la façon dont le chemin final sera l'air. Vous obtiendrez toujours la voie optimale si vous avez une heuristique admissible, mais les nœuds visités augmenteront avec le nombre de liens que vous avez (par rapport à une fabrication heuristique, pas autant de cravates).
Si vous ne pensez pas à visiter plus de nœuds, c'est un problème, je suggérerais d'utiliser la suggestion de randomisation (qui correspond à votre réponse acceptée actuelle). Si vous pensez à rechercher plus de nœuds, c'est un problème et souhaitez optimiser, je vous suggérerais d'utiliser une sorte de creusement. Il semble que vous utilisiez la distance de Manhattan, si vous utilisez une distance de l'euclidien lorsque deux nœuds attachent comme un creusement d'égalité, vous obtiendrez des chemins supplémentaires dans le but et vous visiterez moins de nœuds. Ceci est bien sûr, aucun piège ni bloc de mire de vue au but.
Pour éviter de visiter des nœuds avec des éléments de blocage dans la ligne de visée, je suggérerais de trouver une heuristique qui prend en compte ces éléments de blocage. Sincèrement une nouvelle heuristique ne devrait pas faire plus de travail qu'une recherche d'une étoile normale ferait.
Je suggérerais de regarder ma question car cela pourrait produire des idées et des solutions à ce problème.
D'accord, la vidéo est une excellente idée.
Yeh, ScreenJelly est génial pour des choses comme ça!
Pour quiconque se demande, ScraguneJelly vous permet d'enregistrer directement à partir de votre navigateur à l'aide d'un applet Web Java! puis relie avec votre compte Twitter pour ID. Astucieux!
Vous avez presque certainement lu ma réponse et je ne le lirai plus, alors je vais coller ma dernière modification ici, car je pense que c'est probablement le moyen le plus simple de vous aider à comprendre le comportement que vous voyez: Si vous vous voyez: Nous sommes vraiment intéressés par l'apprentissage de ce qui se passe, je suggérerais de raincre les étapes de la recherche A *. Compte tenu de votre question, cela pourrait être très utile pour vous.
Un algorithme de recherche d'un chemin d'inondation serait encore plus rapide qu'un * dans ce cas. Il n'aurait besoin que de O (k * n).
Re Mike, malade de votre réponse. REG, ça peut bien faire, mais je ne comprends que simplement comment un * fonctionne et j'ai utilisé un exemple déjà de travail qui contenait une interface de type API de base. Je vais m'en tenir à un * pour l'instant, car l'utilisation du processeur n'est pas un problème. Si finalement, je trouve que cela prend trop de choses, je serai sûr de regarder. Merci
duplicablé possible de Comment puis-je Trouvez la route directe la plus «naturellement» à l'aide d'A-Star (A *)
Le lien est soit spam, soit cassé.