Determine the closest free set of X/Y coordinates within an ever expanding 2D grid stored in MySQL

Question

I have a very basic MySQL table in which X and Y coordinates are stored for tiles within a grid. The center of the grid is 0,0 and tiles can be created in any direction. If the coordinates exists in the MySQL table, they are considered "taken".

+---------+------------+------------+
| tile_id | position_x | position_y |
+---------+------------+------------+
|       1 |          0 |          0 |
|       2 |          1 |          0 |
|       3 |          0 |          1 |
|       4 |          1 |          1 |
|       5 |         -1 |         -1 |
+---------+------------+------------+

I need to place a set of 4 tiles (as a square, not a rectangle) into the grid in the closest possible position to 0,0.

To illustrate - the green tiles below would need to be found.

Sadly, I'm not even sure where to start with this one :(

Answer 1

Here's a single-query solution.

For any given square t on the grid, we can identify 8 possible 4-square tiles around it that may be empty:

If none of the 4 possible tiles that include (0,0) are available, the closest available tile to (0,0) must be adjacent to an existing taken square (since for any available tile not adjacent to an existing taken square, we can find an available tile that is closer).

That means we can construct a query over the taken squares to calculate possible available tiles.

To check whether we have an available tile adjacent to square t, we can use a query like the following:

  SELECT t.x AS x1, t.y-2 AS y1, t.x+1 AS x2, t.y-1 AS y2, LEAST(ABS(x1),ABS(x2))+LEAST(ABS(y1),ABS(y2)) AS distance
  FROM tiles t
  LEFT JOIN tiles t1 ON (t.x = t1.x OR t.x+1 = t1.x) AND (t.y-2 = t1.y OR t.y-1 = t1.y)
  WHERE t1.tile_id IS NULL

This will determine the left, top, right and bottom coordinates, as well as the Manhattan distance from (0,0), of available tiles in the t1 position relative to the taken squares.

Next we need a union of the available tiles in all 8 positions. We also need to check for the 4 possibly available tiles that include (0,0), since they're not necessarily adjacent to an existing taken square.

SELECT *, LEAST(ABS(x1),ABS(x2))+LEAST(ABS(y1),ABS(y2)) AS distance
FROM (
  SELECT t.x   AS x1, t.y-2 AS y1, t.x+1 AS x2, t.y-1 AS y2
  FROM tiles t
  LEFT JOIN tiles t1 ON (t.x   = t1.x OR t.x+1 = t1.x) AND (t.y-2 = t1.y OR t.y-1 = t1.y)
  WHERE t.y <= 0 AND t1.tile_id IS NULL

  UNION ALL

  SELECT t.x+1 AS x1, t.y-1 AS y1, t.x+2 AS x2, t.y   AS y2
  FROM tiles t
  LEFT JOIN tiles t2 ON (t.x+1 = t2.x OR t.x+2 = t2.x) AND (t.y-1 = t2.y OR t.y   = t2.y)
  WHERE t.x >= 0 AND t2.tile_id IS NULL

  UNION ALL

  SELECT t.x+1 AS x1, t.y   AS y1, t.x+2 AS x2, t.y+1 AS y2
  FROM tiles t
  LEFT JOIN tiles t3 ON (t.x+1 = t3.x OR t.x+2 = t3.x) AND (t.y   = t3.y OR t.y+1 = t3.y)
  WHERE t.x >= 0 AND t3.tile_id IS NULL

  UNION ALL

  SELECT t.x   AS x1, t.y+1 AS y1, t.x+1 AS x2, t.y+2 AS y2
  FROM tiles t
  LEFT JOIN tiles t4 ON (t.x   = t4.x OR t.x+1 = t4.x) AND (t.y+1 = t4.y OR t.y+2 = t4.y)
  WHERE t.y >= 0 AND t4.tile_id IS NULL

  UNION ALL

  SELECT t.x-1 AS x1, t.y+1 AS y1, t.x   AS x2, t.y+2 AS y2
  FROM tiles t
  LEFT JOIN tiles t5 ON (t.x-1 = t5.x OR t.x   = t5.x) AND (t.y+1 = t5.y OR t.y+2 = t5.y)
  WHERE t.y >= 0 AND t5.tile_id IS NULL

  UNION ALL

  SELECT t.x-2 AS x1, t.y   AS y1, t.x-1 AS x2, t.y+1 AS y2
  FROM tiles t
  LEFT JOIN tiles t6 ON (t.x-2 = t6.x OR t.x-1 = t6.x) AND (t.y   = t6.y OR t.y+1 = t6.y)
  WHERE t.x <= 0 AND t6.tile_id IS NULL

  UNION ALL

  SELECT t.x-2 AS x1, t.y-1 AS y1, t.x-1 AS x2, t.y   AS y2
  FROM tiles t
  LEFT JOIN tiles t7 ON (t.x-2 = t7.x OR t.x-1 = t7.x) AND (t.y-1 = t7.y OR t.y   = t7.y)
  WHERE t.x <= 0 AND t7.tile_id IS NULL

  UNION ALL

  SELECT t.x-1 AS x1, t.y-2 AS y1, t.x   AS x2, t.y-1 AS y2
  FROM tiles t
  LEFT JOIN tiles t8 ON (t.x-1 = t8.x OR t.x   = t8.x) AND (t.y-2 = t8.y OR t.y-1 = t8.y)
  WHERE t.y <= 0 AND t8.tile_id IS NULL

  UNION ALL

  SELECT 0 AS x1, -1 AS y1, 1 AS x2, 0 AS y2
  FROM dual
  WHERE NOT EXISTS (
    SELECT 1
    FROM tiles
    WHERE (x = 0 OR x = 1) AND (y = -1 OR y = 0)
  )

  UNION ALL

  SELECT 0 AS x1, 0 AS y1, 1 AS x2, 1 AS y2
  FROM dual
  WHERE NOT EXISTS (
    SELECT 1
    FROM tiles
    WHERE (x = 0 OR x = 1) AND (y = 0 OR y = 1)
  )

  UNION ALL

  SELECT -1 AS x1, 0 AS y1, 0 AS x2, 1 AS y2
  FROM dual
  WHERE NOT EXISTS (
    SELECT 1
    FROM tiles
    WHERE (x = -1 OR x = 0) AND (y = 0 OR y = 1)
  )

  UNION ALL

  SELECT -1 AS x1, -1 AS y1, 0 AS x2, 0 AS y2
  FROM dual
  WHERE NOT EXISTS (
    SELECT 1
    FROM tiles
    WHERE (x = -1 OR x = 0) AND (y = -1 OR y = 0)
  )
) z
ORDER BY distance
LIMIT 1

For brevity I used x and y instead of position_x and position_y. I used UNION ALL for speed since it avoids checking for duplicate rows, we only need one after all. Another optimization is to only check for tiles to the right of t where x >= 0, below t where y >= 0, and so on. Indexes on the x and y columns should be crucial to performance.

I tested it with your example grid:

+---+---+---+---+---------+
| x1| y1| x2| y2| distance|
+---+---+---+---+---------+
|-2 |  0| -1|  1|        1|
+---+---+---+---+---------+

Answer 2

As the logic is quite involved, I will not attempt a unique SQL statement; I will use auxiliary tables instead. Of course, these may be replaced by derived tables if needed.

To begin with, let's assume that we have a numbers table with values 0, 1, 2, 3, ... (large enough).

drop table if exists numbers;
create table numbers (nr int);
insert numbers (nr) values (0), (1), (2), (3), (4);

From this populate a points table. This table holds the entire grid (or at least a sufficiently large rectangular subset of it which contains the (0,0) point).

drop table if exists points;
create table points (x int, y int);

insert points (x, y) 
select x.nr, y.nr from numbers x, numbers y 
union all select -x.nr, y.nr from numbers x, numbers y where x.nr <> 0 or y.nr <> 0
union all select x.nr, -y.nr from numbers x, numbers y where x.nr <> 0 or y.nr <> 0
union all select -x.nr, -y.nr from numbers x, numbers y where x.nr <> 0 or y.nr <> 0;

Next compute all possible 2x2 squares:

drop table if exists squares;
create table squares (x_lo int, y_lo int, x_hi int, y_hi int);

insert squares (x_lo, y_lo, x_hi, y_hi)
select a.*, b.* from points a join points b on a.x = b.x - 1 and a.y = b.y-1;

Finally, this query will find all empty squares and order them according to the sum of their points' distance from (0.0). By limiting the result to 1 the "best" square is returned:

select x_lo, y_lo, x_hi, y_hi
, abs(s.x_lo) + abs(s.y_lo) + abs(s.x_hi) + abs(s.y_hi) as total_distance
from squares s 
left join t on t.position_x between s.x_lo and s.x_hi 
    and t.position_y between s.y_lo and s.y_hi
where t.position_x is null
order by abs(s.x_lo) + abs(s.y_lo) + abs(s.x_hi) + abs(s.y_hi)
limit 1
;

Your original data is in the t table:

drop table if exists t;
create table t (tile_id int, position_x int, position_y int);
insert t values (1,0,0),(2,0,1),(3,1,0),(4,1,1),(5,2,1),(6,2,2),
       (7,3,1),(8,3,2),(9,0,-1),(10,0,-2),(11,-1,-1),(12,-1,-2);

DEMO