mais du coup je comprends pas bien, tu n'as aucun objet mobile à prendre en compte dans ton graphe en fait ? (i.e. c'est pas parce qu'il y a un autre monstre entre ton monstre et le joueur que tu vas devoir éviter de prendre ce chemin-là)
du coup tu peux subdiviser ton niveau en lignes droites, calculer la matrice des distances minimales entre toutes les extrêmités de lignes droites et hop, non ?