Tag: unity

Your code is written under the assumption that the player can see directly into the memory of the program as it’s running. So as long as you change a variable, the player should be able to immediately observe that change, like if you’d flipped a physical card on the table in front of them.

Games don’t work that way. If we want a player to see something change in our world, we need to draw it to an image and put that image on the player’s screen first. That takes some work from the CPU to initiate. And the CPU can’t do that work if it’s busy doing something else.

A typical game loop looks something like this, in a simplified model:

1. Process window messages – this is what keeps the application from hanging, and allows it to read user input provided from the OS

2. Update the game state, running any per-object update scripts

3. Render the resulting frame and present it to the screen

4. Sleep until it’s time for the next frame

This most often runs single-threaded, and that’s the case for the Unity game loop too. (Even systems that use threading typically use it to “go wide” in a single step, like running multiple non-conflicting state updates in parallel in step 2, while still finishing all step 2 work before taking a state snapshot to render in step 3)

So, as long as you’re keeping the CPU busy in step 2, it never gets to step 3, so you never get to see an intermediate state rendered. And it also never gets back to step 1, which is what makes the app go unresponsive until your script finishes its work.

The culprit is your MyDelay function:

public static void MyDelay(float seconds)
{
    DateTime dt = DateTime.Now + TimeSpan.FromSeconds(seconds);
    do { } while (DateTime.Now < dt);
}

This is what’s called a “Busy Wait” – it tells the CPU to sit there checking and re-checking the time, burning millions of cycles doing nothing useful at all, until it’s allowed to continue on to the next line of code. You’ve temporarily suspended any real processing and turned this CPU core into a space heater.

(There are times when a busy wait is appropriate, when you think you’ll very likely be waiting less time than it takes to sleep and wake a thread. A busy loop running for a hundredth of a second as you have here is never a good idea, and you should throw away any tutorial that told you to do that)

Because you’ve kept this thread busy this whole time, it’s not allowed to exit step 2 and continue on to step 3, rendering your changes for the player to see them, until the whole routine has finished. At that point it shows only the finished state.

The better way to do something like this in Unity is to use Coroutines. This is a function that can run partially, then yield control flow back to the code that called it, so the CPU can finish the rest of step 2 and draw it in step 3. Then, in the next iteration of the game loop, the calling code can resume your coroutine right where it left off, and continue until the next yield. In this way it takes turns with all the other work needed to update and render your scene, rather than hogging the CPU to itself until it’s finished.

Here’s an example of what that could look like. Along the way I also cleaned up some issues:

• Used a descriptive enumeration instead of magic numbers to define the different tile states
• Swapped empty and wall so we get the border around the map for free from default initialization
• Used the built-in Vector2Int type instead of a tuple that needs a new add method defined
• Reduced the number of temporary collections allocated during the search

public class BFS : MonoBehaviour
{
    public enum TileState {        
        Wall,
        Empty,
        Start,
        Goal,
        Visited,
        Current
    }

    static readonly Vector2Int() MOVES = new Vector2Int() {
        Vector2Int.right, Vector2Int.up, Vector2Int.left, Vector2Int.down
    };

    public float delayPerStep = 0.01f;

    TileState(,) InitializeSearchSpace(Block(,) blocks, Queue<Vector2Int> startingPoints, out int goalCount) {
        goalCount = 0;

        int width = blocks.GetLength(0);
        int height = blocks.GetLength(1);
        TileState(,) area = new TileState(width + 2, height + 2);

        for (int x = 0; x < width; x++) {
            for (int y = 0; y < width; y++) {
                TileState state = blocks(x, y).GetState();
                switch (state) {
                    case TileState.Start:
                        startingPoints.Enqueue(new Vector2Int(x + 1, y + 1));
                        break;
                    case TileState.Goal:
                        goalCount++;
                        break;
                }
                area(x + 1, y + 1) = state;
            }
        }

        return area;
    }

    IEnumerator RunSearch(Block(,) blocks, TileState(,) area, Queue<Vector2Int> openSet, int goalsRemaining) {

        float timeBudget = Time.deltaTime;

        while (openSet.Count > 0 && goalsRemaining > 0) {
            var tile = openSet.Dequeue();

            foreach(var move in MOVES) {
                var next = tile + move;
                switch(area(next.x, next.y)) {
                    case TileState.Wall:
                    case TileState.Visited:
                        continue;                    
                    case TileState.Goal:
                        goalsRemaining--;
                        break;
                }
                blocks(next.x - 1, next.y - 1).SetState(TileState.Current);

                timeBudget -= delayPerStep;
                while (timeBudget <= 0f) {
                     yield return null;
                     timeBudget += Time.deltaTime;
                }

                blocks(next.x - 1, next.y - 1).SetState(TileState.Visited);
                area(next.x, next.y) = TileState.Visited;

                openSet.Enqueue(next);
            }
        }
    }

    public void BreadthFirstSearch(Block(,) blocks) {
        var openSet = new Queue<Vector2Int>();

        var area = InitializeSearchSpace(blocks, openSet, out int goalCount);

        StartCoroutine(RunSearch(blocks, area, openSet, goalCount));
    }
}