騎士之旅遞歸C＃我在做東西的方式中弄錯了東西

Question

class Knight 
{ 
    public static readonly double LegalDistance = Math.Sqrt(5); 
    public Stack<Field> Steps { get; set; } 

    private static readonly List<Field> board = Board.GameBoard; 
    private static List<Field> fields;  

    private static readonly Random random = new Random(); 
    private static readonly object synLock = new object(); 

    public Knight(Field initial) 
    { 
     Steps = new Stack<Field>(); 
     Steps.Push(initial); 
    } 

    public void Move() 
    { 
     Field destination = Choose(); 

     if (destination == null) 
     { 
      return; 
     } 

     Console.WriteLine("Moving from " + GetPosition().GetFieldName() + " to " + destination.GetFieldName()); 
     Steps.Push(destination); 
    } 

    public Field Back() 
    { 
     Field from = Steps.Pop(); 
     Console.WriteLine("Moving back from " + from.GetFieldName() + " to " + GetPosition().GetFieldName()); 

     return from; 
    } 

    public Field Choose() 
    { 
     List<Field> legalMoves = Behaviour(); 

     legalMoves.RemoveAll(field => Steps.Contains(field, new FieldValueComparer())); 

     if (legalMoves.Count == 0) 
     { 
      return null; 
     } 

     Field theChoosenOne; 

     int index; 
     lock (synLock) 
     { 
      index = random.Next(0, legalMoves.Count); 
     } 

     theChoosenOne = legalMoves.ElementAt(index); 


     return theChoosenOne; 
    } 

    private List<Field> Behaviour() 
    { 
     fields = new List<Field>(); 
     fields.AddRange(board); 

     for (int i = fields.Count - 1; i >= 0; i--) 
     { 
      double actualDistance = fields[i].GetDistance(GetPosition()); 
      if (!actualDistance.Equals(LegalDistance)) 
      { 
       fields.Remove(fields[i]); 
      } 
     } 

     return fields; 
    } 
    public List<Field> GetSteps() 
    { 
     return Steps.ToList(); 
    } 

    public Field GetPosition() 
    { 
     return Steps.Peek(); 
    } 
} 

所以這就是我要做的東西。問題是，我缺少一些關鍵功能，因爲在低給定的stepcount時，它回溯到開始時，在高臺階上，它會導致StackOverFlow。

這裏有一些其他的功能，讓你明白我想做的事： 計算距離：

public double GetDistance(Field other) 
{ 
     return Math.Sqrt(Math.Pow(other.X - X, 2) + Math.Pow(other.Y - Y, 2)); 
} 

找到路徑：

class PathFinder 
    { 
     public static void FindPath(Knight knight) 
     { 

      if (knight.Steps.Count != 20) 
      { 
       knight.Move(); 

       FindPath(knight); 

       knight.Back(); 
      } 
     } 
    } 

Answer 1

你的路徑搜索本質上是隨機遊走。無論如何，這可能需要一段時間。

現在關於StackOverflow：請注意，當沒有可去的地方時，您不會推送Move()上的任何東西。因此，遞歸調用FindPath()仍然會有相同的knight.Steps.Count，相同的位置，相同的null返回Choose() ...等等，直到您超出堆棧空間。

明顯的解決將是bool返回值添加到Move()表示，如果有爲任何舉動。除非使用隨機移動背後有實際的理由，否則推薦使用更多的確定性搜索算法。