Hoshimi: Mapping avant pathfinding !
Premiere difficulté, construire un des élements clef de mon AI, c-a-d le pathfinding.
Tout naturellement, je me penche sur les solutions existantes et donc je démarre par les tutos proposés sur les forums de the Spoke et sur divers sites connexes au Project Hoshimi 2006.
Très vite on se rend compte d'une chose, l'algo star est A* (ne voillez aucun jeu de mots ...) pour le pathfinding rapide et efficace et pour trouver LE chemin le plus court c'est
Dijkstra.
Ok, je regarde rapidement les algos et leur implémentation de base....
Et fidele à moi même je décide de les oublier pour l'instant et de me
jeter corps et âme dans la recherche de mon propre "systeme" de
pathfinding pour Ray (Ha oui au fait j'ai baptisé mon AI "Ray"
... Allez savoir pourquoi ?!).
Résultats de mes méditations, il est 2h19 am et j'ai un concept alpha :
Il repose sur la maxime suivante (celle du titre également) : Mapping Before Pathfinding !
Quezaquo ? Il faut bien partir de quelque chose pour trouver un
chemin, et comme je l'ai dit je ne m'occupe pas de savoir comment
integrer A* ou autres à Ray.
Donc d'abord le mapping, c-a-d que l'on subdivise la map en cases et
que pour chaqu'une d'elle on test et on stock ses propriétés (Type de tissu =>
note en fonction de l'influence sur le déplacement) à l'issue de ces
test on a éliminé toutes les zones inacessibles et chaque case a
une "note".
On a donc une carte épuré de la map actuelle.
Maintenant le pathfinding, si vous avez bien suivi on a obtenu une
carte contenant uniquement des "cases naviguables" et qui sont
adjacentes.
Par conséquent, quelque soit deux points A et B théoriquement reliable
par un chemin, leurs coordonnés sont présentes dans notre carte et pour
aller de A vers B on se déplace de case adjacente en case adjacente.
Voila où j'en suis ! Il me reste donc à réfléchir sur le moyen de
trouver un chemin en utilisant ma carte et plus tard de trouver un
moyen d'avoir le plus court chemin a 80% ou plus ;-] (ça me parait
correct).
Dr. JiBz On The Spoke.