home..

Choosing Enemy Spawn Locations

Nathan Reilly / November 2025 (2867 Words, 16 Minutes)

blizzardgame

Overview

This is a problem within my “Blizzard Game” project.

Currently, I have a basic enemy type. I also have a service, EnemyService, that is responsible for spawning enemies. The EnemyService currently uses pooling to avoid redundant prefab instantiation, which is great. As of now, I can spawn an enemy at any grid position using the SpawnEnemy(EnemyID enemyId, Vector2Int gridPosition) function.

So, the foundation is laid for an enemy wave system, but this is where I’ve gotten stuck. The wave system’s design, that is the decision on when to spawn which enemies, is not a large issue. That itself will be more of an exercise in design rather than a technical problem. This is because, given a plan on when and how many of which enemies to spawn, I can easily implement it with the tools I have already built. The technical problem, therefore, instead lies in where to spawn the enemies.

In my game, there are what are called Obstacles. This represents any kind of natural or player-built structure that is in the environment, ranging from trees to crossbows. I store them in a grid-based system within the ObstacleGridService, which is a grid with the same dimensions that I use for the enemy spawn (I had chosen to match the enemy spawn coordinates with the obstacle system in anticipation of this problem). Given the existence of obstacles, I need to ideally ensure that enemies don’t spawn inside of them, as that may cause issues where they get stuck.

Additionally, there are certain areas where I don’t want enemies to spawn. The most important of these areas is the player’s base. As agreed upon by the spawning system of many games (e.g. Minecraft, Terraria, Rimworld, etc.), enemies should spawn outside of the player’s base and attempt to infiltrate it. However, the player’s base is not that clear-cut, so I’ll need to define some rules that describe what is and isn’t considered a spawning safe zone.

With these considerations, the problem becomes more nuanced than simply choosing a random location, or even a random location some distance from the player. It will require some game design decisions, and some technical problem solving.

Problem: Given an enemy (or group of enemies) that I’d like to spawn, where do I spawn them? Problem Variables:

Working through it

In this section, I type out my ideas as I come up with them, but you’ll notice I try to keep it organized as if this was written after the problem was solved. In reality, I’m taking rough notes on my notebook with pen and paper, and then writing them here as I refine the ideas. Simultaneously, I may be implementing or prototyping these ideas.

Filtering

One of the few first ideas that I came up with was filtering. Specifically, take some set (an “upper bound” of sorts) of valid locations, and then iterate through them, removing any that don’t meet the desired conditions. Then, pick a random location out of that set.

This set could then be cached, and then updated whenever the player moves, or whenever obstacles are added/removed.

In-fact, we could do one better by distributing the construction of this set over multiple frames. This would avoid random frame drops whenever the set construction runs.

The idea I had for the initial set was to use all locations within a certain distance range of the player. This range is defined by two quantities:

So, given \(r\) and \(t\), and player location \(p\), our valid location set starts as:

\[\{x \in \mathbb{Z}^2 : r-t \leq |x-p| \leq r\}\]

Then, the idea is to iterate through all locations in this set, and remove each one that doesn’t meet the desired criteria. To be able to do this, we first need to define the criteria.

Filter Criteria

Recall that we have two general conditions for our spawn location:

The first condition is easy to check for. We can simply check whether the given location is occupied by an obstacle through the ObstacleGridService, which provides functionality for exactly this type of check.

The second condition is more nuanced. Given some location, how do we figure out whether its considered “inside of the player’s base”? We’ll need to define what is actually considered a safe area for the player.

Defining the player’s base

The initial thought was to check if the location is enclosed within walls. My intuition rejected this almost immediately though, as this would not be trivial to implement, and likely comes with many edge cases or exploits.

My next thought was in relation to Minecraft’s spawning system. In Minecraft (at least in the early days), hostile enemies would only spawn under a certain light level. Since most uninhabited areas are naturally dark, this is a good solution. Enemies naturally spawn at night or in dark areas, and players can easily mitigate it by placing light sources. This prevents enemies from spawning within the base, as most bases are well lit.

Taking inspiration, my next idea was similar: enemies cannot spawn near heat sources. Generally, the player needs to stay warm in my game to survive, and they do so by placing down heat sources. Thus, this would have enemies spawn far from active player constructions, which is intended. Additionally, it would also make sense lore-wise to have enemies depend on the cold, as the main theme of the game is surviving against the cold and the threats that lie within it.

Going further from this idea, why not just use temperature in general? The game is designed such that any grid location also has a real-time temperature value, which is affected by these heat sources. This would also simplify the “near heat source” check to just “location’s actual temperature”. Lore-wise, it could be the case that the cold “manifests” other enemies, further uniting the two threats under the overarching theme.

Sidenote: I believe it is often beneficial to base game design decisions around the “lore” or “themes” of your game. Not only does it make the game likely feel more immersive (as the game design is consistent with what it intends to imitate), it will also make it more likely that independant design decisions synergize well with each other. For instance, if enemies spawn in the cold, this synergizes well with my previous decision (consistently with my theme) that structures function better in the heat. The intended gameplay experience of both decisions naturally complement each other through the idea to “fight against the cold”.

So, this was what I initially decided on as my criteria for the player’s “base”. Rather than checking if the location is actually near a base, we simply check if it is under a certain temperature threshold. This check will encompass the actual “near a base” check, and perhaps other interesting environmental cases. It also force the player to spend energy to prevent enemy spawns no matter what, as heat always costs something to the player. It won’t be so easy to “enemy-proof” an area like this.

Final Criteria

So, as of this point, my decision for the filter criteria was these to use these two checks:

Constructing the Initial Set

With filter criteria defined, the next challenge is to actually construct the initial coordinate set to filter from. Since this set will need to be re-constructed over and over again as the player’s location or the environment changes, its construction needs to be as efficient as possible.

Recall that we are looking for the following set of integer coordinates:

\[\{x \in \mathbb{Z}^2 : r-t \leq |x-p| \leq r\}\]

This set forms a ring or annulus shape, defined by \(R_1\) and \(R_2\), the outer and inner radii, respectively. Here, we have \(R_1=r\) and \(R_2=r-t\).

Through looking this problem up online, the more common variation was finding all integer coordinates within a circle. The simplest solution was to construct a minimal bounding box around the circle, and then removing any coordinates within it that are not within the circle. We can thus take a similar approach with our ring shape, ensuring to also discard points within the inner-circle of the ring.

Note that this approach’s time complexity is \(O(r)\), where \(r\) is the outer radius. This is because we iterate through all points with an entire bounding box with area \((2r)^2\).

After further research, I found an approach that can fortunately improve upon this complexity, taking advantage of the annulus shape.

Rather than checking an entire bounding box, we instead use “scanlines”. With this approach, we iterate through each possible \(y\) value (i.e. the range \([p_y-r,p_y+r]\)), and then extract the bounds of the \(x\) value for each coordinate with that \(y\) value.

To illustrate how this bounds extraction is done, suppose \(p = (0,0)\) and select our \(y\) value as \(y_0 \in [p_y-r, p_y+r]\). With this, we have that \(x^2 + y_0^2 \leq r^2 \rightarrow |x| \leq \sqrt{r^2-y_0^2}\) . Additionally, if \(y_0 < r-t\), we have that \(x^2+y_0^2 \geq (r-t)^2 \rightarrow |x| \geq \sqrt{(r-t)^2-y_0^2}\) Denoting our bounds for the positive \(x\) coordinate as \(x \in [L(y_0), H(y_0)]\), we define the bounds as follows:

\[L(y_0) = I_{y_0\leq r-t} \sqrt{(r-t)^2-y_0^2}\] \[H(y_0) = \sqrt{r^2-y_0^2}\]

Where \(I\) is the indicator function. We can then mirror these bounds for the negative \(x\) coordinate by flipping the signs. Note that, for each \(y\) coordinate, constructing the bounds can be done in constant time. With the bounds, we can fetch each valid coordinate in \(O(k)\) time, where \(k\) is the amount of valid coordinates with \(y=y_0\). Thus, our overall time complexity becomes \(O(r+k)\), where \(k\) is the total amount of valid coordinates!

Note that using this method for a circle is not a significant improvement, as in that case \(k\) would be approximately the area of the circle, which would make \(k\in O(r^2)\) and degrade back to \(O(r^2)\). However, in our case, the area of the annulus is calculated as follows:

\[A=\pi(r^2-(r-t)^2) = \pi(2rt-t^2)\]

If we fix \(t\), i.e. the thickness of the annulus, then we have \(k\in O(r)\), which maintains our overall algorithm’s time complexity at \(O(r+k) = O(r)\).

Note that this time complexity is not completely relevant, however, since our value for \(r\) (and also \(t\)) will likely be pre-configured and constant during runtime. However, it does suggest that the method is more performant than the bounding box method for the same radius, especially for larger and larger radii, which is what we were looking for.

Baking the Initial Set

A thought I then had while writing the following section, is that we only need to compute the initial set once!

The set of coordinates within the initial set is simply the set of coordinates within an annulus centered on the player’s position. Note, however, that given fixed values for \(r\) and \(t\), the annulus has an identical shape no matter the value of the player’s position.

Thus, we can instead compute the entire set once, with the assumption that \(p=(0,0)\). Then, every time we need the initial set relative to the player’s actual position, we simply offset all of the coordinates within the set by the player position, which will take \(O(k)\) time, where \(k\) is the amount of valid coordinates. That time complexity is the best case scenario, as the process itself is lower bounded by \(\Omega(k)\), given that we must always at least output all \(k\) valid coordinates.

Bringing it Together

With a strategy for initial set construction and filtering, it seems that our strategy is complete! To fetch all valid coordinates, our algorithm is as follows:

Let \(V\) denote the valid location set, a set of integer coordinates. Let \(V_0\) denote the baked annulus coordinate set, a set of integer coordinates.

1) Bake \(V_0\) using the scanline method with pre-configured values for \(r\) and \(t\) as input, and with the assumption that \(p=(0,0)\). 2) At the start of runtime, and then whenever the game state is updated such that the valid location set must be updated: 1) Set \(V\) to \(V_0\) offset by the player position 2) Iterate through \(V\). For each coordinate: 1) If it is occupied by an obstacle, remove it from \(V\). 2) If its temperature is higher than a given threshold (pre-configured), remove it from \(V\). 3) When a valid location for spawn is requested: 1) Pick a random coordinate from \(V\).

And there we have it. Now, we'll try it out in practice.

Implementation

I decided to create a dedicated class, EnemySpawnRange, that was responsible for fetching valid enemy spawn positions.

The first step was implementing the baking of \(V_0\), which was done as follows (note all of the code is in C#):

/// <summary>  
/// Bakes unbiased coordinate set, i.e. coordinates that are within a specific distance range  
/// from the point (0,0).  
/// </summary>  
/// <param name="l">Minimum distance</param>  
/// <param name="u">Maximum distance</param>  
private void BakeUnbiasedSet(float l, float u)  
{  
    int maxDistanceInt = Mathf.FloorToInt(u);  
    float u_2 = u * u;  
    float l_2 = l * l;  
    // Scan each valid y coordinate  
    for (int y = -maxDistanceInt; y <= maxDistanceInt; ++y)  
    {  
        float y_2 = y * y;  
        int xOuter = Mathf.FloorToInt(Mathf.Sqrt(u_2 - y_2));  // Outer bound for x value  
        if (y_2 >= l_2)  
        {  
            // No inner circle on this y value, return all coordinates within outer bound  
            _unbiasedInitialSet.AddRange(  
                Enumerable  
                    .Range(-xOuter, 2 * xOuter + 1)  
                    .Convert(x => new Vector2Int((int)x, y))  
                );  
        }  
        else  
        {  
            // Inner circle present, add coordinates between inner/outer bounds  
            int xInner = Mathf.CeilToInt(Mathf.Sqrt(l_2 - y_2));  
            _unbiasedInitialSet.AddRange(  
                Enumerable  
                    .Range(xInner, (xOuter - xInner) + 1)  
                    .Convert(x => new Vector2Int((int)x, y))  
            );  
            // Mirror inner/outer bounds to account for negative x values  
            _unbiasedInitialSet.AddRange(  
                Enumerable  
                    .Range(xInner, (xOuter - xInner) + 1)  
                    .Convert(x => new Vector2Int(-(int)x, y))  
            );  
        }  
    }  
}

And then, constructing the initial unfiltered set was very simple from there:

/// <summary>  /// Constructs unfiltered coordinate set within a specific distance range from the player  /// </summary>  /// <param name="playerPosition">Current player position</param>  private List<Vector2Int> ConstructUnfilteredSet(Vector2Int playerPosition)  
{  
    return _unbiasedInitialSet.Select(coordinate => coordinate + playerPosition).ToList();  
}

To then filter the unfiltered set, it is also simple. We first define a filtering predicate:

/// <summary>  
/// Determines whether a given location is a valid enemy spawn location.  
/// </summary>  
/// <returns>True if location is valid, false otherwise</returns>  
private bool FilterLocation(Vector2Int location)  
{  
    // Location must be unoccupied and below threshold temperature  
    return !_obstacleGridService.IsOccupied(location) &&  
           _temperatureService.GetTemperatureAt(location) <= EnemyConstants.MaxSpawnTemperature;  
}

And then we use it to filter locations from the unfiltered set:

/// <summary>  
/// Updates the set of valid enemy spawn locations  
/// </summary>  
private void UpdateValidLocations()  
{  
    // Ensure unfiltered set is up to date  
    UpdateUnfilteredSet(  
        _obstacleGridService.Grids[ObstacleLayer.Main]  
            .WorldToCellPos(_playerService.PlayerPosition)  
    );  
    _validLocationsSet = _unfilteredSet.Where(FilterLocation).ToList();  
}

And this completes the core implementation. However, given that temperature, environment and player position updates are extremely common, it won’t be practical to do this at every single relevant event invocation. Instead, we should distribute this work over multiple frames.

Coroutines

To distribute the valid location set construction over multiple frames, we use coroutines. Coroutines are functions that execute only a subset of their code per frame, continuing their execution on the next frame. They are implemented using the IEnumerator interface, and the yield directive.

While implementing this version of the valid location set construction, I noticed that the unfiltered set construction and the filtering step can be aggregated into a single step by offsetting the coordinate and filtering it immediately, creating a single coroutine function as follows:

/// <summary>  
/// Updates the set of valid enemy spawn locations  
/// </summary>  
private IEnumerator UpdateValidLocations()  
{  
    Vector2Int playerGridPos = _obstacleGridService.Grids[ObstacleConstants.MainObstacleLayer]  
        .WorldToCellPos(_playerService.PlayerPosition);  
    List<Vector2Int> newValidLocations = new();  
    foreach (Vector2Int unbiasedCoordinate in _unbiasedInitialSet)  
    {  
        if (FilterLocation(unbiasedCoordinate + playerGridPos))   
            newValidLocations.Add(unbiasedCoordinate + playerGridPos);  
        yield return null; // Wait until next frame to continue
    }  
  
    _validLocationsSet = newValidLocations;  
}

Then, we expose a Tick() function that allows the external EnemyService to update it over multiple frames:

/// <summary>  
/// Ticks the enemy spawn range, performing one step toward updating the current valid locations.  
/// </summary>  
public IEnumerator Tick()  
{  
    _validLocationUpdater = UpdateValidLocations();  
    while (true)  
    {  
        if (_validLocationUpdater == null || !_validLocationUpdater.MoveNext())   
            // Restart valid locations update  
            _validLocationUpdater = UpdateValidLocations();  
        yield return null;  
    }  
}

Finally, in our EnemyService, we run one iteration of the Tick() function, which allows us to continuously work towards our next valid locations:

In Practice

In practice, this approach seems to work! Alongside this, I implemented the enemy wave spawning system that decides when to spawn enemies, and which ones to spawn, and it works great alongside the EnemySpawnRange class that I’ve implemented with the above methods.

A short problem, I worked through this one in an hour or two, but still an interesting one. Thanks for reading.