How to add new rectangles close to 0,0 on a infinite grid with later additions

Question

people of Stackoverflow. I am trying to write an algorithm that allows me to place rectangles close right next to (but not overlapping) each other. I wrote a quick mock-up in using pygame but it seems to not be quite right. I will be adding an x value to every rectangle to act as spacing. rectangles will only be added never removed

I tried

def find_adjacent_position(open_rectangles, all_rectangles, w, h):
    for existing_rect in open_rectangles:
        for offset in [(1,0), (-1,0), (0,1), (0,-1)]:
            x = existing_rect[0] + (existing_rect[2] * offset[0]) + offset[0]
            y = existing_rect[1] + (existing_rect[3] * offset[1]) + offset[1]
            if 0 < x + w <= SCREEN_WIDTH // 2 and 0 < y + h <= SCREEN_HEIGHT // 2:
                new_rect = (x, y, w, h)
                overlap = any(is_overlap(new_rect, rect) for rect in all_rectangles)
                if not overlap:
                    open_rectangles.append(new_rect)
                    return new_rect
        op = 4
        for offset in [(1,0), (-1,0), (0,1), (0,-1)]:
            x = existing_rect[0] + (16 * offset[0])
            y = existing_rect[1] + (16 * offset[1])
            if 0 < x + offset[0] <= SCREEN_WIDTH // 2 and 0 < y + offset[1] <= SCREEN_HEIGHT // 2:
                new_rect = (x, y, 16, 16)
                overlap = any(is_overlap(new_rect, rect) for rect in all_rectangles)
                if overlap: #cannot place it there, it overlaps
                    op-=1
            else:
                op -= 1 #offscreen
        if op <= 0:
            print(f"could not place anywhere. rect is now closed {len(open_rectangles)-1}")
            open_rectangles.remove(existing_rect)
        else: print(op)
    return None

this function takes 2 list. a list of all rectangles, and a list of rectangles who's sides are "empty" and more rectangles can be placed onto. this results in which as you can see fails to expand despite there being space on screen

manually drawn example with a x of 2 and the rectangles (2,4) (3,4) (3,3) (6,3) (3,5) (5,4) (4,9) (these are out of order but idea should be communicated) the red rectangle indicates a "closed" rectangle, and the blue rectangles are "open" rectangles (they are in the open_rectangles list and can have others rectangles placed off of them).

Answer 1

I implemented it in kotlin but the implementation boils down to.

1. get all valid positions a rectangle could occupy without overlapping
2. sort by distance to specified point (0,0)
3. create new rectangle and add to list of all rectangles.

(my kotlin function inside of another class which has some... optimisations?)

    // target is width,height to try and get all fitting points
    // all is a list of all rectangles
    // minimum is the minimum space that must be avaliable for a side to still be considered "open"
    fun getPossibleSections(target: Pair<Int,Int>, all: List<Rectangle>, minimum: Pair<Int,Int>): PossiblePointsCheck {
        val locations = ArrayList<Pair<Int,Int>>() // maintain a list of all possible locations
        val toClose = ArrayList<RectSideOpen>() // maintain a list of sides that should be marked closed
        for (side in openSides) {
            val xy = when (side) { //calculate where to put the x,y of the new rectangle
                RectSideOpen.Up -> Pair(x,y-target.second)
                RectSideOpen.Down -> Pair(x,y+h)
                RectSideOpen.Left -> Pair(x-target.first,y)
                RectSideOpen.Right -> Pair(x+w,y)
            }
            val newRect = Rectangle(xy.first,xy.second,target.first,target.second)
            if (!newRect.isOverlap(all)) { //isOverlap takes a list of rectangles and returns true if it overlaps any of them
                locations.add(xy)
            }
            //gonna do the pos-check for possible optimisations
            val testPos = when (side) {
                RectSideOpen.Right, RectSideOpen.Down -> xy //same equation as above so why recalc?
                RectSideOpen.Up -> Pair(x,y-minimum.second)
                RectSideOpen.Left -> Pair(x-minimum.first,y)
            }
            val testRect = Rectangle(testPos.first,testPos.second,minimum.first,minimum.second)
            if (testRect.isOverlap(all)) {
                toClose.add(side) // there is not enough space for even the "minimum" so mark it as dead
            }

        }
        for (side in toClose) { //so we dont get a concurent modification exception above
            openSides.remove(side)
        }
        return PossiblePointsCheck(locations,openSides.isEmpty())
    }