Place Buildings to represent village

Question

I try to convert an array of Buildings into a representation of a small village. There are several different buildings in a village, like factories that are located on the outside of the village, houses that are placed around churches in the center and so on. What would be a good approach to solve such a problem? I thought about using noise but this didn't give me the expected results.

I made a little drawing on what should happen:

I put an array of Buildings like this, for example, through a function

{ houses: 20, churches: 3, factories: 7 }

And i recieve a output similar to this:

Thank you for your help and ideas

Answer 1

One approach is to simulate natural growth of a real village.

• Looks good and organic.
• May be iterated to expand forever.
• Easily adopts to existing terrain (rivers, forests, cliffs).

Start with a house in the middle of the area. These are your first settlers.

Choose a building type that is most needed next, considering what was built already and what is yet in the queue. For example, citizens want no more than 1 church per 5 houses.

Next, choose a good location: sample N random unoccupied locations near existing buildings and rate them based on citizens' preferences. For example, people don't like factories in the middle of the city (that is, near churches and crowded housings).

Place a building. Repeat planning and allocation until queue is exhausted. Output example (imaginary):

Answer 2

Rule based placement

This approach will probably need revising once you start having more different building types and rules to their placement, but the task is assumed to be exactly as specified and should be able to expand somewhat as needed:

• List of fixed building types as input.

• Each building type comes with a set of rules for placement.

• Buildings are laid out on a regular grid.

I will now add a fourth constraint that is not explicitly specified:

• Buildings are placed in a specific order.

This is needed because some buildings depend on other buildings to be placed first.

In your sample, churches should be placed first, then the houses, then the factories.

So we adjust your array to use the new order - not to complicate with yet another data point to store:

{churches: 3, houses: 20, factories: 7}

Then, we iterate over this array.

For each element, we do the following:

Pick a location

Iterate over all possible locations - either one by one, down and across (a standard x,y loop), or by picking a random unoccupied location - this is probably the better choice to avoid bias, although there are probably even better methods that I am not aware of.

Rule function

Once a location is picked, you run a rule function that is unique per building type. This function either returns success or failure. On success, the building is placed and the building count is decreased by one. If the building count becomes 0 or less, move onto next building type. On failure, new location is picked and the rule function runs again - see bottom regarding infinite loops.

For a church, for example, the rule function is a random chance that becomes bigger towards the centre and smaller towards the edges - this will probably work better with the random location method, otherwise your chance would have to be highly nonlinear - nearly 1 in the centre, nearly 0 at the edges but maybe only 0.2 or something halfway through. Even then, there will likely be a bias towards whichever corner is your 0,0 on the map.

It may also be useful to store an additional grid that has a kind of a distance map to each placed church - initialised to a very large value like 9999, and once a church is placed, its corresponding grid position is set to 0, its neighbours to 1 and so on - for performance reasons maybe only going to 5 or 6 which should be enough anyway. Make sure never to overwrite a lower value with the higher one - after all it's the distance to the closest, not to this specific church that is being used.

The rule function then would make use of this value to make sure churches don't get placed too close to each other.

For a house the rule function would determine chance based on a church being nearby - nearly 1 next to one, lesser far away. It would also benefit from the "church proximity map" we created earlier.

Finally, factories can be placed at the edges with a rule function that only returns success if the location is an edge.

Further thoughts and improvements

It may be a good idea to keep some kind of a "failure counter" to prevent infinite loops - after every failure of a rule function, it is incremented, and if it passes a high value like 1000 (this will probably need tuning and scaling based on map size), we give up on placing these buildings: the building counter is exhausted and we move on.

Some way of checking value validity - make sure total building count is not bigger than the map can fit - the above counter would prevent the worst but it's still a good idea to keep some value sanity.

Answer 3

With the following assumptions:

• You have a maximum number of building of each kind to place.
• You have adjacency rules (such as: House can be adjacent to House, Church and Factory; Church can be adjacent to House; and Factory can be adjacent to House and Factory).

You can do this (explanations in comments, ugly details to make it work in JavaScript at the end of the code):

var all_positions = GetAllPositions();
var building_counts = {Church:3,House:20,Factory:7};
var building_kinds = RemainingBuildings(building_counts);
var rules = {Church:["House"],House:["Church","House","Factory"],Factory:["House","Factory"]};

// Start position and building
var position = PickRandomItemFrom(all_positions);
var building = PickRandomItemFrom(building_kinds);
SetBuilding(position, building);
Decrement(building_counts, building);

// Set of available positions to place buildings
var free_set = [];
for (const neighbor_position of NeighborsPositions(all_positions, position))
{
    Add(free_set, neighbor_position);
}

// Place more buildings
while (free_set.length > 0)
{
     // Set of all buildings that could be placed at the position
     var possible_buildings = RemainingBuildings(building_counts);
     // If there are posible buildings to place, we are done
     if (possible_buildings.length == 0)
     {
         break;
     }

     // Pick position
     position = RemoveAtRandomFrom(free_set);
     // Check neighbors
     var free_neighbors = [];
     for (const neighbor_position of NeighborsPositions(all_positions, position))
     {
         if (HasBuilding(neighbor_position))
         {
             // We found a neighbor building
             // Update the set of possible buildings to place accordingly
             var found_building = GetBuilding(neighbor_position);
             var valid_buildings = ValidNeighborBuildings(rules, found_building);
             possible_buildings = Intersect(possible_buildings, valid_buildings);
             // Early exit if there are no possible buildings to place
             if (possible_buildings.length == 0)
             {
                 break;
             }
         }
         else
         {
             // We found a posible position to add more buildings
             Add(free_neighbors, neighbor_position);
         }
     }

     // If there are posible buildings to place, we place none
     if (possible_buildings.length == 0)
     {
         continue;
     }

     // Pick a building to place and place it
     building = PickRandomItemFrom(possible_buildings);
     SetBuilding(position, building);
     Decrement(building_counts, building);
     // Update set of available positions (only when we placed something)
     for (const free_neighbor of free_neighbors){
         Add(free_set, free_neighbor);
     }
}

// ---
// UGLY DETAILS
// ---

function GetAllPositions(){
    return document.getElementsByTagName("td");
}

function Decrement(counts, key){
    counts[key]--;
    if (counts[key] == 0){
       delete counts[key];
    }
}

function PickRandomItemFrom(items){
    return items[items.length * Math.random() << 0]
}

function RemoveAtRandomFrom(items){
    var index = items.length * Math.random() << 0;
    var result = items[index];
    items.splice(index, 1);
    return result;
}

function SetBuilding(position, building){
    const representations = {Church: "⛪", House: "🏠", Factory: "🏭"};
    position.innerText = representations[building];
}

function HasBuilding(position){
    return position.innerText != "_";
}

function GetBuilding(position){
    const representations = {"⛪": "Church", "🏠": "House", "🏭": "Factory"};
    return representations[position.innerText];
}

function RemainingBuildings(items){
    return Object.keys(items);
}

function Add(items, item){
    if (!items.includes(item)){
        items.push(item);
    }
}

function ValidNeighborBuildings(rules, building){
    return rules[building];
}

function Intersect(a, b){
   return a.filter(value => b.includes(value));
}

function AddIfNotNull(array, item){
   if (item == null){
        return;
   }

   array.push(item);
}

function GetOrNull(array, index){
    if (array == null || index < 0 || index >= array.length){
        return null;
    }

    return array[index];
}

function NeighborsPositions(all_positions, position){
    // Actually a position is a DOM element
    // And I don't use the array of all positions
    // because it does not have adjacency information
    // Instead I query the DOM
    // This is not at all what you would do for your game
    var _ = all_positions;
    var result = [];
    AddIfNotNull(result, position.nextElementSibling);
    AddIfNotNull(result, position.previousElementSibling);
    var parent = position.parentElement;
    var nextRow = parent.nextElementSibling; 
    var prevRow = parent.previousElementSibling;
    var siblings = Array.from(parent.children);
    var siblingNumber = siblings.indexOf(position);
    AddIfNotNull(result, GetOrNull(nextRow?.childNodes, siblingNumber));
    AddIfNotNull(result, GetOrNull(prevRow?.childNodes, siblingNumber));
    // // Diagonals
    // AddIfNotNull(result, GetOrNull(nextRow?.childNodes, siblingNumber - 1));
    // AddIfNotNull(result, GetOrNull(nextRow?.childNodes, siblingNumber + 1));
    // AddIfNotNull(result, GetOrNull(prevRow?.childNodes, siblingNumber - 1));
    // AddIfNotNull(result, GetOrNull(prevRow?.childNodes, siblingNumber + 1));
    return result;
}

td{width:20px;}

<table>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
</table>

Please note that this code is based on neighbors (adjacency), not on a grid. And thus it is not limited by the size of the grid. In fact, it could work on any graph.

I'm aware this does not properly capture the idea that factories must be on the outside. You may consider the initial position the "center", and use the distance to it for a weighted random that to make some buildings more common the further away from it they are. In fact, in this implementation each buildings type has the same weight, consider taking into account the number of buildings to place for the weight. You may also try introducing another kind of rule: this building can only be placed when there are no buildings of this other kind to place. So you can have factories be placed only when all houses are placed.

---

Addendum: Updated the code to only place factories when there are no houses left to place.

A factory surrounded by houses is still possible. That might happen when the code managed to leave a hole when placing houses.

var all_positions = GetAllPositions();
var building_counts = {Church:3,House:20,Factory:7};
var building_kinds = RemainingBuildings(building_counts);
var adjacency_rules = {Church:["House"],House:["Church","House","Factory"],Factory:["House","Factory"]};
var unlock_rules = {Church:[],House:[],Factory:["House"]};

// Start position and building
var position = PickRandomItemFrom(all_positions);
var building = PickRandomItemFrom(building_kinds);
SetBuilding(position, building);
Decrement(building_counts, building);

// Set of available positions to place buildings
var free_set = [];
for (const neighbor_position of NeighborsPositions(all_positions, position))
{
    Add(free_set, neighbor_position);
}

// Place more buildings
while (free_set.length > 0)
{
     // Set of all buildings that could be placed at the position
     var possible_buildings = AvailableBuildings(unlock_rules, building_counts);
     // If there are posible buildings to place, we are done
     if (possible_buildings.length == 0)
     {
         break;
     }

     // Pick position
     position = RemoveAtRandomFrom(free_set);
     // Check neighbors
     var free_neighbors = [];
     for (const neighbor_position of NeighborsPositions(all_positions, position))
     {
         if (HasBuilding(neighbor_position))
         {
             // We found a neighbor building
             // Update the set of possible buildings to place accordingly
             var found_building = GetBuilding(neighbor_position);
             var valid_buildings = ValidNeighborBuildings(adjacency_rules, found_building);
             possible_buildings = Intersect(possible_buildings, valid_buildings);
             // Early exit if there are no possible buildings to place
             if (possible_buildings.length == 0)
             {
                 break;
             }
         }
         else
         {
             // We found a posible position to add more buildings
             Add(free_neighbors, neighbor_position);
         }
     }

     // If there are posible buildings to place, we place none
     if (possible_buildings.length == 0)
     {
         continue;
     }

     // Pick a building to place and place it
     building = PickRandomItemFrom(possible_buildings);
     SetBuilding(position, building);
     Decrement(building_counts, building);
     // Update set of available positions (only when we placed something)
     for (const free_neighbor of free_neighbors){
         Add(free_set, free_neighbor);
     }
}

// ---
// UGLY DETAILS
// ---

function GetAllPositions(){
    return document.getElementsByTagName("td");
}

function Decrement(counts, key){
    counts[key]--;
    if (counts[key] == 0){
       delete counts[key];
    }
}

function PickRandomItemFrom(items){
    return items[items.length * Math.random() << 0]
}

function RemoveAtRandomFrom(items){
    var index = items.length * Math.random() << 0;
    var result = items[index];
    items.splice(index, 1);
    return result;
}

function SetBuilding(position, building){
    const representations = {Church: "⛪", House: "🏠", Factory: "🏭"};
    position.innerText = representations[building];
}

function HasBuilding(position){
    return position.innerText != "_";
}

function GetBuilding(position){
    const representations = {"⛪": "Church", "🏠": "House", "🏭": "Factory"};
    return representations[position.innerText];
}

function RemainingBuildings(building_counts){
    return Object.keys(building_counts);
}

function AvailableBuildings(unlock_rules, building_counts){
    var remaining_buildins = RemainingBuildings(building_counts);
    var result = Object.keys(building_counts);
    var buildings = Object.keys(unlock_rules);
    for (const building of buildings){
        for (const contraint of unlock_rules[building]){
            if (remaining_buildins.includes(contraint)){
                var index = result.indexOf(building);
                if (index !== -1) {
                    result.splice(index, 1);
                }
            }
        }
    }

    return result;
}

function Add(items, item){
    if (!items.includes(item)){
        items.push(item);
    }
}

function ValidNeighborBuildings(rules, building){
    return rules[building];
}

function Intersect(a, b){
   return a.filter(value => b.includes(value));
}

function AddIfNotNull(array, item){
   if (item == null){
        return;
   }

   array.push(item);
}

function GetOrNull(array, index){
    if (array == null || index < 0 || index >= array.length){
        return null;
    }

    return array[index];
}

function NeighborsPositions(all_positions, position){
    // Actually a position is a DOM element
    // And I don't use the array of all positions
    // because it does not have adjacency information
    // Instead I query the DOM
    // This is not at all what you would do for your game
    var _ = all_positions;
    var result = [];
    AddIfNotNull(result, position.nextElementSibling);
    AddIfNotNull(result, position.previousElementSibling);
    var parent = position.parentElement;
    var nextRow = parent.nextElementSibling; 
    var prevRow = parent.previousElementSibling;
    var siblings = Array.from(parent.children);
    var siblingNumber = siblings.indexOf(position);
    AddIfNotNull(result, GetOrNull(nextRow?.childNodes, siblingNumber));
    AddIfNotNull(result, GetOrNull(prevRow?.childNodes, siblingNumber));
    // // Diagonals
    // AddIfNotNull(result, GetOrNull(nextRow?.childNodes, siblingNumber - 1));
    // AddIfNotNull(result, GetOrNull(nextRow?.childNodes, siblingNumber + 1));
    // AddIfNotNull(result, GetOrNull(prevRow?.childNodes, siblingNumber - 1));
    // AddIfNotNull(result, GetOrNull(prevRow?.childNodes, siblingNumber + 1));
    return result;
}

td{width:20px;}

<table>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
<tr><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td><td>_</td></tr>
</table>

This also gives me yet another idea: we can define constraints by number of neighbors. For example we could say that a factory can have one or two house neighbors, but not more. That would also prompt some refactoring, since I would rather be working with generators (function* and yield in JavaScript). The idea would be to have a generator that gives me the neighbors, then I can pass it to a function that gives the list of valid buildings. I will not do it for this answer.