Commits

Robin Harper  committed 6b4cecf

Added a merge sort to gridnode

  • Participants
  • Parent commits 3ebe40b

Comments (0)

Files changed (2)

File AstarPath/AstarPathfinder.cs

 
                 while (opened.Count > 0)
                 {
-                    //opened = BubbleSort.SortImageGridF(opened);
-                    opened.Sort(GridNode.CompareNodesByCost);
+                    opened = GridNode.MergeSort(opened);
+
                     var parent = opened[0];
                     closed.Add(parent);
                     opened.RemoveAt(0);

File AstarPath/GridNode.cs

                 }
             }
         }
+
+        public static List<GridNode> MergeSort(List<GridNode> list)
+        {
+            if (list.Count <= 1)
+            {
+                return list;
+            }
+
+            var left = new List<GridNode>();
+            var right = new List<GridNode>();
+            var result = new List<GridNode>();
+
+            int middle = list.Count / 2;
+
+            for (int i = 0; i < middle; i++)
+            {
+                left.Add(list[i]);
+            }
+
+            for (int i = middle; i < list.Count; i++)
+            {
+                right.Add(list[i]);
+            }
+
+            left = MergeSort(left);
+            right = MergeSort(right);
+            result = Merge(left, right);
+
+            return result;
+        }
+
+        public static List<GridNode> Merge(List<GridNode> left, List<GridNode> right)
+        {
+            var result = new List<GridNode>();
+
+            while (left.Count > 0 || right.Count > 0)
+            {
+                if (left.Count > 0 && right.Count > 0)
+                {
+                    if (left[0].Center.f <= right[0].Center.f)
+                    {
+                        result.Add(left[0]);
+                        left.RemoveAt(0);
+
+                        if (left.Count >= 1)
+                        {
+                            left = left.GetRange(0, left.Count);
+                        }
+                    }
+                    else
+                    {
+                        result.Add(right[0]);
+                        right.RemoveAt(0);
+
+                        if (right.Count >= 1)
+                        {
+                            right = right.GetRange(0, right.Count);
+                        }
+                    }
+                }
+                else if (left.Count > 0)
+                {
+                    result.Add(left[0]);
+                    left.RemoveAt(0);
+
+                    if (left.Count >= 1)
+                    {
+                        left = left.GetRange(0, left.Count);
+                    }
+                }
+                else if (right.Count > 0)
+                {
+                    result.Add(right[0]);
+                    right.RemoveAt(0);
+
+                    if (right.Count >= 1)
+                    {
+                        right = right.GetRange(0, right.Count);
+                    }
+                }
+            }
+
+            return result;
+        }
     }
 }