Tutorial original écrit par Fy_Hertz

Voici un petit tutoriel pour apprendre à utiliser un algorithme destiné au pathfinding, sous Dark Basic. Plus d'infos dans le tuto :).



Les Way Points (abrégé WP) sont, en fait, des points qui permettent le déplacement d'objets de façon "intelligente". Exemple dans un jeu : l'ennemi A veut rejoindre le héros B. Les WP lui permettront de se créer une trajectoire pour rejoindre B efficacement et sans avoir recours au traditionel point object A,object position x(B),object position y(B),object position z(B) et move object A,x .



Nous verrons par la suite comment utiliser l'algoritme présenté ici.

Sachez qu'il est totalement inutile de comprendre son fonctionnement pour l'utiliser (même si cela peut-être intéressant)... Tout ce qu'il y a savoir, c'est comment utiliser le tableau id(). J'y reviendrai...

Code :

rem ************************************************************************ 
rem Algorithme by Fy_Hertz for join WP. 
curs=0 

for x=1 to nbWP 
    id(x)=x 
next x 

rem Touver les WP voisins 
for x=1 to nbWP 
    A=1
    for y=1 to nbWP 
        if STATIC LINE OF SIGHT(WP(x,1),0,WP(x,2),WP(y,1),0,WP(y,2),20,1)<>1 and x<>y 
            voisin(x,A)=y 
            inc A 
        endif 
    next y 
next x 

rem initialisation des id 
for x=1 to nbWP 
    id(x,x,1)=x 
    connect(x,x)=1 
next x 

rem Connecter les WP 
AllFind=nbWP-1:D=1:E=1:A=1 

for t=1 to nbWP 
    CurrentWP=t 
    while A<AllFind 
        C=1 
        while voisin(CurrentWP,C)<>0 
            if voisin(CurrentWP,C)<>CurrentWP and connect(t,voisin(CurrentWP,C))=0 
                connect(t,voisin(CurrentWP,C))=1 
                Liste(D)=voisin(CurrentWP,C) 
                W=1 
                while id(t,CurrentWP,W)<>0 
                    id(t,voisin(CurrentWP,C),W)=id(t,CurrentWP,W) 
                    inc W 
                endwhile 
                id(t,voisin(CurrentWP,C),W)=voisin(CurrentWP,C) 
                inc A:inc D 
            endif 
            inc C 
        endwhile 
        CurrentWP=Liste(E) 
        inc E 
    endwhile 

    for h=1 to E 
        Liste(h)=0 
    next h 
    E=1:D=1:A=1 
next t 

rem ************************************************************************ 

Cet algorithme répond exactement à notre besoin. Pour l'utiliser vous n'avez qu'à le copier/coller dans votre programme. La seule partie qu'il peut y avoir à modifier est celle qui détermine les WP qui sont voisins. Ici on considère que deux WP sont voisins si on peut passer de l'un à l'autre sans renconter d'obstacles (sachez que l'on ne considère que les obstacles statiques).




Cet algorithme présente l'avantage d'être extrêmement simple d'utilisation et extrêmement rapide. De plus, il choisit toujours la trajectoire la plus rapide pour atteindre son objectif. La contrepartie est qu'il utilise énormement de mémoire vive puisque que le tableau où sont stockés les résultats a une taille de (Nombre_de_WP ^ 3), ce qui devient rapidement énorme.




Pour que mon algorithme puisse fonctionner, il faut respecter différentes étapes dans son implémentation dans votre programme.

a) Création des structures de données.

Code :

rem nombre de wp 
nbWP=21 

rem tableau 
dim WP(nbWP,2) 
dim id(nbWP,nbWP,nbWP) 
dim connect(nbWP,nbWP) 
dim voisin(nbWP,nbWP) 
dim Liste(nbWP)

b) Création de votre map...

c) Création et Positionnement de vos WP.

Code :

WP(17,1)=150:WP(17,2)=53 
WP(2,1)=-136:WP(2,2)=350 
WP(3,1)=250:WP(3,2)=350 
WP(4,1)=250:WP(4,2)=750 
WP(5,1)=650:WP(5,2)=750 etc... etc... 

Code :

for t=0 to nbWP 
make object box 32000+t,30,30,30 
position object 32000+t,WP(t,1),00,WP(t,2) 
next t 

d) Copier/coller l'algorithme.




Les résultats sont stockés dans le tableau id(). Voici un exemple de son utilisation : Je pars du WP A pour aller au WP B. La trajectoire est id(A,B,X). La variable X pemet de passer de WP en WP composant la trajectoire.

De A à B il y a C, D, E et F, on a donc :
Code :

ID(A,B,1)=A 
ID(A,B,2)=C 
ID(A,B,3)=D `On retrouve bien notre trajectoire en incrementant X. 
ID(A,B,4)=E 
ID(A,B,5)=F 
ID(A,B,6)=B 

Voilà, correctement utilisé, cet algoritme vous permettra simplement de faire se rejoindre plusieurs objets dans n'importe quelle situatuation complexe. Veillez à ce que qu'aucun de vos WP soit voisin à un autre WP : le résultat serait probablement désastreux. Si vous êtes amené à utiliser cet algorithme veuillez ne pas retirer ma signature, merci.