Generating Cell combination (By sizes) on grid using pathfinding algorithm

Question

I'm working on a project and as part of my process, I need to generate all the possible cell combination for given start point while avoiding the invalid cells (The cells filled with black. see down below).

The grid is NxM and each cell can have different width and height. The cell combination shape should not exceed the max Height and Width.

How can I efficiently generate all the combinations (or Only the biggest) for each position? (the grid can be huge).

We are able to go in 4 directions. (up, right, bottom, left)

Example:

S is the start cell. and the goal is to find all the possible cell combinations that can be placed (without exceeding the maximum width and height). In this example MAX_WIDTH - 4, MAX_HEIGHT - 7.

One option could be:

Another option:

and so on..

My Idea is to use a pathfinding algorithm such as Dijkstra or A*. (Each Node is the cell) and the end goal is when we exceed to maximum lengths. I should take into account the option that maybe I'll need to give a score for shape (by the number of vertices etc...)

I tried to go each direction with DFS, but it's working only on small grids.

My Code:

public class CombinationCreator
{
    /// 
    /// The grid that contain 2D array of cells.
    /// 
    private readonly Grid _grid; 
    /// 
    /// Current state of the cell combination shape, used in the recursive function.
    /// 
    private List CurrentState { get; set; } = new List();

    /// 
    /// List of directions used for scanning the cells.
    /// 
    private readonly List<(int row, int column)> Directions = new List<(int row, int column)>()
    {
        (0, 1), // right
        (1, 0), // bottom
        (0, -1), // left
        (-1, 0) // top
    };

    /// 
    /// List of all the possible combinations.
    /// 
    public List> Results { get; set; } = new List>();

    public CombinationCreator(Grid grid)
    {
        _grid = grid;
    }

    /// 
    /// Get i , j indexes of the cell. (will be the starting index)
    /// 
    public List> GetCombinations(int i, int j)
    {
        double MAX_WIDTH = 4;
        double MAX_HEIGHT = 7;
        List> result = new List>;
        return GenerateCombination(i, j, MAX_WIDTH, MAX_HEIGHT);
    }

    /// 
    /// Recursive function to generate all the possible cell combinations by scanning the grid.
    /// 
    private void GenerateCombinations(int i, int j, double maxWidth, double maxHeight, int depth = 0, double minX = double.MaxValue,
        double maxX = double.MinValue, double minY = double.MaxValue, double maxY = double.MinValue)
    {
        if (depth > 50)
        { // to prevent Infinite Recursion
            return;
        }

        if (ShouldSavePreviousState(i, j, maxWidth, maxHeight, minX, maxX, minY, maxY))
        { // If the current cell will exceed maxWidth and maxHeight then we need to save the previous state.
            Results.Add(new List(CurrentState));
        }
        else
        {
            if (i >= 0 && i < _grid.Cells.GetLength(0) &&
                j >= 0 && j < _grid.Cells.GetLength(1))
            {
                Cell currentCell = _grid.Cells[i, j];

                if (!currentCell.Marked && currentCell.Valid && !currentCell.IsUsed)
                {
                    currentCell.Marked = true;
                    CurrentState.Add(currentCell);

                    minX = Math.Min(minX, currentCell.TopLeft.x);
                    maxX = Math.Max(maxX, currentCell.BottomRight.x);
                    minY = Math.Min(minY, currentCell.BottomRight.y);
                    maxY = Math.Max(maxY, currentCell.TopLeft.y);

                    foreach (var direction in Directions)
                    { // Go each direction
                        int newRow = i + direction.row;
                        int newCol = j + direction.column;

                        GenerateCombinations(newRow, newCol, maxWidth, maxHeight, depth + 1, minX, maxX, minY, maxY);
                    }

                    CurrentState.RemoveAt(CurrentState.Count - 1);
                    currentCell.Marked = false;
                }
            }
        }
    }

    /// 
    /// Check if the current cell will exceed maxWidth and maxHeight or the cell is the boundaries.
    /// then we need to save the previous state.
    /// 
    private bool ShouldSavePreviousState(int i, int j, double maxWidth, double maxHeight, double minX = double.MaxValue,
        double maxX = double.MinValue, double minY = double.MaxValue, double maxY = double.MinValue)
    {
        double currentWidth = maxX - minX;
        double currentHeight = maxY - minY;

        if (i >= 0 && i < _grid.Cells.GetLength(0) &&
            j >= 0 && j < _grid.Cells.GetLength(1))
        {
            Cell currentCell = _grid.Cells[i, j];

            if (!currentCell.Marked && currentCell.Valid && !currentCell.IsUsed)
            {
                double nextMinX = Math.Min(minX, currentCell.TopLeft.x);
                double nextMaxX = Math.Max(maxX, currentCell.BottomRight.x);
                double nextMinY = Math.Min(minY, currentCell.BottomRight.y);
                double nextMaxY = Math.Max(maxY, currentCell.TopLeft.y);

                double nextWidth = nextMaxX - nextMinX;
                double nextHeight = nextMaxY - nextMinY;

                if (nextHeight > maxHeight || nextWidth > maxWidth)
                {
                    return true;
                }
            }

            if (!currentCell.Valid || currentCell.IsUsed)
            {
                if (currentHeight > maxHeight || currentWidth > maxWidth)
                {
                    return false;
                }
                return true;
            }
        }

        return false;
    }
}

Cell Class:

public class Cell
{
    public bool Marked { get; set; } // Indicates when already saw the cell during the scanning
    public bool Valid { get; set; } // Indicates if we can use the cell ( white cell ).
    public bool IsUsed { get; set; } // Indicates if another shape use this cell.
    public Point TopLeft { get; set; } // The top left point
    public Point BottomRight { get; set; } // The bottom right point
}

Generating Cell combination (By sizes) on grid using pathfinding algorithm

Answers (1)

Related Questions