Finding nearest shape available in a grid system

Hello there :slight_smile:

So I made a small grid (4x6 units) where you can drag and drop 3D objects. (figure 1 & figure 2)


Based on 3d object and cell centers I can find the x nearest cells, but I need to find the nearest space available instead (vertical or horizontal) (figure 3 or 5)


I do have an idea but I feel it like an overkill method (lot of permutations at the beggining)
1 - Stock all the available places with the same area (based on their tile number) horizontal and vertical
2 - For each stocked place, compare the center with the current object3D and if the distance is smaller than the previous one, save the center.
3 - Position the 3D object in this center

Is there a better way ? (less operations)

Your approach sounds like a good solution. Depending on the size of your grid, you may not need to optimize it further. However, if you start experiencing performance issues, you could improve performance by:

  • Perform the distance calculations only after the active shape moves into a new grid location. This avoids redundant checks, for instance, if you’re running the algorithm 60 times per second.
  • Stopping the loop once a full row yields longer distances than your closest one; at that point, you know you won’t find anything closer.
  • You could also use Manhattan distance to calculate proximity, instead of a true diagonal. Diagonals require square-rooting (expensive :slightly_frowning_face:), while Manhattan distances just require a sum (cheap :slightly_smiling_face:). It may not give you the true closest spot, but a good approximation.
  • A much more challenging but efficient approach would be by “spiraling out” from the desired location. Here’s a good answer with the algorithm necessary (look at the one under “Old Version”)

Thanks for the tips Marquizzo, there are some quite interesting suggestions!
As you said, I’ll check the performances first :slight_smile: , but this manhattan distance is tempting :smiley: