Unity 2d, Place object nearest to a coordinate without overlap?

Question

I am working on a game similar to Pool (Carrom actually). I need to place coins at the center of the board or nearest possible to it without overlapping any other coins. This is a 2d game.

Answer 1

Look into the Bridson algorithm for Poisson disk sampling. You can read about it here: https://www.jasondavies.com/poisson-disc/

Modify it as follows:

• When placing a new point, instead of picking any cell in the background grid from the active list, find the gridcell containing the closest possible point. Use the following formula: Δx = Cx - Gx - max(s, Cx - Gx) Δy = Cy - Gy - max(s, Cy - Gy) minDistSquared=Δx²+Δy². Cx, Cy is the centerpoint, Gx, Gz is the starting point of the grid cell, and s is the side of the square. It would probably help to sort your active list by this metric, or use a sorted list structure.
• Instead of picking points randomly and rejecting after k tries, try all intersection points between the 2r-radius circles around each point which cover it. Also try the closest point on/inside the square <Gx + max(s, Cx - Gx), Gy + max(s, Cy - Gy)>, and the closest point on each circle to the center, if that point is inside the square. Pick the closest valid point. Points are invalid when they're too far inside the range of existing circles. In the special case that the circle is exactly on the center, and there are no intersections between it and other circles, choose a random point on it.
  • If you found a valid point, search the list for all squares whose maximum distance can possibly be closer than it. Use this formula: Δx = max(|Cx - Gx|, |Cx - Gx - s|) Δy = max(|Cy - Gy|, |Cy - Gy - y|) maxDistSquared=Δx²+Δy². Try all those squares to see if you can find a closer valid point.
  • If you didn't find a valid point (not even in the current/original square), keep checking further out in the active list until you find one. Perform the above bullet point once you have.
• After your coins have moved around a result of your game mechanics, fully refresh the state of the underlying background / search grid and active list to account for the new point locations. When placing new coins, continue the algorithm from this updated state.

If you want your implementation to be simpler, and your board is small enough, you can probably omit the active list and just check every grid cell -- just keep track of the furthest point that was placed using the modified poisson rules (resets to the centerpoint when the search is refreshed). You will probably still want to store the order of cells to check in a list though.

And if you only ever need to place one coin after the state is refreshed, then you don't need to update the state of the grid/list or keep track of the furthest Poisson-placed point, just count on refreshing the whole thing each time.