# Finding nearest shape available in a grid system

Hello there

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 ), while Manhattan distances just require a sum (cheap ). 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 , but this manhattan distance is tempting