IA #1 - le pathfinding (2/2)

[daemondragon]

Et voila le deuxieme tutoriel où je vais vous expliquer tout le code
du pathfinding ( et oui enfin ! )

Tout d'abord n'hésitez pas a télécharger les sources en bas du post afin
de les lire en même temps, c'est plus pratique pour comprendre de
quoi je parle.

On va commencer par le prototype de la fonction :

path_direction* create_path(const int largueur, const int hauteur, int map[][hauteur],
                const path_pos debut, const path_pos fin, int pivot)

Cette fonction retourne un pointeur vers une structure, je vais vous expliquer a quoi
elle sert vers la fin. Il faut donc en paramètre la largueur et la hauteur de la map

(attention, la map doit être de format map[largueur][hauteur] et non, map[hauteur][largueur]
la map qui contient des nombres afin de représenter votre terrain, et maintenant les trucs
intéressant : la structure path_pos ne contient que deux int, x et y, pour connaître la position
du début et celle de la fin.

Attention, le début de la map commence a (0, 0), il faut faire attention !
Et enfin le pivot, mais qu'est ce que c'est ?
C'est tout simplement tout les nombres qui sont supérieur ou égal a lui sont traversables,
tout ceux inférieur sont des murs par exemples. cela nécessite par contre de penser a
cela dès le début e la conception du jeu mais c'est pas très difficile. personnellement,
j'utilise souvent des énumération pour définir les différentes tiles (blocs) de la map.

ensuite :

if(debut.x == fin.x && debut.y == fin.y)
{
    return NULL;
}

assez explicite je crois, on retourne NULL afin de savoir qu'il n'y a pas de chemin.

On doit créer ensuite une grille de coût , de la taille qui faut exactement, et on initialise
le tout a 0, c'est très important !
on met a jour a grille de coût, en mettant a 1 le début.

Ainsi, on sait que tout les blocs avec un coût égal a zéro sont non explorés

Il faut ensuite créer une file, les positions actuelle et les suivantes, ce qui donne :

path_pos actuel;
path_pos suivant;
control control_list;

la structure control et donc se qui va nous servir a contrôler la file, on va mettre les donnée
en file a partir de cette structure là.
Elle contient un pointeur vers la première donnée, pour la récupérer. (n'hésitez pas a regarder
le précédent tutoriel pour voir de quoi je veux parler) Et aussi un pointeur vers la dernière
données, afin de mettre les données dans la file plus rapidement. S'il n'y en avait pas, on
aurait du parcourir TOUTES les données de la file une par une afin de trouver la fin.
Vous imaginez sur une énorme file de 1000 données ?
Il faut initialiser la file avec la position de début et on commence les choses sérieuse.

Il faut ensuite créer une boucle qui s’arrête quand on a trouvé la fin ou que la file est vide.
dedans, on met a jour la position actuelle qui erre égale a la valeur du début de file.
si la position actuelle est égale a celle de fin on sort de la boucle, sinon on regarde sur le coté.
Cela donne en code:

while(control_list.premier != NULL && fini)
        {
            actuel.x = control_list.premier->actuel.x;
            actuel.y = control_list.premier->actuel.y;
            
            if(actuel.x == fin.x && actuel.y == fin.y)
            {
                fini = 0;
            }

            if(actuel.x != 0)
            {
                if(map[actuel.x-1][actuel.y] >= pivot && poid[actuel.x-1][actuel.y] == 0)
                {
                    suivant.x = actuel.x-1;
                    suivant.y = actuel.y;
                    poid[suivant.x][suivant.y] = poid[actuel.x][actuel.y] + 1;

                    add_to_file(&control_list, suivant);                    
                }
            }
            if(actuel.x != largueur -1)
            {
                if(map[actuel.x+1][actuel.y] >= pivot && poid[actuel.x+1][actuel.y] == 0)
                {
                    suivant.x = actuel.x+1;
                    suivant.y = actuel.y;
                    poid[suivant.x][suivant.y] = poid[actuel.x][actuel.y] + 1;

                    add_to_file(&control_list, suivant);
                }
            }
            if(actuel.y != 0)
            {
                if(map[actuel.x][actuel.y-1] >= pivot && poid[actuel.x][actuel.y-1] == 0)
                {                
                    suivant.x = actuel.x;
                    suivant.y = actuel.y-1;
                    poid[suivant.x][suivant.y] = poid[actuel.x][actuel.y] + 1;
                    
                    add_to_file(&control_list, suivant);
                }
            }
            if(actuel.y != hauteur - 1)
            {
                if(map[actuel.x][actuel.y+1] >= pivot && poid[actuel.x][actuel.y+1] == 0)
                {                
                    suivant.x = actuel.x;
                    suivant.y = actuel.y+1;
                    poid[suivant.x][suivant.y] = poid[actuel.x][actuel.y] + 1;

                    add_to_file(&control_list, suivant);
                }
            }
            remove_to_file(&control_list);
        }

Il faut bien entendu éviter de partir sur les coté de la map, sinon on risque d'avoir des problèmes de mémoires.
Vous vous dites aussi sûrement : "mais c'est quoi add_to_file et remove to file" non ?
Ce sont les structure qui servent a mettre les données dans la file, ou a les enlever.
(regardez dans le code source fournit, elle y sont au début.)
A partir de là, la grille de coût est fini, on peut vider totalement la file, on
n'en a plus besoin. ( il faut éviter les fuites mémoires) :

while(control_list.premier != NULL)
{
    remove_to_file(&control_list);
}

Et non ce n'est toujours pas fini :
Il faut regarder la variables fini, qui si elle est égale a zéro, signifie qu'on a trouvé la
fin ,sinon, il faut encore retourner NULL.
si le chemin est trouvé, on se place sur la position de fin et regarde a coté.
On va dans la direction on le coût est égal au coût - 1 de la case.
Il ne faut surtout PAS prendre la case qui a un coût inférieur a celle autour, car a ce
stade la, certaine case n'ont pas encore été explorer ( se n'était pas la peine, on
avait trouver le plus court chemin jusqu’à la fin) et sont donc encore égale a 0.
On risque alors de se trompé totalement de chemin.
On met ensuite dans la pile les directions contraire ou on va aller.
(on part de la fin je vous rappelle) et on retourne a la fin cette pile.
En code :

if (fini == 0)
        {
            fini = 1;
            actuel.x = fin.x;
            actuel.y = fin.y;
            path_direction *control = NULL;
            char direction;
            
            while((actuel.x != debut.x && fini) || (actuel.y != debut.y && fini))
            {
                //les directions sont inversé car le png va aller dans l'autre sens
                if(poid[actuel.x][actuel.y+1] == poid[actuel.x][actuel.y] - 1)
                {
                    direction = NORD;
                    actuel.y++;    
                }
                else if(poid[actuel.x][actuel.y-1] == poid[actuel.x][actuel.y] - 1)
                {
                    direction = SUD;
                    actuel.y--;
                }
                else if(poid[actuel.x+1][actuel.y] == poid[actuel.x][actuel.y] - 1)
                {
                    direction = OUEST;
                    actuel.x++;
                }
                else
                {
                    direction = EST;
                    actuel.x--;
                }
                empile(&control, direction);
            }
            return (control);
        }

La structure path_direction comporte, une direction sous forme de point cardinaux (NORD, SUD...)
et un pointeur vers la donnée suivante (c'est une pile je vous rappelle).
la fonction empile sert a empiler la direction dans la pile (elle va tout au début).
A la fin, on retourne la pile, qu'il faut récupérer avec un pointeur sur une structure path_direction

Le seul problème de ce path_finding actuel, c'est qu'il faut éviter que le chemin, se trouve sur les bord,

sinon on peut passer de l'autre coté de la map dans certain cas, ce qu'il faut a tout prix empêcher.

 

Dans le cas de situation différentes a celle d'un labyrinthe, (quand les chemins ont une grande

chance d'être droit, vous pouvez dirigez le path_finding en lui faisant allez dans la direction vers la

fin et en transformant la file de départ en pile. Il faut alors pouvoir réécrire un coût d'une bloc si la

deuxième fois, le coût est plus faible.

Bref, il est facilement améliorable et il ne tiens qu'à vous de le récréer totalement.

Et voila le tour est joué, vous avez maintenant un path_finding qui marche

https://github.com/daemondragon/pathfinding.git

Modifié June 5, 2014 par daemondragon

[AlexMog]

On va commencer par le prototype de la fonction :

path_direction* create_path(const int largueur, const int hauteur, int map[][hauteur],
                const path_pos debut, const path_pos fin, int pivot)

ATTENTION: Ici, tu passe la map en COPIE! C'est pas du tout propre, et tu fais très très mal à ta stack (tu copie toute la map dans ta stack, donc, si tu as une map trop grande, PAFF! Segfault.)

Envois plutot un int **map au lieu d'un int map[][haueur] .