2 
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();
    }
}

So this is how I'd do the stuff. The problem is, I am missing some key functionality, because on low given stepcount it backtracks to the start, on high stepcount, it causes StackOverFlow.

Here are some other functions to let you understand what I want to do: Calculating distance:

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

Finding the path:

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

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

                FindPath(knight);

                knight.Back();
            }
        }
    }
4

1 回答 1

1

您的路径搜索本质上是随机游走。在大板上，无论如何这可能需要一段时间。

Move()现在关于 StackOverflow：请注意，当没有地方可去时，您不会推动任何事情。所以，在递归调用FindPath()那里仍然会是相同knight.Steps.Count的，相同的位置，相同的null返回Choose()......等等，直到你的堆栈空间不足。

明显的解决方法是添加bool返回值来Move()指示是否有任何移动。除非有使用随机移动的实际原因，否则建议使用更具确定性的搜索算法。

于 2015-10-22T16:18:27.403 回答