Résolu WorldGraph (projet de pathFinding)

NollyLaRune · 24 Avril 2022

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:

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.

Code:

"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 · 25 Avril 2022

NollyLaRune a dit:

Je n'ai toujours pas la réponse. J'imagine que les deux sont possibles.

NollyLaRune a dit:

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

NollyLaRune · 27 Avril 2022

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 · 28 Avril 2022

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 · 30 Avril 2022

Merci pour la réponse Asura

Asura a dit:

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 · 30 Avril 2022

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 · 1 Mai 2022

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:

C#:

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:

C#:

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[i].MapChangeData & check) != 0 && ((map.Cells[i].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[i].Mov)
                        {
                            bool possible = false;

                            switch (direction)
                            {
                                case MovementDirectionEnum.North:
                                    if (map.Cells[i].TopArrow == true)
                                        possible = true;
                                    break;
                                case MovementDirectionEnum.South:
                                    if (map.Cells[i].BottomArrow == true)
                                        possible = true;
                                    break;
                                case MovementDirectionEnum.East:
                                    if (map.Cells[i].LeftArrow == true)
                                        possible = true;
                                    break;
                                case MovementDirectionEnum.West:
                                    if (map.Cells[i].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/alexandre10044/Pathfinder-2.0

NollyLaRune · 2 Mai 2022

Merci BlueDream!

BlueDream a dit:

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

NollyLaRune · 5 Mai 2022

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

NollyLaRune a dit:

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?

hadamard · 5 Mai 2022

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:

```

Snipet change map to dest:

@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 · 5 Mai 2022

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 · 5 Mai 2022

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

hadamard · 5 Mai 2022

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 · 5 Mai 2022

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 · 6 Mai 2022

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

hadamard a dit:

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:

Code:

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.

NollyLaRune · 3 Juin 2022

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. :*

Résolu WorldGraph (projet de pathFinding)

NollyLaRune

Membre

NollyLaRune

Membre

NollyLaRune

Membre

Asura

Membre

NollyLaRune

Membre

Asura

Membre

BlueDream

Administrateur

NollyLaRune

Membre

NollyLaRune

Membre

hadamard

Membre

hadamard

Membre

hadamard

Membre

hadamard

Membre

NollyLaRune

Membre

NollyLaRune

Membre

NollyLaRune

Membre