« 1 2 (3) 4 5 »


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
19/03/2016 15:30
De Belgique
Post(s): 1761
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/2020 11:11
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): 2931
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/2020 11:46
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): 1761
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/2020 16:46
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): 2931
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/2020 21:33
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): 1761
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/2020 10:23
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): 2931
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/2020 11:31
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): 2931
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/2020 11:49
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): 1761
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/2020 11:28
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): 2931
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/2020 20:38
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): 1761
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/2020 07:58
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
Questions & Réponses objet suivant chemin en prenant la courbure du chemin 0 8 Aujourd'hui 01:58:52
neonclignote 
Hors Sujet !! Sappling gen generateur d'arbres - tuto blender 0 7 Aujourd'hui 00:02:16
meltingman 
Moteur de jeu GameBlender et alternatives Mes participations aux gamejam :    [1][2] 10 599 Hier 22:42:31
timeman13 
Questions & Réponses Plusieurs object qui avance sur une ligne trajectoire 7 140 Hier 20:18:06
Warels 
Questions & Réponses [résolu] Mirror ne fonctionne plus bien 8 136 Hier 18:08:35
GFC 
Moteur de jeu GameBlender et alternatives [non résolu] Cs (vaisseau)    [1][2][3]...[54] 534 158189 Hier 09:37:14
Redstar 
Questions & Réponses Le linking ne marche pas avec mon n personnage 1 41 Hier 09:32:00
Redstar 
Hors Sujet !! les tutos de Moonboots    [1][2][3]...[10] 93 6544 13/05 11:28:17
moonboots 
Questions & Réponses Occlusion ambiante dans 2.80 et plus avec eevee 2 198 12/05 06:40:35
xorturion 
Moteur de jeu GameBlender et alternatives [WIP] DeadSigns FPS horreur - Version alpha disponible + discord    [1][2][3]...[66] 656 133317 10/05 11:44:04
Hook 
Questions & Réponses [résolu] Transparence et Dynamic Paint pour un tag 5 685 10/05 10:51:42
CBY 
Questions & Réponses Text comme screen overlay 5 238 10/05 04:02:53
meltingman 
Questions & Réponses [non résolu] Exécuter un script à l'ouverture 0 60 09/05 21:45:09
Melodicpinpon 
Questions & Réponses Lancer un script par défaut/à l'ouverture 0 47 09/05 19:25:33
Melodicpinpon 
The Blender Clan 'tchat Benchmark EEVEE    [1][2][3]...[5] 41 9081 09/05 17:08:59
Keezty 
Questions & Réponses Garder la lumière allumée en local view, et dans toutes les collections 0 186 09/05 16:58:11
Melodicpinpon 
Python & Plugins ardoise 3D en add-on? 2 185 07/05 14:18:47
neonclignote 
Questions & Réponses [non résolu] Dynamic paint + particle 2 175 06/05 18:39:49
Jeanclaude25 
Questions & Réponses [résolu] Lier visibilité et rendering 4 1078 06/05 10:32:29
Melodicpinpon 
Moteur de jeu GameBlender et alternatives [WIP] Jeu "Collapsing - Quandore's Fate"    [1][2][3]...[5] 46 19834 06/05 09:36:54
Redstar 

Qui est en ligne
92 utilisateur(s) en ligne (dont 64 sur Forums)

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


plus...
Nouveaux membres

Nemo
11/3/2021
qingjie 10/3/2021
Kask909 9/3/2021
marie-antoinette 7/3/2021
Bugs 7/3/2021
lolorogli75 4/3/2021
Flagiel 4/3/2021
thedeathclown 1/3/2021
Littlespoon 28/2/2021
luxperpetua 27/2/2021
Dernier Ajout
2020-09-24.jpg

Evènements à venir
Mai 18
Anniversaire Luneo
Jui 30
Anniv des Jedi :-D
Jui 10
BUG de Lyon
plus 256 plus d'élément(s)
 Par Mickaël Guédon [ebrain] © 2003-2021 The Blender Clan - hébergé par TuxFamily - Site déclaré à la CNIL sous le numéro 1155445