Graphes

Un graphe est une structure composée de nœuds (ou sommets) connectés par des arêtes. Ils peuvent être catégorisés comme suit :

• Graphe non orienté : Les arêtes n'ont pas de direction.
• Graphe orienté : Les arêtes ont une direction spécifique.
• Graphe pondéré : Chaque arête a une valeur numérique associée (un poids).

Graphe Hamiltonien

Un chemin qui traverse chaque sommet exactement une fois est appelé chemin hamiltonien. Si ce chemin revient à son point de départ, il est appelé circuit hamiltonien. Un exemple concret est une tournée de livraison où un véhicule part d'un dépôt, visite chaque quartier une seule fois, puis retourne au dépôt.

Représentation des Graphes

La relation entre les nœuds peut être représentée de plusieurs manières :

• Matrice d'adjacence : Une matrice carrée où une entrée (i, j) est 1 si une arête existe entre le nœud i et le nœud j, et 0 sinon. Ce format est utile pour représenter des cartes de jeu dans des fichiers de configuraton (par exemple, JSON), permettant aux concepteurs de niveaux de définir facilement la topologie. Les nœuds peuvent être encapsulés dans des classes pour stocker des informations supplémentaires.
• Liste d'adjacence : Une collection de listes où chaque liste contient les voisins d'un nœud spécifique. Ce format est plus économe en espace car il ne stocke que les connexions existantes.

Le choix de la représentation dépend des besoins spécifiques de l'application.

Les arbres sont des structures de données hiérarchiques. Nous allons explorer plusieurs types :

Arbre Binaire

Un arbre binaire est un arbre où chaque nœud a au plus deux enfants, souvent appelés sous-arbre gauche et sous-arbre droit.

Arbre Binaire Complet

Dans un arbre binaire complet, tous les niveaux sont entièrement remplis, sauf potentiellement le dernier niveau, qui est rempli de gauche à droite.

Arbre Binaire Parfait

Un arbre binaire parfait est un arbre binaire complet dans lequel tous les nœuds internes ont deux enfants et toutes les feuilles sont au même niveau.

Arbre Binaire Équilibré

Un arbre binaire est considéré comme équilibré si la différence de profondeur entre le sous-arbre gauche et le sous-arbre droit de tout nœud ne dépasse pas 1. Cela garantit que les opérations de recherche et d'insertion restent efficaces.

Arbre de Recherche Binaire (BST)

Dans un BST, pour chaque nœud, toutes les valeurs du sous-arbre gauche sont inférieures à la valeur du nœud, et toutes les valeurs du sous-arbre droit sont supérieures à la valeur du nœud.

Arbre Rouge-Noir

Un arbre rouge-noir est un type d'arbre de recherche binaire auto-équilibré où chaque nœud est coloré en rouge ou en noir. Ces couleurs suivent des règles spécifiques qui garantissent que l'arbre reste approximativement équilibré, maintenant ainsi des performances de recherche efficaces.

Recherche en Largeur d'Abord (BFS) et Recherche en Profondeur d'Abord (DFS)

• BFS : Explore le graphe niveau par niveau, en commençant par le nœud racine. Il est garanti de trouver le chemin le plus court dans un graphe non pondéré. Son inconvénient est qu'il peut visiter un grand nombre de nœuds.
• DFS : Explore le graphe en allant aussi loin que possible le long de chaque branche avant de revenir en arrière. Il est généralement plus rapide en termes de consommation mémoire mais ne garantit pas de trouver le chemin le plus court.

Algorithme de Dijkstra

Cet algorithme utilise une approche gloutonne pour trouver le chemin le plus court d'un nœud source vers tous les autres nœuds d'un graphe pondéré. Il sélectionne toujours le nœud accessible avec la plus petite distance connue depuis la source.

Algorithme A*

L'algorithme A* est une amélioration de Dijkstra qui utilise une fonction heuristique pour guider sa recherche. La fonction d'évaluation d'un nœud n est f(n) = g(n) + h(n), où :

• g(n) : Le coût réel du chemin de la position de départ au nœud n.
• h(n) : Le coût heuristique estimé du chemin du nœud n à la position d'arrivée.

Cas Spécifiques de A* :

• Si h(n) = 0 pour tous les nœuds, A* se comporte comme l'algorithme de Dijkstra.
• Si g(n) = 0 pour tous les nœuds, A* devient une recherche par priorité, se concentrant uniquement sur l'estimation de la distance à la cible.

Fonctions d'Heuristique Courantes :

• Distance de Manhattan : Pour les mouvements autorisés dans les quatre directions cardinales (haut, bas, gauche, droite), elle est calculée comme abs(x1 - x2) + abs(y1 - y2).
• Distance Euclidienne : Pour les mouvements diagonaux, elle est calculée comme sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)). Dans les jeux, une approximation (comme 1.4 pour les diagonales et 1 pour les mouvements cardinaux) est souvent suffisante pour l'efficacité.

Implémentation A* en Unity

Voici une implémentation simplifiée de l'algorithme A* en C# pour Unity.

Classe Node

Représente un emplacement sur la grile de jeu.

public enum NodeType
{
   Walkable,
   Obstacle
}

public class Node
{
   public int GridX;
   public int GridY;
   public Node Parent;
   public NodeType Type;
   public float G_Cost; // Coût depuis le début
   public float H_Cost; // Coût heuristique vers la fin
   public float F_Cost => G_Cost + H_Cost; // Coût total

   public Node(int x, int y, NodeType type)
   {
       this.GridX = x;
       this.GridY = y;
       this.Type = type;
   }

   public void SetMovementCosts(Node parent, float gCost, float hCost)
   {
       this.Parent = parent;
       this.G_Cost = gCost;
       this.H_Cost = hCost;
   }

   // Méthode pour vérifier si deux nœuds sont les mêmes
   public bool IsSameNode(Node other)
   {
       return this.GridX == other.GridX && this.GridY == other.GridY;
   }
}
       

Classe PathfinderAStar

Implémente la logique de l'algorithme A*.

using UnityEngine;
using System.Collections.Generic;
using System.Linq; // Nécessaire pour OrderBy

public class PathfinderAStar : MonoBehaviour
{
   public static PathfinderAStar Instance;

   [SerializeField] private int mapWidth = 50;
   [SerializeField] private int mapHeight = 50;
   [SerializeField] private float obstacleProbability = 0.3f;

   private Node[,] grid;
   private List<node> openSet = new List<node>();
   private List<node> closedSet = new List<node>();

   private void Awake()
   {
       if (Instance == null)
       {
           Instance = this;
       }
       else
       {
           Destroy(gameObject);
       }
       InitializeGrid();
   }

   private void InitializeGrid()
   {
       grid = new Node[mapWidth, mapHeight];
       for (int x = 0; x < mapWidth; x++)
       {
           for (int y = 0; y < mapHeight; y++)
           {
               NodeType type = Random.value < obstacleProbability ? NodeType.Obstacle : NodeType.Walkable;
               grid[x, y] = new Node(x, y, type);
           }
       }
   }

   public List<node> FindPath(Vector2 startPos, Vector2 endPos)
   {
       // Vérifications initiales
       if (!IsValidPosition(startPos) || !IsValidPosition(endPos))
       {
           Debug.LogError("Start or End position is out of bounds.");
           return null;
       }

       Node startNode = grid[(int)startPos.x, (int)startPos.y];
       Node endNode = grid[(int)endPos.x, (int)endPos.y];

       if (startNode.Type == NodeType.Obstacle || endNode.Type == NodeType.Obstacle)
       {
           Debug.LogWarning("Start or End node is an obstacle.");
           return null;
       }

       // Réinitialisation des ensembles
       openSet.Clear();
       closedSet.Clear();

       // Ajout du nœud de départ
       startNode.SetMovementCosts(null, 0, CalculateHeuristic(startNode, endNode));
       openSet.Add(startNode);

       while (openSet.Any())
       {
           // Sélection du nœud avec le plus petit F_Cost dans l'ensemble ouvert
           Node currentNode = openSet.OrderBy(node => node.F_Cost).First();

           // Si le nœud courant est le nœud final, on a trouvé le chemin
           if (currentNode.IsSameNode(endNode))
           {
               return ReconstructPath(currentNode);
           }

           // Déplacer le nœud courant de l'ensemble ouvert vers l'ensemble fermé
           openSet.Remove(currentNode);
           closedSet.Add(currentNode);

           // Examiner les voisins
           foreach (Node neighbor in GetNeighborNodes(currentNode))
           {
               // Ignorer si le voisin est un obstacle ou déjà dans l'ensemble fermé
               if (neighbor.Type == NodeType.Obstacle || closedSet.Contains(neighbor))
               {
                   continue;
               }

               // Calculer le coût pour atteindre le voisin via le nœud courant
               float movementCostToNeighbor = GetDistance(currentNode, neighbor);
               float tentativeG_Cost = currentNode.G_Cost + movementCostToNeighbor;

               // Si ce chemin vers le voisin est meilleur que le précédent, ou si le voisin n'est pas encore dans l'ensemble ouvert
               if (tentativeG_Cost < neighbor.G_Cost || !openSet.Contains(neighbor))
               {
                   neighbor.SetMovementCosts(currentNode, tentativeG_Cost, CalculateHeuristic(neighbor, endNode));

                   if (!openSet.Contains(neighbor))
                   {
                       openSet.Add(neighbor);
                   }
               }
           }
       }

       // Si l'ensemble ouvert est vide et que le chemin n'a pas été trouvé
       Debug.Log("Path not found.");
       return null;
   }

   private List<node> ReconstructPath(Node endNode)
   {
       List<node> path = new List<node>();
       Node currentNode = endNode;

       while (currentNode != null)
       {
           path.Add(currentNode);
           currentNode = currentNode.Parent;
       }
       path.Reverse(); // Le chemin est reconstruit de la fin au début
       return path;
   }

   private float GetDistance(Node nodeA, Node nodeB)
   {
       // Coût de déplacement : 1 pour les mouvements cardinaux, 1.4 pour les diagonales
       float distX = Mathf.Abs(nodeA.GridX - nodeB.GridX);
       float distY = Mathf.Abs(nodeA.GridY - nodeB.GridY);

       if (distX > distY)
       {
           return 1.4f * distY + 1.0f * (distX - distY);
       }
       else
       {
           return 1.4f * distX + 1.0f * (distY - distX);
       }
   }

   private float CalculateHeuristic(Node node, Node endNode)
   {
       // Utilisation de la distance de Manhattan comme heuristique
       return Mathf.Abs(node.GridX - endNode.GridX) + Mathf.Abs(node.GridY - endNode.GridY);
   }

   private IEnumerable<node> GetNeighborNodes(Node node)
   {
       List<node> neighbors = new List<node>();
       int[] xOffsets = { -1, 0, 1, -1, 1, -1, 0, 1 };
       int[] yOffsets = { -1, -1, -1, 0, 0, 1, 1, 1 };

       for (int i = 0; i < 8; i++)
       {
           int checkX = node.GridX + xOffsets[i];
           int checkY = node.GridY + yOffsets[i];

           if (IsValidPosition(new Vector2(checkX, checkY)))
           {
               neighbors.Add(grid[checkX, checkY]);
           }
       }
       return neighbors;
   }

   private bool IsValidPosition(Vector2 pos)
   {
       return pos.x >= 0 && pos.x < mapWidth && pos.y >= 0 && pos.y < mapHeight;
   }

   // Méthode pour obtenir la grille (pour le débogage ou la visualisation)
   public Node[,] GetGrid()
   {
       return grid;
   }
}
       </node></node></node></node></node></node></node></node></node></node></node>

Exemple de Scène de Test en Unity

Ce script permet de visualiser la grille et de tester la recherche de chemin en cliquant sur deux points.

using UnityEngine;
using System.Collections.Generic;

public class TestSceneManager : MonoBehaviour
{
   [Header("Grid Settings")]
   public int gridWidth = 20;
   public int gridHeight = 20;
   public float cellSize = 1.0f;
   public Vector3 gridOffset = Vector3.zero;

   [Header("Pathfinding Test")]
   public Color walkableColor = Color.white;
   public Color obstacleColor = Color.red;
   public Color startColor = Color.yellow;
   public Color endColor = Color.yellow;
   public Color pathColor = Color.green;

   private Dictionary<string gameobject=""> gridCubes = new Dictionary<string gameobject="">();
   private Node startNode = null;
   private Node endNode = null;

   private void Start()
   {
       InitializeScene();
   }

   private void InitializeScene()
   {
       // Assurez-vous que le PathfinderAStar est initialisé avec les bonnes dimensions
       // Si vous utilisez la configuration par défaut dans PathfinderAStar, ce n'est pas nécessaire.
       // Sinon, appelez PathfinderAStar.Instance.SetupGrid(gridWidth, gridHeight, ...);

       if (PathfinderAStar.Instance == null)
       {
           Debug.LogError("PathfinderAStar instance not found. Make sure it's attached to a GameObject and Awake has run.");
           return;
       }

       // S'assurer que les dimensions du Pathfinder correspondent
       // Ou mieux, que le Pathfinder gère sa propre initialisation basée sur les dimensions fournies.
       // Pour cet exemple, nous supposons que PathfinderAStar est configuré pour ces dimensions.
       // Si vous voulez contrôler les dimensions d'ici, vous devrez ajuster PathfinderAStar.
       // Ici, nous allons juste créer les cubes visuels.

       for (int x = 0; x < gridWidth; x++)
       {
           for (int y = 0; y < gridHeight; y++)
           {
               GameObject cube = GameObject.CreatePrimitive(PrimitiveType.Cube);
               cube.transform.position = gridOffset + new Vector3(x * cellSize, y * cellSize, 0);
               cube.transform.localScale = new Vector3(cellSize, cellSize, cellSize);
               cube.name = $"{x}_{y}";
               gridCubes.Add(cube.name, cube);

               Node node = PathfinderAStar.Instance.GetGrid()?[x, y];
               if (node != null)
               {
                   if (node.Type == NodeType.Obstacle)
                   {
                       cube.GetComponent<renderer>().material.color = obstacleColor;
                   }
                   else
                   {
                       cube.GetComponent<renderer>().material.color = walkableColor;
                   }
               }
           }
       }
   }

   private void Update()
   {
       if (Input.GetMouseButtonDown(0))
       {
           Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);
           RaycastHit hit;

           if (Physics.Raycast(ray, out hit))
           {
               string[] nameParts = hit.collider.gameObject.name.Split('_');
               int x = int.Parse(nameParts[0]);
               int y = int.Parse(nameParts[1]);

               if (startNode == null)
               {
                   startNode = PathfinderAStar.Instance.GetGrid()?[x, y];
                   if (startNode != null && startNode.Type != NodeType.Obstacle)
                   {
                       hit.collider.gameObject.GetComponent<renderer>().material.color = startColor;
                   }
                   else
                   {
                       startNode = null; // Ne pas définir si c'est un obstacle
                   }
               }
               else if (endNode == null)
               {
                   endNode = PathfinderAStar.Instance.GetGrid()?[x, y];
                   if (endNode != null && endNode.Type != NodeType.Obstacle)
                   {
                       hit.collider.gameObject.GetComponent<renderer>().material.color = endColor;
                       FindAndDrawPath();
                   }
                   else
                   {
                       endNode = null; // Ne pas définir si c'est un obstacle
                   }
               }
               else // Si start et end sont déjà définis, réinitialiser pour un nouveau chemin
               {
                   ResetPathVisualization();
                   startNode = PathfinderAStar.Instance.GetGrid()?[x, y];
                   if (startNode != null && startNode.Type != NodeType.Obstacle)
                   {
                       hit.collider.gameObject.GetComponent<renderer>().material.color = startColor;
                   }
                   else
                   {
                       startNode = null;
                   }
                   endNode = null; // Réinitialiser endNode pour permettre une nouvelle sélection
               }
           }
       }
   }

   private void FindAndDrawPath()
   {
       if (startNode != null && endNode != null)
       {
           List<node> path = PathfinderAStar.Instance.FindPath(new Vector2(startNode.GridX, startNode.GridY), new Vector2(endNode.GridX, endNode.GridY));

           if (path != null)
           {
               for (int i = 0; i < path.Count; i++)
               {
                   Node pathNode = path[i];
                   if (gridCubes.ContainsKey($"{pathNode.GridX}_{pathNode.GridY}"))
                   {
                       // Ne pas écraser les couleurs de début et de fin
                       if (!pathNode.IsSameNode(startNode) && !pathNode.IsSameNode(endNode))
                       {
                           gridCubes[$"{pathNode.GridX}_{pathNode.GridY}"].GetComponent<renderer>().material.color = pathColor;
                       }
                   }
               }
           }
       }
   }

   private void ResetPathVisualization()
   {
       // Réinitialiser les couleurs de tous les nœuds
       for (int x = 0; x < gridWidth; x++)
       {
           for (int y = 0; y < gridHeight; y++)
           {
               if (gridCubes.ContainsKey($"{x}_{y}"))
               {
                   Node node = PathfinderAStar.Instance.GetGrid()?[x, y];
                   if (node != null)
                   {
                       if (node.Type == NodeType.Obstacle)
                       {
                           gridCubes[$"{x}_{y}"].GetComponent<renderer>().material.color = obstacleColor;
                       }
                       else
                       {
                           gridCubes[$"{x}_{y}"].GetComponent<renderer>().material.color = walkableColor;
                       }
                   }
               }
           }
       }
       startNode = null;
       endNode = null;
   }
}
       </renderer></renderer></renderer></node></renderer></renderer></renderer></renderer></renderer></string></string>