I have written a recursive formula that finds a path between two nodes arranged in a grid pattern. My code works with two problems. The first is that sometimes the start node's position is changed from one to another number, but I fixed this by reassigning it after the recursion so it's not that big of a deal. The second issue is that it runs unbearably slow. It takes about 30 seconds to generate a 5x5 and I haven't been able to generate a 7x7 which is my ultimate goal. I am hoping that someone will see if there are any optimizations that can be made.
The Node class, shown below, has a Key property and a Value property. The Key is the position in the grid starting at 0. So, for a 5x5, the top left node will have a Key of 0 and the bottom right node will have a Key of 24. Each node has Up, Down, Left and Right properties that are the other nodes it is connected to. When there are no nodes in that direction, the value is null. For example, in a 5x5, a node with Key = 0 will have an Up of null, a Down of the node with Key = 5, a Left of null, and a Right of the node with Key = 1. As another example, still in a 5x5, a node with Key = 6 will have an Up of the node with Key = 1, a Down of the node with Key = 11, a Left of the node with Key = 5, and a Right of the node with Key = 7. The Position property is the path. The path starts with the node with Position = 1, then goes to the node with Position = 2 etc. until it reaches the end node, which would be position N*N on a NxN board (e.g. a 5x5 board would have an end node with position 25). These nodes are added to a list called nodeList-(a global variable). One of these nodes gets randomly marked as Start-(boolean) and a different node gets randomly assigned as End-(boolean).
The next part is the path. We want to find a random path (starting at 1) between the Start and End nodes that touches every other node without touching the same node twice. This is for a game, so it is important that it is random so the user doesn't play the same board twice. If this is not possible given the Start and End Positions, new Start and End positions are chosen and the algorithm is run again.
class Node
{
public int Key { get; set; }
public int? Position { get; set; } = null;
public Node Up { get; set; } = null;
public Node Down { get; set; } = null;
public Node Left { get; set; } = null;
public Node Right { get; set; } = null;
public bool Start = false;
public bool End = false;
public Node(int key)
{
Key = key;
}
}
public bool GeneratePath()
{
var current = nodeList.Where(w => w.Start).FirstOrDefault();
var start = current;
int position = 1;
bool Recurse(Node caller)
{
if (current.Position == null)
{
current.Position = position;
}
if (current.End)
{
return true;
}
var directions = GetDirections();
for (var i = 0; i < 4; i++)
{
var done = false;
if (directions[i] == 0 && current.Up != null && current.Up.Position == null
&& (!current.Up.End || position == n * n - 1))
{
var temp = current;
current = current.Up;
position++;
done = Recurse(temp);
}
else if (directions[i] == 1 && current.Down != null && current.Down.Position == null
&& (!current.Down.End || position == n * n - 1))
{
var temp = current;
current = current.Down;
position++;
done = Recurse(temp);
}
else if (directions[i] == 2 && current.Left != null && current.Left.Position == null
&& (!current.Left.End || position == n * n - 1))
{
var temp = current;
current = current.Left;
position++;
done = Recurse(temp);
}
else if (directions[i] == 3 && current.Right != null && current.Right.Position == null
&& (!current.Right.End || position == n*n - 1))
{
var temp = current;
current = current.Right;
position++;
done = Recurse(temp);
}
if(done)
{
return true;
}
}
current.Position = null;
position--;
if(caller == null)
{
return false;
}
current = caller;
return false;
}
var success = Recurse(null);
if (success)
{
start.Position = 1;
}
return success;
}
private int[] GetDirections()
{
List<int> toPerm = new List<int>();
for (var i = 0; i < 4; i++)
{
toPerm.Add(i);
}
Random random = new Random();
var perms = HelperMethods.GetPermutations(toPerm, toPerm.Count);
var randomNumber = random.Next(0, perms.Count());
var directions = perms.ElementAt(randomNumber).ToArray();
return directions;
}
public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
{
if (length == 1) return list.Select(t => new T[] { t });
return GetPermutations(list, length - 1)
.SelectMany(t => list.Where(o => !t.Contains(o)),
(t1, t2) => t1.Concat(new T[] { t2 }));
}
To reiterate, I am wondering if there are optimizations I can make as it runs too slow for my purposes.