Base de pathfinding avec évitement d'obstacle continu d'un espace 2D

Je suis en train d'écrire une simulation dans lequel une créature objet doit être capable de se déplacer vers un autre objet arbitraire dans l'environnement, en glissant à travers les obstacles plutôt que de faire tout intelligent de pathfinding. Je ne suis pas d'essayer de l'avoir plan un chemin d'accès -- pour se déplacer dans une direction générale, et rebondir sur les obstacles.

C'est un environnement 2D (vue de dessus), et chaque objet a un rectangle de délimitation pour la détection de collision. Il n'y a pas de réseau, et je ne suis pas à la recherche d'Un* la solution.

Je n'ai pas été en mesure de trouver des tutoriels sur ce genre de "stupide" collision à base de pathfinding, donc je ne pourrais pas décrire ce en utilisant les termes les plus courants.

Des recommandations sur la façon de mettre en œuvre des ce (ou des liens vers des tutoriels)?

OriginalL'auteur kpozin | 2009-05-17

  1. 6

    Étendre sur ce que Guillaume a dit à propos de l'évitement d'obstacle, une technique qui fonctionne bien pour vous, c'est l'anti-gravité mouvement. Vous traitez les locaux des obstacles comme des sources de l'anti-gravité, la destination comme la gravité, et votre ordinateur contrôlé caractère de glissement (comme le savon!) les obstacles pour arriver à la destination.

    Sur le côté négatif, vous devez avoir un anti-champ de gravité qui est plus grande que l'objet à éviter, afin que vous commencez à tourner avant de véhicule est sur l'obstacle. Ainsi, vous pouvez avoir une configuration où vous obtenez une accélération qui va directement à l'encontre de l'une d'elles (deux à l'obstacle en face de vous, annuler l'accélération latérale, et overridding l'accélération de l'objectif) sur le côté de plus, ce serait bien travailler contre les obstacles en mouvement.
    Alors que les deux obstacles peuvent théoriquement s'annuler l'une l'autre, dans la pratique c'est rare et instable... juste un petit changement de position et vous obtenez tiré autour de l'obstacle. Si c'est un problème, vous pouvez contrer avec un bruit aléatoire.
    L'anti-gravité solution semble une bonne option dans mon cas. C'est très simple, et les calculs sont triviales. Je n'ai pas besoin de garanties que les agents vont atteindre des cibles sur la première tentative, donc c'est pas grave si ils sont bloqués par des obstacles (si application occasionnelle de l'aléatoire des forces supplémentaires pourraient permettre de résoudre ce problème).
    Je suis d'accord que sa instable et peu probable. J'ai juste dit parce que j'ai utilisé cette solution dans un cas où les joueurs pouvaient place "défenses" très précisément, et c'était un tricheur que notre test a montré. Je n'ai pas pensé à l'ajout de bruit aléatoire 🙁
    L'objet pourrait très facilement se retrouver coincé entre d'autres objets, tels que les deux murs adjacents. Il ne serait pas bien fonctionner pour naviguer dans un labyrinthe, se déplaçant autour de L en forme de bâtiments et autres obstacles. Il ne serait pas approprié à l'intérieur des bâtiments comme les AIs dans un FPS où ils auraient besoin de monter des escaliers. Il serait toutefois être adapté pour les grands espaces ouverts avec peu peuplées obstacles.

    OriginalL'auteur Paul

  2. 5

    vous pouvez combiner les deux algorithme de pilotage :

    chercher : vous appliquez un comité de pilotage de la force dans la direction qui est la différence entre la vitesse actuelle et la vitesse souhaitée en direction de la cible

    D'Évitement d'un Obstacle : vous anticipe le véhicule de l'avenir à l'aide d'une boîte dont la longueur est une constante de temps multiplié par la vitesse actuelle du véhicule. Tout obstacle qui croise cette case est les risques de collision. Le plus proche de cette menace est choisi pour l'évasion. Pour éviter un obstacle, une latérale de la direction de la force est appliquée en face de l'obstacle du centre. En outre, un freinage (décélération) force est appliquée. Ces forces varient avec l'urgence (la distance entre la pointe de la boîte au point de risque de collision). De direction varie de façon linéaire, de freinage varie quadratiquement.

    Vous pouvez en savoir plus sur le site "Directeur Des Comportements Autonomes Caractères"

    ce qui concerne

    Guillaume

    PS : cette supposent que vous utilisez un point d'/vitesse/accélération de la méthode pour le mouvement de l'objet.

    Cela aurait dû être la réponse. Au moins, c'est sur la base des concepts utilisés dans les jeux AAA. Plus de Craig Reynolds est génial

    OriginalL'auteur PATRY Guillaume

  3. 2

    Peut-être que vous pourriez utiliser Gage de l'algorithme de

    OriginalL'auteur Dario

  4. 1

    À chaque fois que votre créature, le voyage dans le vecteur direction v, entre en collision avec un mur, dont la direction est représentée par le vecteur w, la direction que vous avez besoin de "slide" est donnée par le vecteur qui est la projection de v sur w. Cela peut être trouvé à l'aide de

      v . w
--------- w
 |w|*|w|

    où . est le vecteur produit scalaire et |w| est la magnitude du vecteur w ( = sqrt(w . w)). Si w est un vecteur unitaire, cela devient tout simplement

    (v . w) w

    En utilisant le vecteur résultant que de votre créature de la vitesse moyenne de votre créature se déplace rapidement quand il suffit de "broute" le mur, et, lentement, quand il frappe le mur près de la mort. (C'est la façon dont la plupart à la première personne jeux de tir gérer des collisions pour le joueur humain.)

    Si au contraire vous souhaitez que votre créature, toujours à pleine vitesse, vous avez besoin seulement le signe de v . w -- vous serez toujours en voyageant dans la direction du mur de visages (w) ou la direction opposée (-w).

    Le problème que vous aurez est lorsque votre créature frappe le mur de la mort. Dans ce cas, vos prévisions de vecteur (0, 0), et vous avez besoin d'une autre technique pour décider de la voie (w ou -w). L'approche habituelle ici est Un*, même si cela peut être inutile si votre environnement dispose d'assez de structure.

    OriginalL'auteur j_random_hacker

  5. -1

    J'ai posté un algorithme de pathfinding en C# d'un moment de retour

    Voici le lien

    Vous pouvez essayer de l'utiliser comme un point de départ, c'est à dire, vous pouvez modifier la fonction qui vérifie la cellule d'à côté pour voir si elle est valide pour vérifier les obstacles, et vous pouvez vous nourrir de petits intervalles au lieu de départ et le point de fin, un peu comme de multiples mini-pahfinding routes.

    (Le texte est en espagnol, mais vous pouvez télécharger l'application à partir du lien en haut)

    pour citer le origial question: "je ne suis pas d'essayer de l'avoir de plan d'un chemin"
    Qui a été édité en après ma réponse
    Votre réponse est dans un autre château: quand est-ce une réponse pas de réponse?

    OriginalL'auteur juan