AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  Connexion  

Partagez | 
 

 [C#] Calcul de mouvement avec A*

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
Wargamer
*Excellent utilisateur*
avatar

Messages : 6936
Projet Actuel : Bataille de cake au fruits

MessageSujet: [C#] Calcul de mouvement avec A*   Jeu 16 Mai 2013 - 21:24

Comme j'avais besoin d'un calcul de mouvement pour mon jeu pour savoir où je pouvais me déplacer ou non sur un grille j'ai décidé d'utiliser l'algo de A*(quoi que au final c'est peut être un algo de Dijkstra vu que j'ai presque tout virer de l'exemple de base A* que j'avais)
D'ailleurs, comme je ne connais pas grand chose au sujet de cet algo et que j'ai fait pas mal de modifications, je pense qu'il est possible de virer les new dans le AddSuccessor, mais je connais pas assez cet algo pour réussir et je préfère continuer d'autres chose pour l'instant. Si quelqu'un a une idée, je suis preneur.

Donc en image ça donne ceci:


X: Mur
Nombre: Valeur de mouvement requise pour se déplacer jusqu'à ce point
Vert: Coût de déplacement de 1
Rouge: Coût de déplacement de 5

https://dl.dropboxusercontent.com/u/4195829/A%20Star.7z

Code:
Code:
    /// <summary>
    /// Base class for pathfinding nodes, it holds no actual information about the map.
    /// An inherited class must be constructed from this class and all virtual methods must be
    /// implemented. Note, that calling base() in the overridden methods is not needed.
    /// </summary>
    public class AStarNode
    {
        public int XPos;
        public int YPos;

        public AStarNode Parent;
        public int MovementCost;

        public AStarNode(AStarNode Parent, int XPos, int YPos)
        {
            this.Parent = Parent;
            this.XPos = XPos;
            this.YPos = YPos;
        }

        /// <summary>
        /// Determines wheather the current node is the same state as the on passed.
        /// </summary>
        /// <param name="ANode">AStarNode to compare the current node to</param>
        /// <returns>Returns true if they are the same state</returns>
        public override bool Equals(object Node)
        {
            if (((AStarNode)Node) == null)
            {
                return false;
            }
            return (((AStarNode)Node).XPos == XPos && ((AStarNode)Node).YPos == YPos);
        }
    }

    /// <summary>
    /// Class for performing A* pathfinding
    /// </summary>
    public sealed class AStar
    {
        private List<AStarNode> ListSuccessors;
        private List<AStarNode> ListOpenNode;
        private List<AStarNode> ListCloseNode;
        public List<AStarNode>  ListAllNode;

        /// <summary>
        /// Holds the solution after pathfinding is done. <see>FindPath()</see>
        /// </summary>
        public List<AStarNode> Solution;

        public int[,] Map = {
            { 1,-1, 1, 1, 1,-1, 1, 1, 1, 1 },
            { 1,-1, 1,-1, 1,-1, 1, 1, 1, 1 },
            { 1,-1, 1,-1, 1,-1, 1, 1, 1, 1 },
            { 1,-1, 1,-1, 1,-1, 1, 1, 1, 1 },
            { 1,-1, 1,-1, 1,-1, 1, 5, 5, 5 },
            { 1,-1, 1,-1, 1,-1, 1, 1, 1, 1 },
            { 1,-1, 1,-1, 1,-1, 1, 1, 1, 1 },
            { 1,-1, 1,-1, 1,-1, 1, 1, 1, 1 },
            { 1,-1, 1,-1, 1,-1, 1, 1, 1, 1 },
            { 1, 1, 1,-1, 1, 1, 1, 1, 1, 1 }
        };

        public AStar()
        {
            ListSuccessors = new List<AStarNode>();
            Solution = new List<AStarNode>();
            ListOpenNode = new List<AStarNode>();
            ListCloseNode = new List<AStarNode>();
            ListAllNode = new List<AStarNode>();
        }

        public void AddSuccessor(AStarNode ActiveNode, int AX, int AY)
        {
            if (AX < 0 || AX > 9 || AY < 0 || AY > 9)
                return;
            int CurrentCost = Map[AX, AY];
            //Wall
            if (CurrentCost == -1)
            {
                return;
            }
            AStarNode NewNode = new AStarNode(ActiveNode, AX, AY);
            if (NewNode.Equals(ActiveNode.Parent))
            {
                return;
            }
            ListSuccessors.Add(NewNode);
        }

        public void PrintSolution(List<AStarNode> ASolution)
        {
            for (int j = 0; j < 10; j++)
            {
                for (int i = 0; i < 10; i++)
                {
                    bool solution = false;
                    int SolutionIndex;
                    for (SolutionIndex = 0; SolutionIndex < ASolution.Count; SolutionIndex++)
                    {
                        AStarNode tmp = new AStarNode(null, i, j);
                        solution = ASolution[SolutionIndex].Equals(tmp);
                        if (solution)
                            break;
                    }
                    if (solution)//Path chosen.
                    {
                        if (Map[i, j] == 1)
                            Console.ForegroundColor = ConsoleColor.Green;
                        if (Map[i, j] == 5)
                            Console.ForegroundColor = ConsoleColor.Red;
                        string Cost = ASolution[SolutionIndex].MovementCost.ToString();
                        while (Cost.Length < 3)
                            Cost += " ";
                        Console.Write(Cost);
                        Console.ResetColor();
                    }
                    else
                        if (Map[i, j] == -1)//if it's a wall.
                            Console.Write("X  ");
                        else
                            Console.Write(".  ");//Nothing.
                }
                Console.WriteLine("");
            }
        }

        public void GetSuccessors(AStarNode ActiveNode)
        {
            ListSuccessors.Clear();
            AddSuccessor(ActiveNode, ActiveNode.XPos - 1, ActiveNode.YPos);
            AddSuccessor(ActiveNode, ActiveNode.XPos + 1, ActiveNode.YPos);
            AddSuccessor(ActiveNode, ActiveNode.XPos, ActiveNode.YPos - 1);
            AddSuccessor(ActiveNode, ActiveNode.XPos, ActiveNode.YPos + 1);
            //Diagonal movement
            //AddSuccessor(ActiveNode, ActiveNode.XPos + 1, ActiveNode.YPos + 1);
            //AddSuccessor(ActiveNode, ActiveNode.XPos + 1, ActiveNode.YPos - 1);
            //AddSuccessor(ActiveNode, ActiveNode.XPos - 1, ActiveNode.YPos + 1);
            //AddSuccessor(ActiveNode, ActiveNode.XPos - 1, ActiveNode.YPos - 1);
        }

        public void FindPath(AStarNode AStartNode)
        {
            ListSuccessors.Clear();
            ListOpenNode.Clear();
            ListCloseNode.Clear();
            ListAllNode.Clear();

            AStarNode CurrentNode;

            ListOpenNode.Add(AStartNode);
            ListAllNode.Add(AStartNode);

            while (ListOpenNode.Count > 0)
            {
                //Use the node with the lowest cost.(Sort it first)
                CurrentNode = ListOpenNode[0];
                for (int i = 1; i < ListOpenNode.Count; i++)
                    if (ListOpenNode[i].MovementCost < CurrentNode.MovementCost)
                        CurrentNode = ListOpenNode[i];

                ListOpenNode.Remove(CurrentNode);
                ListCloseNode.Add(CurrentNode);
                // Get successors to the current node
                GetSuccessors(CurrentNode);
                foreach (AStarNode Neighbor in ListSuccessors)
                {
                    if (!ListAllNode.Contains(Neighbor))
                        ListAllNode.Add(Neighbor);

                    int MovementCostToNeighbor = CurrentNode.MovementCost + Map[Neighbor.XPos, Neighbor.YPos];

                    if (ListCloseNode.Contains(Neighbor) && MovementCostToNeighbor >= Neighbor.MovementCost)
                        continue;

                    if (!ListOpenNode.Contains(Neighbor) || MovementCostToNeighbor < Neighbor.MovementCost)
                    {
                        Neighbor.Parent = CurrentNode;
                        Neighbor.MovementCost = MovementCostToNeighbor;

                        if (!ListOpenNode.Contains(Neighbor))
                            ListOpenNode.Add(Neighbor);
                    }
                }
            }
        }
    }

Références:
http://www.codeproject.com/Articles/5758/Path-finding-in-C
http://en.wikipedia.org/wiki/A*_search_algorithm

_________________

Règle #1 du CBNA, ne pas chercher à faire dans la subtilité; personne comprend
Revenir en haut Aller en bas
BobLeNolife
Nouveau


Messages : 1

MessageSujet: Re: [C#] Calcul de mouvement avec A*   Jeu 16 Mai 2013 - 21:57

Mes des téléporteurs. Et des dinosaures aussi c'est toujours bien des programmes avec des dinosaures.
Revenir en haut Aller en bas
 
[C#] Calcul de mouvement avec A*
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» [C#] Calcul de mouvement avec A*
» [Obsolète] Une autre programme d'animation gratuit.
» bugs Oregon 400T
» Collision avec objet à mouvement vertical.
» Calcul de dénivelé par Memory Map

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum Le CBNA :: Développement :: Programmation-
Sauter vers: