« 1 2 (3) 4 5 »


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
19/03/2016 15:30
De Belgique
Post(s): 1593
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): 2337
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): 1593
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): 2337
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): 1593
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): 2337
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): 2337
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): 1593
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): 2337
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): 1593
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
Questions & Réponses [terminé] contrôle de l'angle d'incision du chanfrein/bevel 2 9 Aujourd'hui 16:08:24
halphasten 
Le coin des geeks pc bas prix    [1][2] 16 144 Aujourd'hui 15:39:21
Bibi09 
The Blender Clan 'tchat Clignotement de l'interface de blender 7 304 Aujourd'hui 13:13:40
zezer 
Questions & Réponses Pass index 1 25 Aujourd'hui 12:47:07
Rimpotche 
Questions & Réponses [non résolu] Adoucir les courbes et espacer uniformément les vertices dans l'UV Map 0 24 Aujourd'hui 11:28:59
Gizmil 
[WIP] et travaux terminés [terminé] court métrage 2020 8 169 Hier 18:44:19
flahaut 
Questions & Réponses épaisseur sur une texture 6 76 Hier 15:28:27
moonboots 
Questions & Réponses [résolu] Affichage de la grille du plan et des axes 2 57 Hier 14:27:44
gedru 
Questions & Réponses [résolu] Blender 2.80 ne démarre pas 7 1072 Hier 09:42:16
geo160 
Moteur de jeu GameBlender et alternatives [WIP] DeadSigns FPS horreur - Première version disponible !    [1][2][3]...[56] 559 93272 06/07 17:08:42
Bibi09 
Moteur de jeu GameBlender et alternatives hARMful engine    [1][2][3]...[9] 80 9048 06/07 16:58:20
Bibi09 
Questions & Réponses Knife tool a arrêté de fonctionner 1 59 06/07 16:29:51
Rimpotche 
Hors Sujet !! Système solaire open source 5 1542 26/12/2019 12:46
Bibi09 
Questions & Réponses [non résolu] Ecran bleu 2 93 05/07 18:35:32
alexmge 
Questions & Réponses [non résolu] va et vient entre sculpt et layout impossible    [1][2] 11 223 05/07 09:56:50
manondup 
Le coin des geeks carte graphique Intel(R) HD Graphics et OpenGL    [1][2][3] 24 956 04/07 22:47:15
Bibi09 
Questions & Réponses shader 5 181 04/07 20:23:23
Rimpotche 
[WIP] et travaux terminés Le Tigre 4 265 04/07 11:19:09
lastrodamo 
Questions & Réponses [non résolu] le Rendu de preview et le rendu final ne sonts pas pareils 2 151 03/07 23:18:27
Pinguinax 
Questions & Réponses [non résolu] Particules system dynamique 0 87 03/07 13:27:09
Ramar 

Qui est en ligne
189 utilisateur(s) en ligne (dont 154 sur Forums)

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


plus...
Nouveaux membres
halphasten 8/7/2020
KOALA_NET21 8/7/2020
singinzerin 6/7/2020
Dartank 5/7/2020
manondup 3/7/2020
Ramar 3/7/2020
Blendnoob 2/7/2020
blendmus 30/6/2020
Rafalithique2020 29/6/2020
rainbowfruit 27/6/2020
Dernier Ajout
mirages-preview~0.jpg

Evènements à venir
Jui 11
BUG de Lyon
Jui 23
Anniv du BlenderClan !
Aou 7
anniversaire Cem47
plus 269 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