Pathfinding A-star sur bitmap
Par -Alexandre LEGOUT aka LAlex- le jeudi, février 21 2008, 20:02 - AS3 / Flex2 - Lien permanent
L'algorithme A* (A-star) connait de nombreuses implémentations. La plupart utilisent une grille (tableau à deux dimensions) en tant que carte. Etant à la base des jeux "tile-based", celles-ci suffisent la plupart du temps à la grande majorité des jeux. Seulement cela impose un certain nombre de contraintes, notamment en terme de dimensions des "obstacles", mais aussi en terme de performances: l'algorythme se basant sur des noeux (nodes), une grille de 40/40 offre 1600 cases (maximum, l'A* n'étant pas exhaustif), ce qui est déjà bien important...
J'ai voulu essayer de me baser plutôt sur un bitmap, simple (pour l'instant), une couleur étant celle du sol, l'autre celle des obstacles :
En gros, l'appel de méthode utilisé ici est
var bmp:BitmapData = new BitmapData(400, 400);
// Génération d'un bitmap aléatoire: fillRect aléatoires, etc...
var finder:BitmapAStar = new BitmapAStar;
var path: /*Point*/ Array = finder.findPath(bmp, new Point(5, 5), new Point(395, 395));
L'A* n'a évidemment pas été le plus compliqué à mettre en oeuvre, mais c'est bien l'analyse et le découpage de ce bitmap qui ont été difficiles à mettre en place. Beaucoup de choses restent à faire malgré cette démo fonctionnelle, notamment l'optimisation du placement des "portes" (ronds blancs sur l'affichage "debug"), et des trajectoires (je pense notamment faire un lissage du chemin à parcourir). D'autres fonctionnalités peuvent être envisagées, comme la gestion des altitudes (terrain en pente, ou les falaises qui seraient des portes à sens unique - qu'on peut sauter mais pas grimper) ou des types de terrain (un malus associé à chaque couleur par exemple).
Dans le plus ardu, on peut aussi imaginer un découpage des formes non rectangulaires (polygones ou courbes).
Une fois cleanées (l'API notamment) et optimisées, je mettrai les sources à
disposition sur ce blog... 
Commentaires
Salut,
cette technique à l'air pas mal du tout, je dirai même que ça défonce
j'attends les sources avec impatience !
Terrible !!!
Ca me donne plein d'idées.
salut,
Ayant déjà dit tout le bien que j'en pense, je me permets de te dire que ce script n'a aucun avenir. le temps de calcul calamiteux et les résultats approximatifs relèvent de l'essai bâclé, voire de la pure supercherie.
malgré un bel effort au niveau graphique (quasiment du Malévitch), je ne vous salue pas monsieur.
...
..
bon, ça tue et ça pourrait changer l'avenir du game design surtout couplé à une couche haptique pour simuler les qualités de terrain. avec les perfs qui vont bien et le lissage des trajets, ça devrait envoyer du mouflon.
beau boulot et vivement la release
Super Taf lalex !
Salut Lalex,
impressionnant... vraiment...
Tout comme les liquidComponent tu pars d'un bitmap et il est vrai que cela donne de nb idées, cette technique deviens de plus en plus utilisée...
bonne continuation
Salut,
Je trouve cela impressionnant, mais en générant des tonnes de cas je n'en ai jamais vu de cas impossible ( sortie inaccessible ) ou de cas ou le chemin devait revenir vers le point départ pour éviter un obstacle (j'aimerais bien voir un trajet en forme de "Z" ).
Serait-ce des cas qui ne marche pas (pas géré par ton code) ? Ou serait-ce le générateur qui n'affiche volontairement pas ce genre de cas ?
En tout cas je suis intéressé par ton travail et je suis impatient d'en voir la suite ^^
Du bon boulot
Fil des commentaires de ce billet