[Resolu][DB/MY-AL]PathFinding perso

Pour les scripts écrits en C#
Règles du forum
Merci de respecter la NOMENCLATURE suivante pour vos TITRES de messages :

Commencez par le niveau de vos scripts
DB = Débutant
MY = Moyen
CF = Confirmé

Puis le domaine d'application
-RS = Réseau
-AL = Algorithmie

Exemple :

[DB-RS] Mouvement perso multijoueur
djulio74
Messages : 682
Inscription : 19 Déc 2009 22:55

Re: [DB/MY-AL]PathFinding perso

Message par djulio74 » 16 Oct 2018 20:06

vraiment tant mieux si ton script marche, même sans utiliser les struct. Comme quoi des fois a vouloir en faire trop... :hehe:

Mais je me demande vraiment pourquoi du coup ça ne marche que moins bien, ça me perturbe. lol.
Comment est défini la position de Mimi?
Quand tu vois le trajet avec le debug elle ne se contente pas de ce trajet?

Arf à l'occaz je ré-comparerai ton script original avant que j'y foute le bordel, avec celui ou j'y ai justement mis le bordel, voir si j'ai pas fait une petite faute quelque part en recopiant. Vraiment ça me perturbe :hehe: (non pas que je soit véxé que ça marche mieux sans, mais que j'aime bien quad j'ai une idée arriver a faire qu'elle fonctionne, même si ça doit être moins bien qu'avant. lol)

EDIT :
Je crois avoir trouvé :
dans la fonction rechercheChemin(), l'initialisation Path = new List<int>(); n'est pas au bon endroit. il doit être juste apres le retour:. sinon oui normal, chaque nouveau chemin cherché est ajouté a la suite du précédent.

______________________________________________________________
\_______________________ Impossible is nothing _______________________/

EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

Re: [DB/MY-AL]PathFinding perso

Message par EmileF » 16 Oct 2018 20:36

Bravo, super, mégatop, tu es le meilleur :mdr3:

C'était ça, maintenant Mimi fait bien le chemin le plus court quand je clique sur la case diagonalement opposée elle va bien dans la case sans soucis. et si je clique sur une case juste avant ou juste après, mimi prend bien le chemin le plus court.

Tu es le plus fort, je vais adopter ton script, il doit être mieux optimisé, merci.

J'ai d'autres scripts à proposer notamment pour le circuit ou pour les portails, si ce n'est pas abusé, je vais les revoir et les présenter pour en parler.

En tout cas, merci Djulio
La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

Re: [DB/MY-AL]PathFinding perso

Message par EmileF » 17 Oct 2018 10:27

Voici l'intégralité du script au cas ou ça intéresserait quelqu'un.

Je crois que le script est suffisamment commenté pour s"y retrouvé.

Code : Tout sélectionner

using UnityEngine;
using System.Collections.Generic;

//Djulio à l'origine du script
public class Trajet : MonoBehaviour
{

    // definition d'une struc pour garder les données dans le script
    // pour n'accéder qu'une seule fois aux GameObjects cellule.
    public struct CEL
    {
        public Vector3 position;
        public bool visite;
        public List<int> voisin;
        public bool carrefour;
        public Tile tile;

        public CEL(GameObject objet, bool visite, List<int> voisin, bool carrefour)
        {
            this.tile = objet.GetComponent<Tile>();
            this.position = objet.transform.position;
            this.visite = visite;
            this.voisin = voisin;
            this.carrefour = carrefour;
        }
    }

    public static int ACTIVE;           // cellule survolée par la souris
    public static CEL[] cellules;       // un array de la struct CEL defini plus haut
    public static List<List<int>> Paths; // liste de tout lein possile 
    public static List<int> Path;       // le path qu'on est en train de calculer puis le path court retenu.
    public static int end;              // index de cellules ou se trouve l'arrivé.
    public static int start;            // index de cellules ou se trouve mimi.

    public static int EnCours;          // l'index de la case ou en est la recherche de chemin.
    public static int Lenght;

    void Start()
    {
        ACTIVE = 0;

        // lance l'initialisation de la struct
        Initialisation();

        Path = new List<int>();
    }

    //n'est utilisé que pour le débug
    //void Update()
    //{
    //    if (cellules == null || cellules.Length == 0) return;
    //    // juste un debugage que me suis servit pour visualiser les chemin.

    //    for (int i = 0; i < cellules[ACTIVE].voisin.Count; i++)
    //    {
    //        Debug.DrawLine(cellules[ACTIVE].position, cellules[cellules[ACTIVE].voisin[i]].position, Color.red);

    //    }

    //    for (int i = 0; i < Path.Count - 1; i++)
    //    {
    //        Debug.DrawLine(cellules[Path[i]].position, cellules[Path[i + 1]].position, Color.blue);

    //    }

    //    Debug.DrawRay(cellules[end].position, Vector3.up, Color.red);
    //    Debug.DrawRay(cellules[start].position, Vector3.up, Color.green);
    //    Debug.DrawRay(cellules[ACTIVE].position, Vector3.up * 2, Color.blue);
    //}

    /// <summary>
    /// N'est appelé qu'une fois à la fin de la création du niveau
    /// parce que le niveau ne change pas en cours de jeu
    /// </summary>
    public static void Initialisation()
    {

        GameObject[] CelluleGO = GameObject.FindGameObjectsWithTag("Cellule");
        cellules = new CEL[CelluleGO.Length];

        for (int i = 0; i < cellules.Length; i++)
        {
            cellules[i] = new CEL(CelluleGO[i], false, new List<int>(), false);
            CelluleGO[i].GetComponent<Tile>().Index = i; // on assigne au GameObject cellule l'index dans lequel il se trouve
        }
        RechercheVoisin();

    }

    static void RechercheVoisin()
    {

        for (int i = 0; i < cellules.Length - 1; i++)
        {
            for (int j = i + 1; j < cellules.Length; j++)
            {
                float distance = (cellules[i].position - cellules[j].position).magnitude;
                if (Mathf.Approximately(distance, 1f))
                {
                    if (!cellules[i].voisin.Contains(j))
                    {
                        cellules[i].voisin.Add(j);
                        cellules[j].voisin.Add(i);


                    }
                }
            }
        }
        // apres avoir trouvé tout les voisins
        // on assigne le bool carrefour en fonction du nombre de voisins.
        for (int i = 0; i < cellules.Length - 1; i++)
        {
            if (cellules[i].voisin.Count > 2)
            {
                cellules[i].carrefour = true;
            }
        }
    }

    public static void RechercheChemin(int start)
    {
        // on assigne false a toute les cellules (à la struct qui lui correspond)
        for (int i = 0; i < cellules.Length; i++)
        {
            cellules[i].visite = false;
        }

        // remise a zero des paths possible. On efface tout on recommence
        Paths = new List<List<int>>();

        retour:
        //Le chemin final
        Path = new List<int>();

        EnCours = start;
        Path.Add(EnCours);                  // ajout de la case
        cellules[EnCours].visite = true;    // la cellule ou se trouve mimi est marquée visitée.
        RechercheCheminPossible();

        //Si le chemin est très court on arrête là
        if (Path.Count > 0 && Path.Count < 5)
        {
            Lenght = Path.Count-1;
            return;
        }

        //si le chemin n'est pas null on le stocke
        if (Path.Count > 1)
        {
            Paths.Add(Path);
        }

        //on repart du départ
        EnCours = start;

        //si on trouve un carrefour avec une direction non explorée
        //on reprend la recherche
        if (RechercheCarrefour(EnCours))
        {
            goto retour;
        }

        //s'il y a plusieurs chemin on cherche le plus court
        if (Paths.Count > 0)
        {
            RechercheLePlusCourt();
        }

        Lenght = Path.Count-1;

    }

    public static void RechercheCheminPossible()
    {
        retour:
        //s'il y a une cellule voisine à de la cellule en cours
        if (RechercheCarrefour(EnCours))
        {
            //on ajoute son index au chemin
            Path.Add(EnCours);
            cellules[EnCours].visite = true;
            //si on est arrivé
            if (EnCours == end)
            {
                //on demarque visité de la dernière cellule en cas de recherche supplémentaire et on sort
                cellules[EnCours].visite = false;
                return;
            }
            //sinon on continue
            goto retour;
        }
        //il n'y a pas de cellule accessible autour de la cellule en cours
        for (int i = Path.Count - 1; i > -1; i--)
        {
            //on remonte le chemin à la recherche d'un carrefour
            if (!RechercheCarrefour(Path[i]))
            {
                Path.Remove(Path[i]);
            }
            else
            {
                //on reprend à partir du carrefour
                EnCours = Path[i];
                goto retour;
            }
        }
        return;
    }

    static bool RechercheCarrefour(int index)
    {
        foreach (int item in cellules[index].voisin)
        {
            if (cellules[item].visite == false)
            {
                EnCours = item;
                return true;
            }
        }
        return false;
    }

    public static void RechercheLePlusCourt()
    {
        Path = Paths[0]; // on prend le premier Path de Paths
        foreach (var item in Paths)
        {
            if (item.Count < Path.Count)
                Path = item;
        }
    }
}

La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

djulio74
Messages : 682
Inscription : 19 Déc 2009 22:55

Re: [Resolu][DB/MY-AL]PathFinding perso

Message par djulio74 » 17 Oct 2018 10:36

Hé Hé, j'avais pas vu ta réponse d'hier! ^^
Ah bah super si ça marche comme ça! ;-)
Comme quoi des fois une erreur toute bête peut être source de gros ennuie, lol

Je suis content si tout fonctionne bien, et si tu as compris surtout la mise en place des struct.
Avec plaisir en tout cas, et puis si t'as d'autre script comme tu dis, tu sais ou poster :super:

Ravi d'avoir pu aider.

______________________________________________________________
\_______________________ Impossible is nothing _______________________/

Répondre

Revenir vers « (C#) CSharp »