Ce site est optimisé pour être consulté depuis un navigateur moderne dans lequel JavaScript est activé.

WorldGraph (projet de pathFinding)

NollyLaRune

Bonjour à tous,

Je me suis présenté il y a peu. Je disais que je commençais à m'intéresser à la lecture de packet. Je travail en Python.

Je suis maintenant un peu plus loin. Je me suis lancé dans le pathfinding à travers les fonctions en AS3 de D%fus dans la partie ankamagames>dofus>module>utils>pathfinding:

- WorldPathfinder

- WorldGraph

- AStar

J'ai suivi les conseils des articles:

- Bot Chasses au Trésor et maps bloquantes

- Compréhension des maps (DLM)

Il me semble avoir réussi à extraire les données de world-graph.bin à partir des codes de WorldGraph.as. J'ai transformé les objets vertex, edge, et transitions par des dictionnaires et listes. Cela me permet de sauvegarder la donnée en format .json et de la lire.

Je me pose quelques questions: est-ce une bonne idée de faire disparaître les objets créés spécifiquement par les programmeurs du jeu au profit de simples dictionnaires?

Je récupère donc 3 dictionnaires: vertices, edges et outgoingEdges.

De ce que j'ai compris, outgoingEdges donne les informations qui permettent de faire la transition entre deux maps (notamment lorsqu'on doit changer entre deux maps différentes de deux zones différentes). Un autre truc que je ne comprend pas: J'ai remarqué que je pouvais avoir une transition d'une map x à une map y, et ne pas avoir l'inverse, soit la transition de la map y à la map x.


"1": [
      {
        "from": {
          "mapId": 54173482.0,
          "zoneId": 1,
          "uid": 1
        },
        "to": {
          "mapId": 54534175.0,
          "zoneId": 1,
          "uid": 2
        },
        "transitions": [
          {
            "type": 32,
            "direction": -1,
            "skillId": 184,
            "criterion": "",
            "transitionMapId": 54534175.0,
            "cell": 298,
            "id": 457133.0
          }
        ]
      }

Autre chose, j'ai déjà commencé à travaillé sur le code de AStar.as. Des gens ont essayé de faire de même? :)

J'ai l'impression que tout fonctionne pas mal, sauf… que la partie criterion m'a l'air d'être un sacré sac de nœuds, non?

Je peux ajouter du code si besoin. :)

Si des gens sont déjà passés par là, n'hésitez pas *-*

NollyLaRune

NollyLaRune
J'ai remarqué que je pouvais avoir une transition d'une map x à une map y, et ne pas avoir l'inverse, soit la transition de la map y à la map x.

Je crois avoir trouvé un exemple qui explique ce que j'explique ici: En donjon, on passe d'une map a une autre, mais on ne peut pas revenir sur une map précédente.

Sinon, AStar a l'air de fonctionner à peu près correctement sans criterion (je break à chaque fois que je tombe sur un criterion sans me poser de question pour le moment). J'imagine qu'il faudra s'en occuper au bout d'un moment. Je n'ai testé que des petits trajets.

Voilà mon avancement. N'hésitez pas à ajouter des commentaires ou des petits tips, ou même votre expérience par rapport à cette partie de code.

Cœur sur vous :inlove:

NollyLaRune

En fait, BlueDream, il me semble que tu ne parles pas du pathfinding que l'on peut trouver dans les codes du jeu :

NollyLaRune
ankamagames>dofus>module>utils>pathfinding

mais plutôt d'un pathfinding fait main, non? D'où l'utilisation dans ton code du fichier MapPositions qui permet de récupérer les maps adjacentes (sauf erreur si la map n'existe pas ou qu'il y a un changement de zone, il me semble). Je me trompe?

NollyLaRune

Merci beaucoup, j'avoue avoir déjà jeté un coup d'œil sur ton repo (c'est d'ailleurs génial, parce que ça permet de vérifier tout ce que j'ai fait en amont), mais je n'avais pas vu l'exemple en particulier. Je me remet dessus quand j'ai plus de temps.

Passe une bonne journée!

Asura

Hey,

Pour te répondre simplement, oui c'est la bonne méthode à suivre :)

Il te manque plus qu'à prendre en compte les différents criterions (Possession d'un objet, étape d'une quête, niveau, etc etc) et l'interaction avec les zaap/zaapi pour pouvoir te déplacer librement :)

NollyLaRune

Merci pour la réponse Asura

Asura
Pour te répondre simplement, oui c'est la bonne méthode à suivre :)

Quand tu dis "c'est la bonne méthode à suivre", tu parles de transformer les objets en dictionnaires?

Ou parles-tu d'autre chose? :)

Asura

Peu importe si tu consommes directement le .bin, ou si tu préfères te baser sur tes Json :)

J'insinuais juste que ton raisonnement était le bon!

BlueDream

La difficulté majeure, c'est le fait que les mapIds de transition de zone soient faussés.

Lorsqu'on souhaite prévoir le déplacement d'une map x à une map y qui se trouvent dans deux zone différentes,

on se retrouve avec des mapIds invalides dans les mapData, ce qui rend difficile la prévision du déplacement,

puisqu'on doit être capable de déterminer si une map permet l'accès à une certaines direction (north, south, west, east) depuis un emplacement de joueur (pour ne pas se bloquer dans les murs d'astrub par exemple).

Pour remédier à ça, j'avais fait un truc comme ça:

MapData = MapsManager.GetMapFromId((int)MapId);
            WorldMap currentPosition = null;

            if (finder.Path.Count > 2)
                currentPosition = finder.Path[finder.Path.Count - 2];

            if (MapData == null && currentPosition != null)
            {
                MapData = MapsManager.GetMapFromCoord(RealCoordinates.X, RealCoordinates.Y, currentPosition.CoordinatesData.worldMap);
                if (MapData == null)
                {
                    Console.WriteLine("Map inexistante : " + map.RealCoordinates.ToString());
                    return;
                }
                MapId = (uint)MapData.Id;
            }

MapData = MapsManager.GetMapFromId((int)MapId);
            WorldMap currentPosition = null;

            if (finder.Path.Count > 2)
                currentPosition = finder.Path[finder.Path.Count - 2];

            if (MapData == null && currentPosition != null)
            {
                MapData = MapsManager.GetMapFromCoord(RealCoordinates.X, RealCoordinates.Y, currentPosition.CoordinatesData.worldMap);
                if (MapData == null)
                {
                    Console.WriteLine("Map inexistante : " + map.RealCoordinates.ToString());
                    return;
                }
                MapId = (uint)MapData.Id;
            }

Si on trouve pas la map via sa mapId, on la recherche via ses coordonnées dans les mapData.

Si on ne trouve toujours rien, je récupère la map ayant le niveau le plus haut (map extérieur) dans les D2O et ayant l'area & la subArea correspondantes.

Attention c'est à adapter, si vous êtes dans des mines, des maisons ou des ateliers etc ça ne fonctionne pas.

Et en cadeau c'était mon CanChangeMap:

public static int CanChangeMap(uint mapId, uint startCell, Map map, MovementDirectionEnum direction)
        {
            int neighbourId = -1;
            int check = -1;
            bool special = false;

            if (map == null)
                return -1;

            switch (direction)
            {
                case MovementDirectionEnum.North:
                    neighbourId = map.TopNeighbourId;
                    check = 64;
                    break;
                case MovementDirectionEnum.South:
                    neighbourId = map.BottomNeighbourId;
                    check = 4;
                    break;
                case MovementDirectionEnum.East:
                    neighbourId = map.RightNeighbourId;
                    check = 1;
                    break;
                case MovementDirectionEnum.West:
                    neighbourId = map.LeftNeighbourId;
                    check = 16;
                    break;
            }

            if ((check != -1) && (neighbourId >= 0))
            {
                List<int> possibleCells = new List<int>();

                // Possible Basic Cells

                for (int i = 0; i <= map.Cells.Count - 1; i++)
                    if (((map.Cells.MapChangeData & check) != 0 && ((map.Cells.Mov))))
                        possibleCells.Add(i);

                if (possibleCells.Count == 0)
                {
                    // Possible Special Cells

                    special = true;

                    for (int i = 0; i <= map.Cells.Count - 1; i++)
                    {
                        if (map.Cells.Mov)
                        {
                            bool possible = false;

                            switch (direction)
                            {
                                case MovementDirectionEnum.North:
                                    if (map.Cells.TopArrow == true)
                                        possible = true;
                                    break;
                                case MovementDirectionEnum.South:
                                    if (map.Cells.BottomArrow == true)
                                        possible = true;
                                    break;
                                case MovementDirectionEnum.East:
                                    if (map.Cells.LeftArrow == true)
                                        possible = true;
                                    break;
                                case MovementDirectionEnum.West:
                                    if (map.Cells.RightArrow == true)
                                        possible = true;
                                    break;
                            }

                            if (possible == true)
                                possibleCells.Add(i);
                        }
                    }
                }

                if (possibleCells.Count == 0)
                    return -1;

                int cell = possibleCells[RandomCell(0, possibleCells.Count - 1)];

                Pathfinder finder = new Pathfinder();
                finder.SetMap(map, null, true);
                List<CellWithOrientation> path = finder.GetPath((short)startCell, (short)cell);

                if (path != null)
                {
                    return cell;
                }
            }

            return -1;
        }

Ya le gamePathinder ici aussi : https://github.com/BlueDream145/Pathfinder-2.0

NollyLaRune

Merci BlueDream!

BlueDream
ayant le niveau le plus haut (map extérieur)

Je ne comprends pas bien ce que ça veux dire "avoir le niveau le plus haut". Est-ce que ça a un rapport avec le fichier MapCoordinates (qui donne plusieurs map qui possèdent les mêmes coordonnées)? Ou avec MapPositions qui décompte toutes (toutes?) les map avec leurs données?

J'ai une autre question. Si on cherche une map par son id, on va possiblement chercher la map dans les d2p. Mais je ne sais pas si l'organisation des maps est expliquée quelque part:

maps0: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

maps1: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

...

maps11_2: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Je sais que les fichiers de chaque map sont placés dans un dossier qui finit par le dernier chiffre de l'id de la map.

exemple: mapId 54530069 -> sera dans un dossier 9

Mais comment savoir dans quel dossier mapsX il sera placé? Suis-je suffisamment clair?

Peut-être qu'on ne peut pas le savoir. Mais je serais heureux de le savoir, si quelqu'un a une idée :D

hadamard

Nolly dans le WorldGraph t'as tous cedon't t'as besoin pour se deplacer.

voici un petit coup de main de comment utiliser le worldGraph pour te deplacer:

```

@classmethod
def getOutGoingTransitions(
    cls, discard=[], noskill=True, directions: list[DirectionsEnum] = [], mapIds=[]
) -> list[Transition]:
    result = []
    v = WorldPathFinder().getCurrentPlayerVertex()
    outgoingEdges = WorldPathFinder().worldGraph.getOutgoingEdgesFromVertex(v)
    for e in outgoingEdges:
        for tr in e.transitions:
            if tr.transitionMapId not in discard:
                if noskill and tr.skillId > 0:
                    continue
                if directions and (tr.direction < 0 or DirectionsEnum(tr.direction) not in directions):
                    continue
                if mapIds and tr.transitionMapId not in mapIds:
                     continue
                 result.append(tr)
   return result

@classmethod
def changeMapToDstDirection(cls, direction: DirectionsEnum, discard: list[int] = []) -> None:
    transitions = cls.getOutGoingTransitions(discard=discard, directions=[direction])
    if len(transitions) == 0:
        raise Exception(f"No transition found towards direction '{direction.name}'")
        cls.sendClickAdjacentMsg(transitions[0].transitionMapId, transitions[0].cell)

@classmethod
def changeMapToDstCoords(cls, x: int, y: int, discard: list[int] = []):
    transitions = cls.getOutGoingTransitions(discard)
    if len(transitions) == 0:
        raise Exception(f"No transition found towards coords '{x, y}'")
    for tr in transitions:
        mp = MapPosition.getMapPositionById(tr.transitionMapId)
        if mp.posX == x and mp.posY == y:
            cls.sendClickAdjacentMsg(tr.transitionMapId, tr.cell)
            return tr.transitionMapId
    return -1

hadamard

Ce que tu veux faire c'est recuperer le vertex de ta map courante, du vertex tu peux recuperer toutes les transitions sortantes puis dans les transitions t'as tous les infos pour changer de map comme la direction, l'id de la map destination et meme le cellId sur le quel il faut se placer pour changer la map

hadamard

L'info sur la map courante peut etre extraite du message 'CurrentMap' ou se trouve l'id de la map.

Depuis l'id tu peux recuperer les donnees de la map avec un dlm reader et dans celle-ci tu veux utiliser linkedZoneRp.

Un map id + linkedZoneRp = un vertex dans le graph.

Dans la class WorldGraph t'as une fonction qui permet de recuperer le vertex depuis mapId, linkedZoneRp.

voila bon courage

NollyLaRune

Encore merci hadamard, tout à l'air de concorder. Juste une dernière question pour être sûr. Quand tu dis:

hadamard
L'info sur la map courante peut etre extraite du message 'CurrentMap' ou se trouve l'id de la map.

Ce 'CurrentMap', c'est bien "MapComplementaryInformationsDataMessage", que l'on reçoit à chaque changement de map et qui permet d'avoir l'id de la map en question, non?

Je me trompe? Y a-t-il une autre manière de faire?

Je vais essayer de me renseigner sur le forum. Je marquerai la réponse si je la trouve et que personne n'y a répondu d'ici là.

Pour répondre (environ 5 minutes après avoir écrit ma question précédente), j'ai trouvé ça:


playedCharacterManager = PlayedCharacterManager()  # ça, ça va nous intéresser
logger.info("Start searching path to " + str(destinationMapId))
TimeDebug.reset()
playedEntity: IEntity = DofusEntities.getEntity(playedCharacterManager.id)
if not playedEntity:
    callback(None)
    return
playedEntityCellId: int = playedEntity.position.cellId
playerCell: Cell = MapDisplayManager().dataMap.cells[playedEntityCellId]
self.src = self.worldGraph.getVertex(
    playedCharacterManager.currentMap.mapId, playerCell.linkedZoneRP  # ici, on trouve bien currentMap!!!
            )

Donc j'imagine qu'hadamard parle de ça. Me reste plus qu'à trouver comment récupérer le PlayedCharacterManager.

hadamard

Pour la question dict ou object.

T'as pas le choix pour du cde propre tu dois avoir une class qui represente le graph pour l'exploiter d'une maniere organisee.

Aussi lire un json est plus couteux que lire un fichier binaire qui suit un protocole d'encodage tres simple conmme le worldGraph.bin

NollyLaRune

Bah écoute. C'est super...

Je me posais beaucoup de questions. Et je pense que tu as répondu à pas mal d'entres-elles. Je regarde ce que tu m'as mis quand j'ai le temps.

Merci beaucoup hadamard!

NollyLaRune

Le pathfinding avance plutôt bien. (Merci à vous)

Je suis sur un problème différent à présent. Je souhaite comparer un chemin de pathfinding à pied avec des chemins possibles à partir de zaaps connus. En gros, si je dois faire 30 min de marche alors que je peux juste prendre un zaap pour y arriver, et bien il est tout simplement préférable de prendre le zaap.

En ayant cherché sur le forum, j'ai appris que Waypoints.d2o stockait les id des maps comportant des zaaps. Fou de joie, j'ai directement essayé de faire mon algo, jusqu'à ce que je me rende compte que toutes les maps stockées n'étaient pas celles que j'attendais (pas des zaaps). S'agit-il des transporteurs brigandins et autres zaap de wabbit (forreuse)? Quelqu'un aurait-il une idée? (par exemple les maps [2, -5], [21, 6], et d'autres encore...)

Aussi, j'ai une idée de ce que représente les valeurs de worldMap du fichier MapPositions.d2o : il s'agit d'après-moi de "plans" sur lequel le personnage peut bouger. Un peu comme des zones (mais différent tout de même). Quelqu'un aurait-il plus d'information là-dessus?

Je vous embrasse. :*