« 1 2 (3) 4 5 »


Re: système Sid Meyer like (Civilization)
OverdOzed
Inscrit:
19/03/2016 15:30
De Belgique
Post(s): 1655
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): 2658
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): 1655
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): 2658
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): 1655
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): 2658
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): 2658
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): 1655
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): 2658
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): 1655
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
Hors Sujet !! Un poisson clown low poly - 15 mm - Tutoriel - 2.9 1 48 Hier 23:10:43
debutant 
Hors Sujet !! Le petit déjeuner à la Française - série de tutos - 2.9 1 18 Hier 21:47:50
moonboots 
[WIP] et travaux terminés [terminé] Scène de Pti dej à la Française - EVEE a donf - 2.9 Blender    [1][2][3]...[5] 44 519 Hier 20:44:23
meltingman 
Questions & Réponses Peindre des voxels 3D: Est-ce possible? 0 18 Hier 17:23:30
Melodicpinpon 
Questions & Réponses Disparition de matériaux après système de particule 2 55 Hier 12:43:02
Zarathoustra 
Questions & Réponses Esalier avec ARRAY 4 37 Hier 11:04:28
francerf 
Questions & Réponses [résolu] Modificateur Curve sur une courbe multiple 3 57 Hier 09:29:38
oliviertij 
[WIP] et travaux terminés [WIP] Teeny Tiny - Story    [1][2][3]...[13] 125 10029 Hier 01:53:31
meltingman 
The Blender Clan 'tchat Pour les arboriculteurs 3D 2 127 26/10 21:47:01
iet 
Hors Sujet !! Quels secteurs exploite l'impression 3D ? 1 42 26/10 16:12:54
Bibi09 
Questions & Réponses Problème de collision dans un player FPS 1 59 26/10 14:56:23
Redstar 
Questions & Réponses [résolu] Placer sa camera sur un HDRI    [1][2] 11 367 26/10 14:38:31
Crocodile_13 
Questions & Réponses [WIP] Problème Rétopo    [1][2] 10 121 26/10 09:53:59
Laorz 
Questions & Réponses Prioriser la visibilité d'un objet ? 2 66 25/10 17:31:26
Rimpotche 
[WIP] et travaux terminés image couteau dans caillou qui saigne 2 66 25/10 07:03:37
Crocodile_13 
[WIP] et travaux terminés [terminé] Chaussures Très Réalistes (.bend disponible) 5 162 24/10 21:23:47
Crocodile_13 
Le coin des geeks gain de fluidité viewport entre ryzen 3900X et 3950X    [1][2][3] 28 1432 24/10 15:45:54
papillon 
Questions & Réponses hdri en mode ombrage 2 136 24/10 10:27:06
kimlicrea 
Questions & Réponses Modifier les attribue de plusieurs objet en même temps (lumière) 3 88 24/10 10:21:47
kimlicrea 
[WIP] et travaux terminés [terminé] Moderno 404    [1][2] 13 585 23/10 20:26:41
moonboots 

Qui est en ligne
196 utilisateur(s) en ligne (dont 127 sur Forums)

Membre(s): 1
Invité(s): 195


Ugolin_D, plus...
Nouveaux membres
Ugolin_D 28/10/2020
LEZTiffany 28/10/2020
VINCHZ 27/10/2020
yawdpwal 26/10/2020
stano123 26/10/2020
Electricskull885 26/10/2020

Sina
25/10/2020
Christoph 24/10/2020
Sylv07 23/10/2020
Maxence34 23/10/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