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

[djulio74]

Est-ce que c'est à cause de l'absence de la boucle du départ,

Oui oui il faut ta boucle de depart, mais faut larreter a i = Cellules.Length-1

je ne comprend pas pourquoi la derniere ligne : DefinitLesVoisins(j); Je pense elle est inutile pour la recherche de voisin, ça ajoute juste des conditions a vérifier. essaye en la supprimant.

Code : Tout sélectionner

    
    public int COUNT = 0; // comptera le nombre d'appel de la fonction DefinitLesVoisins(int i)
    
      private void DefinitLesVoisins()
    {
        for (int i = 0; i < Cellules.Length; i++)
        //essaye avec : ( juste -1 apres Length)
        //  for (int i = 0; i < Cellules.Length -1; i++)
        {
            DefinitLesVoisinsBis(i);
        }
        
        print (COUNT); 
    }
    
    private void DefinitLesVoisins(int i)
    {
        for (int j = i+1; j< Cellules.Length; j++)
        {
            Vector3 PositionItem1 = Cellules[i].transform.position;
            Vector3 PositionItem2 = Cellules[j].transform.position;
            float distance = (PositionItem1 - PositionItem2).magnitude;
            if (distance == 1)
            {
                //il faut quand même vérifier qu'il n'y ai pas redondance
                if (!Cellules[i].GetComponent<Tile>().Voisins.Contains(Cellules[j]))
                {
                    Cellules[i].GetComponent<Tile>().Voisins.Add(Cellules[j]);
                    Cellules[j].GetComponent<Tile>().Voisins.Add(Cellules[i]);
                }
               //  DefinitLesVoisins(j); Compare COUNT avec et sans cette ligne.
            }
		COUNT +=1;
        }
    }

[EmileF]

J'ai essayé ce code avant de compter les itérations et ça ne marche pas

Code : Tout sélectionner

    /// <summary>
    /// Parcours toutes les celules et ajoute à Voisins de chacune les cellules 
    /// qui sont à 1 case de décalage dans chaque direction
    /// </summary>
    private void DefinitLesVoisins()
    {
        for (int i = 0; i < Cellules.Length-1; i++)
        {
            DefinitLesVoisins(0);
        }
    }

    private void DefinitLesVoisins(int i)
    {
        for (int j = i + 1; j < Cellules.Length; j++)
        {
            Vector3 PositionItem1 = Cellules[i].transform.position;
            Vector3 PositionItem2 = Cellules[j].transform.position;
            float distance = (PositionItem1 - PositionItem2).magnitude;
            if (distance == 1)
            {
                //il faut quand même vérifier qu'il n'y ai pas redondance
                if (!Cellules[i].GetComponent<Tile>().Voisins.Contains(Cellules[j]))
                {
                    Cellules[i].GetComponent<Tile>().Voisins.Add(Cellules[j]);
                    Cellules[j].GetComponent<Tile>().Voisins.Add(Cellules[i]);
                }
                //DefinitLesVoisins(j);
            }

        }
    }

[EmileF]

je ne comprend pas pourquoi la derniere ligne : DefinitLesVoisins(j)

Elle permet de chercher les voisins de voisins et ainsi de suite je crois

[djulio74]

je ne comprend pas pourquoi la derniere ligne : DefinitLesVoisins(j)

Elle permet de chercher les voisins de voisins et ainsi de suite je crois

justement pas utile dans ce cas,
Avec i < Cellules.Length-1 et j> i, tu couvre deja toute les possibilité (en testant les 4 directions a chaque fois)
Essaye les dernier code que j'ai posté qui contiennent "COUNT", qui te permetra de visualiser le nombre d'appel de la fonction. (normalement 55 pour 10 cellules)

par contre ton script,avec DefinitLesVoisins(j), en legerement moifié ferait un bon pathfinding. lol.

[boubouk50]

La récursivité est un appel de la fonction dans elle-même, donc il y aura plusieurs appels.
Si tu préfère utiliser des boucles, ça fonctionne aussi. C'est un autre choix d'utilisation.

Concernant le code, tu n'utilises que les j à partir de i+1. (Tu noteras que dans mon pseudo-code, j'ai mis tous les autres). Imaginons que le premier voisin soit le dernier de la liste, alors tu auras tout de suite terminé. Là, c'est un mélange de boucle et de récursivité, ce serait plutôt l'un ou l'autre.

Je pense que tu devrais utiliser une fonction qui boucle comme Julio te le conseille, tu es plus à l'aise avec, et c'est plus intuitif, et peut-être même plus rapide. Qui plus est, moi-même, je suis pas plus confiant que ça avec la récursivité...

[EmileF]

Voila le code qui marche avec une itération de moins qu'il y a de cellules

Code : Tout sélectionner

    /// <summary>
    /// Parcours toutes les celules et ajoute à Voisins de chacune les cellules 
    /// qui sont à 1 case de décalage dans chaque direction
    /// </summary>
    private void DefinitLesVoisins()
    {
        Count = 0;
        for (int i = 0; i < Cellules.Length-1; i++)
        {
            DefinitLesVoisins(i);
        }
        print(Count);
    }

    private void DefinitLesVoisins(int i)
    {
        for (int j = i + 1; j < Cellules.Length; j++)
        {
            Vector3 PositionItem1 = Cellules[i].transform.position;
            Vector3 PositionItem2 = Cellules[j].transform.position;
            float distance = (PositionItem1 - PositionItem2).magnitude;
            if (distance == 1)
            //if (PositionItem1 + Vector3.forward == PositionItem2 ||
            //    PositionItem1 + Vector3.right == PositionItem2)
            {
                //il faut quand même vérifier qu'il n'y ai pas redondance
                if (!Cellules[i].GetComponent<Tile>().Voisins.Contains(Cellules[j]))
                {
                    Cellules[i].GetComponent<Tile>().Voisins.Add(Cellules[j]);
                    Cellules[j].GetComponent<Tile>().Voisins.Add(Cellules[i]);
                }
                //DefinitLesVoisins(j);
                Count++;
            }

        }
    }

Il semblerai que la récursivité dans ce cas soit inutile et pour 11 cellules je compte 10 itérations

Je pense que c'est le mieux qu'on puisse atteindre.

[boubouk50]

Code : Tout sélectionner

/// <summary>
    /// Parcours toutes les celules et ajoute à Voisins de chacune les cellules 
    /// qui sont à 1 case de décalage dans chaque direction
    /// </summary>
    private void DefinitLesVoisins()
    {
    	int size = Cellules.Length-1;
    	for (int i = 0; i < size ; i++) //Le dernier aura forcément ses voisins trouvés
    	{
       	 	for (int j = i + 1; j <= size ; j++)
        	{
            		float distance = (Cellules[i].transform.position - Cellules[j].transform.position).magnitude;
            		//Attention tu as un float, pas un entier
           		if (Mathf.Approximately(distance,  1f)
            		{
                	//Pas besoin de vérifier la redondance, tu testes deux cellules jamais associés, car la boucle t'en empêche: j est forcément supérieur à i
                    		Cellules[i].GetComponent<Tile>().Voisins.Add(Cellules[j]);
                    		Cellules[j].GetComponent<Tile>().Voisins.Add(Cellules[i]);
            		}
        	}
        }
    }

Voilà ce que cela devrait donner avec juste une fonction et imbrication de boucle

EDIT: on fait tout en même temps à chaque fois
Au final, on a (+/-) le même code.

[EmileF]

Hop excuses j'ai mal placé Count++;

J'ai 55 itérations pour 11 cellules.

[djulio74]

Cest exactement ça Emile, par contre au lieu d'avoir un fonction supplémentaire, tu peux tout mettre ce qu'il y a dans ta fonction private void DefinitLesVoisins(int i) a la place de l'appel de celle ci. Tout comme l'as fait Boubouk.

[EmileF]

J'ai testé le script de Boubouk, sur plusieurs niveaux, ça a l'air impeccable.
Il faut être à trois, enfin 2 plus moi pour tester pour arriver à un script optimisé
merci à tous les deux, je crains pour la suite.