Pathfinder through maps

[Timorem]

Voilà le prochain challenge, réaliser un algorithme capable de trouver le chemin du bot pour aller d'une map à une autre et cela peut importe les moyens à emprunter.
C'est un algorithme de taille qui doit prendre en compte un tas de possibilités

Voici les critères :

• être capable de trouver un chemin depuis n'importe quelle map, vers n'importe quelle map accessible par le joueur.
• le trouver en un temps honorable (quelques secondes pas plus)
• pouvoir utiliser
  • les soleils (cell trigger)
  • les interactives objects téléporteurs
  • les npcs téléporteurs
  • les zaaps
  • les potions de téléportations
• et bien sûr ne pas se bloquer contre un mur :D

J'ai quelques idées pour le réaliser.

Tout d'abord il faudrait faire une sorte de map géante qui regrouperait les 5 600 000 cellules avec leur propriété (ça fait un truc assez lourd :p). Bien entendu on ne peut pas le charger directement dans le bot, ce serait beaucoup trop long et inutile.

L'idée serait alors de faire un outil qui calculerai des tas de chemins possibles qui relieraient les différentes subareas à l'aide du mappage géant (environ 1000 chemins). Avec ces chemins le bot pourrait passer d'une subarea à une autre en suivant le chemin. Ce qui sera plus compliqué à gérer ce sera les interactives objects et les cell triggers (quoique ce dernier peut être +/- deviné)

Reste à voir comment se déplacer dans les subareas. Et bien c'est beaucoup plus simple, on charge les maps de la subarea (il y a en a rarement plus d'une vingtaine) quand on change de subarea et on fait comme pour le mappage géant mais à plus petite échelle. Cela nous fait un pathfinding dans environ 10 000 cellules ce qui avec un pathfinding optimisé est honorable.

Maintenant ce qui est plus compliqué à gérer ce sont les "raccourcis", càd les zaaps, les potions, ...

Mais voilà en tout cas l'idée de départ.

[vendethiel]

var BankMap = GetNearestMap(Maps.Filter(x => x.HasNpc(NPC.Banker));
var walkingDist = GetMapDistance(CurrentMap, BankMap);
var ZaapMaps = Maps.Filter(x => x.HasInteractiveObject(IO.Zaap));
var zaapDist = GetMapDistanceToNearest(CurrentMap, ZaapMaps) + GetMapDistanceToNearest(BankMap, ZaapMaps);

BOURRIN

[Timorem]

...

Très drole

[FastFrench]

Hello,

j'avais commencé à coder un algo de PathFinding au niveau du monde. In fine, on arrive à quelque chose d'assez proche de ce que tu proposes, même si j'ai pris le problème dans l'autre sens. En effet, je pars non pas du principe que toutes les cellules de toutes les maps sont mises à plat, car ça pose d'emblée pas mal de problèmes (perfs, mémoire, affichage...). Donc je pars du principe que je fais un PathFinding au niveau des maps.
Simplement, comme certaines maps contiennent plusieurs zones non communiquantes, je coupe chaque map en autant de "submaps" qu'il y a de zones isolées au sein de la map.
La détection de ces zones est assez simple, avec un algorithme dérivé du A*.

En pratique, cela signifie que chaque cellule est associée à un identifiant de map et un identifiant de submap. A chaque submap est associée la liste des submaps voisines (accessibles directement). Les portails sont assez simple à prendre en compte dans le PathFinding en ajoutant les voisinages correspondant (avec éventuellement une pénalité dans l'algo A* associée à l'usage des portails payants). Ce qui est plus délicat, c'est d'utiliser effectivement le portail une fois dans la bonne map.

Dans mon proto, j'effectuais tous les calculs associés à la détection des submaps et la détermination des voisins au chargement initial des cartes. Ca rend ce chargement un peu long (mais ça reste acceptable), donc on peut envisager de stocker ces infos pour ne pas avoir à les recalculer à chaque fois. Mais du coup l'usage d'une BdD devient souhaitable, ou alors passer par un format propriétaire efficace pour permettre un chargement rapide.

[Timorem]

C'est exactement l'idée que j'ai eu et qu'on a travaillé avec Tidus (seulement j'appelle ça des Regions et pas des submap, mais submap est définitivement mieux :p)
En ce qui concerne la DB je préfère éviter au maximum la dépendance à des données sur le net, on peut très bien faire tous les calculs au premier lancement et ensuite les stocker dans un fichier formaté intelligemment.
En ce qui concerne ce fichier il faudrait faire quelque chose d'indexé pour pouvoir s'y référer dynamiquement et pas tout charger d'un coup, mais ce ne sera pas très dur à réaliser.

Pour les portails j'ai pas vraiment planché dessus.

[vendethiel]

Now named "Maptraveling"

[Jean22]

Je voulais demander où on se situait au niveau du dev du pathfinder. En regardant le code j'ai trouvé des méthodes pour trouver une path entre deux maps, deux cells mais pas encore de méthodes prenant en charge le déplacement d'un personnage d'une map à l'autre. Est ce un oubli de ma part, ou elle n'est pas encore implémentée?

[Timorem]

Ce sera implémentée prochainement