AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  Connexion  

Partagez
 

 [C#] Calcul de mouvement avec A*

Aller en bas 
AuteurMessage
Wargamer
*Excellent utilisateur*
Wargamer

Messages : 6936
Projet Actuel : Bataille de cake au fruits

[C#] Calcul de mouvement avec A* Empty
MessageSujet: [C#] Calcul de mouvement avec A*   [C#] Calcul de mouvement avec A* EmptyJeu 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:
[C#] Calcul de mouvement avec A* O60PlQF

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

_________________
[C#] Calcul de mouvement avec A* Wargamer3
Règle #1 du CBNA, ne pas chercher à faire dans la subtilité; personne comprend
Revenir en haut Aller en bas
BobLeNolife
Nouveau


Messages : 1

[C#] Calcul de mouvement avec A* Empty
MessageSujet: Re: [C#] Calcul de mouvement avec A*   [C#] Calcul de mouvement avec A* EmptyJeu 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*
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Cycle de 26 jours = à combien de jour l'ovulation??
» calcul perimetre avec collimateur
» Calcul de RCA
» Calcul de remise en suspension de poussières
» recherche modèle de contrat (avec dérogation scolaire)

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