π
<-
Chat plein-écran
[^]

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

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

Message non lude SlyVTT » 15 Oct 2021, 12:32

Dubs a écrit: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
Some works in progress :
The GUI Toolkit NF for nSpireMyShmup for fxCG-50Magic Light for Casio Graph 90+E
and
Magic Light for nSpire CX/CX-II
Simple Text Editor for nSpireOutRun for Casio Graph 90+E
95%
50%
100%
75%
100%
And more to come ... stay tuned
Avatar de l’utilisateur
SlyVTTPremium
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Prochain niv.: 43%
 
Messages: 481
Images: 31
Inscription: 19 Jan 2021, 09:41
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
GitHub: SlyVTT

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

Message non lude Dubs » 15 Oct 2021, 12:53

SlyVTT a écrit:
Dubs a écrit: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 !
Avatar de l’utilisateur
DubsVIP++
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Prochain niv.: 37.9%
 
Messages: 125
Inscription: 06 Jan 2016, 13:44
Genre: Homme
Calculatrice(s):
MyCalcs profile

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

Message non lude SlyVTT » 15 Oct 2021, 13:10

Dubs a écrit:
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
Some works in progress :
The GUI Toolkit NF for nSpireMyShmup for fxCG-50Magic Light for Casio Graph 90+E
and
Magic Light for nSpire CX/CX-II
Simple Text Editor for nSpireOutRun for Casio Graph 90+E
95%
50%
100%
75%
100%
And more to come ... stay tuned
Avatar de l’utilisateur
SlyVTTPremium
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Prochain niv.: 43%
 
Messages: 481
Images: 31
Inscription: 19 Jan 2021, 09:41
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
GitHub: SlyVTT

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

Message non lude Dubs » 15 Oct 2021, 16:16

SlyVTT a écrit:
Dubs a écrit:
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é...
Avatar de l’utilisateur
DubsVIP++
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Prochain niv.: 37.9%
 
Messages: 125
Inscription: 06 Jan 2016, 13:44
Genre: Homme
Calculatrice(s):
MyCalcs profile

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

Message non lude SlyVTT » 15 Oct 2021, 16:48

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
Some works in progress :
The GUI Toolkit NF for nSpireMyShmup for fxCG-50Magic Light for Casio Graph 90+E
and
Magic Light for nSpire CX/CX-II
Simple Text Editor for nSpireOutRun for Casio Graph 90+E
95%
50%
100%
75%
100%
And more to come ... stay tuned
Avatar de l’utilisateur
SlyVTTPremium
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Prochain niv.: 43%
 
Messages: 481
Images: 31
Inscription: 19 Jan 2021, 09:41
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
GitHub: SlyVTT

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

Message non lude Dubs » 16 Oct 2021, 07:13

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.
Avatar de l’utilisateur
DubsVIP++
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Prochain niv.: 37.9%
 
Messages: 125
Inscription: 06 Jan 2016, 13:44
Genre: Homme
Calculatrice(s):
MyCalcs profile

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

Message non lude SlyVTT » 16 Oct 2021, 07:41

Dubs a écrit: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 ;-)
Some works in progress :
The GUI Toolkit NF for nSpireMyShmup for fxCG-50Magic Light for Casio Graph 90+E
and
Magic Light for nSpire CX/CX-II
Simple Text Editor for nSpireOutRun for Casio Graph 90+E
95%
50%
100%
75%
100%
And more to come ... stay tuned
Avatar de l’utilisateur
SlyVTTPremium
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Prochain niv.: 43%
 
Messages: 481
Images: 31
Inscription: 19 Jan 2021, 09:41
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
GitHub: SlyVTT

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

Message non lude Pavel » 16 Oct 2021, 11:21

Dubs a écrit: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.
Avatar de l’utilisateur
PavelPremium
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Prochain niv.: 83.6%
 
Messages: 107
Inscription: 19 Sep 2018, 10:50
Genre: Homme
Calculatrice(s):
MyCalcs profile

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

Message non lude critor » 16 Oct 2021, 11:26

Merci pour tes partages. :)

Pavel a écrit: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.
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.8%
 
Messages: 41464
Images: 14477
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

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

Message non lude Hayleia » 16 Oct 2021, 11:53

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: Tout sélectionner
# 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

Image
ImageImageImage
Pokemon Topaze (Axe) discussion and download links here
(19:29:36) noelnadal: plus sérieusemen​t, j'ai très peu de problèmes
(22:45:44) Clifward: J'aime rire du malheur des autres :troll:

(2017.11.18 - 17:07:12) Fireworks: Hayleia !!!!!
(2017.11.18 - 17:07:19) TI-Bot: Fireworks has been logged out (Kicked).
(2017.11.18 - 17:07:22) TI-Bot: Ban of user Fireworks revoked.
(2017.11.18 - 17:07:25) TI-Bot: Fireworks logs into the Chat.
(2017.11.18 - 17:07:28) Fireworks: <3
(2017.11.18 - 17:07:31) Fireworks: 208
Avatar de l’utilisateur
HayleiaGénéreux
Niveau 17: GM (Grand Maître des calculatrices)
Niveau 17: GM (Grand Maître des calculatrices)
Prochain niv.: 43.8%
 
Messages: 2509
Images: 2
Inscription: 30 Aoû 2011, 08:22
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: Templar

PrécédenteSuivante

Retourner vers News Divers

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 33 invités

-
Rechercher
-
Social TI-Planet
-
Sujets à la une
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
Phi NumWorks jailbreak
123
-
Faire un don / Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
Faire un don
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
826 utilisateurs:
>814 invités
>8 membres
>4 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)