hofmeister Bavard
Messages : 109
| Sujet: [Script] A* pathfinding (partiel) [maj:rapidité d'exécution] Sam 24 Jan 2015 - 16: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 |
|