Commits

Robin Harper committed 3ebe40b

Initial Import

  • Participants

Comments (0)

Files changed (7)

File AstarPath.sln

+
+Microsoft Visual Studio Solution File, Format Version 11.00
+# Visual Studio 2010
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "AstarPath", "AstarPath\AstarPath.csproj", "{00BA3E47-FFBD-421B-B13D-98F02A25D115}"
+EndProject
+Global
+	GlobalSection(SolutionConfigurationPlatforms) = preSolution
+		Debug|Any CPU = Debug|Any CPU
+		Release|Any CPU = Release|Any CPU
+	EndGlobalSection
+	GlobalSection(ProjectConfigurationPlatforms) = postSolution
+		{00BA3E47-FFBD-421B-B13D-98F02A25D115}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{00BA3E47-FFBD-421B-B13D-98F02A25D115}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{00BA3E47-FFBD-421B-B13D-98F02A25D115}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{00BA3E47-FFBD-421B-B13D-98F02A25D115}.Release|Any CPU.Build.0 = Release|Any CPU
+	EndGlobalSection
+	GlobalSection(SolutionProperties) = preSolution
+		HideSolutionNode = FALSE
+	EndGlobalSection
+EndGlobal

File AstarPath/AstarPath.csproj

+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProductVersion>8.0.30703</ProductVersion>
+    <SchemaVersion>2.0</SchemaVersion>
+    <ProjectGuid>{00BA3E47-FFBD-421B-B13D-98F02A25D115}</ProjectGuid>
+    <OutputType>Library</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>AstarPath</RootNamespace>
+    <AssemblyName>AstarPath</AssemblyName>
+    <TargetFrameworkVersion>v3.5</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+    <TargetFrameworkProfile />
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+    <DebugSymbols>true</DebugSymbols>
+    <DebugType>full</DebugType>
+    <Optimize>false</Optimize>
+    <OutputPath>bin\Debug\</OutputPath>
+    <DefineConstants>DEBUG;TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <PropertyGroup>
+    <SignAssembly>false</SignAssembly>
+  </PropertyGroup>
+  <PropertyGroup>
+    <AssemblyOriginatorKeyFile>
+    </AssemblyOriginatorKeyFile>
+  </PropertyGroup>
+  <ItemGroup>
+    <Reference Include="System" />
+    <Reference Include="System.Core" />
+    <Reference Include="System.Drawing" />
+    <Reference Include="System.Xml.Linq" />
+    <Reference Include="System.Data.DataSetExtensions" />
+    <Reference Include="Microsoft.CSharp" />
+    <Reference Include="System.Data" />
+    <Reference Include="System.Xml" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="AstarPathfinder.cs" />
+    <Compile Include="GridNode.cs" />
+    <Compile Include="Location.cs" />
+    <Compile Include="PathfinderUtilities.cs" />
+    <Compile Include="Properties\AssemblyInfo.cs" />
+  </ItemGroup>
+  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
+  <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
+       Other similar extension points exist, see Microsoft.Common.targets.
+  <Target Name="BeforeBuild">
+  </Target>
+  <Target Name="AfterBuild">
+  </Target>
+  -->
+</Project>

File AstarPath/AstarPathfinder.cs

+//==================================================================================================
+//
+//   Copyright 2010 Robin C. Harper 
+//
+//   Licensed under the Apache License, Version 2.0 (the "License");
+//   you may not use this file except in compliance with the License.
+//   You may obtain a copy of the License at
+//
+//       http://www.apache.org/licenses/LICENSE-2.0
+//
+//   Unless required by applicable law or agreed to in writing, software
+//   distributed under the License is distributed on an "AS IS" BASIS,
+//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+//   See the License for the specific language governing permissions and
+//   limitations under the License.
+//
+//==================================================================================================
+
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Drawing;
+using System.Linq;
+
+namespace AstarPath
+{
+    [Serializable]
+    public class AstarPathfinder
+    {
+        private const double Alpha = 0.4999;
+        private const double DefaultCost = 1.0;
+        private const int MaxEstimatedPathLength = 1500;
+        private readonly int DirectionalMove = 1;
+        private const double Nudge = DefaultCost / MaxEstimatedPathLength;
+        public readonly int[,] Obstacles;
+        public readonly List<GridNode> Grid;
+
+        public readonly int BitmapHeight;
+        public readonly int BitmapWidth;
+
+        public readonly PathfinderUtilities.PathfinderType CurrentPathfinderType;
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="map"></param>
+        /// <param name="type"></param>
+        /// <param name="size"></param>
+        public AstarPathfinder(Bitmap map, PathfinderUtilities.PathfinderType type, int size)
+        {
+            BitmapHeight = map.Height;
+            BitmapWidth = map.Width;
+            CurrentPathfinderType = type;
+            Obstacles = PathfinderUtilities.GetObstacles(map);
+            Grid = PathfinderUtilities.CreateGrid(map, Obstacles, size);
+
+            switch (type)
+            {
+                case PathfinderUtilities.PathfinderType.AdvancedManhattan:
+                    DirectionalMove = 4;
+                    break;
+                case PathfinderUtilities.PathfinderType.Euclidean:
+                    DirectionalMove = 8;
+                    break;
+                default:
+                    DirectionalMove = 1;
+                    break;
+            }
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="inputStart"></param>
+        /// <param name="inputGoal"></param>
+        /// <returns></returns>
+        public List<GridNode> GridSearch(Point inputStart, Point inputGoal)
+        {
+            List<GridNode> opened = new List<GridNode>();
+            List<GridNode> closed = new List<GridNode>();
+            var start = Grid.FirstOrDefault(t => t.PointsInsideGrid.Contains(inputStart));
+            var goal = Grid.FirstOrDefault(t => t.PointsInsideGrid.Contains(inputGoal));
+
+            if (start != null && goal != null)
+            {
+                if (goal.IsObstacle)
+                {
+                    goal.IsObstacle = false;
+                }
+
+                if (start.IsObstacle)
+                {
+                    start.IsObstacle = false;
+                }
+
+                start = UpdateHeuristics(start, start, start, goal);
+                opened.Add(start);
+
+                while (opened.Count > 0)
+                {
+                    //opened = BubbleSort.SortImageGridF(opened);
+                    opened.Sort(GridNode.CompareNodesByCost);
+                    var parent = opened[0];
+                    closed.Add(parent);
+                    opened.RemoveAt(0);
+
+                    if ((parent.GridBorder == goal.GridBorder) || opened.Count >= MaxEstimatedPathLength)
+                    {
+                        goal = parent;
+                        opened.Clear();
+                        break;
+                    }
+                    else
+                    {
+                        var adjacentNodes = PathfinderUtilities.FindAdjacentNodes(
+                            Grid, 
+                            parent, 
+                            CurrentPathfinderType,
+                            Obstacles,
+                            BitmapHeight, 
+                            BitmapHeight);
+
+                        adjacentNodes = UpdateHeuristics(adjacentNodes, parent, start, goal);
+
+                        if (adjacentNodes.Count > 0)
+                        {
+                            foreach (var node in adjacentNodes)
+                            {
+                                var closedXList = closed.FindAll(t => t.X == node.X);
+                                var onClosed = closedXList.Find(t => t.Y == node.Y);
+
+                                var openedXList = opened.FindAll(t => t.X == node.X);
+                                var onOpened = openedXList.Find(t => t.Y == node.Y);
+
+                                if (onClosed == null)
+                                {
+                                    opened.Add(node);
+                                }
+                            }
+                        }
+                    }
+                }
+
+                //return closed;
+                return PathToStart(goal);
+            }
+            else
+            {
+                throw new ArgumentNullException("start and/or goal could not be found in the current grid.", new Exception());
+            }
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="adjacentNodes"></param>
+        /// <param name="parent"></param>
+        /// <param name="start"></param>
+        /// <param name="goal"></param>
+        /// <returns></returns>
+        private List<GridNode> UpdateHeuristics(
+            List<GridNode> adjacentNodes, 
+            GridNode parent, 
+            GridNode start, 
+            GridNode goal)
+        {
+            var updated = new List<GridNode>();
+            foreach(var localGridBlock in adjacentNodes)
+            {
+                updated.Add(UpdateHeuristics(localGridBlock, parent, start, goal));
+            }
+
+            return updated;
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="neighboor"></param>
+        /// <param name="parent"></param>
+        /// <param name="start"></param>
+        /// <param name="goal"></param>
+        /// <returns></returns>
+        private GridNode UpdateHeuristics(GridNode neighboor, GridNode parent, GridNode start, GridNode goal)
+        {
+            var center = CalculateHeuristics(neighboor.Center, parent.Center, start.Center, goal.Center);
+            var newNeighboor = new GridNode(neighboor.GridBorder, neighboor.IsObstacle, center, parent);
+
+            return newNeighboor;
+        }
+
+        /// <summary>
+        /// A method for grouping all the heuristic calculations together
+        /// </summary>
+        /// <param name="neighboor"></param>
+        /// <param name="parent"></param>
+        /// <param name="goal"></param>
+        /// <returns></returns>
+        private Location CalculateHeuristics(Location neighboor, Location parent, Location start, Location goal)
+        {
+            var g = CalculateG(parent, neighboor);
+            var h = 0.0;
+            switch(CurrentPathfinderType)
+            {
+                case PathfinderUtilities.PathfinderType.BasicManhattan:
+                    h = CalculateHWithBasicManhattan(neighboor, parent, start, goal);
+                    break;
+                case PathfinderUtilities.PathfinderType.AdvancedManhattan:
+                    h = CalculateHWithAdvancedManhattan(neighboor, parent, start, goal);
+                    break;
+                case PathfinderUtilities.PathfinderType.Euclidean:
+                    h = CalculateHWithEuclidian(neighboor, parent, start, goal);
+                    break;
+            }
+
+             var f = (Alpha * g) + (((DefaultCost - Alpha) * h) / Math.Max(Alpha, (DefaultCost - Alpha)));
+
+             return new Location(neighboor.x, neighboor.y, g, f, h);
+        }
+
+        /// <summary>
+        /// This is an implementation of the basic manhattan heuristic.
+        /// 
+        /// It does not take diagnols so it only travels in N,S,E,W directions
+        /// </summary>
+        /// <param name="neighboor">The node we are looking at</param>
+        /// <param name="parent">The current node from which we are looking at the neighboors of</param>
+        /// <param name="start">The original start position on the map</param>
+        /// <param name="goal">Our goal position on the map</param>
+        /// <returns></returns>
+        private double CalculateHWithBasicManhattan(Location neighboor, Location parent, Location start, Location goal)
+        {
+            var h = GetCost(parent, neighboor) * ((Math.Abs(neighboor.x - goal.x) + Math.Abs(neighboor.y - goal.y)));
+            return CalculateSimpleNudge(h);
+        }
+
+        /// <summary>
+        /// Manhattan distance with diagonals factored in
+        /// 
+        /// This is the most optimal choice for this implementation
+        /// </summary>
+        /// <param name="neighboor">The node we are looking at</param>
+        /// <param name="parent">The current node from which we are looking at the neighboors of</param>
+        /// <param name="start">The original start position on the map</param>
+        /// <param name="goal">Our goal position on the map</param>
+        /// <returns></returns>
+        private double CalculateHWithAdvancedManhattan(Location neighboor, Location parent, Location start, Location goal)
+        {
+            var h = GetCost(parent, neighboor) * Math.Max(Math.Abs(neighboor.x - goal.x), Math.Abs(neighboor.y - goal.y));
+            return CalculateComplexNudge(h, parent.ToPoint(), start.ToPoint(), goal.ToPoint());
+        }
+
+        /// <summary>
+        /// Euclidean distance
+        /// </summary>
+        /// <param name="neighboor">The node we are looking at</param>
+        /// <param name="parent">The current node from which we are looking at the neighboors of</param>
+        /// <param name="start">The original start position on the map</param>
+        /// <param name="goal">Our goal position on the map</param>
+        /// <returns></returns>
+        private double CalculateHWithEuclidian(Location neighboor, Location parent, Location start, Location goal)
+        {
+            var h = GetCost(parent, neighboor) * (Math.Sqrt(Math.Pow((neighboor.x - goal.x), 2) + Math.Pow((neighboor.y - goal.y), 2)));
+            return CalculateSimpleNudge(h);
+        }
+
+        /// <summary>
+        /// The calculation of the cost of moving from the parent node
+        /// to the next node
+        /// </summary>
+        /// <param name="parentLocation"></param>
+        /// <param name="alpha"></param>
+        /// <returns></returns>
+        private double CalculateG(Location parentLocation, Location currentLocation)
+        {
+            return GetCost(parentLocation, currentLocation) + parentLocation.g;
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="start"></param>
+        /// <param name="goal"></param>
+        /// <returns></returns>
+        private double GetCost(Location start, Location goal)
+        {
+            return (Obstacles[start.x, start.y] + Obstacles[goal.x, goal.y]) * DirectionalMove;
+        }
+
+        /// <summary>
+        /// Simple nudge, evolves into more diagonal steps
+        /// </summary>
+        /// <param name="existingH"></param>
+        /// <returns></returns>
+        private double CalculateSimpleNudge(double existingH)
+        {
+            return existingH *= 1.0 + Nudge;
+        }
+
+        /// <summary>
+        /// Favors straight paths
+        /// </summary>
+        /// <param name="existingH"></param>
+        /// <returns></returns>
+        private double CalculateComplexNudge(double existingH, Point current, Point start, Point goal)
+        {
+            int dx1 = current.X - goal.X;
+            int dy1 = current.Y - goal.Y;
+            int dx2 = start.X - goal.X;
+            int dy2 = start.Y - goal.Y;
+            double cross = Math.Abs((dx1 * dy2) - (dx2 * dy1));
+            existingH += cross * Nudge;
+            return existingH;
+        }
+
+        /// <summary>
+        /// Traces the path back to the goal node, following only the
+        /// parent objects which represent the 'best' path that we found
+        /// </summary>
+        /// <param name="node">The last node in the closed list</param>
+        /// <returns></returns>
+        private List<GridNode> PathToStart(GridNode node)
+        {
+            var paths = new List<GridNode>();
+
+            while (true)
+            {
+                paths.Add(node);
+                if (node.Parent != null)
+                {
+                    node = node.Parent;
+                }
+                else
+                {
+                    break;
+                }
+            }
+
+            paths.Reverse();
+            return paths;
+        }
+    }
+}

File AstarPath/GridNode.cs

+//==================================================================================================
+//
+//   Copyright 2010 Robin C. Harper 
+//
+//   Licensed under the Apache License, Version 2.0 (the "License");
+//   you may not use this file except in compliance with the License.
+//   You may obtain a copy of the License at
+//
+//       http://www.apache.org/licenses/LICENSE-2.0
+//
+//   Unless required by applicable law or agreed to in writing, software
+//   distributed under the License is distributed on an "AS IS" BASIS,
+//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+//   See the License for the specific language governing permissions and
+//   limitations under the License.
+//
+//==================================================================================================
+
+using System.Collections.Generic;
+using System.Drawing;
+
+namespace AstarPath
+{
+    public class GridNode
+    {
+        public readonly List<Point> PointsInsideGrid;
+        public readonly Rectangle GridBorder;
+        public readonly Location Center = null;
+        public readonly GridNode Parent = null;
+
+        // Grid block x, y. Not related to pixel coordinates
+        public readonly int X;
+        public readonly int Y;
+        // Center point of the grid block in pixel coordinates 
+        public readonly int PixelX;
+        public readonly int PixelY;
+
+        public string Name { get { return "("+X+","+Y+")"; } }
+        public readonly int Size;
+        public bool IsObstacle;
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="inputGridBlock"></param>
+        /// <param name="obstacle"></param>
+        /// <param name="center"></param>
+        /// <param name="parent"></param>
+        public GridNode(Rectangle inputGridBlock, bool obstacle, Location center, GridNode parent)
+        {
+            IsObstacle = obstacle;
+            GridBorder = inputGridBlock;
+            Size = inputGridBlock.Height;
+            Parent = parent;
+            Center = center;
+
+            X = GridBorder.X;
+            Y = GridBorder.Y;
+            PixelX = Center.x;
+            PixelY = Center.y;
+
+            PointsInsideGrid = CalculateInnerPoints();
+        }
+
+        /// <summary>
+        /// Creates a list of all the x,y points inside of the given
+        /// grid.
+        /// 
+        /// Returns a pixel-correct list which can be used to search for if 
+        /// a given point exists within this grid block.
+        /// </summary>
+        /// <returns></returns>
+        private List<Point> CalculateInnerPoints()
+        {
+            var points = new List<Point>();
+            var tp = PathfinderUtilities.GetTopLeftPoint(PixelX, PixelY, Size);
+            var TopLeftPixelX = tp.X;
+            var TopLeftPixelY = tp.Y;
+            for(int x = 0; x < GridBorder.Width; x++)
+            {
+                for (int y = 0; y < GridBorder.Height; y++)
+                {
+                    var localPoint = new Point(TopLeftPixelX + x, TopLeftPixelY + y);
+
+                    if ((localPoint.X < TopLeftPixelX + Size) && 
+                        (localPoint.Y < TopLeftPixelY + Size))
+                    {
+                        points.Add(localPoint);
+                    }
+                }
+            }
+
+            return points;
+        }
+
+        /// <summary>
+        /// The Center object is the pixel coordinate object for the
+        /// center of this node. The object contains properties that
+        /// hold the cost and current distance from our target from
+        /// this current node
+        /// </summary>
+        /// <param name="a"></param>
+        /// <param name="b"></param>
+        /// <returns></returns>
+        public static int CompareNodesByCost(GridNode a, GridNode b)
+        {
+            if (a == null)
+            {
+                if (b == null)
+                {
+                    // equal
+                    return 0;
+                }
+                else
+                {
+                    // b was greater than a
+                    return -1;
+                }
+            }
+            else
+            {
+                if (b == null)
+                {
+                    // a was greater than b
+                    return 1;
+                }
+                else
+                {
+                    int retval = a.Center.f.CompareTo(b.Center.f);
+
+                    if (retval != 0)
+                    {
+                        return retval;
+                    }
+                    else
+                    {
+                        // in the event the costs are the same return them as 
+                        // equal so that we don't end up moving low cost items
+                        // to far away from the top
+                        return 0;
+                    }
+                }
+            }
+        }
+    }
+}

File AstarPath/Location.cs

+//==================================================================================================
+//
+//   Copyright 2010 Robin C. Harper 
+//
+//   Licensed under the Apache License, Version 2.0 (the "License");
+//   you may not use this file except in compliance with the License.
+//   You may obtain a copy of the License at
+//
+//       http://www.apache.org/licenses/LICENSE-2.0
+//
+//   Unless required by applicable law or agreed to in writing, software
+//   distributed under the License is distributed on an "AS IS" BASIS,
+//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+//   See the License for the specific language governing permissions and
+//   limitations under the License.
+//
+//==================================================================================================
+
+using System;
+using System.Collections.Generic;
+using System.Drawing;
+using System.Text;
+using System.ComponentModel;
+
+namespace AstarPath
+{
+    [Serializable]
+    public class Location : INotifyPropertyChanged
+    {
+        public string _name;
+        public string Name
+        {
+            get { return _name; }
+            private set
+            {
+                _name = value;
+                OnPropertyChanged("Name");
+            }
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        public readonly int x;
+        public readonly int y;
+
+        /// <summary>
+        /// 
+        /// </summary>
+        public readonly double g;
+        public readonly double h;
+        public readonly double f;
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="x"></param>
+        /// <param name="y"></param>
+        /// <param name="g"></param>
+        /// <param name="f"></param>
+        /// <param name="h"></param>
+        public Location(int x, int y, double g, double f, double h)
+        {
+            this.x = x;
+            this.y = y;
+            this.g = g;
+            this.h = h;
+            this.f = f;
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="name"></param>
+        /// <param name="x"></param>
+        /// <param name="y"></param>
+        public Location(string name, int x, int y)
+        {
+            Name = name;
+            this.x = x;
+            this.y = y;
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="x"></param>
+        /// <param name="y"></param>
+        public Location(int x, int y)
+        {
+            Name = "";
+            this.x = x;
+            this.y = y;
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="p"></param>
+        public Location(Point p)
+        {
+            Name = "";
+            this.x = p.X;
+            this.y = p.Y;
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <returns></returns>
+        public Point ToPoint()
+        {
+            return new Point(this.x, this.y);
+        }
+
+        #region INotifyPropertyChanged Members
+
+        public event PropertyChangedEventHandler PropertyChanged;
+
+        #endregion
+
+        // Create the OnPropertyChanged method to raise the event
+        protected void OnPropertyChanged(string name)
+        {
+            PropertyChangedEventHandler handler = PropertyChanged;
+            if (handler != null)
+            {
+                handler(this, new PropertyChangedEventArgs(name));
+            }
+        }
+    }
+}

File AstarPath/PathfinderUtilities.cs

+//==================================================================================================
+//
+//   Copyright 2010 Robin C. Harper 
+//
+//   Licensed under the Apache License, Version 2.0 (the "License");
+//   you may not use this file except in compliance with the License.
+//   You may obtain a copy of the License at
+//
+//       http://www.apache.org/licenses/LICENSE-2.0
+//
+//   Unless required by applicable law or agreed to in writing, software
+//   distributed under the License is distributed on an "AS IS" BASIS,
+//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+//   See the License for the specific language governing permissions and
+//   limitations under the License.
+//
+//==================================================================================================
+
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Drawing;
+
+namespace AstarPath
+{
+    public class PathfinderUtilities
+    {
+        #region PathfinderType enum
+
+        public enum PathfinderType
+        {
+            BasicManhattan,
+            AdvancedManhattan,
+            Euclidean
+        } ;
+
+        #endregion
+
+        public static object locker = new object();
+
+        /// <summary>
+        /// Searches the actual bitmap object at position x, y and
+        /// using GetPixel returns a color and then verifies it against
+        /// the given color in the parameters
+        /// </summary>
+        /// <param name="x"></param>
+        /// <param name="y"></param>
+        /// <param name="color"></param>
+        /// <param name="inputBitmap"></param>
+        /// <returns></returns>
+        public static bool CheckPixelColor(int x, int y, Color color, Bitmap inputBitmap)
+        {
+            Color node = inputBitmap.GetPixel(x, y);
+
+            if (node.R == color.R && node.B == color.B && node.G == color.G)
+            {
+                return true;
+            }
+            return false;
+        }
+
+        /// <summary>
+        /// Used to service bitmaps which are considered unprocessed.
+        /// 
+        /// By determining the RGB value of a given pixel in the bitmap,
+        /// if it meets the constraints to match an obstacle, then we set it
+        /// as a pure black color as defined by the Color property.
+        /// </summary>
+        /// <param name="map"></param>
+        /// <returns></returns>
+        public static Bitmap CleanBitmap(Bitmap map)
+        {
+            var localMap = map;
+
+            for (int x = 0; x < localMap.Width; x++)
+            {
+                for (int y = 0; y < localMap.Height; y++)
+                {
+                    Color tempColor = localMap.GetPixel(x, y);
+
+                    if (tempColor.R >= 100 && tempColor.B >= 100 && tempColor.G >= 100)
+                    {
+                        localMap.SetPixel(x, y, Color.White);
+                    }
+                    else
+                    {
+                        localMap.SetPixel(x, y, Color.Black);
+                    }
+                }
+            }
+
+            return localMap;
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="inputMap"></param>
+        /// <param name="obstacleMap"></param>
+        /// <param name="gridSize"></param>
+        /// <returns></returns>
+        public static List<GridNode> CreateGrid(Bitmap inputMap, int[,] obstacleMap, int gridSize)
+        {
+            var localGrid = new List<GridNode>();
+            int ycounter = 0;
+            for (int y = 0; y < inputMap.Height; y += gridSize)
+            {
+                int xcounter = 0;
+                for (int x = 0; x < inputMap.Width; x += gridSize)
+                {
+                    var rectangle = new Rectangle(xcounter, ycounter, gridSize, gridSize);
+                    // set default obstacle status to false
+                    var cp = PathfinderUtilities.GetActualCenterPoint(x, y, gridSize);
+                    var center = new Location(cp);
+                    //var gridBlock = new GridNode(rectangle, x, y, false);
+                    var gridBlock = new GridNode(rectangle, false, center, null);
+
+                    // now check each inner point of the block
+                    // and evaluate if it is infact an obstacle or not
+                    foreach (var innerPoint in gridBlock.PointsInsideGrid)
+                    {
+                        if (innerPoint.X >= 0 && innerPoint.X < inputMap.Width)
+                        {
+                            if (innerPoint.Y >= 0 && innerPoint.Y < inputMap.Height)
+                            {
+                                if (obstacleMap[innerPoint.X, innerPoint.Y] > 1)
+                                {
+                                    gridBlock.IsObstacle = true;
+                                    break;
+                                }
+                            }
+                        }
+                    }
+
+                    localGrid.Add(gridBlock);
+
+                    xcounter++;
+                }
+
+                ycounter++;
+            }
+
+            return localGrid;
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="fixedDistance"></param>
+        /// <param name="inputPathfinderType"></param>
+        /// <returns></returns>
+        public static List<Location> CreateSearchList(int fixedDistance, 
+            PathfinderType inputPathfinderType)
+        {
+            var list = new List<Location>
+                           {
+                               new Location(0, -fixedDistance), // north
+                               new Location(0, fixedDistance), // south
+                               new Location(fixedDistance, 0), //east
+                               new Location(-fixedDistance, 0) // west
+                           };
+
+            if (inputPathfinderType == PathfinderType.AdvancedManhattan || 
+                inputPathfinderType == PathfinderType.Euclidean)
+            {
+                list.Add(new Location(fixedDistance, -fixedDistance)); // north-east
+                list.Add(new Location(fixedDistance, fixedDistance)); // south-east
+                list.Add(new Location(-fixedDistance, fixedDistance)); // south-west
+                list.Add(new Location(-fixedDistance, -fixedDistance)); // north-west
+            }
+
+            return list;
+        }
+
+        /// <summary>
+        /// Searches in all the directions around an input node
+        /// and returns its neighboors
+        /// </summary>
+        /// <param name="grid"></param>
+        /// <param name="current"></param>
+        /// <param name="pathfinderHeuristic"></param>
+        /// <param name="obstacles"></param>
+        /// <param name="maxX"></param>
+        /// <param name="maxY"></param>
+        /// <returns></returns>
+        public static List<GridNode> FindAdjacentNodes(
+            List<GridNode> grid, 
+            GridNode current, 
+            PathfinderType pathfinderHeuristic,
+            int[,] obstacles, 
+            int maxX, 
+            int maxY)
+        {
+            var adjacentNodes = new List<GridNode>();
+            var searchList = CreateSearchList(1, pathfinderHeuristic);
+
+            foreach (var searchValue in searchList)
+            {
+                var searchPoint =
+                    new Point(current.X + searchValue.x, current.Y + searchValue.y);
+
+                if ((searchPoint.X >= 0 && searchPoint.X < maxX) && (searchPoint.Y >= 0 && searchPoint.Y < maxY))
+                {
+                    var xList = grid.FindAll(t => t.X == searchPoint.X);
+                    var gridBlock = xList.Find(t => t.Y == searchPoint.Y);
+                    /*
+                    GridNode gridBlock = grid.FirstOrDefault(t => 
+                        t.X == searchPoint.X && t.Y == searchPoint.Y);
+                     */
+
+                    if (gridBlock != null && gridBlock != current)
+                    {
+                        if (!gridBlock.IsObstacle)
+                        {
+                            adjacentNodes.Add(gridBlock);
+                        }
+                    }
+                }
+            }
+
+            return adjacentNodes;
+        }
+
+        /// <summary>
+        /// Iterates over the bitmap to generate an obstacle map.
+        /// 
+        /// By iterating through the bitmap we check each
+        /// individual pixel at a given x,y coordinate and determine
+        /// if it represents an obstacle or if it is passable. 
+        /// </summary>
+        /// <param name="inputMap"></param>
+        /// <returns></returns>
+        public static int[,] GetObstacles(Bitmap inputMap)
+        {
+            var map = new int[inputMap.Width, inputMap.Height];
+
+            for (var x = 0; x < inputMap.Width; x++)
+            {
+                for (var y = 0; y < inputMap.Height; y++)
+                {
+                    if (x >= 0 && x < inputMap.Width)
+                    {
+                        if (y >= 0 && y < inputMap.Height)
+                        {
+                            if (CheckPixelColor(x, y, Color.Black, inputMap))
+                            {
+                                map[x, y] = 2;
+                            }
+                            else
+                            {
+                                map[x, y] = 1;
+                            }
+                        }
+                    }
+                }
+            }
+
+            return map;
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="x"></param>
+        /// <param name="y"></param>
+        /// <param name="gridSize"></param>
+        /// <returns></returns>
+        public static Point GetActualCenterPoint(int x, int y, int gridSize)
+        {
+            switch (gridSize)
+            {
+                default:
+                    return new Point(x + 1, y + 1);
+                case 5:
+                    return new Point(x + 2, y + 2);
+                case 7:
+                    return new Point(x + 3, y + 3);
+                case 9:
+                    return new Point(x + 4, y + 4);
+                case 11:
+                    return new Point(x + 5, y + 5);
+                case 13:
+                    return new Point(x + 6, y + 6);
+                case 15:
+                    return new Point(x + 7, y + 7);
+            }
+        }
+
+        /// <summary>
+        /// 
+        /// </summary>
+        /// <param name="centerX"></param>
+        /// <param name="centerY"></param>
+        /// <param name="gridSize"></param>
+        /// <returns></returns>
+        public static Point GetTopLeftPoint(int centerX, int centerY, int gridSize)
+        {
+            switch(gridSize)
+            {
+                default:
+                    return new Point(centerX - 1, centerY - 1);
+                case 5:
+                    return new Point(centerX - 2, centerY - 2);
+                case 7:
+                    return new Point(centerX - 3, centerY - 3);
+                case 9:
+                    return new Point(centerX - 4, centerY - 4);
+                case 11:
+                    return new Point(centerX - 5, centerY - 5);
+                case 13:
+                    return new Point(centerX - 6, centerY - 6);
+                case 15:
+                    return new Point(centerX - 7, centerY - 7);
+            }
+        }
+    }
+}

File AstarPath/Properties/AssemblyInfo.cs

+//==================================================================================================
+//
+//   Copyright 2010 Robin C. Harper 
+//
+//   Licensed under the Apache License, Version 2.0 (the "License");
+//   you may not use this file except in compliance with the License.
+//   You may obtain a copy of the License at
+//
+//       http://www.apache.org/licenses/LICENSE-2.0
+//
+//   Unless required by applicable law or agreed to in writing, software
+//   distributed under the License is distributed on an "AS IS" BASIS,
+//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+//   See the License for the specific language governing permissions and
+//   limitations under the License.
+//
+//==================================================================================================
+
+using System.Reflection;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+// General Information about an assembly is controlled through the following 
+// set of attributes. Change these attribute values to modify the information
+// associated with an assembly.
+[assembly: AssemblyTitle("AstarPath")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("Microsoft")]
+[assembly: AssemblyProduct("AstarPath")]
+[assembly: AssemblyCopyright("Copyright © Microsoft 2010")]
+[assembly: AssemblyTrademark("")]
+[assembly: AssemblyCulture("")]
+
+// Setting ComVisible to false makes the types in this assembly not visible 
+// to COM components.  If you need to access a type in this assembly from 
+// COM, set the ComVisible attribute to true on that type.
+[assembly: ComVisible(false)]
+
+// The following GUID is for the ID of the typelib if this project is exposed to COM
+[assembly: Guid("3cf0428d-48f0-44b8-b7ff-673b057b572b")]
+
+// Version information for an assembly consists of the following four values:
+//
+//      Major Version
+//      Minor Version 
+//      Build Number
+//      Revision
+//
+// You can specify all the values or you can default the Build and Revision Numbers 
+// by using the '*' as shown below:
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyVersion("1.0.0.0")]
+[assembly: AssemblyFileVersion("1.0.0.0")]