Dv. dapplication interactive III Recherche de chemin
Page 2
Plan de leon Recherche de chemin (pathfinding) Dfinition et
principes Algorithme A*
Page 3
Recherche de chemin Consiste en la recherche du chemin le plus
court entre deux points (nuds) Un problme de lintelligence
artificielle Utile entre autres dans les domaines suivants Jeux
vidos Planification Routing Recherche de solution Robotique
Page 4
Recherche de chemin Algorithmes coteux Complexit augmente avec
les obstacles Obstacles peuvent tre Immobiles : Arbres, lacs,
bureau Mobiles : Voitures, personnes, ennemis Infranchissable :
Murs, trous Franchissable : Boue, sable, lacs Temps rel ou
diffr
Page 5
Recherche de chemin Algorithmes dterministes : On connat les
distances intermdiaires Algorithme de Dijkstra Algorithme A* Near
optimal hierarchical pathfinding Near optimal hierarchical
pathfinding Algorithmes probabilistes : On ne connat pas les
paramtres Processus de dcision markovien Chanes de Markov
Page 6
Recherche de chemin Algorithme de Dijsktra Algorithme de
Dijsktra Plus coteux Utilis dans le domaine du rseautage pour
trouver le chemin le plus optimal Open shortest path first Open
shortest path first Minimum spanning tree Minimum spanning
tree
Page 7
Recherche de chemin Algorithme A* Plus rapide selon certaines
conditions + Obstacles = moins rapides Utilis dans le domaine du
jeu Ne retourne pas ncessairement le chemin optimal Bon compromis
entre le chemin optimal et la rapidit
Page 8
Algorithme A* Lalgorithme A* (prononc : A-star)est lalgorithme
le plus frquemment utilis dans les jeuxalgorithme A*
Page 9
Algorithme A* : Termes G : Distance parcouru du nud de dpart au
nud actuel H : Heuristique soit lestimation de la distance en le
nud actuel et le nud final F : Distance parcourir entre le dpart et
la fin si lon passe par ce nud F = G + H
Page 10
Algorithme A* : Termes File dattente prioritaire (open list) :
Liste de nuds qui sont considrer lors de la recherche du chemin
Liste de nuds vrifis (closed list) : Liste de nuds qui ont t vrifis
Utilise sassurer que lon ne considre pas un nud plus dune fois
Parent : Rfrence au nud parent du nud actuel soit le nud qui a
ajout le nud actuel dans la open list
Page 11
Algorithme A* Le principe est le suivant On vide la file
dattente et la liste des nuds vrifis, on remet zro les valeurs F et
G des nuds de la carte Mettre la valeur G du nud de dpart 0 Mettre
la valeur F du nud de dpart la distance entre le dpart et la fin
soit le H Ajouter le nud de dpart la file dattente
Page 12
Algorithme A* Tant que la file dattente contient des nuds
Trouver dans la file dattente le nud qui a la plus petite valeur F
et lassigner comme nud actif Si la file dattente est vide ou encore
aucun nud ne peut tre trouv, i.e. que lon ne peut trouver de
chemin, mettre fin lalgorithme
Page 13
Algorithme A* Si le nud actif est le nud final, on trouve et
retourne le chemin final Sinon pour chaque voisin du nud actif
Sassurer que le voisin est marchable Calculer une valeur G' G du
nud actif + le cot de dplacement vers le voisin Si le voisin nest
pas dans la file dattente ou la liste vrifie
Page 14
Algorithme A* Mettre la valeur G' dans celle du voisin Mettre
la valeur F du voisin G + la distance du voisin au nud final Mettre
comme parent du voisin le nud actif Ajouter le nud actif dans la
file dattente Fin si
Page 15
Algorithme A* Sinon si le voisin est dans la file dattente ou
encore dans la liste vrifie Si la valeur calcule G' est infrieure
voisin.G Voisin.G = G Voisin.F = G' + H Voisin.Parent = noeudActif
Fin Si Fin si
Page 16
Algorithme A* Retirer le nud actif de la file dattente Mettre
le nud actif dans la listes vrifies Fin tant que nud dans la file
dattente Retourner une nouvelle liste de points
Page 17
Exemple Source : http://youtu.be/uvIIzj11ayM
Page 18
Exemple AB
Page 19
Page 20
Page 21
Page 22
Exercices laide du projet Tile Mapping du cours prcdent,
ajouter le code ncessaire pour trouver le chemin le plus court
entre 2 tuiles
Page 23
function A*(start,goal) closedset := the empty set // The set
of nodes already evaluated. openset := {start} // The set of
tentative nodes to be evaluated, initially containing the start
node came_from := the empty map // The map of navigated nodes.
g_score[start] := 0 // Cost from start along best known path. //
Estimated total cost from start to goal through y. f_score[start]
:= g_score[start] + heuristic_cost_estimate(start, goal) while
openset is not empty current := the node in openset having the
lowest f_score[] value if current = goal return
reconstruct_path(came_from, goal) remove current from openset add
current to closedset for each neighbor in neighbor_nodes(current)
if neighbor in closedset continue tentative_g_score :=
g_score[current] + dist_between(current,neighbor) if neighbor not
in openset or tentative_g_score < g_score[neighbor]
came_from[neighbor] := current g_score[neighbor] :=
tentative_g_score f_score[neighbor] := g_score[neighbor] +
heuristic_cost_estimate(neighbor, goal) if neighbor not in openset
add neighbor to openset return failure
Page 24
function reconstruct_path(came_from,current) total_path :=
[current] while current in came_from: current := came_from[current]
total_path.append(current) return total_path
Page 25
Rfrences Vido http://www.youtube.com/watch?feature=
player_embedded&v=uvIIzj11ayM#!
http://www.youtube.com/watch?feature=
player_embedded&v=uvIIzj11ayM#! Recherche de chemin Recherche
de chemin A* pathfinding for beginners A* pathfinding for
beginners
