C#: A* applikasjon

[Velena]

Jeg har laget en A* applikasjon i C# som jeg gjerne vil dele. Annet enn formene som er til input/output, er det fire klasser: Node, og NodeGrid tar seg av å holde orden på dataene som brukes i algoritmen, mens AStar har ansvaret for selve kalkuleringen. GridPanel arver fra Panel, og består hovedsakelig av en override av OnPaint som håndterer renderingen. Akkurat dette er en flaskehals i programmet som jeg gjerne skulle vært foruten, så om noen kan gi råd om hvordan dette kan effektiviseres hadde det vært flott.

 

Kildekoden + de binære filene kan lastes ned via Mediafire. For de som ikke vil det har jeg lagt ved filene av størst interesse:

 

 

 public class AStar
   {
//Algoritmen er basert på Patrick Lester's artikkel: A* pathfinding for beginners
//http://www.policyalmanac.org/games/aStarTutorial.htm
       #region Private variables
       private List<Node> _openList;
       private List<Node> _closedList;
       private int _heuristicCost = 10;
       private NodeType _defaultType = NodeType.Pathable;
       #endregion
       #region Methods
       public List<Node> FindPath(NodeGrid grid)
       {
           _openList = new List<Node>();
           _closedList = new List<Node>();
           _openList.Add(grid.StartNode);

           while (!_closedList.Contains(grid.EndNode) && _openList.Count != 0)
           {

               Node currentNode = GetLowestFNode(_openList);
               _openList.Remove(currentNode);
               _closedList.Add(currentNode);
               if (currentNode == grid.EndNode)
               {
                   return GetParentPath(grid.StartNode, grid.EndNode);
               }
               List<Node> adjacentNodes = grid.GetAdjacentNodes(currentNode);
               for (int i = 0; i < adjacentNodes.Count; )
               {
                   Node nodeBuf = adjacentNodes[i];
                   if (nodeBuf.Type != NodeType.NonPathable && (!_closedList.Contains(nodeBuf)))
                   {

                       if (!_openList.Contains(nodeBuf))
                       {
                           nodeBuf.Parent = currentNode;
                           if (nodeBuf.Position.X != currentNode.Position.X && nodeBuf.Position.Y != currentNode.Position.Y)
                               nodeBuf.G = currentNode.G + nodeBuf.DiagonalCost;
                           else
                               nodeBuf.G = currentNode.G + nodeBuf.StandardCost;
                           nodeBuf.H = (Math.Abs(grid.EndNode.Position.X - nodeBuf.Position.X)  + Math.Abs(grid.EndNode.Position.Y - nodeBuf.Position.Y)) * _heuristicCost;
                           _openList.Add(nodeBuf);
                       }
                       else if (nodeBuf.G > currentNode.G + nodeBuf.StandardCost)
                       {
                           nodeBuf.Parent = currentNode;
                           if (nodeBuf.Position.X != currentNode.Position.X && nodeBuf.Position.Y != currentNode.Position.Y)
                               nodeBuf.G = currentNode.G + nodeBuf.DiagonalCost;
                           else
                               nodeBuf.G = currentNode.G + nodeBuf.StandardCost;
                       }
                   }
                   ++i;
               }

           }
           return null;
       }
       public List<Node> FindPathReportProgress(NodeGrid grid, BackgroundWorker worker)
       {
           _openList = new List<Node>();
           _closedList = new List<Node>();
           List<Node>[] lists = {_openList,_closedList};
           _openList.Add(grid.StartNode);

           while (!_closedList.Contains(grid.EndNode) && _openList.Count != 0)
           {

               Node currentNode = GetLowestFNode(_openList);
               _openList.Remove(currentNode);
               _closedList.Add(currentNode);
               if (currentNode == grid.EndNode)
               {
                   return GetParentPath(grid.StartNode, grid.EndNode);
               }
               List<Node> adjacentNodes = grid.GetAdjacentNodes(currentNode);
               for (int i = 0; i < adjacentNodes.Count; )
               {
                   Node nodeBuf = adjacentNodes[i];
                   if (nodeBuf.Type != NodeType.NonPathable && (!_closedList.Contains(nodeBuf)))
                   {

                       if (!_openList.Contains(nodeBuf))
                       {
                           nodeBuf.Parent = currentNode;
                           if (nodeBuf.Position.X != currentNode.Position.X && nodeBuf.Position.Y != currentNode.Position.Y)
                               nodeBuf.G = currentNode.G + nodeBuf.DiagonalCost;
                           else
                               nodeBuf.G = currentNode.G + nodeBuf.StandardCost;
                           nodeBuf.H = (Math.Abs(grid.EndNode.Position.X - nodeBuf.Position.X) + Math.Abs(grid.EndNode.Position.Y - nodeBuf.Position.Y)) * _heuristicCost;
                           _openList.Add(nodeBuf);
                       }
                       else if (nodeBuf.G > currentNode.G + nodeBuf.StandardCost)
                       {
                           nodeBuf.Parent = currentNode;
                           if (nodeBuf.Position.X != currentNode.Position.X && nodeBuf.Position.Y != currentNode.Position.Y)
                               nodeBuf.G = currentNode.G + nodeBuf.DiagonalCost;
                           else
                               nodeBuf.G = currentNode.G + nodeBuf.StandardCost;
                       }
                   }
                   ++i;
               }
               worker.ReportProgress(0,lists);
               System.Threading.Thread.Sleep(300);
           }
           return null;
       }
       public Node GetLowestFNode (List<Node>nodes)
       {
           int lowestFIndex = 0;
           for(int i = 0; i <nodes.Count;)
           {
               if (nodes[i].F < nodes[lowestFIndex].F)
                   lowestFIndex = i;
               ++i;
           }
           return nodes[lowestFIndex];
       }
       public List<Node>GetAdjacentNodes (NodeGrid grid, Node node)
       {
           int x = node.Position.X;
           int y = node.Position.Y;
           List<Node> nodesToReturn = new List<Node>();
           for (int i = -1; i < 2; )
           {
               for (int j = -1; j < 2; )
               {

                   if ((x + i >= 0 && y + j >= 0) && (x + i < grid.Width && y + j < grid.Height))
                   {
                       if (!(i == 0 && j == 0))
                       {
                           nodesToReturn.Add(grid.Grid[x + i, y + j]);
                       }
                   }
                   ++j;

               }
               ++i;
           }
           return nodesToReturn;
       }// TODO: Move this to NodeGrid.
       public void SetNodeType(NodeGrid grid, Node node, NodeType type, int diagonalCost, int standardCost)
       {
           if (type == NodeType.Start || type == NodeType.End)
           {
               Node prevNode = null;
               for (int i = 0; i < grid.Width; )
               {
                   for (int j = 0; j < grid.Height; )
                   {
                       if (grid.Grid[i, j].Type == type)
                       {
                           prevNode = grid.Grid[i, j];
                           prevNode.Type = _defaultType;
                           continue;
                       }
                       ++j;
                   }
                   ++i;
                   if (prevNode != null)
                       continue;
               }
           }
           else if (type == NodeType.CustomCost)
           {
               node.DiagonalCost = diagonalCost;
               node.StandardCost = standardCost;
           }
           else if (type == NodeType.Pathable)
           {
               node.StandardCost = grid.StandardCost;
               node.DiagonalCost = grid.DiagonalCost;
           }
           node.Type = type;
       }//TODO:-----""-------
       private List<Node> GetParentPath(Node startNode, Node endNode)
       {
           List<Node> nodesToReturn = new List<Node>();
           Node currentParent = endNode.Parent;
           while(currentParent != startNode && currentParent != null)
           {
               nodesToReturn.Add(currentParent);
               currentParent = currentParent.Parent;
           }
           if (currentParent == null)
               return null;//Could not find a path to the starting node
           else
               return nodesToReturn;
       }
       #endregion
   }

 

 

 public class Node
   {
       #region Private Variables
       private int _f = 0;
       private int _g = 0;
       private int _h = 0;
       private int _standardCost = 10;
       private int _diagonalCost = 14;
       private Node _parent = null;
       private Point _pos= new Point(0,0);
       private NodeType _type = NodeType.Pathable;
       #endregion
       #region Properties
       public int F
       {
           get 
           { 
               return _f; 
           }
           set 
           { 
               _f = value; 
           }
       }
       public int G
       {
           get 
           { 
               return _g; 
           }
           set
           {
               _g = value;
               _f = _g + _h;
           }
       }
       public int H
       {
           get
           {
               return _h;
           }
           set
           {
               _h = value;
               _f = _g + _h;
           }
       }
       public int StandardCost
       {
           get
           {
               return _standardCost;
           }
           set
           {
               _standardCost = value;
           }
       }
       public int DiagonalCost
       {
           get
           {
               return _diagonalCost;
           }
           set
           {
               _diagonalCost = value;
           }
       }

       public Node Parent
       {
           get
           {
               return _parent;
           }
           set
           {
               _parent = value;
           }
       }
       public Point Position
       {
           get
           {
               return _pos;
           }
           set
           {
               _pos = value;
           }
       }
       public NodeType Type
       {
           get
           {
               return _type;
           }
           set
           {
               _type = value;
           }
       }
       #endregion
       #region Constructor
       public Node(Point position)
       {
           _pos = position;
       }
       #endregion
   }
   public enum NodeType
   {
       Pathable = 0,
       NonPathable= 1,
       Start= 2,
       End=3,
       CustomCost=4
   }

 

 

 public class NodeGrid
   {
       #region Private variables
       private int _height = 0;
       private int _width = 0;
       #endregion
       #region Public variables
       public int StandardCost = 10;
       public int DiagonalCost = 14;
       public Node[,] Grid;
       public Node StartNode, EndNode;
       #endregion
       #region Properties
       public int Height
       {
           get
           {
               return _height;
           }
           set
           {
               _height = value;
           }
       }
       public int Width
       {
           get
           {
               return _width;
           }
           set
           {
               _width = value;
           }
       }
       #endregion
       #region Constructors
       public NodeGrid (int height, int width)
       {
           if (width > 0 && height > 0)
           {
               _width = width;
               _height = height;
               Initialize();
           }
           else
               throw new ArgumentNullException("The bounds of the grid must be greater than zero.");
       }
       #endregion
       #region Indexer
       public Node this[int x, int y]
       {
           get
           {
               return Grid[x, y];
           }
           set 
           { 
               Grid[x, y] = value;
           }
       }
       #endregion
       #region Methods
       public void Initialize ()
       {
           Grid = new Node[Width, Height];

           for (int i = 0; i < Width; )
           {
               for (int j = 0; j < Height; )
               {
                   Grid[i, j] = new Node(new Point(i, j));
                   Grid[i, j].StandardCost = StandardCost;
                   Grid[i, j].DiagonalCost = DiagonalCost;
                   Grid[i, j].F = int.MaxValue;
                   Grid[i, j].G = int.MaxValue;
                   Grid[i, j].H = int.MaxValue;
                   ++j;
               }
               ++i;
           }
       }
       public void Reset()
       {
           for (int i = 0; i < Width; )
           {
               for (int j = 0; j < Height; )
               {
                   Grid[i, j].F = int.MaxValue;
                   Grid[i, j].G = int.MaxValue;
                   Grid[i, j].H = int.MaxValue;
                   Grid[i, j].Parent = null;
                   ++j;
               }
               ++i;
           }
       }
       public List<Node> GetAdjacentNodes(Node node)
       {
           int x = node.Position.X;
           int y = node.Position.Y;
           List<Node> nodesToReturn = new List<Node>();
           for (int i = -1; i < 2; )
           {
               for (int j = -1; j < 2; )
               {

                   if ((x + i >= 0 && y + j >= 0) && (x + i < Width && y + j < Height))
                   {
                       if (!(i == 0 && j == 0))
                       {
                           nodesToReturn.Add(Grid[x + i, y + j]);
                       }
                   }
                   ++j;

               }
               ++i;
           }
           return nodesToReturn;
       }
       public void SetNodeType(Node node, NodeType type, int diagonalCost, int standardCost)
       {
           switch (type)
           {
               case NodeType.Start:
                   if (StartNode != null)
                       StartNode.Type = NodeType.Pathable;
                   StartNode = node;
                   if (node.Type == NodeType.End)
                       EndNode = null;
                   break;
               case NodeType.End:
                   if (EndNode != null)
                   {
                       EndNode.Type = NodeType.Pathable;
                   }
                   if (node.Type == NodeType.Start)
                       StartNode = null;
                   EndNode = node;
                   break;
               case NodeType.CustomCost:
                   node.DiagonalCost = diagonalCost;
                   node.StandardCost = standardCost;
                   if (node.Type == NodeType.Start)
                       StartNode = null;
                   else if (node.Type == NodeType.End)
                       EndNode = null;
                   break;
               case NodeType.Pathable:
                   node.StandardCost = StandardCost;
                   node.DiagonalCost = DiagonalCost;
                   if (node.Type == NodeType.Start)
                       StartNode = null;
                   else if (node.Type == NodeType.End)
                       EndNode = null;
                   break;
           }
           node.Type = type;
       }
       #endregion
   }

 

 

public class GridPanel:Panel
   {
       #region Public variables
       public NodeGrid Grid = new NodeGrid(5, 5);
       public List<Node> CurrentPath = new List<Node>();
       public List<Node> CurrentOpenList = new List<Node>();
       public List<Node> CurrentClosedList = new List<Node>();
       public int NodeWidth=60;
       public int NodeHeight=60;
       #endregion
       #region Private variables
       private SolidBrush _startBrush = new SolidBrush(Color.Yellow),
           _endBrush = new SolidBrush(Color.Orange),
           _nonpathableBrush = new SolidBrush(Color.Green),
           _edgeBrush = new SolidBrush(Color.Black),
           _backgroundBrush = new SolidBrush(Color.White),
           _currentPathBrush = new SolidBrush(Color.Magenta),
           _currentOpenListBrush = new SolidBrush(Color.BlueViolet),
           _currentClosedListBrush = new SolidBrush(Color.Blue),
           _customCostBrush = new SolidBrush(Color.Red);
       #endregion
       #region Overrides
       protected override void OnPaint(PaintEventArgs e)// TODO: Optimize this.
       {
           //base.OnPaint(e);
           e.Graphics.Clear(Color.White);

           if (CurrentClosedList != null && CurrentClosedList.Count != 0)
           {
               for (int i = 0; i < CurrentClosedList.Count; )
               {
                   e.Graphics.FillRectangle(_currentClosedListBrush, new Rectangle(CurrentClosedList[i].Position.X * NodeWidth, CurrentClosedList[i].Position.Y * NodeHeight, NodeWidth, NodeHeight));
                   ++i;
               }
           }
           if (CurrentOpenList != null && CurrentOpenList.Count != 0)
           {
               for (int i = 0; i < CurrentOpenList.Count; )
               {
                   e.Graphics.FillRectangle(_currentOpenListBrush, new Rectangle(CurrentOpenList[i].Position.X * NodeWidth, CurrentOpenList[i].Position.Y * NodeHeight, NodeWidth, NodeHeight));
                   ++i;
               }
           }
           if (CurrentPath != null)// TODO: Find a way to include this loop in the one above. 
           {
               if (CurrentPath.Count != 0)
               {
                   for (int i = 0; i < CurrentPath.Count; )
                   {
                       e.Graphics.FillRectangle(_currentPathBrush, new Rectangle(CurrentPath[i].Position.X * NodeWidth, CurrentPath[i].Position.Y * NodeHeight, NodeWidth, NodeHeight));
                       ++i;
                   }
               }
           }

           for (int i = 0; i < Grid.Width; )
           {
               for (int j = 0; j < Grid.Height; )
               {
                   switch (Grid[i, j].Type)
                   {
                       case NodeType.Start:
                           e.Graphics.FillRectangle(_startBrush, new Rectangle(i * NodeWidth, j * NodeHeight, NodeWidth, NodeHeight));
                           break;
                       case NodeType.End:
                           e.Graphics.FillRectangle(_endBrush, new Rectangle(i * NodeWidth, j * NodeHeight, NodeWidth, NodeHeight));
                           break;
                       case NodeType.NonPathable:
                           e.Graphics.FillRectangle(_nonpathableBrush, new Rectangle(i * NodeWidth, j * NodeHeight, NodeWidth, NodeHeight));
                           break;
                       case NodeType.Pathable:

                           //e.Graphics.FillRectangle(_backgroundBrush, new Rectangle(i * NodeWidth, j * NodeHeight, NodeWidth, NodeHeight));
                           break;
                       case NodeType.CustomCost:
                           e.Graphics.FillRectangle(_customCostBrush, new Rectangle(i * NodeWidth, j * NodeHeight, NodeWidth, NodeHeight));
                           break;
                       default:
                           break;
                   }
                   e.Graphics.DrawRectangle(new Pen(new SolidBrush(Color.Black)), new Rectangle(i * NodeWidth, j * NodeHeight, NodeWidth, NodeHeight));
                   ++j;
               }
               ++i;
           }

       }
       #endregion
       #region Methhods
       public void ClearLists()
       {
           CurrentOpenList = null;
           CurrentClosedList = null;
       }
       #endregion
   }

 

 

Om GUIet ikke er intuitivt nok, har jeg og laget en liten video som viser hvordan programmet fungerer:

 

Tilbakemelding er som alltid ønsket.

[etse]

Ut i fra videoen ser det ut som du oppdaterer hele skjermen hver gang man trykker og endrer en rute. I så fall ville jeg sørget for at programmet kun redret den ene ruta på nytt igjen når man trykket. Og ikke rendret noe om det ikke var noen endringer.

[GeirGrusom]

Det er nok det at han kaller e.Graphics.Clear på OnPaint. Dette skal være unødvendig.

 

Det er laget en forkortet versjon for properties, slik at du skal slippe å definere dem to ganger:

 

public class Sample
{
 public string Name { get; set; }
 public int ID { get; private set; }

 public Sample()
 {
   ID = 100;
 }
}

 

Ellers ser alt ut til å fungere flott

[Velena]

Etse: Jeg har fikset det nå (Har dog ikke oppdatert linkene).

 

GeirGrusom: Det går raskere etter at jeg fjernet e.Graphics.Clear(), men det er fremdeles en merkbar flikkring hver gang kontrollen blir oppdatert, dette øker jo flere noder det er. Ang. properties, er ikke det beste å bare deklarere variabelen som public om du ikke trenger å vite når den oppdateres?

 

En ting til: Jeg kom i skade for å lage en infinite loop i OnPaint metoden til GridPanel:blush:, noe som fører til at VS låser seg hver gang jeg åpner prosjektet. Hvordan fikser jeg dette?

[Degeim]

Du kan løse det siste problemet ved å åpne filen i notisblokk og redigere bort loopen din.

[GeirGrusom]

Etse: Jeg har fikset det nå (Har dog ikke oppdatert linkene).

 

GeirGrusom: Det går raskere etter at jeg fjernet e.Graphics.Clear(), men det er fremdeles en merkbar flikkring hver gang kontrollen blir oppdatert, dette øker jo flere noder det er. Ang. properties, er ikke det beste å bare deklarere variabelen som public om du ikke trenger å vite når den oppdateres?

 

En ting til: Jeg kom i skade for å lage en infinite loop i OnPaint metoden til GridPanel:blush:, noe som fører til at VS låser seg hver gang jeg åpner prosjektet. Hvordan fikser jeg dette?

Å bare deklarere variabler publig har ingen hensikt ytelsesmesssig (properties blir inlinet under normale omstendigheter) og er en ulempe med tanke på reflection og videre oppdatering av programmet.

Bruk properties med mindre du har en spesifikk grunn til å ikke gjøre det.

 

Det jeg merker, er at dersom en tegner rett på en kontroll med OnPaint, så vil det ofte bli flimring. Jeg vet om en "hack" for å omgå dette, og det er enkelt nok å plassere en picturebox på kontrollen, og tegne på den istedet gjennom Paint eventet. Fuglene vet hvorfor det spiller noen rolle, men det gjør det ihvertfall.

 

For å fikse den feilen, kan du prøve slette alt i temp mappa di, og i binærmappa til programmet.

[Wedvich]

Du kunne jo forsøkt double buffering for å motvirke flimringen? Da vil den tegne ferdig neste "bilde" i bakgrunnen før den viser det til brukeren.

 

public class GridPanel:Panel
{
// alt det andre

public GridPanel()
{
	this.SetStyle(ControlStyles.DoubleBuffer |
		ControlStyles.UserPaint |
		ControlStyles.AllPaintingInWmPaint,
		true);
	this.UpdateStyles();
}
}

[GeirGrusom]

Skal ikke være nødvendig.

[Velena]

GeirGrusom: Takk for informasjonen, ser ut til at jeg har blitt misinformert.

 

Wedvich: Ser ut til å fungere bedre med Double-buffering, men jeg tror den største forskjellen kom fra at jeg gikk fra å tegne rutene en for en til å bare dra hele linjer fra ende til ende på kontrollen.

 

Uansett så virker programmet knirkefritt nå, så takk igjen alle sammen =).