网格式游戏城市生成器：现有实现方案的优化建议求助

Great question! Let's break down how to optimize your grid-based city generator for efficiency, simplicity, and future extensibility—all while keeping that clean, right-angle blocky layout you want.

1. Replace the "fill + scale + retroactively add roads" workflow entirely #

Your current approach wastes cycles on cell-level operations (shuffling every cell, filling rectangles, scaling the entire grid) that get exponentially slow for large maps. Instead, generate blocks and roads in a single pass by defining block boundaries first.

Here's a faster, simpler alternative:

• Start with your empty map grid.
• Lay out horizontal and vertical road lines with randomized spacing (e.g., horizontal roads every 3–8 rows, vertical every 4–7 columns) to split the map into rectangular blocks.
• Assign a random type (residential/industrial/commercial) to each enclosed rectangle and mark all its cells as that block type.
• The gaps between blocks are automatically your roads—no need to scan for differing IDs or scale grids later.

This cuts out the scaling step entirely and reduces your algorithm from O(n²) cell operations to O(n) road line + block assignments, which is far more efficient for large maps.

2. Use Recursive Subdivision for Natural Block Variety (No Cell Shuffling) #

If you want more organic block sizes than uniform grid spacing, try recursive rectangle subdivision:

• Start with the entire map as one big rectangle.
• Randomly choose to split it horizontally or vertically (weight the choice if you want more of one direction).
• Pick a split position that’s not too close to edges (enforce a minimum block size like 2x2 here to avoid tiny trapped blocks).
• Repeat the split on the resulting sub-rectangles until you’re happy with the average block size.
• Assign types to each final rectangle and mark roads along the split lines.

This method guarantees no 1x1 blocks (if you set a minimum size) and generates clean, blocky layouts without touching individual cells until the final assignment step. It’s also extremely easy to write pseudocode for!

3. Build Future Features Into the Core Workflow #

You mentioned wanting to remove 1x1 blocks and create non-square cities—let’s address these upfront to avoid adding complexity later:

• Eliminate 1x1 blocks: When splitting rectangles (via grid lines or recursive subdivision), enforce a minimum width/height (e.g., 2 cells). This means you never generate blocks that can get trapped by roads in the first place.
• Non-square cities: Instead of starting with a perfect square, define an irregular boundary first (e.g., a rectangle with random chunks cut from edges, or a shape made of connected rectangles). Run your block generation only within that boundary. Alternatively, generate a square city first, then randomly erase edge blocks/roads to make it look less uniform.

4. Quick Fixes for Your Existing Workflow (If You Want to Keep the Core Idea) #

If you prefer to stick close to your original method but boost efficiency:

• Skip the cell shuffle: Instead of shuffling all cells, randomly pick starting positions for blocks and expand outward until you hit an existing block or map edge. This avoids processing every cell.
• Replace scaling with pre-road padding: When generating each original rectangle, leave a 1-cell gap around it (instead of scaling later). This ensures roads sit between blocks without the O(n²) scaling step.
• Use spatial indexing: Track block boundaries in a list (e.g., [{x1, y1, x2, y2, type}, ...]) instead of checking every cell. This lets you quickly check if a new block overlaps existing ones without scanning cells.

Here’s a simple snippet to show how streamlined this approach can be:

function generateCity(width, height, minBlockSize):
    blocks = []
    stack = [ {x: 0, y: 0, w: width, h: height} ]
    
    while stack is not empty:
        rect = stack.pop()
        // Check if we can split this rectangle
        canSplitHorizontally = rect.h > minBlockSize * 2
        canSplitVertically = rect.w > minBlockSize * 2
        
        if not canSplitHorizontally and not canSplitVertically:
            // Assign type and add to blocks
            blocks.push({...rect, type: random(["residential", "industrial", "commercial"])})
            continue
        
        // Choose split direction
        if canSplitHorizontally and (not canSplitVertically or Math.random() > 0.5):
            // Split horizontally
            splitY = Math.floor(Math.random() * (rect.h - minBlockSize*2)) + minBlockSize
            stack.push({x: rect.x, y: rect.y, w: rect.w, h: splitY})
            stack.push({x: rect.x, y: rect.y + splitY, w: rect.w, h: rect.h - splitY})
        else:
            // Split vertically
            splitX = Math.floor(Math.random() * (rect.w - minBlockSize*2)) + minBlockSize
            stack.push({x: rect.x, y: rect.y, w: splitX, h: rect.h})
            stack.push({x: rect.x + splitX, y: rect.y, w: rect.w - splitX, h: rect.h})
    
    // Draw blocks and roads
    const grid = Array(height).fill().map(() => Array(width).fill("ROAD"))
    for (const block of blocks) {
        for (let y = block.y; y < block.y + block.h; y++) {
            for (let x = block.x; x < block.x + block.w; x++) {
                grid[y][x] = block.type
            }
        }
    }
    return grid

内容的提问来源于stack exchange，提问作者Joe Jankowiak