2d topfindflex pathfinding libGDX

Question

J'essaye de faire un pote ai qui suit le joueur (que vous contrôlez) autour et au moment où cela fonctionne mais quand j'ajoute la détection de collision ça ne marche pas très bien quand le mon pote heurte un obstacle. Je me demandais juste quelle serait la meilleure approche (comme peut-être une implémentation de l'algorithme a *) pour rendre le mouvement de l'IA plus fluide et éviter ainsi les obstacles? Voici la méthode de mise à jour actuellement pour ma classe d'amis:

public void update() { 

    setBounds(getX(), getY(), getWidth(), getHeight()); 

    float xDiff = Math.abs(player.getX() - getX()); 
    float yDiff = Math.abs(player.getY() - getY()); 

    if (player.getX() > getX() && xDiff > buddyDistance) { 
     setX(getX()+speed); 
    } 
    else if (player.getX() < getX() && xDiff > buddyDistance) { 
     setX(getX()-speed); 
    } 

    if (player.getY() > getY() && yDiff > buddyDistance) { 
     setY(getY()+speed); 
    } 
    else if (player.getY() < getY() && yDiff > buddyDistance) { 
     setY(getY()-speed); 
    } 

} 

Answer 1

Une solution qui est facile à mettre en œuvre et pourrait fonctionner en fonction de votre type d'obstacles est l'utilisation de champs potentiels. L'idée est simple: le joueur se comporte comme un aimant qui attire le copain vers lui. Dans le même temps, les obstacles repoussent le copain pour que le copain les évite. Je vais utiliser des vecteurs pour l'expliquer d'abord, au lieu de Java, pour une meilleure lisibilité. Disons, b est la position du copain et p les positions du joueur et o_1, ... o_k sont les positions de vos obstacles.

Chacun des b, p, o_1, ..., o_k sont des vecteurs bidimensionnels avec les coordonnées x et y.

Ensuite, le vecteur (p-b) est le vecteur qui pointe du buddy au joueur. Ce dont nous avons également besoin est le vecteur (b-o_i) qui pointe de l'obstacle i au pote. De plus, au lieu d'utiliser directement les vecteurs (p-b), (b-o_i), nous les normalisons d'abord.

Ensuite, normalized(p-b) est déjà tout ce dont nous avons besoin pour attirer l'attention du joueur. Pour repousser le copain des obstacles, nous aimerions que la répulsion soit forte si le copain est proche de lui et petite (voire nulle) si le copain est loin de lui. Par conséquent, un choix évident serait de mettre à l'échelle la direction que nous voulons, c'est-à-dire normalized(b-o_i), avec 1/|b-o_i|, où |. | dénote la norme d'un vecteur.

Maintenant, nous pouvons simplement mélanger toutes ces « forces magnétiques » avec:

w = normalized(p-b) + normalized(b-o_1)/|b-o_1| + ... + normalized(b-o_l)/|b-o_k| 

Ce vecteur w les points généralement vers le joueur, mais chaque fois que le copain est proche des obstacles, il sera repoussé d'eux, ce qui est exactement ce que vous voulez. Mais comment pouvons-nous nous assurer que le copain se déplace à la bonne vitesse? C'est facile. Nous normalisons w, puis redimensionnons en fonction de la vitesse. Autrement dit, notre vecteur final de vitesse est v = speed*w/|w|

Cela peut facilement être ajouté dans votre code:

public void update() { 

    setBounds(getX(), getY(), getWidth(), getHeight()); //I kept this from your code, but I don't actually know what it does 

    float dx = player.getX() - getX(); //note: I removed abs 
    float dy = player.getY() - getY(); 

    float norm = Math.sqrt(dx*dx + dy*dy); 

    //normalization: 
    float wx = dx/norm; 
    float wy = dy/norm; 

    for (obstacle o : obstacles) { //assuming obstacles is an iterable datastructure containing instances of the class obstacle 
     //note, it suffices to iterate over close by obstacles 
     dx = getX() - o.getX(); 
     dy = getY() - o.getY(); 

     norm = Math.sqrt(dx*dx + dy*dy); 

     //normalization: 
     float ox = dx/norm; 
     float oy = dy/norm; 

     //add scaling to get the repulsion force we want 
     wx += ox/norm; 
     wy += oy/norm; 
    } 

    float norm_of_w = Math.sqrt(wx*wx + wy*wy); 
    float vx = speed * wx/norm_of_w; 
    float vy = speed * wy/norm_of_w; 

    setX(getX() + vx); 
    setY(getY() + vy); 
} 

Malheureusement, il y a plusieurs choses à considérer:

• Différents types de répulsion peuvent travailler mieux que 1/| b-o_i |, par exemple 1/| b-o_i |^2.
• Il peut être utile de jouer avec les forces, par exemple essayer c*(b-o_i)/|b-o_i| pour différentes valeurs de c (c'est-à-dire ox = c*dx/norm; et ainsi de suite). Si c est trop petit, alors le pote va se déplacer dans des obstacles dans une certaine mesure, si c est très grand, il les évitera déjà quand ils sont loin d'eux. L'utilisation de valeurs différentes de c pour différentes tailles d'obstacles peut également donner un meilleur résultat.
• L'évitement des obstacles fonctionne mieux si les obstacles sont de forme circulaire et qu'il y a suffisamment d'espace entre deux obstacles. Sinon, le copain pourrait être coincé dans un optima local et le joueur devra le «sauver» en se déplaçant vers un endroit qui éloignera le copain de l'optimum local.
• Si les obstacles ne sont pas symétriques et circulaires mais de grands polygones, vous pouvez essayer une très grande force de répulsion qui couvre la plus grande partie du polygone (c'est-à-dire un très grand c pour ce type d'obstacle). L'avantage est que le copain peut éviter l'obstacle mais malheureusement, si vous voulez qu'il se rapproche, il refusera simplement en raison de la forte répulsion.
• Il est important de garder à l'esprit que 1/|b-o_i| est grand si le contact et l'obstacle sont proches. S'ils sont à la même position, votre programme essaiera de diviser par zéro. Vous pourriez vouloir vérifier pour ce cas et l'éviter.

---

C'est, mais il pourrait être intéressant de noter que généralement avec des champs potentiels, l'idée est d'utiliser une charge négative pour l'objectif et la charge positive pour les obstacles, à savoir

w = -|p-b| + 1/|b-o_1| + ... + 1/|b-o_k| 

Notez que ici, w est seulement un scalaire et non un vecteur. Ensuite, la descente de gradient est appliquée pour se rapprocher du but. Cela signifie que le gradient de w par rapport à b.x, b.y est calculé. Ce gradient pointe alors vers la direction pour atteindre le joueur tout en évitant les obstacles. C'est une meilleure approche que ce que je vous ai proposé, mais nécessite plus de connaissances en mathématiques. N'hésitez pas à essayer ou demander si c'est ce que vous voulez.

---

plus probable, la meilleure réponse si les obstacles ont une forme arbitraire et minima locaux ne sont pas acceptables pour vous est d'utiliser un combiné avec Delaunay Triangulation l'algorithme Entonnoir. Vous pouvez en savoir plus sur est en https://www.aaai.org/Papers/AAAI/2006/AAAI06-148.pdf

Mais je suppose que vous préférez quelque chose qui est facile à mettre en œuvre.