Research: Indoor CQC Map Generation (1)

Objective: write an algorithm that can create a floor plan (single story) that is reasonable enough to be used as a top-down close quarter combat (CQC) game map.

I don’t know how to do it yet, so I’d study some basic floorplan design principles. The remaining of the article would be my notes watching this video.


  • Size of the floorplan
  • Number of stories
  • Single/Multi-family
  • Number of each type of rooms, also garage
  • Thickness of external/internal walls

Features of Space/Room

Y/S/N – Yes/Semi/No

  • Sqft needs (Y/S/N)
  • Adjacencies (list of room references, immediate or not)
  • Public access (Y/S/N)
  • Daylight/Views (Y/S/N)
  • Acoustical privacy (Y/S/N)
  • Plumbing (Y/S/N)
  • Special equipment (DW, MW, Refri…)

Macro Constraint Solving

  1. Fill in the features of each unary feature (anything other than adjacency) with average value + variation
  2. Create a few reasonble and strict requirements on adjacency
  3. Constraint solving on adjacency
  4. Generate Relationship-Diagram (9:08 in the video)

Grouping by Constraints

  1. Group rooms by their features. (e.g. kitchen+living room + dining room since none of them requires privacy)
  2. Place rooms in different directions and makes it somewhat reasonable.

Abstract Floor Plan

  1. Follow the grouping result, draw circles of correct scale with respect to the actual space requirement, at the approximate place we planned earlier.
  2. Ensure each “connected component” is pure, rather than mixed with private and non-private.
  3. Set daylight direction and try to satisfy lighting/view requirements.
  4. Resolve adjacency problems by not allowing adjacency edges to cross. (How)

Bubble Diagram

Draw bubbles (fat circles just like in the abstract floor plan) and make them fit.

Block Diagram

Growing bubbles and make them squarer. Okay to leave some space in between squares as hallways.

(How to make things align though?)

Figure out room sizes

Tip: sum of furniture area + circulation room ~= final room size

Ideas: pre-make furniture assets so save some difficulty generating furnitures.

Open Correct Doors

  • Open correct doors according to the adjacency map.
  • Make sure every room can be accessed
  • Special restrictions for bathroom
  • Keep doors away from beds, toilets, desks


  • Pluming walls
  • Exterior walls
  • Seperating walls
  • No walls (Imaginary walls that’s removed with common sense, e.g. living & dining & kitchen)
  • Half walls (Shelves or anything that works as a half-separation)

UNet Multiple Character Solution

(This post is originally from the wiki I wrote for my recent game project Runner or Dinner

Dead ends

  • Add components according to the character type after a playerPrefab is spawned: Unity does not support adding NetworkBehaviour to a spawned GameObject
  • Bind every possible component to playerPrefab and disable some of them according to the character type: Too hard to organize component relationships on that prefab. Dirty component references.


Unreal Method

Let playerPrefab be a ‘player controller’,and the characters are Pawns/Characters in Unreal concepts. A player controller can possess a character.

Pros: this method is universal, easily comprehensible, fully-controlled

Cons: you have to implement possess, and native helper components like NetworkTransform and NetworkAnimator cannot help you anymore.

P.S: I haven’t think over how to implement this feature, will research on Unreal’s implementation further.

Spawn-time Replacement (Our Way!)

If your game has a lobby scene, a traditional way to share information between lobbyPlayer and gamePlayer is to customize OnLobbyServerSceneLoadedForPlayer

// class NetworkLobbyPlayer
public override bool OnLobbyServerSceneLoadedForPlayer(GameObject lobbyPlayer,
                                                       GameObject gamePlayer);

This callback runs when the server notices a client has finished loading game scene. By default it spawns a game player prefab and transfer the control from lobbyPlayer to gamePlayer. But we can ignore the existing gamePlayer and create a new character for this client, which requires ReplacePlayerForConnection

public static bool ReplacePlayerForConnection(Networking.NetworkConnection conn,
                                              GameObject player, 
                                              short playerControllerId);

From server’s view, clients are just connections. We can get a client’s connection from a NetworkIdentity that is spawned for that client, for us that is, the lobbyPlayer.

var clientConn = lobbyPlayer.GetComponent<NetworkIdentity>().connectionToClient;

Then we spawn a new character prefab for the client to ‘possess’.

// instantiate on server side
var newPlayer = Instantiate(characterPrefab);

// tell all clients to spawn (auto-synced)

// destroy auto-created gamePlayer                      

No need to worry about synchronization problem. The Spawn method of NetworkServer will ensure that every client scene will create a same copy when they are ready.

Finally, we return false for OnLobbyServerSceneLoadedForPlayer to prevent transfer of player control, because we have destroyed the game player and given the control to newPlayer by replacement.

How to Build a Heatmap for Tactic AI : Attempt 2

After a little bit more thinking I changed the propagation function from

Heat(neighbor) += Heat(this) * decay / numberOfOpenNeighbors


Heat(neighbor) = Max(Heat(neighbor), Heat(this) - numOpenNeighbors * decay)

And now the decay factor is the valve for linear decreasing speed.

Intuitively you can see the ‘heat’ is decreasing linearly relative to ‘distance’ from heat source. But remember, we want a 1/distance^2 like curve for it, therefore we apply a post-processing step to the temperature we got for each grid. That is:

(1) Distance(grid) = Heat(source) - Heat(grid)
(2) Factor(grid) = 1 / (Distance(grid) * Distance(grid) + 1)
(3) Factor(grid) = Factor(grid) - 1 / (Heat(source) * Heat(source) + 1)
(4) Heat(grid) = Heat(source) * Factor(grid)

By applying step (2), we generated a 1/distance^2 like function. (The +1 term on the denominator is to avoid divide by zero at source point.) But you can see that even a grid originally with Heat = 0 will be assigned with a positive factor. Step (3) is responsible for eliminating those residues.

Here I present the test results:

Compared with the result of last post, the result of this new mathematical model yields more reasonable area of influence, as well as easier-to-tune heatmap parameters.

Hope it helps you somehow!

PS: this algorithm takes 1~2 ms to run on my Unity3D scene, with grid map size ~60*40, which is acceptable for my current need, but not as good as expected. Later post I might talk about my experiments on optimizing the algorithm.


How to Build a Heatmap for Tactic AI : Attempt 1

I’ve been doing experiments on game AI, tactic team AI to be specific. And currently I’m looking forward to make use of a heatmap.

My idea is to make a grid map and assign heat value (or temperature) on grids so that it represents value of some property that can be reasoned about by an agent. An example would be to represent the potential danger. Think of a group of defenders who wants to defend a room with two entrance from waves of zombies. The area close to the two entrances are most dangerous, therefore have highest temperature in the heatmap. In addition to those two points, places nearby should also be ranked more dangerous than any other places. And a corner of the room could be a safer place to hold (although it’s not always true).

However I’d like the heatmap to have some extra characteristics. Namely, I want the emission of the heat satisfy this constraint:

The narrower the space is, the harder for the heat to go away.

It makes sense because it’s most dangerous if you are trapped in a small cage or a narrow corridor with a ruthless zombie than in a open space, where you can run and turn freely.

My first implementation attempt is to use Breadth-First Search to spread the heat and decrease the energy as it goes farther and farther. And to satisfy the requirement above, I made the decrease factor negatively related to the number of open spaces (neighbor grid without obstacles) next to a grid. For instance, let’s say first there’s a heat source somewhere in the grid field, and 5 out of it’s 8 neighbors are obstacles. And those 3 open neighbors will share all the energy the heat source emits. On the other hand, if all 8 neighbors of some heat source are open, the heat emit will be evenly distributed among them, therefore each neighbor receives less energy.

Intuitively this method tends to keep energy in small room and makes heat in narrow hallways to travel further before the energy becomes insignificant, than in a wide open space. However, the experiment didn’t work out well.

In the experiment I use the number of grids a heat source can influence to indicate whether this model makes sense. In common sense, a heat source with the same initial energy should influence same number of grids regardless of geometry, assuming the obstacles are made of insulation materials. But this naive model cannot guarantee it. Also, exponentially decreasing energy feels wrong. You can see the results from the image below. (Depth of green-ish color indicates the energy. Two heat sources are on the same row, different columns of the field)

Heat in narrow spaces does influence further, but the area of influence is unproportional.

Next step I’ll figure out how to preserve the area of influence on any geometry, and try to invite some 1/distance^2 like factor into the function because it feels more natural.