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

[Argorate]

Ok, on se comprends pas à cause de la terminologie (comme souvent). ^^

Il y a effectivement deux choses à distinguer : le poids des cases, c'est à dire le "coût" pour marcher sur tel case/terrain ; On peut donc dire qu'on a une bitmap qui contient le poids de toute les cases (pour simplifier, moi elles sont tous à 1).
Puis y a le "coût", l'autre coût, celui que calcule l'algo, toi tu parles d’heuristiquement si j'ai bien suivit, qui est en fait le coût cumulé depuis le point de départ des différents coût de case pour parvenir sur celle-ci. Bien sur, a chaque qu'on a plusieurs cases/noeux pour arriver sur une même case, on garde que le coût le plus faible...

Quand je disais mettre à 1 partout autour, c'était du coût cumulé, celui calculé dont je parlais, en gros ça revient à prendre chaque case du contour de la zone de départ et lancer l'algo dessus, il va mettre 1 partout autour, mais c'était pour gagner du temps.

[Xenos]

Non, tu es en train d'inverser les deux pondérations (enfin, dans ta formulation, c'est ce que je lis).

Ton poids (on va l'appeler "coût de déplacement") de 1 est posé sur les edges de ton graph (pour aller d'une case à sa voisine, tu fais 1 pas), et non sur les noeuds du graph (les cases elles-mêmes). Le poids (on va l'appeler "heuristique") qui est sur les cases elle-même, c'est la distance minimale à la zone d'arrivée (ou, plus généralement, une valeur inférieure à la somme des couts de déplacement depuis la case en question jusqu'à l'arrivée). C'est cette heuristique qui permet à l'A* de savoir quel noeud (quelle case) il doit utiliser pour poursuivre son cheminement. En revanche, le coût de déplacement (le poids du edge), c'est la valeur que l'A* rajoute au chemin ainsi généré pour savoir quel est le coût réel du chemin.

Si ta fonction heuristique est une constante de "1", alors A* est inefficace, car il va piocher les noeuds complètement au pif. En revanche, ton coût de déplacement, lui, peut-être une constante de 1. Pour que ton A* soit efficace, il faut que ta fonction heuristique soit "bien choisie".

Je ne vois pas l'intérêt de prendre chaque case du contour de ta zone: c'est inefficace, car le nombre de cases sera plus grand que le nombre de cases du contour intérieur de ta zone de départ, et tu n'auras pas la réponse à ta question car tu ne sauras pas passer de ta zone de départ à la case de contour. La méthode brutale, c'est de lancer ton implé sur chaque case du contour intérieur de la zone de départ, et de laisser l'algo se démerder pour rejoindre la zone d'arrivée. Dans ta zone d'arrivée, toutes les cases ont une heuristique de 0, et tous les couts de déplacement sont à 0. Tu peux alors choisir n'importe quelle cas de ta zone d'arrivée en guise de cible (et dans le résultat de l'A*, tu retireras juste les cases qui sont dans cette zone d'arrivée, sauf la 1ere case, qui est celle sur laquelle ton chemin arrive réellement). Et pour ta zone de départ, tes heuristiques sont inchangées (distance eulérienne à la zone d'arrivée) et seuls les couts de déplacement sont à zéro. Tu n'auras alors plus qu'à retirer les premiers points du chemin qui sont dans la zone de départ (ie: virer tous les points avant le dernier points de la zone de départ, car l'A* pourrait sortir de la zone de départ et y ré-entrer ensuite, suivant la forme de cette zone; idem pour l'arrivée, tu vires tous les points après le premier dans la zone d'arrivée).
Et tu réitères le principe pour chaque case de la zone de depart qui n'a jamais été traversée par un chemin précédent. D'une itération à l'autre, tu peux changer ton heuristique, car tu sais la distance réelle entre les cases des chemins déjà calculées et la zone d'arrivée (donc, tu utilises cette valeur en guise d'heuristique). Voire, si tu peux altérer les heuristiques pendant l'exécution de l'A* (mais j'en doute vu la signature de l'implé proposée), tu peux basculer les heuristiques des points des chemins déjà trouvés à 0 dès que l'A* a croisé un de ces chemins déjà calculés (l'A* va alors filer directement le long de ce chemin déjà calculé jusqu'à la zone d'arrivée).

[Argorate]

on dit la meme chose, y a plus qu'à

[niahoo]

Le poids de déplacement peut être associé aux cases et non aux edges. C'est d'ailleurs le cas le plus souvent, avec des cases "marais" ou "désert" que l'on traverse moins vite, quelle que soit la case de provenance.

[Xenos]

Tu prends le risques de ramer en faisant ça (pour moi). Par exemple, si ta case de marais est ta case de départ ou d'arrivée, tu vas rater un des coûts. Et je trouve compliqué, point de vue raisonnement, de se dire "je pose le coût de déplacement sur ma case", qui est une notion statique, plutôt que "je pose le coût de déplacement sur mon edge orienté".

Et si le graph est orienté, alors tu ne peux plus le faire du tout (comme dit, t'es obligé de ne faire des coûts qui "ne dépendant pas de la case de provenance" pour toute la grille). Après, si tu veux mettre les coûts sur les cases, je pense que le mieux est de faire une pré-passe qui convertir ce coût de la case vers les edges. Ca te permet de monter facilement ta grille de coût (de sortir une image raster des coputs des cases par exemple) sans pour autant restreindre l'algo et risquer de mixer coût de déplacement et heuristique.

[niahoo]

Alors en vrac: on s'en fout des couts des cases d'arrivée et de départ car ils sont obligatoires. Tu trouves honnêtement plus compliqué de dire "le marais c'est -50% de vitesse dessus" plutôt que d'utiliser un graphe orienté et de dire "si tu entres dans un marais depuis une forêt c'est -50% de vitesse" ? Si le graph est orienté tu peux quand même le faire, ce sont deux notions indépendantes, comme tu dis, pour toute la grille. Et encore, tu peux additionner différents coûts.

Il n'y a pas de "risque" de mixer les couts ... à moins d'être un gros manche et d'utiliser le même nom de variable ou ce genre de trucs ... Ou de ne pas avoir compris l'algo.

Ensuite tu fais comme tu veux, perso je n'utilise pas A*. Je dis juste que les implémentations à base de cases que j'ai vues ne se compliquent pas plus que ça généralement.

[Ter Rowan]

Hello, à mon sens, si on ne gère pas des routes (mais des vraies routes) ça peut être utile de travailler les poids sur les edges.

par contre si on n'a pas de route ou des fausses, ca simplifie la vie de dire arriver sur une case = conso. sur le long terme ça lisse. exemple ultra simplifié :
- je viens d'une case forêt vers une case marais puis de la case marais vers une case marais puis vers une case forêt

cas edge :

forêt -> marais = 1.5 coût
marais -> marais = 2 coûts
marais -> forêt = 1.5 cout

soit au total 5

maintenant si on raisonne en case (marais = 2, forêt =1)

forêt -> marais = 2 coûts
marais -> marais = 2 coûts
marais -> forêt = 1 coût

soit au total 5. Alors ok faut avoir plus de réserve dans ce cas pour quitter la forêt que dans le edge, mais c'est quedalle en terme de gameplay



ce que j'appelle une vraie route :
les cases sont des terrains en aucun cas des routes
les routes sont en plus des cases. Elles comportent l'avantage d'aller plus vite / d'être plus sécurisée (plus de monde, moins d'accident type la branche qui tombe, la racine qui fait péter l'essieu...) l'inconvénient on ne va pas partout mais là où elle mène / plus facile d'être retrouvé ou pris dans une embuscade (pas facile de trouver quelqu'un en pleine forêt, plus facile sur la route qui traverse la forêt) etc...

dans ce cas on est sur une complexité bien plus grande et qui nécessite des calculs complexes. Si on veut du simple; pourquoi s'embêter à manipuler des notions complexes équivalentes à des notions simples ?

[Xenos]

On fait comme on veut, je disais juste que je trouvais bien plus simple à comprendre (y compris à long terme) de se dire "je me déplace entre deux points selon une route, donc la longueur de mon déplacement, ben c'est la longueur de la route" plutôt que "le poids de chaque case c'est le coût de déplacement quand on arrive dessus" (l'autre dev qui passe après, ou toi dans 6 mois, va te demander "c'est le poids pour quitter la case? ou pour arriver dessus?").

[Argorate]

Ensuite tu fais comme tu veux, perso je n'utilise pas A*. Je dis juste que les implémentations à base de cases que j'ai vues ne se compliquent pas plus que ça généralement.

Tu utilises quoi, comment, pourquoi? (par curiosité )

[niahoo]

Ben je ne fais pas de pathfinding sur aucun de mes projets actuellement, tout simplement

J'avais réalisé un outil pour Eve Online, j'utilisais A* pour calculer le déplacement dans le système solaire. Là, typiquement, le temps de warp entre les gates entrait en compte donc j'utilisais le coût de déplacement lié à une "case" (un système solaire), dépendant de la "case" d'arrivée ET de celle de sortie : le temps de warp pour traverser le système d'une gate à une autre. (chaque système connecté ayant sa propre gate).

C'est très important parce que dans un système A, connecté à B, C et D, tu as les gates vers B et C juste à côté, mais D est à l'autre bout. Donc pour faire B -> A -> C c'est super rapide, par contre B -> A -> D est très long.

Fin bon, tout ça pour dire que ça dépend vraiment du gameplay et qu'il faut pas se compliquer la life. Surtout que si les données sont calculables, on peut toujours complexifier l'algo à tout moment.