Click here to Skip to main content
15,885,435 members
Articles / Programming Languages / C# 4.0

A Complex - Yet Quite Intelligible - Pathfinding in C#

Rate me:
Please Sign up or sign in to vote.
4.96/5 (41 votes)
30 Aug 2013CPOL21 min read 59.5K   2.5K   88  
A semi-analytic 2D path-finding for large dynamic scenarios.
using System;
using System.Drawing;
using YinYang.CodeProject.Projects.SimplePathfinding.Helpers;

namespace YinYang.CodeProject.Projects.SimplePathfinding.PathFinders.AStar
{
    public class AStarMap
    {
        #region | Fields |

        private readonly Int32 width;
        private readonly Int32 height;

        private Node[] nodes;
        private Int32[] fastY;

        private readonly PriorityQueue<Node> priorityQueue;

        #endregion

        #region | Properties |

        /// <summary>
        /// Gets the open nodes count.
        /// </summary>
        public Int32 OpenCount
        {
            get { return priorityQueue.Count; }
        }

        #endregion

        #region | Indexers |

        /// <summary>
        /// Gets the <see cref="Node"/> on a given coordinates.
        /// </summary>
        public Node this[Int32 x, Int32 y]
        {
            get { return nodes[x + fastY[y]]; }
        }

        #endregion

        #region | Constructors |

        /// <summary>
        /// Initializes a new instance of the <see cref="AStarMap"/> class.
        /// </summary>
        /// <param name="width">The width.</param>
        /// <param name="height">The height.</param>
        public AStarMap(Int32 width, Int32 height)
        {
            this.width = width;
            this.height = height;

            priorityQueue = new PriorityQueue<Node>();

            Clear();
            Precalculate();
        }

        #endregion

        #region | Helper methods |

        private void Precalculate()
        {
            fastY = new Int32[height];

            for (Int32 y = 0; y < height; y++)
            {
                fastY[y] = y * width;
            }
        }

        #endregion

        #region | Methods |

        /// <summary>
        /// Creates new open node on a map at given coordinates and parameters.
        /// </summary>
        public void OpenNode(Point point, Int32 score, Int32 estimatedScore, Node origin)
        {
            Node result = new Node(point, score, estimatedScore, origin);
            nodes[point.X + fastY[point.Y]] = result;
            priorityQueue.Enqueue(result);
        }

        /// <summary>
        /// Returns top node (best estimated score), and closes it.
        /// </summary>
        /// <returns></returns>
        public Node CloseTopNode()
        {
            Node result = priorityQueue.Dequeue();
            result.MarkClosed();
            return result;
        }

        /// <summary>
        /// Clears map for another round.
        /// </summary>
        public void Clear()
        {
            nodes = new Node[width * height];
            priorityQueue.Clear();
        }

        #endregion
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer
Czech Republic Czech Republic
Contacts: EMAIL - smartk8@gmail.com

Comments and Discussions