Picking a random neighbouring cell, but only picking previously-visited ones if there aren't any unvisited

Question

I'm creating mazes, and have a Cell class (only relevant code shown)...

public class Cell {
  public int Row { get; }
  public int Col { get; }

  public List<Cell> Links { get; }

  public Cell North { get; set; }
  public Cell South { get; set; }
  public Cell East { get; set; }
  public Cell West { get; set; }

  public Cell(int row, int col) {
    Row = row;
    Col = col;
    Links = new List<Cell>();
  }

  public bool Linked(Cell cell) =>
    Links.Contains(cell);

  public bool DeadEnd =>
    Links.Count == 1;

  public IEnumerable<Cell> Neighbours =>
    new List<Cell> { North, South, East, West }.Where(c => c != null);

}

The mazes are all (currently) rectangular, so a Cell starts off with 2, 3 or 4 neighbours (depending on where it is in the maze, eg corner cells only have two neighbours, other edge cells have three, internal cells have four). These are set during the maze initialisation code (In Maze class which is not shown as it's not relevant here), and the Neighbours property gives the resulting neighbouring cells.

Given a grid of cells, the maze-generation algorithm links cells together using Link() and Unlink() methods (not shown as they aren't relevant here).

The Linked method then allows you to check if a cell is linked to the current one.

As I often need to pick a random cell from a collection, I have the following extension method defined...

public static Cell Rand<Cell>(this IEnumerable<Cell> items, Random r) =>
  items.OrderBy(n => r.Next()).First();

I create one Random object at the start, and pass it around, hence the second parameter.

Some of the maze-generation algorithms work by taking a random walk around the grid. When on a cell, they pick a neighbouring cell to be the next in the walk.

One specific algorithm will try and avoid previously visited cells. This means that if there are any neighbours that don't yet have any links, then it will pick one of those. If all neighbouring cells have links, it picks one of those instead.

My current code for this is shown below. This is on the maze-generating class, and current is the cell we're currently visiting in our random walk. We pick the next by...

Cell next = current.Neighbours.Any(c => c.Links.Count == 0)
  ? current.Neighbours.Where(c => c.Links.Count == 0).Rand(r)
  : current.Neighbours.Rand(r);

This works fine, but I can't help feeling that there is a way to combine this into one Linq query instead of the three required for the ?: operator.

Any suggestions? Thanks.

Answer 1

Using straight linq you could get to two iterations over Neighbours, assuming Neighbours is a class and not a struct.

var neighbour = current.Neighbours.FirstOrDefault(n => n.DeadEnd) ?? current.Neighbours.Where(n => !current.Linked(n)).First();

Pretty similar to yours except we using FirstOrDefault to return null if not found and using the ?? to execute the 2nd iteration if it's null.

If it is a struct then you would need to compare the FirstOrDefault to default. At that point I would just do the FirstOrDefault and write an If statement on next line comparing it to default.

If you want to do it in one iteration then will need to break out into a foreach loop. The downside is it will be calling the Linked() method even if it will never be used. As needs to store the value just in case it can't find DeadEnd.

Neighbour defaultValue == null;
foreach (var neighbour in current.Neighbours)
{
    if (neighbour.DeadEnd)
    {
        return neighbour;
    } else if (defaultValue == null && !current.Linked(neighbour))
    {
        defaultValue = neighbour;
    }
}

return defaultValue;

Without knowing what Linked does - aka does it have side effects or performance issues. This might not be the best answer.

As you can see from my review there are questions: Neighbours a class or struct? Should post the source code for Neighbours. What does Linked method do? Because of this the code can't fully be reviewed and is not complete. I would suggest you update your question to get better answers.