« 1 2 (3) 4 5 »


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
19/03/2016 15:30
De Belgique
Post(s): 1615
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): 2375
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
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): 1615
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): 2375
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
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): 1615
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): 2375
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
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): 2375
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
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): 1615
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): 2375
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
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): 1615
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 [WIP] Teeny Tiny - Story    [1][2][3]...[5] 44 4000 Aujourd'hui 17:48:45
Bibi09 
Moteur de jeu GameBlender et alternatives [WIP] DeadSigns FPS horreur - Première version disponible !    [1][2][3]...[58] 577 98251 Aujourd'hui 17:24:51
Hook 
[WIP] et travaux terminés [WIP] Tutoriel vidéo et création de mon prochain court métrage 4 218 Aujourd'hui 15:58:49
Bibi09 
Questions & Réponses switch entre IK/FK 4 48 Hier 18:54:05
prometheusx 
Questions & Réponses Je bloque sur la modélisation de ce verre! Avez-vous une solution? 8 256 Hier 13:23:47
debutant 
Questions & Réponses [non résolu] cloth: déformation bizzarre au rendu 3 72 07/08 09:21:18
Arielboid 
Questions & Réponses les cheveux longueur 1 56 06/08 19:53:18
Rimpotche 
Questions & Réponses ADDON MB - Lab 0 64 06/08 15:29:23
GI-jo13 
Questions & Réponses [résolu] en sculpt mode 5 185 04/08 18:21:10
prometheusx 
Questions & Réponses [résolu] Array circulaire 2 151 04/08 15:22:46
Redstar 
Questions & Réponses Addon pour textures procedurales 2 150 02/08 20:11:35
Crocodile_13 
Questions & Réponses avis animation marche :)    [1][2][3][4] 34 742 02/08 20:03:14
prometheusx 
[WIP] et travaux terminés [terminé] court métrage 2020    [1][2] 13 886 02/08 15:28:29
flahaut 
Questions & Réponses [résolu] Générique, sous-titres etc 3 155 02/08 09:18:02
Corpia 
Questions & Réponses [résolu] Scène prend la couleur du fond    [1][2] 11 294 02/08 08:20:32
Arielboid 
Questions & Réponses [non résolu] Problele d'addon 0 121 02/08 01:52:30
nayther 
Questions & Réponses Addon pour textures procedurales 1 115 01/08 12:22:52
moonboots 
Questions & Réponses hair densité sélection de polys 9 252 30/07 23:18:21
lenogre 
Questions & Réponses [résolu] graph editor et location key frame 7 217 30/07 16:41:18
math_ 
Questions & Réponses les graphs editor :/ 4 201 30/07 11:19:07
prometheusx 

Qui est en ligne
185 utilisateur(s) en ligne (dont 53 sur Forums)

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


plus...
Nouveaux membres
JacintoMac 9/8/2020
ViolaJzr12 9/8/2020
AlanMcgoug 9/8/2020
WendyMarqu 9/8/2020
LeonardBer 9/8/2020
Raul42N48 9/8/2020
KarolJ669 9/8/2020
SEFCliff84 9/8/2020
WilburnWim 9/8/2020
ReinaKalma 9/8/2020
Dernier Ajout
mirages-preview~0.jpg

Evènements à venir
Aou 13
Anniversaire Siskas
Sep 8
Anniversaire de ang
Nov 18
Anniversaire de RichDeg
plus 266 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