Pathfinding vers une zone (ensemble de coordonnées) et non pas juste une coordonnée?

[Argorate]

Imaginons la map suivante :



considérant le repère suivant :



en partant d'un exemple où notre personnage est en 0,0.


Je souhaite savoir quel algorithme utiliser pour aller sur la case adjacente la plus proche du bâtiment.

Il semble que faire un A* sur l'ensemble des coordonnées que représente le bâtiment [ (1;2), (8,2), (1,10), (8, 10) ] semble pas très optimisé...

Comment faire pour trouver le chemin le plus court entre un point et un ensemble de point?
Et à y être, peut on abstraire le tout et permettre également d'avoir une area en "point" de départ, comme ça toute les combinaisons sont couvertes.

dans l'exemple, l'algo devrait retourner un array de solutions : [ (0,2), (1,1) ]

[Xenos]

Salut,

tu fais simplement la même que ton A*, sauf que tu définis le poids des noeuds par rapport à la distance à la zone (ou, par approximation, la distance à son barycentre) et tu arrêtes ton A* dès que tu as trouvé un point dans la zone d'arrivée (au lieu du point ciblé spécifique).

Note que faire un A* sur chaque coordonnées peut très bien marcher, la problématique de performances ne se pose qu'à moitié. Ok, si ton bâtiment fais 10K cases, y'a sûrement plus rapide, mais tant que tu n'as pas fait simplement l'essai de perf, ce problème est probablement négligeable: un A* en JS fait par le client et simplement vérifié par le serveur [ie: le serveur regarde juste que le chemin est valide, et s'en fiche de savoir si c'était le plus court] a une durée hyper-négligeable pour des cartes de jeux comme cela. Donc x10, (parce que ta zone fait 10 cases) bof, ça ne changera rien.

[edit: histoire de m'appuyer sur qqc, https://briangrinstead.com/blog/astar-se...t-updated/ annonce 5-10ms/A* pour une grille 100x100, donc bon, même x10, tu restes raisonnable]

[Argorate]

Oui c'est déjà ce que je fais A* JS + verif serveur du path uniquement. Mais j'aime bien l'algorithmie, savoir ce qui est optimal.
Donc en gros faut que je bidouille mon A* et que je géré le cas d'une grille, je vais remplacer les arguments pour que ça accepte des "grilles" en départ et en arrivé.
Pour le départ en grille, c'est assez simple, il suffit par simple soustraction de savoir quel case de mon personnage (multi-case) est la plus proche du point / grille ciblé.

(j'avais déjà bidouillé pour prendre en compte ma spécificité qui est qu'une case à 0 ou 1 pour savoir si c'est walkable, mais il y a aussi 4 autre boolean pour simuler les murs des 4 points cardinaux.)

Sinon pour le barycentre c'est une bonne idée, mais il faut s’arrêter avant (collision).

[Xenos]

Pour l'arrivée, je ne comprends pas ton soucis: ton A* n'a qu'à stopper quand il atteint l'une des cases (l'un des noeuds) de la grille cible et bast?! A la limite, la seule "difficulté" serait le calcul du poids de chaque noeud, mais bon, la distance eulérienne au point de destination (dans un A* "classique") ou la distance eulérienne à la grille cible, c'est kiff kiff (quitte à faire bêtement le minimum des distances à chaque case)...

Pour le départ, ton A* est symétrique, donc il suffit de partir du point d'arrivée et t'es dans le même cas que précédemment.

Pour le cas d'un zone à zone, je pense que tu peux partir d'un point au pif de la zone de départ, aller à l'arrivée, puis de ce point d'arrivée, tu repars vers la zone de départ. Ca devrait donner un résultat pas trop mal. Eventuellement, à faire converger?!

[Argorate]

Z à Z : Le hasard dans un algo est tjs la marque d'un manque de réflexion, il ne faut rien faire au hasard, en l’occurrence, on peut déjà bannir toutes les cases du milieu de la grille de départ et en prendre une sur les bords.
Et le mieux est même sans doute de mettre à 1 le poids de chaque case qui entoure la grille et lancer l'algo dans cet état, ça me semble mieux non? et ça évite de faire l'aller retour si tu pondères normalement?

P à Z : Mon "problème", c'est que A* prend comme param

Code :

function Astar(x0,y0 , x1,y1)

, donc quand tu me dis qu'il "suffit" quand tu atteignes l'une des cases de la grille cible, oui, mais l'algo ne les connaît pas ; tu lui passe qu'une coordonné à atteindre, d'où ma conclusion de devoir bidouiller l'algo d'origine pour gérer les paramètres d'entrées de type "grille". (mais sinon on est d'accord)

[Xenos]

Sur un A* aux points positifs, oui, tu peu éviter le centre. En revanche, non, le hasard n'est pas nécessairement le reflet d'un "mauvais algo", dans certains cas, les méthodes type Monte-Carlo sont parfaitement efficace (car le calcul exhaustif, justement, est trop lourd). Dans le cas présent, ce "tirage au hasard" peut de toute façon se remplacer par "partir de la case au points [distance eulérienne à la cible par exemple] le plus faible". De toute façon, tant que tu restes dans la zone de départ, tu n'enregistre pas les cases par lesquelles tu passes.
Je ne vois pas l'intérêt de toucher au poids des cases adjacente à ta zone de départ?!

Tu utilises une implémentation de l'A* qui est construite sur ce modèle Point-Point. L'algo A* en lui-même est plus vaste que cette implé. Si tu veux utiliser quand même cette implé sans mettre le nez dedans (perso, je pense qu'alors tu devrais regarder directement dans les SDK, parce qu'ils te fournissent ce qu'il faut pour aller d'un point à l'autre et ils se démerdent pour piocher le bon algo, cf Neoaxis qui l'a implémenté il y a quelques années et probablement Unity), alors le problème devient totalement différent. Tu ne veux pas "comment faire un A* d'un point à une zone? D'une zone à un point? D'une zone à une zone?" mais "en utilisant un algo A* Point-Point, comment puis-je faire un A* Zone-Point, Point-Zone, et Zone-Zone? (sans traiter chaque pair de points)".

Dans ce cas, le plus simple, c'est justement de piocher 2 cases au hasard des zones de départ et d'arrivée, de lancer l'implé de ton algo, de supprimer tous les points dans la zone de départ (sauf 1) par lesquels le chemin est passé et de supprimer tous les points dans la zone d'arrivée (sauf 1) de la liste de points que l'implé t'as retournée, et de réitérer l'opération pour toutes les cases de la zone de départ (sauf celles que t'as déjà traité, et celles que t'as déjà retirées).
Tu peux sinon te fixer un nombre d'itérations, et le faire de manière probabiliste (après N essais, tu pioche le meilleur résultat). Ce "hasard" pouvant également être orienté (de même que le caractère exhaustif précédent a été orienté en ignorant le cases déjà traitées).

Edit:
Autre possibilité, tu pars du points de poids de plus faible dans ta zone de départ (ie: distance eulérienne à ta zone d'arrivée), t'obtiens un chemin A-B
Ensuite, tu modifies les poids de tous les noeuds de ta grille (ou ta fonction de calcul de poids) pour qu'elle ne considère non plus la distance à la zone d'arrivée, mais le minimum entre la distance à la zone d'arrivée, et (la distance à chaque chemin déjà trouvé + la distance le long de ce chemin) jusqu'à la zone d'arrivée. Et tu réitère avec chaque point de ta zone de départ (et avec B comme destination). Bon, à mon avis, c'est pas franchement plus simple (ni performant?) que juste lancer l'algo entre chaque point de la zone de départ et n'importe quel point de la zone d'arrivée (en évitant de faire plusieurs fois les mêmes points dans la zone de départ, et en le gardant que le chemin le plus court trouvé).

Code :

Tant qu'il existe un point P non-traité de la zone de départ
  Lancer ton A* entre P et un point quelconque de la zone d'arrivée (le plus proche de ta zone de départ par exemple)
  Considérer tous les points du chemin C trouvé qui sont dans la zone de départ comme "traité"
Recommencer
Retirer de chaque chemin de C tous les points de la zone d'arrivée, sauf 1 (le premier sur lequel le chemin C a tapé)
Garder le chemin de longueur minimale parmi tous les chemins trouvés

[Argorate]

l’intérêt de mettre à 1 toutes les cases autour de la zone de départ, et d'itérer sur chacune et de trouver le plus court chemin en les considérant tous.

je vais mettre le nez dedans comme je l'ai déjà fait, faut que je vois un peu comment il a été implémenter vu que ce n'est pas le mien de base, et j'adapterai pour gérer la grille d'arriver. c'est le plus simple et sans doute le plus performant.


PS : oui il y a des exceptions pour le hasard, mais 99% du temps un random dans un algo c'est louche, c'est l'absence de stratégie pour résoudre le problème, qui, s'il existe une stratégie, sera donc un algo moins performant.

[Xenos]

Je ne vois toujours pas l'utilité de mettre à 1 (que mettre "à 1" d'ailleurs?!) les cases du pourtour de ta zone de départ. Ce qui compte dans l'A*, c'est ta fonction de calcul des poids de chaque noeud (souvent, une simple distance eulérienne). C'est là-dessus qu'il faut travailler si tu veux faire de l'A* de zone. Ce "1234" que tu montres dans tes images, c'est juste le poids du chemin, pas ta fonction heuristique. C'est celle-là qu'il faudra complexifier pour prendre en compte la distance à la zone et les éventuels chemins déjà traités.

Tu recours aux méthodes statistiques simplement quand tu cherches une solution probabiliste, c'est pas forcément un truc louche ou mauvais. D'ailleurs, ta notion de "performance" est fausse: la méthode statistique est justement utilisée pour trouver rapidement une réponse acceptable, au lieu de passer une infinité de temps à chercher une "réponse parfaite" (pas toujours existante d'ailleurs). C'est bien plus performant de faire de la statistique dans certains cas, mais moins précis.

Edit: D'ailleurs, certains algo qu'on peut voir comme "non-probabilistes" le sont en fait. Supposons un algo visant à savoir si une chaine String contient une lettre (disons "X"), alors l'algo qui prend chaque lettre une à une (du début à la fin) et fait le check est le même que l'algo qui prendrait une lettre au pif de la chaine (mais jamais deux fois la même) et ferait le test. Dans certains cas, le 1er trouvera avant le 2nd (pour la chaine "X est plus grand que Y" par exemple) et dans d'autres, le 2nd algo trouvera avant ou en même temps que le 1er (pour la chaîne "Y est plus petit que X").

[Argorate]

On reconnaît bien la le discours d'un probabiliste bref, on ne va pas débattre de ça, ça ne m'interesse pas en l'état.

Oui, c'est des poids des cases dont je parlais à mattre à "1".

C'est quoi la définition de la fonction heuristique du A* du coup? Pour moi c'était juste le parcours d'un graph avec la pondération des cases à chaque fois comme sur les images. je ne vois pas ce qu'il y a de plus?

[Xenos]

L'A* (pour moi, c'est peut-être une version généralisée), c'est un algorithme permettant de parcourir un graph de noeuds liés par des... "edges" (merde, je retrouve pas le terme français?!) orientés et pondérés, pour aller d'un noeud à un autre en passant par le chemin "le plus court" (dont la somme des edges est la minimale). Chaque noeud est doté d'un coefficient calculé par une fonction (dite "heuristique", de mémoire). Ce coefficient indique la distance minimale de chez minimale entre ce noeud et le point de destination (d'où le fait qu'on prenne souvent la distance eulérienne, surtout dans les cas pratiques de recherche de chemin en 2D).

A* est alors l'algorithme consistant à dire: "ayant une liste de chemins C à l'itération numéro i, et une liste de noeuds N liés à ces chemins C, je choisis le noeud de n de N de sorte que le chemin c+n soit le plus court possible".

La définition de la fonction heuristique du A* dépend du problème, mais c'est une fonction qui donne une valeur minimale du chemin entre un noeud N et la cible de l'algorithme (d'où la distance eulérienne). La "pondération" des cases peut correspondre à cela, mais il ne faut pas confondre ce coefficient avec le poids de chaque "edge", qui représente le vrai coût du déplacement. Dans ton cas donc, la fonction heuristique va devoir être revue pour prendre en compte la zone d'arrivée (et non juste le point d'arrivée, ie, distance eulérienne à ta zone d'arrivée et non plus à ton point d'arrivée) et éventuellement, les chemins précédemment trouvés (dans ma proposition précédente pour faire Zone-Zone). En revanche, le poids de chaque edge restera probablement de 1 (sauf si t'as des spécificités de terrain, genre un marais où le déplacement est ralenti, ou un mur, qui revient à n'avoir pas de edge entre les deux cases que représentent les noeuds du graph).

Du coup, "mettre à 1" le poids de tes cases n'a pas de sens, puisque cela reviendra à dire "la distance à ma zone d'arrivée depuis ces cases est... 1?!" Et le poids de chaque edge étant déjà de 1 quelque soit l'edge de ton graph...