π
<-
Chat plein-écran
[^]

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

Online

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

Unread postby SlyVTT » 15 Oct 2021, 12:32

Dubs wrote: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
Developing the GUI Toolkit for nSpire
see current revision here : https://github.com/SlyVTT/Widget-for-TI-NSpire

And for the GUI Toolkit NF (New Foundation), this is here https://github.com/SlyVTT/Widgets-Spire-NF

Image Image Image Image
User avatar
SlyVTTPremium
Niveau 11: LV (Légende Vivante)
Niveau 11: LV (Légende Vivante)
Level up: 2.6%
 
Posts: 219
Images: 0
Joined: 19 Jan 2021, 09:41
Gender: Male
Calculator(s):

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

Unread postby Dubs » 15 Oct 2021, 12:53

SlyVTT wrote:
Dubs wrote: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 !
User avatar
DubsVIP++
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 84.4%
 
Posts: 89
Joined: 06 Jan 2016, 13:44
Gender: Male
Calculator(s):

Online

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

Unread postby SlyVTT » 15 Oct 2021, 13:10

Dubs wrote:
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
Developing the GUI Toolkit for nSpire
see current revision here : https://github.com/SlyVTT/Widget-for-TI-NSpire

And for the GUI Toolkit NF (New Foundation), this is here https://github.com/SlyVTT/Widgets-Spire-NF

Image Image Image Image
User avatar
SlyVTTPremium
Niveau 11: LV (Légende Vivante)
Niveau 11: LV (Légende Vivante)
Level up: 2.6%
 
Posts: 219
Images: 0
Joined: 19 Jan 2021, 09:41
Gender: Male
Calculator(s):

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

Unread postby Dubs » 15 Oct 2021, 16:16

SlyVTT wrote:
Dubs wrote:
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é...
User avatar
DubsVIP++
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 84.4%
 
Posts: 89
Joined: 06 Jan 2016, 13:44
Gender: Male
Calculator(s):

Online

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

Unread postby 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
Developing the GUI Toolkit for nSpire
see current revision here : https://github.com/SlyVTT/Widget-for-TI-NSpire

And for the GUI Toolkit NF (New Foundation), this is here https://github.com/SlyVTT/Widgets-Spire-NF

Image Image Image Image
User avatar
SlyVTTPremium
Niveau 11: LV (Légende Vivante)
Niveau 11: LV (Légende Vivante)
Level up: 2.6%
 
Posts: 219
Images: 0
Joined: 19 Jan 2021, 09:41
Gender: Male
Calculator(s):

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

Unread postby 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.
User avatar
DubsVIP++
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 84.4%
 
Posts: 89
Joined: 06 Jan 2016, 13:44
Gender: Male
Calculator(s):

Online

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

Unread postby SlyVTT » 16 Oct 2021, 07:41

Dubs wrote: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 ;-)
Developing the GUI Toolkit for nSpire
see current revision here : https://github.com/SlyVTT/Widget-for-TI-NSpire

And for the GUI Toolkit NF (New Foundation), this is here https://github.com/SlyVTT/Widgets-Spire-NF

Image Image Image Image
User avatar
SlyVTTPremium
Niveau 11: LV (Légende Vivante)
Niveau 11: LV (Légende Vivante)
Level up: 2.6%
 
Posts: 219
Images: 0
Joined: 19 Jan 2021, 09:41
Gender: Male
Calculator(s):

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

Unread postby Pavel » 16 Oct 2021, 11:21

Dubs wrote: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.
User avatar
PavelPremium
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 62.5%
 
Posts: 95
Joined: 19 Sep 2018, 10:50
Gender: Male
Calculator(s):

Online

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

Unread postby critor » 16 Oct 2021, 11:26

Merci pour tes partages. :)

Pavel wrote: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
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 24.3%
 
Posts: 38756
Images: 11320
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti
GitHub: critor

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

Unread postby 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: 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

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
User avatar
HayleiaGénéreux
Niveau 17: GM (Grand Maître des calculatrices)
Niveau 17: GM (Grand Maître des calculatrices)
Level up: 42.4%
 
Posts: 2503
Images: 2
Joined: 30 Aug 2011, 08:22
Gender: Not specified
Calculator(s):
Class: Templar

PreviousNext

Return to News Divers

Who is online

Users browsing this forum: No registered users and 23 guests

-
Search
-
Social
-
Featured topics
Concours Geometry Dash - 2 équipements complets en calculatrices TI (+ goodies et accessoires) à gagner pour les 2 meilleurs niveaux créés
Coque NumWorks édition limitée Novembre 2021 à gagner.
Comparaisons des meilleurs prix pour acheter sa calculatrice !
123
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...
Donate
Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
647 utilisateurs:
>624 invités
>17 membres
>6 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)

-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)