Move object to nearest empty space on a plane

Question

Check the following gif: https://i.gyazo.com/72998b8e2e3174193a6a2956de2ed008.gif

I want the cylinder to instantly change location to the nearest empty space on the plane as soon as I put a cube on the cylinder. The cubes and the cylinder have box colliders attached.

At the moment the cylinder just gets stuck when I put a cube on it, and I have to click in some direction to make it start "swimming" through the cubes.

Is there any easy solution or do I have to create some sort of grid with empty gameobjects that have a tag which tells me if there's an object on them or not?

Answer 1

This is a common problem in RTS-like video games, and I am solving it myself. This requires a breadth-first search algorithm, which means that you're checking the closest neighbors first. You're fortunate to only have to solve this problem in a gridded-environment.

Usually what programmers will do is create a queue and add each node (space) in the entire game to that queue until an empty space is found. It will start with e.g. the above, below, and adjacent spaces to the starting space, and then recursively move out, calling the same function inside of itself and using the queue to keep track of which spaces still need to be checked. It will also need to have a way to know whether a space has already been checked and avoid those spaces.

---

Another solution I'm conceiving of would be to generate a (conceptual) Archimedean spiral from the starting point and somehow check each space along that spiral. The tricky part would be generating the right spiral and checking it at just the right points in order to hit each space once.

Here's my quick-and-dirty solution for the Archimedean spiral approach in c++:

float x, z, max = 150.0f;
vector<pair<float, float>> spiral;

//Generate the spiral vector (run this code once and store the spiral).
for (float n = 0.0f; n < max; n += (max + 1.0f - n) * 0.0001f)
{
    x = cos(n) * n * 0.05f;
    z = sin(n) * n * 0.05f;

    //Change 1.0f to 0.5f for half-sized spaces.
    //fmod is float modulus (remainder).
    x = x - fmod(x, 1.0f);
    z = z - fmod(z, 1.0f);

    pair<float, float> currentPoint = make_pair(x, z);

    //Make sure this pair isn't at (0.0f, 0.0f) and that it's not already in the spiral.
    if ((x != 0.0f || z != 0.0f) && find(spiral.begin(), spiral.end(), currentPoint) == spiral.end())
    {
        spiral.push_back(currentPoint);
    }
}


//Loop through the results (run this code per usage of the spiral).
for (unsigned int n = 0U; n < spiral.size(); ++n)
{
    //Draw or test the spiral.
}

It generates a vector of unique points (float pairs) that can be iterated through in order, which will allow you to draw or test every space around the starting space in a nice, outward (breadth-first), gridded spiral. With 1.0f-sized spaces, it generates a circle of 174 test points, and with 0.5f-sized spaces, it generates a circle of 676 test points. You only have to generate this spiral once and then store it for usage numerous times throughout the rest of the program.

Note:

1. This spiral samples differently as it grows further and further out from the center (in the for loop: n += (max + 1.0f - n) * 0.0001f).
2. If you use the wrong numbers, you could very easily break this code or cause an infinite loop! Use at your own risk.
3. Though more memory intensive, it is probably much more time-efficient than the traditional queue-based solutions due to iterating through each space exactly once.
4. It is not a 100% accurate solution to the problem, however, because it is a gridded spiral; in some cases it may favor the diagonal over the lateral. This is probably negligible in most cases though.

I used this solution for a game I'm working on. More on that here. Here are some pictures (the orange lines in the first are drawn by me in Paint for illustration, and the second picture is just to demonstrate what the spiral looks like if expanded):