06-09-2017, 04:35 PM
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).
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).