How UrbanGroundLookup Identifies and Classifies Urban Areas in Arnis

UrbanGroundLookup employs an eight-stage density-based clustering pipeline that converts building centroids into a compact cell-based hash set, enabling O(1) classification of urban zones for stone ground generation.

The UrbanGroundLookup struct serves as the core classification engine in the Arnis repository, determining where the procedural world generator should place stone ground blocks instead of default grass. Implemented entirely in src/urban_ground.rs, this system processes OpenStreetMap building data through a spatial clustering pipeline that balances detection accuracy with memory efficiency.

The Eight-Stage Urban Detection Pipeline

The classification logic operates as a sequential pipeline, transforming raw building coordinates into a queryable urban mask. Each stage is implemented as a distinct function within src/urban_ground.rs.

1. Density Grid Creation

The algorithm first quantizes the world into a uniform spatial grid to reduce computational complexity. The create_density_grid() function (lines 308–317) buckets every building centroid into square cells of approximately 64 blocks, recording which buildings occupy each cell. This converts O(n) building coordinates into a sparse grid structure where n is the number of cells rather than individual buildings.

2. Identifying Dense Cells

Next, find_urban_clusters() (lines 326–331) filters the grid to identify potentially urban cells—those containing at least min_buildings_per_cell buildings. This threshold eliminates isolated structures like rural farmhouses while retaining areas with genuine building density.

3. Adaptive Expansion Calculation

To prevent fragmented detection in spread-out towns, calculate_adaptive_expansion() (lines 401–466) computes a dynamic expansion radius. When the algorithm detects low building density (low average buildings per cell or low occupancy rates), it automatically increases the expansion radius. This adaptive behavior ensures that sprawling suburban areas are recognized as single contiguous urban zones rather than disconnected clusters.

4. Cell Expansion

The expand_cells_adaptive() function (lines 468–488) grows all dense cells by the adaptive radius calculated in stage 3. Using 8-connected neighborhood expansion, it adds adjacent cells to the urban set, effectively "smoothing" the detection boundary and bridging small gaps between building groups.

5. Connected Component Detection

A flood-fill BFS algorithm (lines 345–382 within find_urban_clusters()) traverses the expanded cell set to identify connected components. Each contiguous group of touching cells forms a candidate urban cluster. This topological separation prevents merging distinct towns that happen to lie close together but are separated by non-urban space.

6. Cluster Filtering

The pipeline filters candidate clusters by total building count (lines 385–393). Only clusters containing at least min_buildings_for_cluster buildings survive this stage. This eliminates small villages or isolated commercial strips that should retain grass ground rather than urban stone.

7. Compact Lookup Construction

The compute_lookup() function (lines 236–267) converts surviving clusters into a HashSet<(cx, cz)> containing only the cell coordinates classified as urban. By storing cell indices rather than individual world blocks, the structure achieves approximately 4000× memory savings compared to a per-block boolean array.

8. O(1) Query Classification

Finally, is_urban() (lines 119–126) provides constant-time classification. It converts world coordinates (x, z) to cell indices and tests membership in the hash set. This O(1) performance allows the terrain generator to query millions of blocks during world generation without bottlenecking the pipeline.

Memory-Efficient Query Design

The UrbanGroundLookup struct prioritizes memory density over geometric precision. Rather than storing a polygonal hull or per-block bitmap, it maintains a sparse hash set of cell coordinates. This design choice reflects the specific constraints of Minecraft world generation, where:

• Lookup speed is critical during chunk generation
• Memory overhead must remain low for large cities (e.g., 10km² maps)
• False positives (stone in grassy areas) are visually acceptable within the 64-block cell resolution

The cell-based approach naturally handles both compact cities (high density, tight clusters) and spread-out towns (low density, large expansion radius) through the adaptive expansion logic described in stage 3.

Using UrbanGroundLookup in Your Code

The Arnis codebase exposes both high-level convenience functions and low-level configuration APIs for ground classification.

Basic Usage with compute_urban_ground_lookup

For most use cases, the compute_urban_ground_lookup function provides the simplest entry point:

use arnis::urban_ground::{compute_urban_ground_lookup, UrbanGroundLookup};
use arnis::coordinate_system::cartesian::XZBBox;

// Define a 1km × 1km world area
let world = XZBBox::rect_from_xz_lengths(1000.0, 1000.0).unwrap();

// Building centroids from OSM parsing (example data)
let buildings = vec![(120, 140), (130, 150), (125, 160), (800, 800)];

// Build the compact lookup
let lookup: UrbanGroundLookup = compute_urban_ground_lookup(buildings, &world);

// Query specific coordinates
assert!(lookup.is_urban(125, 150));  // Returns true (stone ground)
assert!(!lookup.is_urban(900, 900)); // Returns false (grass ground)

Advanced Configuration with UrbanGroundComputer

For custom terrain generation requiring fine-tuned detection parameters, use the lower-level UrbanGroundComputer API:

use arnis::urban_ground::{UrbanGroundComputer, UrbanGroundConfig};
use arnis::coordinate_system::cartesian::XZBBox;

let bbox = XZBBox::rect_from_xz_lengths(2000.0, 2000.0).unwrap();

// Configure detection sensitivity
let cfg = UrbanGroundConfig {
    cell_size: 32,                    // Finer 32-block cells (default is 64)
    min_buildings_per_cell: 2,        // Lower density threshold per cell
    min_buildings_for_cluster: 8,     // Minimum buildings per urban zone
    concavity: 3.0,
    expand_hull: false,
    cell_expansion: 3,                  // Expansion radius in cells
};

let mut computer = UrbanGroundComputer::new(bbox, cfg);
computer.add_building_centroids(my_building_iter);
let lookup = computer.compute_lookup();

// Generate terrain based on classification
if lookup.is_urban(x, z) {
    // Place smooth stone or cobblestone
} else {
    // Place grass or dirt
}

Summary

• UrbanGroundLookup classifies urban zones through an eight-stage pipeline implemented in src/urban_ground.rs, converting building centroids into a memory-efficient cell-based hash set.
• Density-based detection uses 64-block grid cells to identify high-building areas, with adaptive expansion logic that prevents fragmented detection in sprawling towns.
• Connected component analysis groups touching cells into clusters, filtering out small villages below the min_buildings_for_cluster threshold.
• O(1) query performance is achieved through coordinate-to-cell conversion and hash set membership tests, supporting real-time terrain generation during Minecraft world creation.
• Configurable parameters via UrbanGroundConfig allow tuning of cell size, density thresholds, and expansion radii for different map scales and urban morphologies.

Frequently Asked Questions

How does UrbanGroundLookup handle large rural areas with scattered buildings?

The min_buildings_per_cell and min_buildings_for_cluster thresholds act as filters during stages 2 and 6 of the pipeline. Scattered rural buildings typically fail to meet the density requirements for their grid cells, or they form clusters below the minimum building count. These areas are excluded from the HashSet, causing is_urban() to return false and ensuring grass ground generation.

What is the memory advantage of using cell-based coordinates instead of block-level storage?

Storing cell coordinates in a HashSet<(cx, cz)> reduces memory usage by approximately 4000× compared to a per-block boolean array. With a default cell_size of 64 blocks, each cell represents a 4096 m² area (64×64). The algorithm only stores coordinates for urban cells, making it feasible to process city-scale maps (10 km² or larger) without exhausting RAM during Minecraft world generation.

Can the detection sensitivity be adjusted for different types of urban development?

Yes, the UrbanGroundConfig struct exposes multiple tuning parameters. Increasing cell_expansion and reducing min_buildings_per_cell captures sprawling suburban development, while decreasing cell_size and increasing min_buildings_for_cluster targets dense metropolitan cores. The concavity parameter further controls the geometric complexity of cluster boundaries, allowing customization for medieval town layouts versus modern grid cities.

How does the adaptive expansion logic prevent over-segmentation of towns?

The calculate_adaptive_expansion() function (lines 401–466) computes a dynamic radius that inversely scales with building density. When the algorithm detects low average buildings per cell or low occupancy rates—indicating a spread-out town—it automatically increases the expansion radius. This bridges gaps between distant buildings during the expand_cells_adaptive() stage, ensuring the subsequent BFS groups them into a single connected cluster rather than fragmenting the town into multiple tiny urban zones.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}