Crossarea Pathfinding ou Transitions de zones à zones pour les PNJs

Laban · 17/10/2009, 15h10

Question : Avez-vous déjà cherché à obtenir dans NWN2 ce que NWN1 proposait, à savoir permettre à un NPC de choisir la transition la plus proche lui permettant de rejoindre un objet situé dans une autre zone ?

C'est ce qu'on appelle le crossarea pathfinding, et je sais que sous des formes plus ou moins simples Ariok ou Deyonara et consorts ont fourni des solutions.

Dans le cadre du système d'IA sociale que je prépare, je me suis retrouvé confronté au problème. Et j'ai mis au point une solution qui se trouve ici en anglais et en traduction plus ou moins automatique à la fin du post.

En gros l'idée c'est que le moddeur utiliserait une application autonome ( java en l'occurence ) à laquelle il faudrait désigner le module à ouvrir.

Il obtiendrait par défaut un fichier 2DA ou en option un fichier SQL. Celui ci désignerait pour chaque zone la meilleure transition pour rejoindre n'importe quelle autre. Et ainsi, passant de zone en zone, il pourrait atteindre l'objet final.

Le calcul favoriserait les zones ayant les mêmes paramètres suivant :

Intérieur / Extérieur
Souterrain
Naturel

Qu'en pensez-vous ?

TRADUCTION PLUS OU MOINS AUTOMATIQUE :

Sujet: Comment mettre en œuvre pour NWN2 une solution pour avoir un PNJ allant de la zone A à Z compte tenu du graphe suivant.

Code:

 A à Z = zones  

A — B — C
|       |
D — E — F
|   |
G   H — Z

Ma solution est d'avoir une matrice statique ( stockée sous forme de lignes dans une base MySQL ou dans un fichier 2DA) de [Area_From, Area_To] => meilleure transition. De cette manière les PNJs vont accéder récursivement à la zone finale

Code:

 A à Z Domaines tags =  
 de a à z = object transition tag  


–––––––––————————————
|   | A | B | … | Z |
–––––––––————————————
| A |   | c | … | y |
–––––––––————————————
| B | a |   | … | z |
–––––––––————————————
| … | … | … |   | … |
–––––––––————————————
| Z | b | d | … |   |
–––––––––————————————


 Ex:  

 A -> Z  
 (  
     A -> Z => transition à D,  
     D -> Z => transition à E,  
     E -> Z => transition à H,  
     H -> Z => passage à Z  
 )  

Donc le PNJ sera envoyé vers D en premier, puis une fois dans D vers E, dans E vers H et dans H vers Z.

Cela nécessite un outil autonome / script qui calculerait la matrice statique. Voici l'algorithme que j'ai imaginé jusque là.

1. Construire la matrice L des zones N dans le module: [area_tag, area_parameters]
2. Construire la matrice d'adjacence M [area_tag_from, area_tag_to] = transition_tag
3. Construire la matrice F avec un algorithme A* pour chaque L qui est un extérieur en utilisant M
4. Construire la matrice F avec un algorithme A* pour chaque L qui est un intérieur en utilisant M et F pour les extérieurs
5. Export de F vers un fichier

Notes:

• les paramètres de zones de L sont: Extérieur: true | false, naturel: true | false, souterrain: true | false
• Ces paramètres de zones qualifient la distance entre les points: plus de paramètres identiques, zones plus proches
• La différenciation des zones intérieur et extérieur permet l'optimisation heuristique : les zones intérieures dépendant généralement des extérieures pour se connecter entre elles.

Questions:

• Cas particulier: Extérieurs liée seulement à travers (un certain nombre d ') intérieur (s)
• les zones instanciées de manière dynamique

En nwscript:

Code:

 const int TRANSAREA_MOVE = 0x01;  
 const int TRANSAREA_DONE = 0x02;  

// Moves Action subject to the area object
/*
    Input     An object tag to move to, area or not
    Output    True if a transition was found 
*/
int ActionMoveToAreaObject( string sObject )
{
    // 1. Configure
    // ============

    // Get target area tag
    object oObject = GetObjectByTag(sObject);
    object oArea = GetIsArea( oObject ) ? oObject : GetArea(oObject);
    string sAreaTo = GetTag( oArea );

    // Get source area tag
    string sAreaFrom = GetTag( GetArea( OBJECT_SELF ) );

    // Sanity checks and error reporting …


    // 2. Get target object
    // ====================

    if( sAreaFrom != sAreaTo )
    {   

        // Get transition object
        int nAction = TRANSAREA_MOVE;
        string sTransitionObject = GetAreaTransition( sAreaFrom, sAreaTo );
        object oTarget = GetNearestObjectByTag( sTransitionObject );
        }
    else
    {
        int nAction = TRANSAREA_DONE;
        object oTarget = oObject;
    }

    // Sanity checks and error reporting …

    // 3. Actions
    // ===========


    // Get transition object type
    int nObjectType = GetObjectType( oTransitionObject );

    // Assign actions
    switch( nAction )
    {
        case TRANSAREA_MOVE :


            // Assign actions
            switch( nObjectType )
            {
                case OBJECT_TYPE_TRIGGER :
                // …
                break;
                case OBJECT_TYPE_DOOR :
                // …
                break;
                case OBJECT_TYPE_PLACEABLE :
                // …
                break;
            }
        break;
        case TRANSAREA_DONE :
            ActionForceMoveToLocation( GetLocation( oTarget ) );
        break;

        }
}


// Calls static trans-area table
/*
    Input     Two area tags : source and target
    Output    Nearest transarea transition tag
*/
string GetAreaTransition( string sAreaFrom, string sAreaTo )
{
    string sAreaTransition = "";

    // Storage type depends on module switch or some const

    // if 2DA storage
    //…

    // if SQL storage
    //…
   
    return sAreaTransition;

}

Cedric@Shed · 28/10/2009, 09h23

Ouhaou!

Excellente solution, peut être complexe au 1er abord, mais qui a le mérite de fonctionner. J'ai hâte de voir ton système d'IA social que je puisse l'utiliser dans notre futur module/serveur persistant

.

D'ailleurs, j'en profite pour demander de l'aide, si une personne disponible et passionnée de nwn2 peu venir nous donner un coup de main...

Laban · 02/11/2009, 09h43

Merci

C'est loin d'être fait encore...

Bonne chance pour tes recherches!

Laban · 10/08/2010, 00h52

Ah tiens c'est marrant en regardant si un système de script absolument énorme était référencé dans la liste wiki des scripts je tombe sur ce vieux post.

Marrant parce que si je n'ai pas créé l'appli java qui crée la "table de routage" j'ai par contre implémenté à la main un 2DA et ça marche.

Faudra que je mette ça en ligne.

Argyl · 10/08/2010, 17h49

Entre autre chose

Laban · 12/08/2010, 11h24

Voici en résumé un aperçu du code qui fonctionne. J'ai un module de test que je peux mettre à votre disposition si vous voulez en savoir plus.

Le 2DA qui va bien est dans la miniature attachée.

Pour utiliser le code :

Code PHP:


        object oTransition = GetTransitionObject(  GetTag( oAreaTo ), GetAreaId( oAreaFrom ) );
                
        AssignCommand( oNPC, ActionForceMoveToLocation( GetLocation( oTransition ), bRun ) );

et la fonction :

Code PHP:



// @return Area 2DA Id
int GetAreaId( object oArea )
{

    return GetLocalInt( oArea, AREA_ID );

}


// Runs on module startup : assigns crossareas pathing 2DA row ID to each area  
void InitiateAreas()
{

    int nIterator;
    
    string sLabel;
    
    for( nIterator = 0; nIterator < AMOUNT_AREAS; nIterator++ )
    {
        
        sLabel = Get2DAString( CA_2DA, "Label", nIterator );
    
        SetLocalInt( GetObjectByTag( sLabel ), AREA_ID, nIterator );

    }
    

}

// Returns the best transtion object to reach target
// @params : AreaTo, AreaFrom
// @return : Transition object
object GetTransitionObject( string sAreaTo, int nAreaFrom )
{

    object oTrans = GetObjectByTag( Get2DAString( CA_2DA, sAreaTo, nAreaFrom ) ); // CA_2DA : le nom du 2DA pour le Cross Area
    
    return oTrans;

}

C.DuK · 12/08/2010, 14h49

Oh, ceci annonce donc la fin du "je change de zone pour semer les mobs" ! Toute une époque de vil et lâche Xpage qui s'écroule.

J'attend avec impatience une version avec l'application java (open source ?) pour générer la matrice, parce qu'à la main ça risquerait d'être terriblement complexe et laborieux, il faut l'avouer.

Une petite question, dans les fonctions présentées, CA_2DA et AREA_ID, se sont bien des constantes à définir en début de script ?

Bonne programmation pour tous ces systèmes de votre cru M. Laban !

Laban · 12/08/2010, 16h33

Merci M'sieur le C.Duk.

Alors pour éviter la lâcheté tu changement de zone, je suis quasi certain que Deyonara et Ariok notamment, Kortex aussi il me semble, avaient collaboré sur un système. Pour autant que je me souvienne, ledit script vérifiait à la sortie de zone si une ou plusieurs créatures se trouvaient près du joueur, auquel cas la ou les créature(s) seroient téléportés auprès d'icelui quelques secondes après son arrivée...

Pour revenir au cas qui nous intéresse, les deux constantes sont bien des constantes, celle pour le nom du 2DA et celle pour le nom de la variable stockant l'ID int de la zone sur icelle.

Tu auras noté qu'au chargement du module les IDs de zones sont stockées sur chaque zone, une ID correspondant à une ligne du 2DA.

Ceci afin de récupérer par colonne (string) et ligne (int) le TAG de l'objet de transition présent dans la zone AreaA permettant de passer dans la zone qui permet de rejoindre AreaB de proche en proche.

Ce système pourra certes répondre aux impératifs de la chasse au PJ fuyard, mais c'est surtout destiné à permettre une IA sociale de qualité. Du genre un paysan qui est dans son champs et qui à la nuit tombée est capable d'aller dans la zone extérieure adjacente ( son village ) et de rejoindre sa maison pour se coucher dans son lit. Et vice-versa le matin. Et d'aller à l'église le dimanche. Et d'aller au bois de Boulogne le samedi soir. Mais je m'égare.

À ce sujet, ce système marchera mieux avec des zones intérieures séparées pour chaque étage. Ce qui accentue de fait le besoin d'un outil de décryptage des zones et de retranscription. Transition.

L'outil en Java, j'y pense mais il faut que je me mette à Java En fait, il faut que je demande à GrinningFool le code qu'il a développé : ça parse toutes les zones et ça récupère les transitions.

À moi de faire un joli tableau multidimensionnel avec ça et de suivre l'algorithme que j'ai détaillé dans le premier post. C'est du boulot, et pour le moment je ne pense pas m'y coller avant d'avoir une implémentation suivante du Planner.

Laban · 20/02/2011, 15h44

Hébédidon! Premier message d'octobre 2009, dernier en août 2010... et livraison de la première version en février 2011 !!!

Je sais que ces forums sont en déshérence ( d'ailleurs si un admin passe dans le coin, il y a un ou deux topics stickés qui pourraient dégager et / ou être convertis ) mais je pense pouvoir y trouver quelques testeurs ?

J'ai un exécutable qui sort le 2DA pour n'importe quel module dont les zones sont connectées via des portes ou des triggers de transition standard.

Ami, si tu as un module et que tu veux tester ça et profiter à terme de PNJs capables de se déplacer de zone en zone, envoie moi un MP ou bien poste ici, je te transmets le .exe et la ligne de commande qui va bien !

NB : Au final c'est développé en C++ pour ceux qui veulent, le code source est disponible.

Laban · 22/02/2011, 22h10

Haha, le silence est assourdissant

Bon je mets le lien sur github, on sait jamais
https://github.com/albancrommer/FTP

Utiliser le bouton "Téléchargement" à droite

Cedric@Shed Empereur	Ouhaou! Excellente solution, peut être complexe au 1er abord, mais qui a le mérite de fonctionner. J'ai hâte de voir ton système d'IA social que je puisse l'utiliser dans notre futur module/serveur persistant . D'ailleurs, j'en profite pour demander de l'aide, si une personne disponible et passionnée de nwn2 peu venir nous donner un coup de main...
28/10/2009, 09h23

Laban Alpha & Oméga	Merci C'est loin d'être fait encore... Bonne chance pour tes recherches!
02/11/2009, 09h43

Laban Alpha & Oméga	Ah tiens c'est marrant en regardant si un système de script absolument énorme était référencé dans la liste wiki des scripts je tombe sur ce vieux post. Marrant parce que si je n'ai pas créé l'appli java qui crée la "table de routage" j'ai par contre implémenté à la main un 2DA et ça marche. Faudra que je mette ça en ligne.
10/08/2010, 00h52

Laban Alpha & Oméga	Haha, le silence est assourdissant Bon je mets le lien sur github, on sait jamais https://github.com/albancrommer/FTP Utiliser le bouton "Téléchargement" à droite
22/02/2011, 22h10

Crossarea Pathfinding ou Transitions de zones à zones pour les PNJs

Connectés sur ce fil