Concours de rentrée 2021 - La Geste d'Alrys

[SlyVTT]

Wahou, très sympa ton outil !
je me suis basé sur un A*, mais en divisant les tiles, du coup ça multiplie les cellules et c'est hyper lent...

Dubs, j'ai pensé à ton A* qui est lent, ce que tu peux faire:
- Tu fais une première passe de ton algo sans subdiviser les cases, en restant avec ta grille de 146*91, cela te permet de dégrossir et de trouver un chemin proche de l'optimum.
- Sur la base de ce chemin préliminaire, tu augmentes la densité de ta grille localement (par exemple les cases de ton premier chemin avec+/-1 ou 2 cases autours,
- Tu relances l'optimisation A* sur cette nouvelle grille, ce qui va limiter le nb de tests à faire.

Note; si ca fonctionne, tu peux itérer plusieurs fois de manière à densifier énormément la grille.

La partie complexe sera clairement de créer les liens type "Neighbours" et de mettre la ponderation ad-hoc car fonction de la taille de la cellule.

A plus

Sly

[Dubs]

Wahou, très sympa ton outil !
je me suis basé sur un A*, mais en divisant les tiles, du coup ça multiplie les cellules et c'est hyper lent...

Dubs, j'ai pensé à ton A* qui est lent, ce que tu peux faire:
- Tu fais une première passe de ton algo sans subdiviser les cases, en restant avec ta grille de 146*91, cela te permet de dégrossir et de trouver un chemin proche de l'optimum.
- Sur la base de ce chemin préliminaire, tu augmentes la densité de ta grille localement (par exemple les cases de ton premier chemin avec+/-1 ou 2 cases autours,
- Tu relances l'optimisation A* sur cette nouvelle grille, ce qui va limiter le nb de tests à faire.

Note; si ca fonctionne, tu peux itérer plusieurs fois de manière à densifier énormément la grille.

La partie complexe sera clairement de créer les liens type "Neighbours" et de mettre la ponderation ad-hoc car fonction de la taille de la cellule.

A plus

Sly

hé hé, c'est grosso modo ce que j'ai fait (réduire les zones à utiliser pour l'algo en utilisant des a* sur une grille de 146x91)
ce sont les calculs pour vérifier que les cases sont bien accessibles qui prend du temps (ne pas traverser une montagne en cours de chemin par ex)

j'ai presque fini tout ça, je devrai livrer bientôt la prochaine version
merci pours les astuces !

[SlyVTT]

hé hé, c'est grosso modo ce que j'ai fait (réduire les zones à utiliser pour l'algo en utilisant des a* sur une grille de 146x91)
ce sont les calculs pour vérifier que les cases sont bien accessibles qui prend du temps (ne pas traverser une montagne en cours de chemin par ex)

j'ai presque fini tout ça, je devrai livrer bientôt la prochaine version
merci pours les astuces !

En fait pour gagner du temps, il faut bien préparer sa grille de connection avant de lancer le A*
1/ tu crées une grille de "nodes" qui contient un drapeau "obstacle" poouvant etre true/false (true = montage ou ocean non navigable)
2/ ensuite tu balayes l'ensemble de ta grille de noeuds pour créer les connections (vecteur de pointeurs sur les nodes adjacents (diagonal et directement a côté) :
- si le voisin a le drapeau "obstacle" à false, tu peux le visiter donc tu le mets dans ta liste de voisin pour le noeud courant
- sinon tu ne le mets pas.
ensuite tu deroules ton algo A* juste avec les voisins, tu n'as plus besoin de regarder si c'est un obstacle ou non.


si la configuration change (par exemple tu as le bateau, donc les oceans ne sont plus des obstacles) tu effaces tous les voisins de tous les noeuds et tu refais le mapping.

Va faire un tour ici, je me suis fortement inspiré de la methode de Javidx pour batir le squelette de mon algo A* :

https://github.com/OneLoneCoder/videos/ ... _AStar.cpp

https://www.youtube.com/watch?v=icZj67PTFhc

A plus

Sly

[Dubs]

hé hé, c'est grosso modo ce que j'ai fait (réduire les zones à utiliser pour l'algo en utilisant des a* sur une grille de 146x91)
ce sont les calculs pour vérifier que les cases sont bien accessibles qui prend du temps (ne pas traverser une montagne en cours de chemin par ex)

j'ai presque fini tout ça, je devrai livrer bientôt la prochaine version
merci pours les astuces !

En fait pour gagner du temps, il faut bien préparer sa grille de connection avant de lancer le A*
1/ tu crées une grille de "nodes" qui contient un drapeau "obstacle" poouvant etre true/false (true = montage ou ocean non navigable)
2/ ensuite tu balayes l'ensemble de ta grille de noeuds pour créer les connections (vecteur de pointeurs sur les nodes adjacents (diagonal et directement a côté) :
- si le voisin a le drapeau "obstacle" à false, tu peux le visiter donc tu le mets dans ta liste de voisin pour le noeud courant
- sinon tu ne le mets pas.
ensuite tu deroules ton algo A* juste avec les voisins, tu n'as plus besoin de regarder si c'est un obstacle ou non.


si la configuration change (par exemple tu as le bateau, donc les oceans ne sont plus des obstacles) tu effaces tous les voisins de tous les noeuds et tu refais le mapping.

Va faire un tour ici, je me suis fortement inspiré de la methode de Javidx pour batir le squelette de mon algo A* :

https://github.com/OneLoneCoder/videos/ ... _AStar.cpp

https://www.youtube.com/watch?v=icZj67PTFhc

A plus

Sly

je l'ai fait en mode "pixel" pour l'instant, façon pré-histoire en mode bourrin, on verra plus tard les optis.


J'ai mis à jour l'appli !

Elle est beaucoup plus réactive.
j'espère n'avoir rien cassé...

[SlyVTT]

Je vais tester ça.
Je suis pris ce WE mais je te fais des retour dès que possible.
Je sais pas ce que tu as fait sur la routine de calcul, mais visiblement tu as donné du dopage à Python
Ciao
Sly

[Dubs]

J'ai réussi à accrocher les 1820 !

J'ai des idées pour la prochaine version :
Fusionner deux scripts pour ne garder que les meilleurs segments ( ça permet de travailler sur des tronçons de voie sans tout refaire )
Faire du multi sélection de points, pour en déplacer plusieurs à la fois.

[SlyVTT]

J'ai réussi à accrocher les 1820 !

J'ai des idées pour la prochaine version :
Fusionner deux scripts pour ne garder que les meilleurs segments ( ça permet de travailler sur des tronçons de voie sans tout refaire )
Faire du multi sélection de points, pour en déplacer plusieurs à la fois.

Cool, super que tu sois dans la course

[Pavel]

J'ai des idées pour la prochaine version :
Fusionner deux scripts pour ne garder que les meilleurs segments ( ça permet de travailler sur des tronçons de voie sans tout refaire )
Faire du multi sélection de points, pour en déplacer plusieurs à la fois.

Inspiré par ton superbe logiciel, j'ai expérimenté un peu avec des configurations d'interface utilisateur et j'ai trouvé qu'une combinaison d'une vue graphique avec un éditeur de texte est assez puissante et facile à programmer.

L'éditeur de texte me permet de modifier (copier, coller, réorganiser, etc.) les coordonnées plus flexiblement et précisément que la vue graphique.

Voici le code et une capture d'ecran pour illustrer l'idée.

J'ai aussi une remarque sur la partie Python dans les nouvelles versions de ton appli. Je pense que les problèmes de validation des fichiers Python générés par les versions précédentes étaient plutôt liés à la différence de représentation des nombres en mémoire et en ligne de caractères. Il est également possible de générer avec Python une liste de déplacements qui ne passent pas la validation. Donc, je ne pense pas que la passage au Python résout complètement le problème, mais ralentit beaucoup les calculs.

La fonction getmap fournie avec les scripts pour les calculatrices est très lente. Je l'ai remplacé par une version plus rapide.

[critor]

Merci pour tes partages.

La fonction getmap fournie avec les scripts pour les calculatrices est très lente. Je l'ai remplacé par une version plus rapide.

Désolé, mais si je ne compressais pas la carte ça ne passait pas sur NumWorks, machine où le Python est limité à 32K de tas/heap.

C'est vrai que j'aurais pu faire une version différente non compressée pour les machines correctement dotées en mémoire, mais après ça double le travail de maintenance en cas de nécessité de mises à jour.

[Hayleia]

Pour les gens qui font des outils PC et qui trouvent que getmap est lent, j'ai ce bout de code pour la lire une fois pour toutes sans avoir à hardcoder la map dans le code (ce qui serait relou en cas de mise à jour)

Code: Select all

# read the map if available, or generate it for the next times
try:
   print('reading map from file')
   with open('map.pickle', 'rb') as file:
      map = pickle.load(file)
   assert isinstance(map, list)
   assert all([isinstance(row, list) and len(row) == len(map[0]) for row in map])
   assert all([all([isinstance(i, int) and 0<=i<=7 for i in row]) for row in map])
except:
   print('jk reading map from alryslib')
   print("NEXT TIMES WON'T BE SLOW I PROMISE")
   map = [[alryslib.getmap(0,0)[0]]]
   def growMap(processBooleans):
      canGrowRight = True
      canGrowDown = True
      while canGrowRight or canGrowDown:
         if canGrowRight:
            for y in range(len(map)):
               map[y].append(alryslib.getmap(len(map[-1]), y)[0])
         if canGrowDown:
            map.append([alryslib.getmap(x,len(map))[0] for x in range(len(map[0]))])

         canGrowRight = not all([v == map[0][-1] for v in [map[y][-1] for y in range(len(map))]])
         canGrowDown = not all([v == map[-1][0] for v in map[-1]])

      canGrowRight = processBooleans(canGrowRight)
      canGrowDown = processBooleans(canGrowDown)

   growMap(lambda b: not b)
   growMap(lambda b: b)

   try:
      with open('map.pickle', 'wb') as file:
         pickle.dump(map, file)
   except:
      pass