一、游戏背景与核心机制
“模拟城市”（SimCity）是城市规划类游戏的鼻祖。玩家作为市长，需要在有限的土地上合理规划住宅区、商业区、工业区，并提供道路、水电、警消等基础设施，使城市繁荣发展。游戏的核心乐趣在于观察简单规则如何涌现出复杂的城市演化行为。
本文用Java实现一个简化版的模拟城市算法原型，聚焦两个核心问题：
1. 城市演化：用元胞自动机（Cellular Automata）模拟区域随时间的自然发展
2. 区域规划：用贪心算法为新设施寻找最优建设位置
二、核心算法原理
2.1 元胞自动机模型
将城市地图划分为网格，每个格子具有一个状态（空地、住宅、商业、工业、道路等）。每个时间步，格子的新状态仅由其当前状态和邻居状态决定。经典规则包括：
– 住宅需要临近道路和就业（商业/工业）
– 商业需要消费者（住宅）和货运（工业）
– 工业需要劳动力（住宅）和道路连接
– 基础设施（警消、医院）提升周边区域价值
2.2 区域价值评估
每个格子的”土地价值”由多因素加权决定：
– 到道路的距离（越近越好）
– 到水源/电厂的距离
– 到警消/医院的距离
– 周边同类/互补区域密度
– 污染与噪音（工业区负面影响）
2.3 贪心规划策略
当需要建设新设施时，贪心算法评估每个空地的综合价值，选择价值最高的位置。综合价值 = 设施效用（覆盖更多需求区域） – 建设成本。
三、Java实现
3.1 城市网格与基础设施建模
import java.util.*;
/**
* 模拟城市简化版：元胞自动机演化 + 贪心区域规划
*/
public class SimCitySimulator {
// 地块类型
public static final int EMPTY = 0;
public static final int RESIDENTIAL = 1; // 住宅
public static final int COMMERCIAL = 2; // 商业
public static final int INDUSTRIAL = 3; // 工业
public static final int ROAD = 4; // 道路
public static final int POWER_PLANT = 5; // 电厂
public static final int WATER_TOWER = 6; // 水塔
public static final int POLICE = 7; // 警察局
public static final int FIRE_STATION = 8; // 消防局
public static final int HOSPITAL = 9; // 医院
public static final int PARK = 10; // 公园
public static final String[] TYPE_NAMES = {
"空地", "住宅", "商业", "工业", "道路", "电厂", "水塔", "警局", "消防", "医院", "公园"
};
private int width, height;
private int[][] grid; // 地块类型
private int[][] density; // 建筑密度 0-5
private double[][] landValue; // 土地价值 0.0-1.0
private double[][] pollution; // 污染指数 0.0-1.0
private int[][] powerMap; // 电力覆盖 0/1
private int[][] waterMap; // 供水覆盖 0/1
// 城市统计
public int population = 0;
public int funds = 20000; // 初始资金
public SimCitySimulator(int width, int height) {
this.width = width;
this.height = height;
this.grid = new int[height][width];
this.density = new int[height][width];
this.landValue = new double[height][width];
this.pollution = new double[height][width];
this.powerMap = new int[height][width];
this.waterMap = new int[height][width];
}
/**
* 初始化城市：中心道路 + 少量基础设施
*/
public void initCity() {
// 十字主干道
int cx = width / 2, cy = height / 2;
for (int i = 0; i < width; i++) grid[cy][i] = ROAD;
for (int i = 0; i < height; i++) grid[i][cx] = ROAD;
// 基础公共设施
grid[cy - 2][cx - 2] = POWER_PLANT;
grid[cy - 2][cx + 2] = WATER_TOWER;
grid[cy + 2][cx - 2] = POLICE;
grid[cy + 2][cx + 2] = FIRE_STATION;
updateInfrastructure();
}
/**
* 更新基础设施覆盖图（BFS从设施向外扩散）
*/
public void updateInfrastructure() {
// 电力覆盖：从电厂BFS，沿道路传播
powerMap = computeCoverage(POWER_PLANT, 8);
// 供水覆盖：从水塔BFS，沿道路传播
waterMap = computeCoverage(WATER_TOWER, 8);
}
private int[][] computeCoverage(int facilityType, int maxDist) {
int[][] coverage = new int[height][width];
Queue<int[]> queue = new LinkedList<>();
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (grid[y][x] == facilityType) {
queue.offer(new int[]{x, y, 0});
coverage[y][x] = 1;
}
}
}
int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0], y = cur[1], dist = cur[2];
if (dist >= maxDist) continue;
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || nx >= width || ny < 0 || ny >= height) continue;
if (coverage[ny][nx] == 1) continue;
// 基础设施沿道路和空地传播
if (grid[ny][nx] == ROAD || grid[ny][nx] == EMPTY ||
grid[ny][nx] == RESIDENTIAL || grid[ny][nx] == COMMERCIAL ||
grid[ny][nx] == INDUSTRIAL) {
coverage[ny][nx] = 1;
queue.offer(new int[]{nx, ny, dist + 1});
}
}
}
return coverage;
}
3.2 元胞自动机演化引擎
/**
* 元胞自动机演化一步：根据邻居状态更新每个格子
*/
public void evolveStep() {
int[][] newGrid = new int[height][width];
int[][] newDensity = new int[height][width];
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
newGrid[y][x] = grid[y][x];
newDensity[y][x] = density[y][x];
if (grid[y][x] == EMPTY) {
// 空地可能自发发展为新区
double developChance = computeDevelopmentChance(x, y);
if (Math.random() < developChance) {
int newType = chooseZoneType(x, y);
newGrid[y][x] = newType;
newDensity[y][x] = 1;
}
} else if (grid[y][x] == RESIDENTIAL || grid[y][x] == COMMERCIAL || grid[y][x] == INDUSTRIAL) {
// 已有区域可能升级或降级
double growChance = computeGrowthChance(x, y);
double decayChance = computeDecayChance(x, y);
if (Math.random() < growChance && density[y][x] < 5) {
newDensity[y][x] = density[y][x] + 1;
} else if (Math.random() < decayChance && density[y][x] > 0) {
newDensity[y][x] = density[y][x] - 1;
if (newDensity[y][x] == 0) newGrid[y][x] = EMPTY; // 废弃
}
}
}
}
grid = newGrid;
density = newDensity;
updateLandValue();
updatePollution();
updatePopulation();
}
/**
* 计算空地发展为建筑的概率
*/
private double computeDevelopmentChance(int x, int y) {
if (powerMap[y][x] == 0 || waterMap[y][x] == 0) return 0.0; // 无水无电不发展
if (!hasRoadNeighbor(x, y)) return 0.0; // 无路不通达
double baseChance = 0.05;
double valueBonus = landValue[y][x] * 0.1;
double pollutePenalty = pollution[y][x] * 0.15;
return Math.min(baseChance + valueBonus - pollutePenalty, 0.3);
}
/**
* 根据周边需求选择新区类型（住宅/商业/工业）
*/
private int chooseZoneType(int x, int y) {
int[] counts = countNeighborTypes(x, y, 3);
int res = counts[RESIDENTIAL], com = counts[COMMERCIAL], ind = counts[INDUSTRIAL];
// 需求平衡逻辑：住宅需要就业岗位，商业需要消费者，工业需要劳动力
double needRes = Math.max(0, ind + com - res); // 就业岗位多于住房则缺住宅
double needCom = Math.max(0, res - com); // 消费者多于商店则缺商业
double needInd = Math.max(0, res - ind); // 劳动力多于工厂则缺工业
double total = needRes + needCom + needInd + 1;
double r = Math.random() * total;
if (r < needRes) return RESIDENTIAL;
if (r < needRes + needCom) return COMMERCIAL;
return INDUSTRIAL;
}
/**
* 计算区域升级概率
*/
private double computeGrowthChance(int x, int y) {
double base = 0.1;
double valueFactor = landValue[y][x] * 0.2;
double infraBonus = (hasServiceNeighbor(x, y) ? 0.1 : 0); // 警消医院公园加成
return Math.min(base + valueFactor + infraBonus, 0.5);
}
/**
* 计算区域衰败概率
*/
private double computeDecayChance(int x, int y) {
double base = 0.02;
double polluteFactor = pollution[y][x] * 0.3;
double crimeFactor = (landValue[y][x] < 0.2) ? 0.1 : 0; // 低地价高犯罪
double noPower = (powerMap[y][x] == 0) ? 0.2 : 0;
double noWater = (waterMap[y][x] == 0) ? 0.2 : 0;
return Math.min(base + polluteFactor + crimeFactor + noPower + noWater, 0.8);
}
/**
* 统计某类型在半径r内的邻居数量
*/
private int[] countNeighborTypes(int x, int y, int radius) {
int[] counts = new int[11];
for (int dy = -radius; dy <= radius; dy++) {
for (int dx = -radius; dx <= radius; dx++) {
int nx = x + dx, ny = y + dy;
if (nx < 0 || nx >= width || ny < 0 || ny >= height) continue;
if (grid[ny][nx] >= 0 && grid[ny][nx] < counts.length) {
counts[grid[ny][nx]]++;
}
}
}
return counts;
}
private boolean hasRoadNeighbor(int x, int y) {
int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < width && ny >= 0 && ny < height && grid[ny][nx] == ROAD) return true;
}
return false;
}
private boolean hasServiceNeighbor(int x, int y) {
for (int dy = -2; dy <= 2; dy++) {
for (int dx = -2; dx <= 2; dx++) {
int nx = x + dx, ny = y + dy;
if (nx < 0 || nx >= width || ny < 0 || ny >= height) continue;
int t = grid[ny][nx];
if (t == POLICE || t == FIRE_STATION || t == HOSPITAL || t == PARK) return true;
}
}
return false;
}
3.3 土地价值与污染系统
/**
* 更新全图土地价值（基于基础设施和区域搭配）
*/
public void updateLandValue() {
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (grid[y][x] == ROAD || grid[y][x] == POWER_PLANT || grid[y][x] == WATER_TOWER) {
landValue[y][x] = 0;
continue;
}
double value = 0.3; // 基础价值
// 道路 proximity
int roadDist = findNearestTypeDistance(x, y, ROAD);
value += Math.max(0, (5 - roadDist) * 0.05);
// 公园提升（高价值）
int parkDist = findNearestTypeDistance(x, y, PARK);
if (parkDist <= 3) value += (4 - parkDist) * 0.08;
// 警消提升安全
int policeDist = findNearestTypeDistance(x, y, POLICE);
int fireDist = findNearestTypeDistance(x, y, FIRE_STATION);
value += Math.max(0, (4 - policeDist) * 0.03);
value += Math.max(0, (4 - fireDist) * 0.03);
// 医院
int hospDist = findNearestTypeDistance(x, y, HOSPITAL);
value += Math.max(0, (5 - hospDist) * 0.04);
// 远离工业区
int indDist = findNearestTypeDistance(x, y, INDUSTRIAL);
value -= Math.max(0, (6 - indDist) * 0.05);
// 互补区域搭配加成
if (grid[y][x] == RESIDENTIAL) {
int comDist = findNearestTypeDistance(x, y, COMMERCIAL);
value += Math.max(0, (4 - comDist) * 0.03);
}
landValue[y][x] = Math.max(0.05, Math.min(1.0, value));
}
}
}
/**
* 更新污染分布（从工业区向外扩散，随距离衰减）
*/
public void updatePollution() {
// 重置
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) pollution[y][x] = 0;
}
// 工业区和电厂产生污染
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (grid[y][x] == INDUSTRIAL) {
spreadEffect(x, y, pollution, 0.4, 4); // 工业污染半径4
} else if (grid[y][x] == POWER_PLANT) {
spreadEffect(x, y, pollution, 0.3, 5); // 电厂污染半径5
}
}
}
// 公园降低污染
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (grid[y][x] == PARK) {
spreadEffect(x, y, pollution, -0.15, 3); // 公园净化半径3
}
}
}
// 钳制到0-1
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
pollution[y][x] = Math.max(0, Math.min(1, pollution[y][x]));
}
}
}
/**
* 从源点向外扩散效果（污染或正面效果）
*/
private void spreadEffect(int sx, int sy, double[][] field, double peak, int radius) {
for (int dy = -radius; dy <= radius; dy++) {
for (int dx = -radius; dx <= radius; dx++) {
int nx = sx + dx, ny = sy + dy;
if (nx < 0 || nx >= width || ny < 0 || ny >= height) continue;
double dist = Math.sqrt(dx*dx + dy*dy);
if (dist > radius) continue;
double effect = peak * (1 - dist / radius);
field[ny][nx] += effect;
}
}
}
/**
* 查找最近某类型地块的曼哈顿距离
*/
private int findNearestTypeDistance(int x, int y, int type) {
int best = Integer.MAX_VALUE;
for (int dy = 0; dy < height; dy++) {
for (int dx = 0; dx < width; dx++) {
if (grid[dy][dx] == type) {
int dist = Math.abs(dx - x) + Math.abs(dy - y);
best = Math.min(best, dist);
}
}
}
return best == Integer.MAX_VALUE ? 99 : best;
}
private void updatePopulation() {
population = 0;
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (grid[y][x] == RESIDENTIAL) {
population += density[y][x] * 50; // 每级密度50人
}
}
}
}
3.4 贪心区域规划算法
/**
* 贪心算法：为指定设施寻找最优建设位置
* @param facilityType 设施类型
* @return 推荐坐标 [x, y]，null表示无合适位置
*/
public int[] findOptimalLocation(int facilityType) {
double bestScore = Double.NEGATIVE_INFINITY;
int[] bestPos = null;
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (grid[y][x] != EMPTY) continue; // 只能建在空地上
double score = evaluateLocation(x, y, facilityType);
if (score > bestScore) {
bestScore = score;
bestPos = new int[]{x, y};
}
}
}
return bestPos;
}
/**
* 评估某位置建设特定设施的得分
*/
private double evaluateLocation(int x, int y, int facilityType) {
double score = 0;
switch (facilityType) {
case ROAD:
// 道路：连接尽量多的非道路区域，填补交通盲区
score = countNonRoadNeighbors(x, y) * 10;
score -= findNearestTypeDistance(x, y, ROAD) * 2; // 不要靠太近
break;
case PARK:
// 公园：服务尽量多住宅，远离工业区
score = countTypeInRadius(x, y, RESIDENTIAL, 3) * 15;
score -= countTypeInRadius(x, y, INDUSTRIAL, 4) * 10;
score += landValue[y][x] * 20;
break;
case POLICE:
case FIRE_STATION:
// 警消：覆盖高犯罪/高风险区域（低地价、高密度住宅/工业）
score = countTypeInRadius(x, y, RESIDENTIAL, 4) * 8;
score += countTypeInRadius(x, y, COMMERCIAL, 4) * 6;
score += countTypeInRadius(x, y, INDUSTRIAL, 4) * 5;
// 避免与其他同类设施重叠覆盖
int nearestSame = findNearestTypeDistance(x, y, facilityType);
if (nearestSame < 5) score -= (5 - nearestSame) * 20;
break;
case HOSPITAL:
// 医院：服务高人口密度区域
score = countTypeInRadius(x, y, RESIDENTIAL, 5) * 10;
score += countTypeInRadius(x, y, COMMERCIAL, 5) * 5;
score += landValue[y][x] * 15;
break;
case POWER_PLANT:
case WATER_TOWER:
// 基础设施：中心位置，方便向外辐射
int cx = width / 2, cy = height / 2;
score = 100 - (Math.abs(x - cx) + Math.abs(y - cy));
score -= countTypeInRadius(x, y, RESIDENTIAL, 3) * 5; // 远离住宅区
break;
}
// 通用惩罚
if (!hasRoadNeighbor(x, y)) score -= 50; // 必须临路
return score;
}
private int countNonRoadNeighbors(int x, int y) {
int count = 0;
int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < width && ny >= 0 && ny < height && grid[ny][nx] != ROAD) count++;
}
return count;
}
private int countTypeInRadius(int x, int y, int type, int radius) {
int count = 0;
for (int dy = -radius; dy <= radius; dy++) {
for (int dx = -radius; dx <= radius; dx++) {
int nx = x + dx, ny = y + dy;
if (nx < 0 || nx >= width || ny < 0 || ny >= height) continue;
if (grid[ny][nx] == type) count++;
}
}
return count;
}
/**
* 执行贪心规划：按优先级建设缺失设施
*/
public void greedyPlan() {
int[][] priorities = {
{ROAD, 3}, {RESIDENTIAL, 5}, {COMMERCIAL, 3}, {INDUSTRIAL, 2},
{PARK, 2}, {POLICE, 1}, {FIRE_STATION, 1}
};
for (int[] plan : priorities) {
int type = plan[0];
int count = plan[1];
for (int i = 0; i < count; i++) {
int[] pos = findOptimalLocation(type);
if (pos != null) {
grid[pos[1]][pos[0]] = type;
if (type == RESIDENTIAL || type == COMMERCIAL || type == INDUSTRIAL) {
density[pos[1]][pos[0]] = 1;
}
System.out.println("建设 " + TYPE_NAMES[type] + " 于 (" + pos[0] + "," + pos[1] + ")");
}
}
}
updateInfrastructure();
updateLandValue();
updatePollution();
}
3.5 可视化与主程序
/**
* ASCII可视化当前城市状态
*/
public void printCity() {
char[] symbols = {'.', 'R', 'C', 'I', '=', 'P', 'W', '*', 'F', 'H', 'T'};
System.out.println("\n=== 城市地图 (人口: " + population + ") ===");
System.out.print(" ");
for (int x = 0; x < width; x++) System.out.print(x % 10);
System.out.println();
for (int y = 0; y < height; y++) {
System.out.print(y % 10 + " ");
for (int x = 0; x < width; x++) {
char c = symbols[grid[y][x]];
if (density[y][x] > 0 && grid[y][x] >= RESIDENTIAL && grid[y][x] <= INDUSTRIAL) {
c = (char)('0' + density[y][x]); // 密度数字覆盖
}
System.out.print(c);
}
System.out.println();
}
// 打印统计
int[] counts = new int[11];
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) counts[grid[y][x]]++;
}
System.out.println("统计: 住宅=" + counts[RESIDENTIAL] + " 商业=" + counts[COMMERCIAL] +
" 工业=" + counts[INDUSTRIAL] + " 道路=" + counts[ROAD]);
}
public static void main(String[] args) {
SimCitySimulator city = new SimCitySimulator(20, 20);
city.initCity();
System.out.println("=== 模拟城市演化与规划 ===\n");
System.out.println("【初始状态】");
city.printCity();
// 阶段1：贪心规划基础设施
System.out.println("\n【阶段1：贪心规划】");
city.greedyPlan();
city.printCity();
// 阶段2：元胞自动机演化
System.out.println("\n【阶段2：元胞自动机演化】");
for (int step = 1; step <= 10; step++) {
city.evolveStep();
if (step % 3 == 0) {
System.out.println("\n--- 第 " + step + " 步 ---");
city.printCity();
}
}
// 阶段3：动态规划响应
System.out.println("\n【阶段3：响应式规划（新增公园）】");
int[] parkPos = city.findOptimalLocation(PARK);
if (parkPos != null) {
city.grid[parkPos[1]][parkPos[0]] = PARK;
System.out.println("新增公园于 (" + parkPos[0] + "," + parkPos[1] + ")");
}
city.updatePollution();
city.updateLandValue();
city.printCity();
System.out.println("\n最终人口: " + city.population);
}
}
四、复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 元胞自动机演化 | O(W·H) | O(W·H) | 遍历每个格子，检查邻居 |
| 土地价值更新 | O(W·H·T) | O(W·H) | T为设施类型数 |
| 污染扩散 | O(W·H·R²) | O(W·H) | R为最大扩散半径 |
| 贪心选址 | O(W·H·R²) | O(1) | 评估每个空地 |
| 基础设施覆盖 | O(W·H) | O(W·H) | BFS传播 |
对于20×20的小型城市，单步演化在毫秒级完成；扩展到100×100时，通过空间索引（如R树）可将复杂度降至O(N log N)，N为设施数量。
五、总结
本文用Java实现了一个简化版模拟城市的核心算法引擎，涵盖元胞自动机演化与贪心区域规划两大模块：
- 元胞自动机：通过局部邻居规则模拟城市自然发展，包含区域升级、衰败和自发建设
- 多因素评估：综合考虑道路通达、基础设施覆盖、环境污染和区域互补性计算土地价值
- 贪心规划器：针对不同设施类型设计专用评分函数，自动推荐最优建设位置
- 系统耦合：基础设施覆盖、污染扩散和土地价值三者相互影响，形成闭环反馈
读者可在此基础上加入交通流模拟（A*寻路评估拥堵）、供需平衡市场模型和玩家预算约束，构建更完整的模拟城市游戏体验。元胞自动机规则也可尝试用遗传算法自动优化，寻找使城市最繁荣的规则参数组合。
