« 1 2 (3) 4 5 »


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
19/03/2016 15:30
De Belgique
Post(s): 1637
Il y a du mieux mais ce n'est pas encore parfait, malheureusement, car il y a encore des tuiles qui sont sautées et d'autre ou ça fait un "crochet" inutile. Sinon, par curiosité, j'ai testé avec une carte générée en carré, là c'est nickel.

Je ne crois pas que ce soit mon code qui génère les points de passages qui bug, car il ne fait que suivre au prorata de la liste.

for point in scene.objects: # vérifier tout les objets un par un
        if 'type_case' in point: # vérifier que les objets ayant cette propriété, les tuiles
            if path != []: # tant que la liste est plaine
                if path[0][0] == point['lineX'] and path[0][1] == point['lineY']: # on regarde si le contenu de la tuile correspond avec la liste, si c'est le cas, creer un point de passage vert
                    scene.objects['spawn_jou'].worldPosition[0] = point.worldPosition[0]
                    scene.objects['spawn_jou'].worldPosition[1] = point.worldPosition[1] # on positionne l'empty sur la tuile trouvée
                    scene.addObject('pt_pass_unit', scene.objects['spawn_jou'], 0) # on créer le point de passage "visuel"
                    obj['index_move'] += 1 # ça, c'est le nombre de point de passage a atteindre au total
                    path.pop(0) # on supprime le premier élément de la liste puis on recommence le cycle de vérification


Pour le script Voronoï, je n'arrive pas à comprendre ou je dois indiquer le nombre de pixel. Le script demande un argument 'point' mais n'accepte ni les "integers" ni les "floats", j'ai tenté d'analyser la démo, mais l'autaur indique une résolution X & Y + un radius de 3 ajouté sur chacun (mais c'est pour Tkinter on dirai ?).

Contribution le : 10/04 11:11:32
Créer un fichier PDF de la contribution Imprimer


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
23/02/2006 18:10
De Alpes-Maritimes
Post(s): 2548
J'ai trouvé cette documentation qui donne différentes façons de faire pour le pathfinding dans des map à base d'hexagone.
https://www.redblobgames.com/grids/hexagons/

Par contre, je suis assez fatigué depuis hier pour diverses raisons. Même pour mes projets persos de programmation, ça va aller assez doucement je pense.
Je pourrai pas trop regarder attentivement tout ça aujourd'hui, peut-être ce weekend si je peux me reposer davantage.

Contribution le : 10/04 11:46:19
_________________
Venez tester notre projet de Blender Clan 2.0 + Tchat (en cours de développement) !
Pourquoi ? Retrouver un forum fonctionnel.
Créer un fichier PDF de la contribution Imprimer


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
19/03/2016 15:30
De Belgique
Post(s): 1637
Je comprends, reposes-toi bien .

J'ai tenté d'analyser plus en profondeur le script et j'ai remarqué qu'il y avais pas mal de choses inutiles et aussi des choses incohérentes.

Parmi tout ça, j'ai pu comprendre ceci:

for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1)]: # Adjacent squares


Ça, c'est ce qui permet d'identifier les case avoisinantes et donc les possibles destinations.

Par contre, je n'arrive pas à comprendre comment je dois faire en sorte de choisir la bonne case.

J'ai fais un croquis

Les lignes ou il y a continue, je comprends pas leurs sens.

Quelqu'un sait m'expliquer ?

Contribution le : 10/04 16:46:52
Créer un fichier PDF de la contribution Imprimer


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
23/02/2006 18:10
De Alpes-Maritimes
Post(s): 2548
Citation :

Redstar a écrit:
j'ai remarqué qu'il y avais pas mal de choses inutiles et aussi des choses incohérentes.


Lesquelles ?

Citation :

Redstar a écrit:
Par contre, je n'arrive pas à comprendre comment je dois faire en sorte de choisir la bonne case.


C'est avec le calcul de "f".
f = g + h

g est la distance au point de départ, incrémenté à chaque case.
h est une estimation de la distance entre la case testée et la fin du parcours.

Dans l'algorithme on additionne les deux et on choisit, parmi les cases environnantes, celle qui minimise donc ces deux valeurs. On obtient alors un chemin pour aller du départ à la fin (pas forcément le plus optimal).

Citation :

Redstar a écrit:
Les lignes ou il y a continue, je comprends pas leurs sens.


"continue" est un mot-clé du langage. Il intervient dans une boucle (for, while). Son but est tout simplement de zapper le tour de boucle actuel.

Contribution le : 10/04 21:33:06
_________________
Venez tester notre projet de Blender Clan 2.0 + Tchat (en cours de développement) !
Pourquoi ? Retrouver un forum fonctionnel.
Créer un fichier PDF de la contribution Imprimer


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
19/03/2016 15:30
De Belgique
Post(s): 1637
Je n'en suis plus sûr moi-même, plus j'avance et plus je perds le fil...

- Donc:
- Ma position de départ, si je reprends mon croquis, c'est (2, 2).
- Ma position finale (point rouge), c'est (5, 6).
- Tu dis que "g" est la distance entre le point de départ et le point actuel... mais le point actuel, pour le premier cycle de calcul, est null, c'est bien ça ?
- Tu dis que "h" est la distance entre le point actuel et le point final, or, pour le premier cycle, le point actuel est null.

J'ai 6 possibilité de déplacement, (2, 1), (2, 3), (1, 2), (3, 2), (1, 1), (1, 3)

Mais quel type de distance est-ce ? La distance "getDistanceTo()" ou une autre distance ?

Si c'est avec "getDistanceTo()", c'est 1,95. Et après, que dois-je faire avec ça ?

Contribution le : 11/04 10:23:33
Créer un fichier PDF de la contribution Imprimer


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
23/02/2006 18:10
De Alpes-Maritimes
Post(s): 2548
Quand tu lances l'algorithme, g est à zéro.
Quand tu avances d'une case, il passe à 1. Puis 2, ...

Ton schéma ne me plait pas trop. J'aurais inversé les coordonnées pour coller à la façon dont c'est agencé dans un tableau.
J'en ai donc refait un sur lequel je vais me baser pour les explications.

Je pars de la case (2,2) et je veux aller en (5,6).
Sur la case (2,2), j'avais g et h à zéro.
g = 0 car on est sur la toute première case, donc elle a aucune distance d'elle-même.
h = 0 parce qu'on s'en fout. Dans l'algorithme on vérifie déjà que le départ et l'arrivée ne sont pas la même case. Donc le départ est forcément différent de l'arrivée, donc éloignée.

On regarde les cases aux alentours de (2,2).
On a donc [(1,1), (1,2), (2,3), (3,2), (3,1), (2,1)].



Pour chacune, on prend g = g_actuel + 1.
Ici, le g de la case en cours (2,2) est 0. Donc g = 0 + 1 = 1 pour toutes les cases alentours [(1,1), (1,2), (2,3), (3,2), (3,1), (2,1)].

Pour h, on applique le théorême de Pythagore c² = a² + b².
https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Pythagore

Je précise qu'il s'agit d'une heuristique et non d'une distance. Si on voulait vraiment la distance, il faut calculer la racine carrée de h. Or, c'est d'un côté inutile car on veut simplement faire une comparaison des valeurs et non mesurer exactement la distance (on n e sait pas s'il y aura un obstacle qui nous obligera à faire un détour). De plus, la racine carrée est une opération très coûteuse dont on se passera volontiers.

Ici, on a h = c².
Donc h = a² + b².

Pour a, on prend la différence des coordonnées x entre la case testée et la case d'arrivée.
Pour b, on prend la différence des coordonnées y entre la case testée et la case d'arrivée.

Voici ce que ça donne pour les 6 cases à tester autour de (2,2) :
(1,1): h = (1 - 5)² + (1 - 6)² = 41
(1,2): h = (1 - 5)² + (2 - 6)² = 32
(2,3): h = (2 - 5)² + (3 - 6)² = 18
(3,2): h = (3 - 5)² + (2 - 6)² = 20
(3,1): h = (3 - 5)² + (1 - 6)² = 29
(2,1): h = (2 - 5)² + (1 - 6)² = 34

On calcule ensuite f = g + h pour les 6 cases testées.
(1,1): f = 1 + 41 = 42
(1,2): f = 1 + 32 = 33
(2,3): f = 1 + 18 = 19
(3,2): f = 1 + 20 = 21
(3,1): f = 1 + 29 = 30
(2,1): f = 1 + 34 = 35

On prend enfin la case dont la valeur de f est la plus petite parmi les 6.
Ici, c'est (2,3) car son f = 19 est le plus petit.

On va donc maintenant passer à la case (2,3) et faire le test des 6 cases alentours. On sait qu'on est déjà passés par la case (2,2) donc on ne va pas la prendre en considération, c'est ce que fait l'algorithme.

On a donc les cases suivantes : [(1,2), (1,3), (2,4), (3,3), (3,2)].
On a donc g = g_actuel + 1.
Pour (2,3), g = 1.
Pour toutes les cases autour de (2,3), g = 1 + 1 = 2.



Pour h, on refait la même choses, c'est à dire le théorême de Pythagore.
(1,2): h = (1 - 5)² + (2 - 6)² = 32
(1,3): h = (1 - 5)² + (3 - 6)² = 25
(2,4): h = (2 - 5)² + (4 - 6)² = 13
(3,3): h = (3 - 5)² + (3 - 6)² = 13
(3,2): h = (3 - 5)² + (2 - 6)² = 20

On calcule f = g + h.
(1,2): f = 2 + 32 = 34
(1,3): f = 2 + 25 = 27
(2,4): f = 2 + 13 = 15
(3,3): f = 2 + 13 = 15
(3,2): f = 2 + 20 = 22

Oh ! On a deux cases ex-aequo : (2,4) et (3,3). Ben on en prend une des deux, à tous hasard la première de la liste. Choisissons (2,4) pour continuer.


Bon, tu vois le principe de l'algorithme.
Si on continue, on va avoir le chemin suivant : (2,2) (2,3) (2,4) (3,4) (4,5) (4,6) (5,6)

Contribution le : 11/04 11:31:04
_________________
Venez tester notre projet de Blender Clan 2.0 + Tchat (en cours de développement) !
Pourquoi ? Retrouver un forum fonctionnel.
Créer un fichier PDF de la contribution Imprimer


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
23/02/2006 18:10
De Alpes-Maritimes
Post(s): 2548
Oh, j'oubliais.
Si tu te poses la question de l'intérêt de g, ce qui est évidemment douteux dans le cas que je t'ai présenté : il sert lorsqu'il y a un obstacle.

J'en ai pas parlé ici pour ne pas faire trop de choses d'un coup.

Contribution le : 11/04 11:49:03
_________________
Venez tester notre projet de Blender Clan 2.0 + Tchat (en cours de développement) !
Pourquoi ? Retrouver un forum fonctionnel.
Créer un fichier PDF de la contribution Imprimer


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
19/03/2016 15:30
De Belgique
Post(s): 1637
edit:

Ok, je suis parvenu à faire fonctionner tout ça. Par contre, le deuxième cycle contient un doublon, que j'ai pu supprimer, mais au cycle n°6, il y a deux cases dont une qui fait faire un crochet inutile. Comment supprimer celui-là, alors que les valeurs (f) ne sont pas des doublons cette fois ?

class Node():
    def __init__(self, start, end):
        self.derniere_position = start
        self.destination_suivante = end
        self.case_suivante = None
        
        self.g = 0
        self.h = 0
        self.f = 0

def test():
    compteur = 0
    chemin = []
    liste_tempon1 = []
    liste_tempon2 = []
    
    point_depart = obj['depart']
    point_arrivee = obj['dest_final']
    
    while obj['dest_final'] not in chemin:
        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (1, -1)]: # Adjacent squares
            node_a_chercher = Node(point_depart, point_arrivee)
            node_a_chercher.g = compteur + 1
            
            new_pos_possible = (node_a_chercher.derniere_position[0] + new_position[0], node_a_chercher.derniere_position[1] + new_position[1])
            node_a_chercher.case_suivante = new_pos_possible
            node_a_chercher.h = (new_pos_possible[0] - node_a_chercher.destination_suivante[0])**2 + (new_pos_possible[1] - node_a_chercher.destination_suivante[1])**2
            node_a_chercher.f = node_a_chercher.g + node_a_chercher.h
            
            if node_a_chercher.f not in liste_tempon2:
                liste_tempon1.append(node_a_chercher)
                liste_tempon2.append(node_a_chercher.f)
                #print(node_a_chercher.g, node_a_chercher.f)
            
        val_min = min(liste_tempon2)
        #print(node_a_chercher.g, val_min)
        for test in liste_tempon1:
            if test.f == val_min:
                chemin.append(test.case_suivante)
                point_depart = test.case_suivante
                liste_tempon1 = []
                liste_tempon2 = []
                compteur += 1
                #print('')
        
    print(chemin)

Contribution le : 13/04 11:28:26
Créer un fichier PDF de la contribution Imprimer


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
23/02/2006 18:10
De Alpes-Maritimes
Post(s): 2548
Peux-tu montrer l'image de ce que ça donne, j'ai la flemme de tout dérouler à la main...
Ou mieux, envoie le blend parce que je ne peux pas tester et j'y connais rien en BGE.

Contribution le : 13/04 20:38:18
_________________
Venez tester notre projet de Blender Clan 2.0 + Tchat (en cours de développement) !
Pourquoi ? Retrouver un forum fonctionnel.
Créer un fichier PDF de la contribution Imprimer


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
19/03/2016 15:30
De Belgique
Post(s): 1637
Voilà

"#print(node_a_chercher.g, val_min)" affiche le x cycle de test et val_min le résultat le plus petit

"#print(node_a_chercher.g, node_a_chercher.f)" te permettra d'avoir la liste des valeurs pour chaque cases.

J'en ai profité pour remettre la génération des points de passages pour le visuel. Je constates tout de même que sur la gauche, ça ne s'affiche pas très bien dans le sens ou ça saute une tuile.

Contribution le : 14/04 07:58:30
Créer un fichier PDF de la contribution Imprimer



 Haut   Précédent   Suivant
« 1 2 (3) 4 5 »




Enregistrer votre réponse
Compte*
Nom   Mot de passe   Authentification
Message:*



[Recherche avancée]



Sujets récemment répondus
Forums Sujets Réponses Lus Dernières contributions
[WIP] et travaux terminés La mare aux canards    [1][2] 10 97 Aujourd'hui 17:45:24
Rimpotche 
The Blender Clan 'tchat Benchmark EEVEE    [1][2][3] 24 727 Aujourd'hui 14:37:08
Bibi09 
[WIP] et travaux terminés Différents rendus 2.91 9 131 Aujourd'hui 12:05:20
Bibi09 
Questions & Réponses Render Layers qui n'apparaissent pas    [1][2] 10 100 Aujourd'hui 11:02:12
HarDrive 
Questions & Réponses Problème perso qui bouge des 2 côtés qu'avec 1 coté de l'armature et pas de l'autre    [1][2] 12 1881 Hier 15:14:53
Rimpotche 
The Blender Clan 'tchat Avenir du blender clan    [1][2][3]...[13] 123 8009 Hier 11:39:51
Bibi09 
Hors Sujet !! Nouveau tutoriel : Animation labiale simplifiée 2.9 3 68 Hier 10:07:35
moonboots 
Questions & Réponses [résolu] Problème avec les addons 2 76 Hier 09:42:19
Lamoyse 
Questions & Réponses SCAN 3D - Carrière - animation 6 82 Hier 07:23:48
Versatil 
Questions & Réponses [résolu] Texture Image en noir dans le rendu 3 265 23/09 15:10:30
Horemheb 
Moteur de jeu GameBlender et alternatives [non résolu] Cs (vaisseau)    [1][2][3]...[47] 467 140064 23/09 13:20:39
sbkodama 
Questions & Réponses [non résolu] Move to collection 8 107 22/09 21:15:48
JaAlVir657 
Questions & Réponses Boids, boids, boids...    [1][2] 18 327 22/09 20:53:24
JaAlVir657 
Python & Plugins [WIP] Transportation Add-on pour Blender 5 311 22/09 20:12:35
ferrari6 
[WIP] et travaux terminés Blender 2.9 les outils du sculpte 0 57 22/09 19:51:11
meltingman 
[WIP] et travaux terminés [WIP] Kanata et personnage secret coucours Blender 3D France    [1][2][3] 25 344 22/09 19:19:34
meltingman 
Questions & Réponses [non résolu] Simulation Tissu Temps Reel    [1][2] 14 242 22/09 16:57:22
ThierryT 
[WIP] et travaux terminés [WIP] Teeny Tiny - Story    [1][2][3]...[10] 99 7609 21/09 16:28:45
meltingman 
Le coin des geeks gain de fluidité viewport entre ryzen 3900X et 3950X    [1][2][3] 27 584 21/09 12:12:59
papillon 
Le coin des geeks Ralentissement du chargement de Blender 8 192 20/09 17:43:54
Rimpotche 

Qui est en ligne
104 utilisateur(s) en ligne (dont 72 sur Forums)

Membre(s): 0
Invité(s): 104


plus...
Nouveaux membres
RoccoMathe 25/9/2020
KaySkertch 25/9/2020
TerraWoodr 25/9/2020
Dacia4412 25/9/2020
KazukoKula 25/9/2020
DouglasKea 25/9/2020
GennieSly 25/9/2020
FranklinCh 25/9/2020
ArielleHed 25/9/2020
RollandFar 25/9/2020
Dernier Ajout
mirages-preview~0.jpg

Evènements à venir
Nov 18
Anniversaire de RichDeg
Dec 29
Anniversaire d'ebrain
Jan 9
BUG de Lyon
plus 264 plus d'élément(s)
 Par Mickaël Guédon [ebrain] © 2003-2020 The Blender Clan - hébergé par TuxFamily - Site déclaré à la CNIL sous le numéro 1155445