Find closest open space in grid of rectangles?

Question

I'm making a builder game where you snap arbitrarily sized rectangles into a 2D grid. I want the player to be able to drag and drop these rectangles anywhere on the grid, but prevent collisions (i.e., they snap to the closest available space when the user lets go of the drag). I already have a decent way to determine collisions and "nearby" rectangles, but am looking for an efficient method to find the "closest available grid space" based on this information.

Desired behavior:

In the image, the blue rectangle is the dragged thing; the green is the expected "snapping" spot. I want the "snapping" to happen in realtime and to handle 1) reasonably large numbers of nearby rectangles (at least 20-30?), 2) full intersections (one rect inside the other), 3) "concave" structures like on the top-right example.

My current method:

1. Find all rectangles that are colliding with the active rectangle (not the issue AFAIK).
2. For each axis, generate a list of every possible displacement by summing variants of the intersection size (ex: [-(rectSize - x), -x, 0, x, rectSize - x]). Also take into account cases where one rectangle is fully intersected.
3. Find every combination of the displacements for the two axes (cartesian product).
4. Project the active rectangle to each possible displacement, and drop any that have collisions.
5. Calculate the distance from the center of the active rectangle to each of remaining projected rectangle's centers.
6. The snap position is the remaining projected rectangle with the shortest distance.

The problem:

My method works, but is much more expensive than I'd like. I'm wondering if this is the best solution, but should just be optimized, or if there's a different approach that's naturally more efficient.

I've found some related questions (link, link, link), but they seem focused on solving slightly different problems. Topics like rectangle packing seem similar, but also not the same as what I'm looking for.

Answer 1

I did some tests and found that this method does work.

First you need to find the nearest grid coordinates to the position of the dragged block (blue box). Then do a grid-based BFS on the target coordinates. Find a nearest feasible location(green box).

I use unity for testing, Code:

using System;
using System.Collections.Generic;
using UnityEngine;

public class NewBehaviourScript : MonoBehaviour
{
    public GameObject block;
    private Vector2Int blockSize = Vector2Int.one;
    private Vector3 targetPos;
    private Vector3 putPos;
    private HashSet<Tuple<int, int>> map = new HashSet<Tuple<int, int>>();
    private List<Vector2Int> direction = new List<Vector2Int>{
        new Vector2Int(1,1),
        new Vector2Int(1,-1),
        new Vector2Int(-1,1),
        new Vector2Int(-1,-1),
    };
    void Start()
    {
    }
    void Update()
    {
        var pos = Camera.main.ScreenToWorldPoint(Input.mousePosition);
        block.transform.position = new Vector3(pos.x, pos.y, -1);
        UpdateTargetPos(pos);
        UpdatePutPos();
        if (Input.GetMouseButtonDown(0))
        {
            PutBlock();
            RandBlock();
        }
    }
    private void UpdateTargetPos(Vector3 pos)
    {
        var leftDown = pos - new Vector3(blockSize.x / 2f, blockSize.y / 2f, 0);
        targetPos = new Vector3(Round(leftDown.x), Round(leftDown.y), 0);
        DrawBlock(targetPos, Color.blue);
    }
    private void UpdatePutPos()
    {
        var queue = new Queue<Tuple<int, int>>();
        var closeSet = new HashSet<Tuple<int, int>>();
        var start = new Tuple<int, int>((int)targetPos.x, (int)targetPos.y);
        queue.Enqueue(start);
        while (queue.Count > 0)
        {
            var nodeNow = queue.Dequeue();
            closeSet.Add(nodeNow);
            var hasBlock = false;
            RangePos(new Vector3(nodeNow.Item1, nodeNow.Item2), (key) =>
            {
                if (map.Contains(key))
                {
                    hasBlock = true;
                    return true;
                }
                return false;
            });
            if (!hasBlock)
            {
                putPos = new Vector3(nodeNow.Item1, nodeNow.Item2, 0);
                break;
            }
            foreach (var dir in direction)
            {
                var keyNext = new Tuple<int, int>(nodeNow.Item1 + dir.x, nodeNow.Item2 + dir.y);
                if (!closeSet.Contains(keyNext))
                {
                    queue.Enqueue(keyNext);
                }
            }
        }
        DrawBlock(putPos, Color.green);
    }
    private void DrawBlock(Vector3 leftDown, Color color)
    {
        float sizeX = blockSize.x;
        float sizeY = blockSize.y;
        var rightUp = leftDown + Vector3.right * sizeX + Vector3.up * sizeY;
        Debug.DrawLine(leftDown, leftDown + Vector3.up * sizeY, color);
        Debug.DrawLine(leftDown, leftDown + Vector3.right * sizeX, color);
        Debug.DrawLine(rightUp, leftDown + Vector3.up * sizeY, color);
        Debug.DrawLine(rightUp, leftDown + Vector3.right * sizeX, color);
    }
    private void PutBlock()
    {
        var newblock = GameObject.Instantiate(block);
        newblock.transform.position = putPos + new Vector3(blockSize.x / 2f, blockSize.y / 2f, 0);
        RangePos(putPos, (key) =>
        {
            map.Add(key);
            return false;
        });
    }
    private void RandBlock()
    {
        blockSize = new Vector2Int(UnityEngine.Random.Range(1, 4), UnityEngine.Random.Range(1, 4));
        block.transform.localScale = new Vector3(blockSize.x, blockSize.y, 1);
        block.GetComponent<SpriteRenderer>().color = UnityEngine.Random.ColorHSV();
    }
    private void RangePos(Vector3 leftDown, Func<Tuple<int, int>, bool> f)
    {
        var startX = (int)leftDown.x;
        var startY = (int)leftDown.y;
        for (int i = 0; i < blockSize.x; i++)
        {
            for (int j = 0; j < blockSize.y; j++)
            {
                var key = new Tuple<int, int>(startX + i, startY + j);
                if (f(key))
                {
                    return;
                }
            }
        }
    }
    private float Round(float value)
    {
        var vx = value + 0.5f;
        return (float)Math.Floor(vx);
    }
}