|
alors comment ca marche
- j'ai un script qui parse ce fichier et qui insère chaque kill dans une table, et chaque entité dans une autre (une entité est un troll ou un monstre qui a tué ou s'est fait tuer). la 2e table contient donc tous les trolls et monstres qui ont au moins un event "mort" (la leur ou celle des autres)
l'algo est un Dijkstra classique, à ceci près que je le fais en symétrique : je pars a la fois du troll de départ et de celui de destination, et je regarde ou ca se rejoint au milieu
pour ceux qui connaissent pas le Dijkstra, le principe est simple :
- tu prends ton noeud de départ - tu prends tous les noeuds liés à ton noeud de départ (ici ceux qui ont tué ou été tués par ton noeud de départ) - tu prends tous les noeuds liés à ceux-là, mais tu enlèves ceux que tu connais deja : si A a tué B et C, et que A a aussi tué C, le chemin le plus court c'est A - C, pas A - B - C et ainsi de suite, tu t'arrêtes dès que dans ta liste tu as le noeud que tu cherches
j'ai été obligé de faire ça en symétrique (en partant de 2 extrémités simultanément parce que la plupart des trolls ont une quantité colossale de kills, donc en comptant en moyenne 200 kills par troll, tu multiplies le nombre de noeuds a stocker par 200 a chaque étape. donc 4 étapes ca commence a faire beaucoup. si tu pars des deux côtés, ca limite beaucoup (pour donner un exemple, imaginons que tu as 4 étapes; si tu fais que dans un sens tu vas faire 1 - 200 - 40000 - 8000000
si tu fais dans les deux sens, tu vas faire deux fois 1 -200 - 40000 soit un total de 400K au lieu de 8M
après j'ai quelques optimisations spécifiques, comme la création d'une table pour les trolls/monstres qui ont qu'un seul événement de mort (parce qu'ils ne peuvent pas servir de relai entre deux trolls), ca divise par 10 environ le nombre d'entités considérées
bref, c'était fun à faire
et globalement, ma base est une postgres, et j'ai tout dev manuellement en php
Raistlin
|
