Title: Generate random self-avoiding walks in C#

The previous examples that display self-avoiding walks generate all of the possible walks for a given lattice and then let you select one. Because the programs use a recursive search to find walks, walks near the same part of the sequence tend to share the same initial pieces. For example, if the very first move in the walk is to the right, then many of the following walks will also start by moving to the right.

This example generates random self-avoiding walks so adjacent walks don't necessarily share their initial steps. When you click the Generate button, the program starts a timer. Whenever the timer ticks, the program generates a random walk and displays it.

When the timer's Tick event fires, the program calls the following FindOneWalk method to generate a random self-avoiding walk.

// Find one random self-avoiding walk. private List<Point> FindOneWalk(int width, int height) { // Make an array to show where we have been. bool[,] visited = new bool[width + 1, height + 1]; // Get the number of points we need to visit. int num_points = (width + 1) * (height + 1); // Start at a random vertex. int x = Rand.Next(0, width + 1); int y = Rand.Next(0, height + 1); // Start the walk at (0, 0). Stack<Point> current_walk = new Stack<Point>(); current_walk.Push(new Point(x, y)); visited[x, y] = true; // Search for walks. List<Point> walk = FindOneWalk(num_points, current_walk, x, y, width, height, visited); if (walk != null) return walk; return current_walk.ToList(); }

This method creates a visited array to keep track of the lattice vertices that are in use. It then picks a random lattice vertex, adds it to the current walk, and calls the following overloaded version of the FindOneWalk method to extend the walk to fill the lattice.

// Extend the walk that is at (current_x, current_y). private List<Point> FindOneWalk(int num_points, Stack<Point> current_walk, int current_x, int current_y, int width, int height, bool[,] visited) { // If we have visited every position, and the // last point is in the lower right corner, // then this is a complete walk. if (current_walk.Count == num_points) { return current_walk.ToList(); } else { // Try the possible moves. Point[] next_points = new Point[] { new Point(current_x - 1, current_y), new Point(current_x + 1, current_y), new Point(current_x, current_y - 1), new Point(current_x, current_y + 1), }; // Randomize the moves to try. next_points.Randomize(); // Try the moves. foreach (Point point in next_points) { if (point.X < 0) continue; if (point.X > width) continue; if (point.Y < 0) continue; if (point.Y > height) continue; if (visited[point.X, point.Y]) continue; // Try visiting this point. visited[point.X, point.Y] = true; current_walk.Push(point); List<Point> walk = FindOneWalk(num_points, current_walk, point.X, point.Y, width, height, visited); if (walk != null) return walk; // We're done visiting this point. visited[point.X, point.Y] = false; current_walk.Pop(); } return null; } }

First this method checks the number of vertices visited. If we have visited every vertex, then we have a complete walk so the method returns it as a list of vertex points.

If we don't have a complete walk, the method makes an array holding the adjacent vertices. It then calls the Randomize extension method to randomize the array. Look at the code or see the post Make extension methods that randomize arrays and lists in C# to see how that works.

For each of the points the code adds that point to the current self-avoiding walk and then recursively calls itself to continue extending the walk.

If the recursive call to FindOneWalk returns a non-null value, then that value is a walk that was found farther down in the call stack. In that case the method simply returns the walk, passing it up the call stack.

If the recursive call does not find a complete walk, then the method removes the point from the current walk and tries the next point.

The previous examples find all self-avoiding walks before displaying any of them. This program only finds one walk at a time. The way it randomizes the adjacent points at each step makes it pick a random walk.

Download the example to experiment with it and to see additional details.