Commits

Robin Harper committed 2e06863

Added pathtester to the project folder for easy maintenance.

Updated the pathtester layout to include some positioning of the UI controls
and to expand, based on the image chosen.

Updated some of the cost function in the path finder and attempted to normalize
the scale between g & h

  • Participants
  • Parent commits 51b0565

Comments (0)

Files changed (16)

File AstarPath.sln

 # Visual Studio 2010
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "AstarPath", "AstarPath\AstarPath.csproj", "{00BA3E47-FFBD-421B-B13D-98F02A25D115}"
 EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "PathTester", "PathTester\PathTester.csproj", "{345E33C1-6684-4576-B190-604A0A8224B3}"
+EndProject
 Global
 	GlobalSection(SolutionConfigurationPlatforms) = preSolution
 		Debug|Any CPU = Debug|Any CPU
+		Debug|Mixed Platforms = Debug|Mixed Platforms
+		Debug|x86 = Debug|x86
 		Release|Any CPU = Release|Any CPU
+		Release|Mixed Platforms = Release|Mixed Platforms
+		Release|x86 = Release|x86
 	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}.Debug|Mixed Platforms.ActiveCfg = Debug|Any CPU
+		{00BA3E47-FFBD-421B-B13D-98F02A25D115}.Debug|Mixed Platforms.Build.0 = Debug|Any CPU
+		{00BA3E47-FFBD-421B-B13D-98F02A25D115}.Debug|x86.ActiveCfg = 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
+		{00BA3E47-FFBD-421B-B13D-98F02A25D115}.Release|Mixed Platforms.ActiveCfg = Release|Any CPU
+		{00BA3E47-FFBD-421B-B13D-98F02A25D115}.Release|Mixed Platforms.Build.0 = Release|Any CPU
+		{00BA3E47-FFBD-421B-B13D-98F02A25D115}.Release|x86.ActiveCfg = Release|Any CPU
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Debug|Any CPU.ActiveCfg = Debug|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Debug|Mixed Platforms.ActiveCfg = Debug|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Debug|Mixed Platforms.Build.0 = Debug|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Debug|x86.ActiveCfg = Debug|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Debug|x86.Build.0 = Debug|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Release|Any CPU.ActiveCfg = Release|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Release|Mixed Platforms.ActiveCfg = Release|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Release|Mixed Platforms.Build.0 = Release|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Release|x86.ActiveCfg = Release|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Release|x86.Build.0 = Release|x86
 	EndGlobalSection
 	GlobalSection(SolutionProperties) = preSolution
 		HideSolutionNode = FALSE

File AstarPath/AstarPath.csproj

     <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>

File AstarPath/AstarPathfinder.cs

     {
         private const double Alpha = 0.4999;
         private const double DefaultCost = 1.0;
-        private const int MaxEstimatedPathLength = 2000;
+        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 Grid Grid;
 
         public readonly int BitmapHeight;
             BitmapWidth = map.Width;
             CurrentPathfinderType = type;
             _size = size;
-            //Obstacles = PathfinderUtilities.GetObstacles(map);
-            //Grid = PathfinderUtilities.CreateGrid(map, Obstacles, size);
+
             Grid = PathfinderUtilities.CreateGrid(map, size);
 
             switch (type)
         /// <returns></returns>
         public List<GridNode> GridSearch(Point inputStart, Point inputGoal)
         {
-            //List<GridNode> opened = new List<GridNode>();
-            //List<GridNode> closed = new List<GridNode>();
             var opened = new Grid();
             var closed = new Grid();
             var start = Grid.FirstOrDefault(t => t.PointsInsideGrid.Contains(inputStart));
                     start.IsObstacle = false;
                 }
 
-                //start = UpdateHeuristics(start, start, start, goal);
                 start = CalculateHeuristics(start, start, start, goal);
                 opened.Add(start);
 
                 while (opened.Count > 0)
                 {
-                    //opened = GridNode.MergeSort(opened);
                     opened = opened.MergeSort(opened);
 
                     var parent = opened[0];
                     else if (opened.Count >= MaxEstimatedPathLength)
                     {
                         opened.Clear();
+                        closed.Clear();
                         break;
                     }
                     else
                             Grid,
                             parent,
                             CurrentPathfinderType);
-                            //Obstacles,
-                            //BitmapHeight,
-                            //BitmapHeight);
 
                         adjacentNodes = UpdateHeuristics(adjacentNodes, parent, start, goal);
 
                     }
                 }
 
-                //return closed;
                 return PathToStart(goal);
             }
             else
             var updated = new List<GridNode>();
             foreach(var localGridBlock in adjacentNodes)
             {
-                //updated.Add(UpdateHeuristics(localGridBlock, parent, start, goal));
                 updated.Add(CalculateHeuristics(localGridBlock, parent, start, goal));
             }
 
         }
 
         /// <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="neighbor"></param>
         /// <param name="parent"></param>
         /// <param name="goal"></param>
         /// <returns></returns>
-        private GridNode CalculateHeuristics(GridNode neighboor, GridNode parent, GridNode start, GridNode goal)
+        private GridNode CalculateHeuristics(GridNode neighbor, GridNode parent, GridNode start, GridNode goal)
         {
-            var g = CalculateG(parent, neighboor);
+            var g = GetCost(parent, neighbor);
             var h = 0.0;
-            switch(CurrentPathfinderType)
+            switch (CurrentPathfinderType)
             {
                 case PathfinderUtilities.PathfinderType.BasicManhattan:
-                    h = CalculateHWithBasicManhattan(neighboor, parent, start, goal);
+                    h = CalculateHWithBasicManhattan(neighbor, parent, start, goal);
                     break;
                 case PathfinderUtilities.PathfinderType.AdvancedManhattan:
-                    h = CalculateHWithAdvancedManhattan(neighboor, parent, start, goal);
+                    h = CalculateHWithAdvancedManhattan(neighbor, parent, start, goal);
                     break;
                 case PathfinderUtilities.PathfinderType.Euclidean:
-                    h = CalculateHWithEuclidian(neighboor, parent, start, goal);
+                    h = CalculateHWithEuclidian(neighbor, parent, start, goal);
                     break;
             }
 
-             var f = (Alpha * g) + (((DefaultCost - Alpha) * h) / Math.Max(Alpha, (DefaultCost - Alpha)));
+            // a more complex f can be generated as such:
+            // var f = (Alpha * g) + (((DefaultCost - Alpha) * h) / Math.Max(Alpha, (DefaultCost - Alpha)));
+            // it will tend to slow down the overall speed of the search however
 
-             //return new Location(neighboor.x, neighboor.y, g, f, h);
-             return new GridNode(neighboor.GridBorder, neighboor.IsObstacle, new Location(neighboor.Center.x, neighboor.Center.y, g, f, h), parent);
+            var f = g + h;
+
+            return new GridNode(neighbor.GridBorder, neighbor.IsObstacle, new Location(neighbor.Center.x, neighbor.Center.y, g, f, h), parent);
         }
 
         /// <summary>
         /// 
         /// 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="neighbor">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(GridNode neighboor, GridNode parent, GridNode start, GridNode goal)
+        private double CalculateHWithBasicManhattan(GridNode neighbor, GridNode parent, GridNode start, GridNode goal)
         {
-            var h = GetCost(parent, neighboor) * ((Math.Abs(neighboor.Center.x - goal.Center.x) + Math.Abs(neighboor.Center.y - goal.Center.y)));
+            var h = DefaultCost * (Math.Abs(neighbor.Center.x - goal.Center.x) + Math.Abs(neighbor.Center.y - goal.Center.y));
             return CalculateSimpleNudge(h);
         }
 
         /// 
         /// This is the most optimal choice for this implementation
         /// </summary>
-        /// <param name="neighboor">The node we are looking at</param>
+        /// <param name="neighbor">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(GridNode neighboor, GridNode parent, GridNode start, GridNode goal)
+        private double CalculateHWithAdvancedManhattan(GridNode neighbor, GridNode parent, GridNode start, GridNode goal)
         {
-            var h = GetCost(parent, neighboor) * Math.Max(Math.Abs(neighboor.Center.x - goal.Center.x), Math.Abs(neighboor.Center.y - goal.Center.y));
-            return CalculateComplexNudge(h, parent.Center.ToPoint(), start.Center.ToPoint(), goal.Center.ToPoint());
+            var h = (DefaultCost * DirectionalMove) * Math.Max(Math.Abs(neighbor.Center.x - goal.Center.x), Math.Abs(neighbor.Center.y - goal.Center.y));
+            return CalculateSimpleNudge(h);
         }
 
         /// <summary>
         /// Euclidean distance
         /// </summary>
-        /// <param name="neighboor">The node we are looking at</param>
+        /// <param name="neighbor">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(GridNode neighboor, GridNode parent, GridNode start, GridNode goal)
+        private double CalculateHWithEuclidian(GridNode neighbor, GridNode parent, GridNode start, GridNode goal)
         {
-            var h = GetCost(parent, neighboor) * (Math.Sqrt(Math.Sqrt((neighboor.Center.x - goal.Center.x)) + 
-                                                                Math.Sqrt((neighboor.Center.y - goal.Center.y))));
-
+            var h = DefaultCost * Math.Sqrt(Math.Pow((neighbor.Center.x - goal.Center.x), 2) + Math.Pow((neighbor.Center.y - goal.Center.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(GridNode parentLocation, GridNode currentLocation)
-        {
-            return GetCost(parentLocation, currentLocation) + parentLocation.Center.g;
-        }
-
-        /// <summary>
-        /// 
+        /// Evaluates the goal node to see if it is an obstacle. If it is,
+        /// then we increase the cost of moving there; otherwise, we return the
+        /// cost x the distance we can move in one direction
         /// </summary>
         /// <param name="start"></param>
         /// <param name="goal"></param>
         /// <returns></returns>
         private double GetCost(GridNode start, GridNode goal)
         {
-            var cost = 1.0;
-            //return (Obstacles[start.x, start.y] + Obstacles[goal.x, goal.y]) * DirectionalMove;
+            var cost = DefaultCost + Alpha * (start.Center.g - DefaultCost);
+
             if (goal.IsObstacle)
             {
-                cost += 1.0;
+                cost += 2;
             }
 
-            return cost * DirectionalMove;
+            return cost;
         }
 
         /// <summary>
         /// Simple nudge, evolves into more diagonal steps
         /// </summary>
-        /// <param name="existingH"></param>
+        /// <param name="h"></param>
         /// <returns></returns>
-        private double CalculateSimpleNudge(double existingH)
+        private double CalculateSimpleNudge(double h)
         {
-            return existingH *= 1.0 + Nudge;
+            return h *= 1.0 + Nudge;
         }
 
         /// <summary>
         {
             var paths = new List<GridNode>();
 
-            while (true)
+            if (node != null)
             {
-                paths.Add(node);
-                if (node.Parent != null)
+                while (true)
                 {
-                    node = node.Parent;
+                    paths.Add(node);
+                    if (node.Parent != null)
+                    {
+                        node = node.Parent;
+                    }
+                    else
+                    {
+                        break;
+                    }
                 }
-                else
-                {
-                    break;
-                }
+
+                paths.Reverse();
             }
 
-            paths.Reverse();
             return paths;
         }
     }

File AstarPath/Grid.cs

 {
     public class Grid : List<GridNode>
     {
-        private int _w = 0;
-        private int _h = 0;
-        private int _size = 0;
-
-
         public Grid() : base()
         {
             

File PathTester.sln

+
+Microsoft Visual Studio Solution File, Format Version 11.00
+# Visual Studio 2010
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "PathTester", "PathTester\PathTester.csproj", "{345E33C1-6684-4576-B190-604A0A8224B3}"
+EndProject
+Global
+	GlobalSection(SolutionConfigurationPlatforms) = preSolution
+		Debug|x86 = Debug|x86
+		Release|x86 = Release|x86
+	EndGlobalSection
+	GlobalSection(ProjectConfigurationPlatforms) = postSolution
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Debug|x86.ActiveCfg = Debug|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Debug|x86.Build.0 = Debug|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Release|x86.ActiveCfg = Release|x86
+		{345E33C1-6684-4576-B190-604A0A8224B3}.Release|x86.Build.0 = Release|x86
+	EndGlobalSection
+	GlobalSection(SolutionProperties) = preSolution
+		HideSolutionNode = FALSE
+	EndGlobalSection
+EndGlobal

File PathTester/App.xaml

+<Application x:Class="PathTester.App"
+             xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
+             xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
+             StartupUri="MainWindow.xaml">
+    <Application.Resources>
+         
+    </Application.Resources>
+</Application>

File PathTester/App.xaml.cs

+using System;
+using System.Collections.Generic;
+using System.Configuration;
+using System.Data;
+using System.Linq;
+using System.Windows;
+
+namespace PathTester
+{
+    /// <summary>
+    /// Interaction logic for App.xaml
+    /// </summary>
+    public partial class App : Application
+    {
+    }
+}

File PathTester/MainWindow.xaml

+<Window x:Class="PathTester.MainWindow"
+        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
+        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
+        Title="MainWindow" SizeToContent="WidthAndHeight">
+    <Grid>
+        <Grid.ColumnDefinitions>
+            <ColumnDefinition Width="Auto"/>
+            <ColumnDefinition Width="*"/>
+        </Grid.ColumnDefinitions>
+        <Grid.RowDefinitions>
+            <RowDefinition Height="Auto" />
+            <RowDefinition Height="*"/>
+            <RowDefinition Height="Auto"/>
+        </Grid.RowDefinitions>
+        <Menu Name="PathTesterMenu" Grid.Row="0" Height="23" Grid.ColumnSpan="2">
+            <MenuItem Header="_Open" Click="MenuItem_Click" />
+        </Menu>
+        <StackPanel Grid.Row="2" Margin="5" HorizontalAlignment="Stretch" Grid.Column="2">
+            <Grid>
+                <Grid.ColumnDefinitions>
+                    <ColumnDefinition Width="Auto" />
+                    <ColumnDefinition Width="Auto"/>
+                    <ColumnDefinition Width="*"/>
+                    <ColumnDefinition Width="Auto"/>
+                    <ColumnDefinition Width="Auto"/>
+                    <ColumnDefinition Width="Auto"/>
+                </Grid.ColumnDefinitions>
+                <Label Content="Grid Size" Grid.Column="0"/>
+                <TextBox Name="GridSizeTextBox" Text="14" MinWidth="60" Margin="2" Grid.Column="1"/>
+                <ComboBox Height="Auto" HorizontalAlignment="Stretch" Name="HeuristicComboBox" VerticalAlignment="Center" Width="Auto" Grid.Column="2" Margin="2"/>
+                <Button Content="Run" Height="23" Name="RunBtn" Width="75" Click="RunBtn_Click" Margin="2" HorizontalAlignment="Right" Grid.Column="3"/>
+                <Button Content="Draw Grid" Height="23" Name="DrawGridBtn" Width="75" Click="DrawGridBtn_Click" Margin="2" Grid.Column="4" HorizontalAlignment="Right"/>
+                <Button Content="Clear" Height="23" Name="ClearBtn" Width="75" Click="ClearBtn_Click" Margin="2" Grid.Column="5" HorizontalAlignment="Right"/>
+            </Grid>
+        </StackPanel>
+
+        <Border BorderThickness="2" BorderBrush="Silver" Grid.Column="0" Grid.ColumnSpan="2" Grid.Row="1" Margin="2">
+            <Canvas Name="LayoutCanvas" MouseLeftButtonDown="LayoutCanvas_MouseLeftButtonDown"/>
+        </Border>
+    </Grid>
+</Window>

File PathTester/MainWindow.xaml.cs

+using System;
+using System.Windows;
+using System.Windows.Media;
+using System.Drawing;
+using System.Collections.Generic;
+using System.Windows.Controls;
+using System.Windows.Forms;
+using System.IO;
+using System.Xml.Linq;
+using System.Threading;
+using System.Windows.Shapes;
+using AstarPath;
+using System.Windows.Media.Imaging;
+
+namespace PathTester
+{
+    /// <summary>
+    /// Interaction logic for MainWindow.xaml
+    /// </summary>
+    public partial class MainWindow : Window
+    {
+        private string layoutFile = "";
+        private AstarPathfinder pathfinder;
+
+        private static Bitmap _processedBitmap;
+
+        private System.Drawing.Point start;
+        private bool startSet = false;
+        private System.Drawing.Point goal;
+        private bool goalSet = false;
+
+        public MainWindow()
+        {
+            InitializeComponent();
+
+            HeuristicComboBox.ItemsSource = Enum.GetNames(typeof(PathfinderUtilities.PathfinderType));
+            HeuristicComboBox.SelectedIndex = 0;
+        }
+
+        private void MenuItem_Click(object sender, RoutedEventArgs e)
+        {
+            using (OpenFileDialog dialog = new OpenFileDialog())
+            {
+                if (dialog.ShowDialog() == System.Windows.Forms.DialogResult.OK)
+                {
+                    layoutFile = dialog.FileName;
+                    SetupBackground();
+                }
+            }
+        }
+
+        private void SetupBackground()
+        {
+            var bitmap = ConvertUriToBitmapImage(layoutFile);
+            LayoutCanvas.Background = new ImageBrush(bitmap);
+            LayoutCanvas.Width = bitmap.PixelWidth;
+            LayoutCanvas.Height = bitmap.PixelHeight;
+
+            byte[] rawBackground = File.ReadAllBytes(layoutFile);
+
+            var temporary = ConvertUriToBitmap(layoutFile);
+            _processedBitmap = PathfinderUtilities.CleanBitmap(temporary);
+        }
+
+        private void RunBtn_Click(object sender, RoutedEventArgs e)
+        {
+            if ((startSet && goalSet) || (!start.IsEmpty && !goal.IsEmpty))
+            {
+                startSet = false;
+                goalSet = false;
+                GetWorkingPath();
+            }
+            else
+            {
+                System.Windows.MessageBox.Show("Choose a start and goal point");
+            }
+        }
+
+        private void GetWorkingPath()
+        {
+            var gridSize = Convert.ToInt32(GridSizeTextBox.Text);
+            var heuristic = (PathfinderUtilities.PathfinderType)Enum.Parse(typeof(PathfinderUtilities.PathfinderType), HeuristicComboBox.SelectedItem.ToString());
+
+            pathfinder = new AstarPathfinder(_processedBitmap,
+                                        heuristic,
+                                        gridSize);
+
+            var results = pathfinder.GridSearch(start, goal);
+
+            int i = 0; 
+            foreach (var ig in results)
+            {
+                if(i > 0)
+                {
+                    var l = new Line();
+                    l.X1 = results[i - 1].PixelX;
+                    l.Y1 = results[i - 1].PixelY;
+                    l.X2 = results[i].PixelX;
+                    l.Y2 = results[i].PixelY;
+                    l.StrokeThickness = 3.0;
+                    l.Stroke = new SolidColorBrush(System.Windows.Media.Color.FromRgb(0, 0, 0));
+                    LayoutCanvas.Children.Add(l);
+                }
+
+                i++;
+            }
+        }
+
+        private void DrawGridOverLay()
+        {
+            foreach (var p in pathfinder.Grid)
+            {
+                LayoutCanvas.Children.Add(CreateRectangle(p, Colors.Green));
+            }
+
+            return;
+        }
+
+        private System.Windows.Controls.TextBlock CreateText(GridNode point, string text)
+        {
+            var tb = new System.Windows.Controls.TextBlock();
+            tb.SetValue(Canvas.LeftProperty, (double)point.PixelX);
+            tb.SetValue(Canvas.TopProperty, (double)point.PixelY);
+            tb.Text = text; 
+
+            return tb;
+        }
+
+        private System.Windows.Shapes.Rectangle CreateRectangle(GridNode point, System.Windows.Media.Color color)
+        {
+            var rect = new System.Windows.Shapes.Rectangle();
+            rect.SetValue(Canvas.LeftProperty, (double)point.PixelX);
+            rect.SetValue(Canvas.TopProperty, (double)point.PixelY);
+            rect.Width = point.Size;
+            rect.Height = point.Size;
+            rect.Stroke = new SolidColorBrush(color);
+
+            return rect;
+        }
+        
+
+        private void LayoutCanvas_MouseLeftButtonDown(object sender, System.Windows.Input.MouseButtonEventArgs e)
+        {
+            if (!startSet)
+            {
+                var localStart = e.GetPosition(LayoutCanvas);
+                start = new System.Drawing.Point((int)localStart.X, (int)localStart.Y);
+                var textBlock = new TextBlock();
+                textBlock.Text = "*";
+                textBlock.FontSize = 14.0;
+                textBlock.SetValue(Canvas.LeftProperty, localStart.X);
+                textBlock.SetValue(Canvas.TopProperty, localStart.Y);
+                LayoutCanvas.Children.Add(textBlock);
+                startSet = true;
+            }
+            else if (!goalSet)
+            {
+                var localGoal = e.GetPosition(LayoutCanvas);
+                goal = new System.Drawing.Point((int)localGoal.X, (int)localGoal.Y);
+                var textBlock = new TextBlock();
+                textBlock.Text = "*";
+                textBlock.FontSize = 14.0;
+                textBlock.SetValue(Canvas.LeftProperty, localGoal.X);
+                textBlock.SetValue(Canvas.TopProperty, localGoal.Y);
+                LayoutCanvas.Children.Add(textBlock);
+                goalSet = true;
+            }
+        }
+
+        private void ClearBtn_Click(object sender, RoutedEventArgs e)
+        {
+            LayoutCanvas.Children.Clear();
+            startSet = false;
+            goalSet = false;
+        }
+
+        private void DrawGridBtn_Click(object sender, RoutedEventArgs e)
+        {
+            DrawGridOverLay();
+        }
+
+        public static Bitmap ConvertUriToBitmap(string imagePath)
+        {
+            if (File.Exists(imagePath))
+            {
+                var bitmapSource = ConvertUriToBitmapImage(imagePath);
+
+                using (var outStream = new MemoryStream())
+                {
+                    var enc = new BmpBitmapEncoder();
+                    enc.Frames.Add(BitmapFrame.Create(bitmapSource));
+                    enc.Save(outStream);
+
+                    return new Bitmap(outStream);
+                }
+            }
+            else
+            {
+                throw new FileNotFoundException();
+            }
+        }
+
+        public static BitmapImage ConvertUriToBitmapImage(string pathToBitmap)
+        {
+            if (File.Exists(pathToBitmap))
+            {
+                var bitmapSource = new BitmapImage();
+                bitmapSource.BeginInit();
+                bitmapSource.CreateOptions = BitmapCreateOptions.PreservePixelFormat;
+                bitmapSource.UriSource = new Uri(pathToBitmap);
+                bitmapSource.CacheOption = BitmapCacheOption.OnLoad;
+                bitmapSource.EndInit();
+
+                return bitmapSource;
+            }
+            else
+            {
+                throw new FileNotFoundException();
+            }
+        }
+    }
+}

File PathTester/PathTester.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)' == '' ">x86</Platform>
+    <ProductVersion>8.0.30703</ProductVersion>
+    <SchemaVersion>2.0</SchemaVersion>
+    <ProjectGuid>{345E33C1-6684-4576-B190-604A0A8224B3}</ProjectGuid>
+    <OutputType>WinExe</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>PathTester</RootNamespace>
+    <AssemblyName>PathTester</AssemblyName>
+    <TargetFrameworkVersion>v4.0</TargetFrameworkVersion>
+    <TargetFrameworkProfile>
+    </TargetFrameworkProfile>
+    <FileAlignment>512</FileAlignment>
+    <ProjectTypeGuids>{60dc8134-eba5-43b8-bcc9-bb4bc16c2548};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|x86' ">
+    <PlatformTarget>x86</PlatformTarget>
+    <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|x86' ">
+    <PlatformTarget>x86</PlatformTarget>
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <ItemGroup>
+    <Reference Include="System" />
+    <Reference Include="System.Data" />
+    <Reference Include="System.Drawing" />
+    <Reference Include="System.Windows.Forms" />
+    <Reference Include="System.Xml" />
+    <Reference Include="Microsoft.CSharp" />
+    <Reference Include="System.Core" />
+    <Reference Include="System.Xml.Linq" />
+    <Reference Include="System.Data.DataSetExtensions" />
+    <Reference Include="System.Xaml">
+      <RequiredTargetFramework>4.0</RequiredTargetFramework>
+    </Reference>
+    <Reference Include="WindowsBase" />
+    <Reference Include="PresentationCore" />
+    <Reference Include="PresentationFramework" />
+  </ItemGroup>
+  <ItemGroup>
+    <ApplicationDefinition Include="App.xaml">
+      <Generator>MSBuild:Compile</Generator>
+      <SubType>Designer</SubType>
+    </ApplicationDefinition>
+    <Page Include="MainWindow.xaml">
+      <Generator>MSBuild:Compile</Generator>
+      <SubType>Designer</SubType>
+    </Page>
+    <Compile Include="App.xaml.cs">
+      <DependentUpon>App.xaml</DependentUpon>
+      <SubType>Code</SubType>
+    </Compile>
+    <Compile Include="MainWindow.xaml.cs">
+      <DependentUpon>MainWindow.xaml</DependentUpon>
+      <SubType>Code</SubType>
+    </Compile>
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="Properties\AssemblyInfo.cs">
+      <SubType>Code</SubType>
+    </Compile>
+    <Compile Include="Properties\Resources.Designer.cs">
+      <AutoGen>True</AutoGen>
+      <DesignTime>True</DesignTime>
+      <DependentUpon>Resources.resx</DependentUpon>
+    </Compile>
+    <Compile Include="Properties\Settings.Designer.cs">
+      <AutoGen>True</AutoGen>
+      <DependentUpon>Settings.settings</DependentUpon>
+      <DesignTimeSharedInput>True</DesignTimeSharedInput>
+    </Compile>
+    <EmbeddedResource Include="Properties\Resources.resx">
+      <Generator>ResXFileCodeGenerator</Generator>
+      <LastGenOutput>Resources.Designer.cs</LastGenOutput>
+    </EmbeddedResource>
+    <None Include="app.config" />
+    <None Include="Properties\Settings.settings">
+      <Generator>SettingsSingleFileGenerator</Generator>
+      <LastGenOutput>Settings.Designer.cs</LastGenOutput>
+    </None>
+    <AppDesigner Include="Properties\" />
+  </ItemGroup>
+  <ItemGroup>
+    <ProjectReference Include="..\..\AstarPath\AstarPath\AstarPath.csproj">
+      <Project>{00BA3E47-FFBD-421B-B13D-98F02A25D115}</Project>
+      <Name>AstarPath</Name>
+    </ProjectReference>
+  </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 PathTester/Properties/AssemblyInfo.cs

+using System.Reflection;
+using System.Resources;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+using System.Windows;
+
+// 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("PathTester")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("Microsoft")]
+[assembly: AssemblyProduct("PathTester")]
+[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)]
+
+//In order to begin building localizable applications, set 
+//<UICulture>CultureYouAreCodingWith</UICulture> in your .csproj file
+//inside a <PropertyGroup>.  For example, if you are using US english
+//in your source files, set the <UICulture> to en-US.  Then uncomment
+//the NeutralResourceLanguage attribute below.  Update the "en-US" in
+//the line below to match the UICulture setting in the project file.
+
+//[assembly: NeutralResourcesLanguage("en-US", UltimateResourceFallbackLocation.Satellite)]
+
+
+[assembly: ThemeInfo(
+    ResourceDictionaryLocation.None, //where theme specific resource dictionaries are located
+    //(used if a resource is not found in the page, 
+    // or application resource dictionaries)
+    ResourceDictionaryLocation.SourceAssembly //where the generic resource dictionary is located
+    //(used if a resource is not found in the page, 
+    // app, or any theme specific resource dictionaries)
+)]
+
+
+// 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")]

File PathTester/Properties/Resources.Designer.cs

+//------------------------------------------------------------------------------
+// <auto-generated>
+//     This code was generated by a tool.
+//     Runtime Version:4.0.30319.1
+//
+//     Changes to this file may cause incorrect behavior and will be lost if
+//     the code is regenerated.
+// </auto-generated>
+//------------------------------------------------------------------------------
+
+namespace PathTester.Properties {
+    using System;
+    
+    
+    /// <summary>
+    ///   A strongly-typed resource class, for looking up localized strings, etc.
+    /// </summary>
+    // This class was auto-generated by the StronglyTypedResourceBuilder
+    // class via a tool like ResGen or Visual Studio.
+    // To add or remove a member, edit your .ResX file then rerun ResGen
+    // with the /str option, or rebuild your VS project.
+    [global::System.CodeDom.Compiler.GeneratedCodeAttribute("System.Resources.Tools.StronglyTypedResourceBuilder", "4.0.0.0")]
+    [global::System.Diagnostics.DebuggerNonUserCodeAttribute()]
+    [global::System.Runtime.CompilerServices.CompilerGeneratedAttribute()]
+    internal class Resources {
+        
+        private static global::System.Resources.ResourceManager resourceMan;
+        
+        private static global::System.Globalization.CultureInfo resourceCulture;
+        
+        [global::System.Diagnostics.CodeAnalysis.SuppressMessageAttribute("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
+        internal Resources() {
+        }
+        
+        /// <summary>
+        ///   Returns the cached ResourceManager instance used by this class.
+        /// </summary>
+        [global::System.ComponentModel.EditorBrowsableAttribute(global::System.ComponentModel.EditorBrowsableState.Advanced)]
+        internal static global::System.Resources.ResourceManager ResourceManager {
+            get {
+                if (object.ReferenceEquals(resourceMan, null)) {
+                    global::System.Resources.ResourceManager temp = new global::System.Resources.ResourceManager("PathTester.Properties.Resources", typeof(Resources).Assembly);
+                    resourceMan = temp;
+                }
+                return resourceMan;
+            }
+        }
+        
+        /// <summary>
+        ///   Overrides the current thread's CurrentUICulture property for all
+        ///   resource lookups using this strongly typed resource class.
+        /// </summary>
+        [global::System.ComponentModel.EditorBrowsableAttribute(global::System.ComponentModel.EditorBrowsableState.Advanced)]
+        internal static global::System.Globalization.CultureInfo Culture {
+            get {
+                return resourceCulture;
+            }
+            set {
+                resourceCulture = value;
+            }
+        }
+    }
+}

File PathTester/Properties/Resources.resx

+<?xml version="1.0" encoding="utf-8"?>
+<root>
+  <!-- 
+    Microsoft ResX Schema 
+    
+    Version 2.0
+    
+    The primary goals of this format is to allow a simple XML format 
+    that is mostly human readable. The generation and parsing of the 
+    various data types are done through the TypeConverter classes 
+    associated with the data types.
+    
+    Example:
+    
+    ... ado.net/XML headers & schema ...
+    <resheader name="resmimetype">text/microsoft-resx</resheader>
+    <resheader name="version">2.0</resheader>
+    <resheader name="reader">System.Resources.ResXResourceReader, System.Windows.Forms, ...</resheader>
+    <resheader name="writer">System.Resources.ResXResourceWriter, System.Windows.Forms, ...</resheader>
+    <data name="Name1"><value>this is my long string</value><comment>this is a comment</comment></data>
+    <data name="Color1" type="System.Drawing.Color, System.Drawing">Blue</data>
+    <data name="Bitmap1" mimetype="application/x-microsoft.net.object.binary.base64">
+        <value>[base64 mime encoded serialized .NET Framework object]</value>
+    </data>
+    <data name="Icon1" type="System.Drawing.Icon, System.Drawing" mimetype="application/x-microsoft.net.object.bytearray.base64">
+        <value>[base64 mime encoded string representing a byte array form of the .NET Framework object]</value>
+        <comment>This is a comment</comment>
+    </data>
+                
+    There are any number of "resheader" rows that contain simple 
+    name/value pairs.
+    
+    Each data row contains a name, and value. The row also contains a 
+    type or mimetype. Type corresponds to a .NET class that support 
+    text/value conversion through the TypeConverter architecture. 
+    Classes that don't support this are serialized and stored with the 
+    mimetype set.
+    
+    The mimetype is used for serialized objects, and tells the 
+    ResXResourceReader how to depersist the object. This is currently not 
+    extensible. For a given mimetype the value must be set accordingly:
+    
+    Note - application/x-microsoft.net.object.binary.base64 is the format 
+    that the ResXResourceWriter will generate, however the reader can 
+    read any of the formats listed below.
+    
+    mimetype: application/x-microsoft.net.object.binary.base64
+    value   : The object must be serialized with 
+            : System.Serialization.Formatters.Binary.BinaryFormatter
+            : and then encoded with base64 encoding.
+    
+    mimetype: application/x-microsoft.net.object.soap.base64
+    value   : The object must be serialized with 
+            : System.Runtime.Serialization.Formatters.Soap.SoapFormatter
+            : and then encoded with base64 encoding.
+
+    mimetype: application/x-microsoft.net.object.bytearray.base64
+    value   : The object must be serialized into a byte array 
+            : using a System.ComponentModel.TypeConverter
+            : and then encoded with base64 encoding.
+    -->
+  <xsd:schema id="root" xmlns="" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:msdata="urn:schemas-microsoft-com:xml-msdata">
+    <xsd:element name="root" msdata:IsDataSet="true">
+      <xsd:complexType>
+        <xsd:choice maxOccurs="unbounded">
+          <xsd:element name="metadata">
+            <xsd:complexType>
+              <xsd:sequence>
+                <xsd:element name="value" type="xsd:string" minOccurs="0" />
+              </xsd:sequence>
+              <xsd:attribute name="name" type="xsd:string" />
+              <xsd:attribute name="type" type="xsd:string" />
+              <xsd:attribute name="mimetype" type="xsd:string" />
+            </xsd:complexType>
+          </xsd:element>
+          <xsd:element name="assembly">
+            <xsd:complexType>
+              <xsd:attribute name="alias" type="xsd:string" />
+              <xsd:attribute name="name" type="xsd:string" />
+            </xsd:complexType>
+          </xsd:element>
+          <xsd:element name="data">
+            <xsd:complexType>
+              <xsd:sequence>
+                <xsd:element name="value" type="xsd:string" minOccurs="0" msdata:Ordinal="1" />
+                <xsd:element name="comment" type="xsd:string" minOccurs="0" msdata:Ordinal="2" />
+              </xsd:sequence>
+              <xsd:attribute name="name" type="xsd:string" msdata:Ordinal="1" />
+              <xsd:attribute name="type" type="xsd:string" msdata:Ordinal="3" />
+              <xsd:attribute name="mimetype" type="xsd:string" msdata:Ordinal="4" />
+            </xsd:complexType>
+          </xsd:element>
+          <xsd:element name="resheader">
+            <xsd:complexType>
+              <xsd:sequence>
+                <xsd:element name="value" type="xsd:string" minOccurs="0" msdata:Ordinal="1" />
+              </xsd:sequence>
+              <xsd:attribute name="name" type="xsd:string" use="required" />
+            </xsd:complexType>
+          </xsd:element>
+        </xsd:choice>
+      </xsd:complexType>
+    </xsd:element>
+  </xsd:schema>
+  <resheader name="resmimetype">
+    <value>text/microsoft-resx</value>
+  </resheader>
+  <resheader name="version">
+    <value>2.0</value>
+  </resheader>
+  <resheader name="reader">
+    <value>System.Resources.ResXResourceReader, System.Windows.Forms, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089</value>
+  </resheader>
+  <resheader name="writer">
+    <value>System.Resources.ResXResourceWriter, System.Windows.Forms, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089</value>
+  </resheader>
+</root>

File PathTester/Properties/Settings.Designer.cs

+//------------------------------------------------------------------------------
+// <auto-generated>
+//     This code was generated by a tool.
+//     Runtime Version:4.0.30319.1
+//
+//     Changes to this file may cause incorrect behavior and will be lost if
+//     the code is regenerated.
+// </auto-generated>
+//------------------------------------------------------------------------------
+
+namespace PathTester.Properties {
+    
+    
+    [global::System.Runtime.CompilerServices.CompilerGeneratedAttribute()]
+    [global::System.CodeDom.Compiler.GeneratedCodeAttribute("Microsoft.VisualStudio.Editors.SettingsDesigner.SettingsSingleFileGenerator", "10.0.0.0")]
+    internal sealed partial class Settings : global::System.Configuration.ApplicationSettingsBase {
+        
+        private static Settings defaultInstance = ((Settings)(global::System.Configuration.ApplicationSettingsBase.Synchronized(new Settings())));
+        
+        public static Settings Default {
+            get {
+                return defaultInstance;
+            }
+        }
+    }
+}

File PathTester/Properties/Settings.settings

+<?xml version='1.0' encoding='utf-8'?>
+<SettingsFile xmlns="uri:settings" CurrentProfile="(Default)">
+  <Profiles>
+    <Profile Name="(Default)" />
+  </Profiles>
+  <Settings />
+</SettingsFile>

File PathTester/app.config

+<?xml version="1.0"?>
+<configuration>
+<startup><supportedRuntime version="v4.0" sku=".NETFramework,Version=v4.0"/></startup></configuration>