I assume that the ignored cell in your image is the cell placed in the previous iteration of the placement loop and that the next potential placement cell is next to the previous placement cell.
If implementing the grid such that you can directly check whether a cell is occupied is not an option, then I can’t think of a way to reduce the time complexity in terms of number of parts but I do have a suggestion for reducing the time complexity in terms of required distance between parts.
If I understood correctly, then in your current approach, checking whether a part can be placed requires going through the list of already placed parts’ grid locations multiple times. The number of times you go through the list depends on the number of cells within the check distance and this number of cells depends on the distance.
Couldn’t you instead just go through that list once per potential placement cell and for each occupied cell that isn’t a cell to ignore, calculate the distance from it to the potential placement cell. If the distance is too small, then the part can’t be placed.
Also, in the image, you mention that the distance is 1 for example purposes so I assume it can be greater than 1 in practice. If the required distance is more than 1, then the strict distance check needs to ignore more than one previous cell. This is because if the check distance was 2, for example, then the first placement cell would prevent the third placement unless it’s ignored. Having to skip the strict distance check for multiple cells may cause problems so in the code below, I added a different kind of check for these cells. For each of these (excluding the latest placement cell), I check whether the distance from the potential placement cell to it is smaller than the distance from the latest placement cell to it. If that’s the case then this potential placement cell is considered invalid for placement.
I wrote this code with the assumption that you are using Manhattan distance for defining which cells to check. You can modify the distance function to use some other kind of distance such as euclidean distance, but that may also require increasing the number of cells that are ignored by the strict distance check.
local function getDistance(cell0: Vector2, cell1: Vector2): number
local offset: Vector2 = cell1 - cell0
local manhattanDistance: number = math.abs(offset.X) + math.abs(offset.Y)
return manhattanDistance
end
local function canPartBePlaced(cell: Vector2, occupiedCells: {Vector2}, checkDist: number): boolean
if cell == occupiedCells[#occupiedCells] then
return false
end
-- last index that is checked is #occupiedCells - checkDist so that bigger checkDist causes more previous
-- cells to be ignored by this loop.
for iOccupiedCell: number = 1, #occupiedCells - checkDist do
local occupiedCell: Vector2 = occupiedCells[iOccupiedCell]
local distance: number = getDistance(cell, occupiedCell)
if distance > checkDist then
continue
end
return false
end
-- This loop checks whether the distance to at least one of the cells ignored in the earlier loop
-- would reduce. If that's the case, then this isn't accepted as a placement position.
for iOccupiedCell: number = math.max(#occupiedCells - checkDist + 1, 1), #occupiedCells - 1 do
local occupiedCell: Vector2 = occupiedCells[iOccupiedCell]
local distance: number = getDistance(cell, occupiedCell)
if distance < getDistance(occupiedCells[#occupiedCells], occupiedCell) then
return false
end
end
return true
end
