AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  Connexion  

Partagez | 
 

 [Script] A* pathfinding (partiel) [maj:rapidité d'exécution]

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
hofmeister
Bavard


Messages : 109

MessageSujet: [Script] A* pathfinding (partiel) [maj:rapidité d'exécution]   Sam 24 Jan 2015 - 15:04

Bonjour, voila quelques scripts pour le pathfinding, si jamais la version de GM ne convient pas.
(entre autres je crois qu'on ne peut pas définir 2 types d'objets considérés comme obstacles + un considéré comme invisible pour le chemin.)
Il reste d'autres choses à faire cependant:
-Définir le coût en mouvement d'une case.
-Définir comment une case est considérée comme obstacle.
-Une méthode pour évaluer la distance entre deux cases.
-Ajouter les nodes adjacents
-Interdire les cases d'arrivée qui ne comportent pas de chemin possible, sinon le script plante.
Ces points dépendent de ce qu'on veut faire, le reste semble générique.
Edit:j'ai changé une bonne partie des scripts pour une gestion plus rapide des listes, avec binary heaps,
selon un lien dans l'article "a* pathfinding for beginners".

Voila les scripts de gestion des listes:
sc_ajout_ol_t:
Code:
{
squaresChecked+=1;
t_o_l+=1;
o_l[t_o_l]=squaresChecked;
acth=t_o_l;
while(acth!=1)
    {
    if f_c[o_l[acth]]<=f_c[o_l[floor(acth/2)]]
        {
        templ=o_l[floor(acth/2)];
        o_l[floor(acth/2)]=o_l[acth];
        o_l[acth]=templ;
        acth=floor(acth/2);
        }
    else
        {
        break;
        }
    }
}
sc_drop_ol_t:
Code:
{
o_l[1]=o_l[t_o_l]
t_o_l-=1;
v=1;nimpi=false;
while(nimpi==false)
    {
    u=v;
    if 2*u+1 <= t_o_l
        {
        if f_c[o_l[u]]>=f_c[o_l[2*u]]
            {
            v=2*u;
            }
        if f_c[o_l[v]]>=f_c[o_l[2*u+1]]
            {
            v=2*u+1;
            }
        }
    else if 2*u <= t_o_l
        {
        if f_c[o_l[u]]>=f_c[o_l[2*u]]
            {
            v=2*u;
            }
        }
    if u!=v
        {
        templ=o_l[u];
        o_l[u]=o_l[v];
        o_l[v]=templ;
        }
    else
        {
        break;
        }
    }
}
sc_actu_ol_t:
Code:
{

acth=argument0;
while(acth!=1)
    {
    if f_c[o_l[acth]]<=f_c[o_l[floor(acth/2)]]
        {
        templ=o_l[floor(acth/2)];
        o_l[floor(acth/2)]=o_l[acth];
        o_l[acth]=templ;
        acth=floor(acth/2);
        }
    else
        {
        break;
        }
    }
}
sc_ajout_c_l:
Code:
{
c_l[t_c_l,0]=argument0;
c_l[t_c_l,1]=argument1;
c_l[t_c_l,2]=argument2;
c_l[t_c_l,3]=argument3;
c_l[t_c_l,4]=argument4;
c_l[t_c_l,5]=argument5;
t_c_l+=1;
}
sc_is_in_c_l:
Code:
{
for(cb=0;cb<t_c_l;cb+=1)
    {
    if (argument0==c_l[cb,0])&&(argument1==c_l[cb,1])
        {
        return true;
        }
    }
return false;
}
sc_find_node_in_o_l:
Code:
{
for(atn=1;atn<t_o_l+1;atn+=1)
    {
    if (argument0==x_c[o_l[atn]])&&(argument1==y_c[o_l[atn]])
        {
        return atn;
        }
    }
return -1;
}
sc_find_node_in_c_l:
Code:
{
for(atn=0;atn<t_c_l;atn+=1)
    {
    if (argument0==c_l[atn,0])&&(argument1==c_l[atn,1])
        {
        return atn;
        }
    }
return -1;
}
sc_find_itemc:
Code:
{
for(atn=1;atn<squaresChecked+1;atn+=1)
    {
    if (argument0==x_c[atn])&&(argument1==y_c[atn])
        {
        return atn;
        }
    }
return -1;
}
sc_pathbis(departx,departy,arriveex,arriveey):
Code:
{
t_o_l=0;t_c_l=0;squaresChecked=0;
if (argument0==argument2)&&(argument1==argument3)
    {
    break;
    }
f_c[squaresChecked+1]=0;
x_c[squaresChecked+1]=argument0;
y_c[squaresChecked+1]=argument1;
g_c[squaresChecked+1]=0;
px_c[squaresChecked+1]=-1;
py_c[squaresChecked+1]=-1;
script_execute(sc_ajout_ol_t);

//sc_check_adj doit enregistrer dans node[nb_nodes,0] la valeur x du node,
//dans node[nb_nodes,1] sa valeur y. Il doit compter le nombre de nodes
//appartenant à la grille de jeu (nb_nodes), et exclure les valeurs en dehors.
script_execute(sc_check_adj,argument0,argument1);
for(nn=0;nn<nb_nodes;nn+=1)
    {
    //Si les nodes ont des valeurs de mouvement différentes, il faut préalablement
    //enregistrer leur valeur dans une grille.
    pn=script_execute(sc_get_poids_node,node[nn,0],node[nn,1]);
    //Votre méthode pour évaluer la distance d'un point à un autre
    ha=script_execute(sc_get_dist2,node[nn,0],node[nn,1],argument2,argument3);
    effe=pn+ha;
    //Determine si le node n'est pas un obstacle
    testn=script_execute(sc_node_is_valid,node[nn,0],node[nn,1]);
    if testn==true
        {
        f_c[squaresChecked+1]=effe;
        x_c[squaresChecked+1]=node[nn,0];
        y_c[squaresChecked+1]=node[nn,1];
        g_c[squaresChecked+1]=pn;
        px_c[squaresChecked+1]=argument0;
        py_c[squaresChecked+1]=argument1;
        script_execute(sc_ajout_ol_t);
        
        }
    }
script_execute(sc_ajout_c_l,argument0,argument1,0,0,-1,-1);
script_execute(sc_drop_ol_t);

supervar=false;
while(supervar==false)
    {
    
    
    actun[0]=x_c[o_l[1]];
    actun[1]=y_c[o_l[1]];
    if(actun[0]==argument2)&&(actun[1]==argument3)
        {
        pr=0;
        path_sqr[pr,0]=px_c[o_l[1]];
        path_sqr[pr,1]=py_c[o_l[1]];
        pr+=1;
        while(!((path_sqr[pr-1,0]==argument0)&&(path_sqr[pr-1,1]==argument1)))
            {
            
            lepr=script_execute(sc_find_node_in_c_l,path_sqr[pr-1,0],path_sqr[pr-1,1]);
            if lepr==-1
                {
                lepr=script_execute(sc_find_node_in_o_l,path_sqr[pr-1,0],path_sqr[pr-1,1]);
                if lepr>-1
                    {
                    lepr=script_execute(sc_find_itemc,path_sqr[pr-1,0],path_sqr[pr-1,1]);
                    path_sqr[pr,0]=px_c[lepr];
                    path_sqr[pr,1]=py_c[lepr];
                    }
                else
                    {
                    break;
                    }
                }
            else
                {
                if ((c_l[lepr,4]==argument0)&&(c_l[lepr,5]==argument1))
                    {
                    break;
                    }
                path_sqr[pr,0]=c_l[lepr,4];
                path_sqr[pr,1]=c_l[lepr,5];
                }
            pr+=1;
            
            }
        break;
        }
    ge=g_c[o_l[1]];
    script_execute(sc_ajout_c_l,actun[0],actun[1],0,0,px_c[o_l[1]],py_c[o_l[1]]);
    script_execute(sc_drop_ol_t);
    
    script_execute(sc_check_adj,actun[0],actun[1]);
    for(nn=0;nn<nb_nodes;nn+=1)
        {
        testcl=script_execute(sc_is_in_c_l,node[nn,0],node[nn,1]);
        if testcl==true{continue;}
        testn=script_execute(sc_node_is_valid,node[nn,0],node[nn,1]);
        if testn==true
            {
            pn=script_execute(sc_get_poids_node,node[nn,0],node[nn,1]);
            ge2=ge+pn;
            ha=script_execute(sc_get_dist2,node[nn,0],node[nn,1],argument2,argument3);
            effe=ge2+ha;
            testo=script_execute(sc_find_node_in_o_l,node[nn,0],node[nn,1]);
            
            if testo==-1
                {
                f_c[squaresChecked+1]=effe;
                x_c[squaresChecked+1]=node[nn,0];
                y_c[squaresChecked+1]=node[nn,1];
                g_c[squaresChecked+1]=pn+ge;
                px_c[squaresChecked+1]=actun[0];
                py_c[squaresChecked+1]=actun[1];
                script_execute(sc_ajout_ol_t);
                
                }
            else
                {
                
                refi=script_execute(sc_find_itemc,node[nn,0],node[nn,1]);
                if ge2<g_c[refi]
                    {
                    f_c[refi]=effe;
                    g_c[refi]=ge2;
                    px_c[refi]=actun[0];
                    py_c[refi]=actun[1];
                    script_execute(sc_actu_ol_t,testo);
                    
                    }
                }
            }
        }
    
    if (!((actun[0]==argument2)&&(actun[1]==argument3)))&&(t_o_l==0)
        {
        break;
        }
    }

}
Voila. Chez moi ça a l'air de marcher sauf chemin introuvable. (je n'ai pas encore défini les cases
inaccessibles).
Il reste donc les scripts:
-sc_check_adj(casex,casey)
-sc_get_poids_node(casex,casey)
-sc_node_is_valid(casex,casey)
-sc_get_dist2(departx,departy,arriveex,arriveey)
Il faut aussi n'exécuter le script que si le point d'arrivée n'est pas entouré d'obstacle, et qu'il n'est pas lui même
un obstacle
Edit: j'ai oublié de dire qu'il faut définir path_sqr  et pr comme variables globales. path_sqr contient l'enregistrement du chemin à partir du point d'arrivée, ne contient ni le point de départ ni le point d'arrivée.
pr est la taille de ce tableau, donc path_sqr[pr-1,0] est la coordonnée x de la case adjacente au départ,
path_sqr[pr-1,1] la coordonnée y de la case adjacente au départ
Revenir en haut Aller en bas
 
[Script] A* pathfinding (partiel) [maj:rapidité d'exécution]
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» script défilement texte ou image
» sevrage partiel , diversification alimentaire reprise de travail
» Recherche testeur pour le script complémentaire du TdH
» recherche assitante temps partiel-st-jean-sur-richelieu
» 312.800 dollarpour le script du "Parrain" annoté p

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum Le CBNA :: Développement :: Scripts GML-
Sauter vers: