如何在2D网格仿真环境中映射真实坐标并消除重叠

我正在基于真实世界坐标构建仿真环境模型，项目采用Java与JASON开发。目前遇到坐标重叠问题（结果图中红线标记的即为重叠坐标），这些重叠坐标对后续智能体仿真无意义，需将其移除。

结果图：

当前建模代码 #

package src.model;

import jason.environment.grid.GridWorldModel;
import jason.environment.grid.Location;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.logging.Logger;

public class AgentModel extends GridWorldModel {

    Logger log = Logger.getLogger(AgentModel.class.getName());

    public static final int WALL = 16;
    public static final int AGENTS = 2;

    private final Set<Location> wallLocation;
    private final Set<Location> processedLocations = new HashSet<>();
    private final int screenWidth;
    private final int screenHeight;
    private final double[][] coordinates;
    private final double[] minMax;
    private double lonScale;
    private double latScale;
    private double x0;
    private double y0;

    protected AgentModel(int gridWidth, int gridHeight, double[][] coordinates, double[] minMax) {
        super(gridWidth, gridHeight, WALL);
        this.coordinates = coordinates;
        this.screenWidth = gridWidth;
        this.screenHeight = gridHeight;
        this.minMax = minMax;
        this.wallLocation = new HashSet<>();

        initializeScaling();
        addWall();
        findEmptyCellsUntilWall();
    }

    private void initializeScaling() {
        double minLon = minMax[0];
        double maxLon = minMax[1];
        double minLat = minMax[2];
        double maxLat = minMax[3];

        double deltaLon = maxLon - minLon;
        double deltaLat = maxLat - minLat;

        if (deltaLon != 0.0 && deltaLat != 0.0) {
            lonScale = (screenWidth - 1) / deltaLon;
            latScale = (screenHeight - 1) / deltaLat;
            x0 = -minLon * lonScale;
            y0 = maxLat * latScale;

            if (lonScale > latScale) {
                lonScale = latScale;
                x0 = ((screenWidth - 1) - (minLon + maxLon) * lonScale) / 2.0;
            } else {
                latScale = lonScale;
                y0 = ((screenHeight - 1) + (minLat + maxLat) * latScale) / 2.0;
            }
        } else if (deltaLon != 0.0) {
            lonScale = (screenWidth - 1) / deltaLon;
            latScale = 0;
            x0 = -minLon * lonScale;
            y0 = (screenHeight - 1) / 2.0;
        } else if (deltaLat != 0.0) {
            lonScale = 0;
            latScale = (screenHeight - 1) / deltaLat;
            x0 = (screenWidth - 1) / 2.0;
            y0 = maxLat * latScale;
        } else {
            lonScale = 0;
            latScale = 0;
            x0 = (screenWidth - 1) / 2.0;
            y0 = (screenHeight - 1) / 2.0;
        }
    }

    private void addWall() {
        List<Location[]> coordinatePairs = new ArrayList<>();
        for (int i = 0; i < coordinates.length - 1; i++) {
            Location start = transformCoordinates(coordinates[i][0], coordinates[i][1]);
            Location end = transformCoordinates(coordinates[i + 1][0], coordinates[i + 1][1]);
            coordinatePairs.add(new Location[]{start, end});
        }
        addWallsBetweenCoordinates(coordinatePairs);
    }

    private void addWallsBetweenCoordinates(List<Location[]> coordinates) {
        for (Location[] pair : coordinates) {
            if (pair.length < 2) continue;

            Location start = pair[0];
            Location end = pair[1];

            if (processedLocations.contains(start) && processedLocations.contains(end)) {
                continue;
            }

            addWallInBetween(start, end);
            processedLocations.add(start);
            processedLocations.add(end);
        }
    }

    private Location transformCoordinates(double x, double y) {
        int gridX = (int) (x0 + x * lonScale);
        int gridY = (int) (y0 - y * latScale);
        return new Location(gridX, gridY);
    }

    private void addWallInBetween(Location start, Location end) {
        int dx = Math.abs(end.x - start.x);
        int dy = Math.abs(end.y - start.y);
        int sx = start.x < end.x ? 1 : -1;
        int sy = start.y < end.y ? 1 : -1;
        int err = dx - dy;

        int x = start.x;
        int y = start.y;

        while (true) {
            Location loc = new Location(x, y);
            if (!wallLocation.contains(loc)) {
                wallLocation.add(loc);
                if (x >= 0 && x < getWidth() && y >= 0 && y < getHeight()) {
                    add(WALL, loc);
                }
            }
            if (x == end.x && y == end.y) {
                break;
            }
            int e2 = 2 * err;
            if (e2 > -dy) {
                err -= dy;
                x += sx;
            }
            if (e2 < dx) {
                err += dx;
                y += sy;
            }
        }
    }

    public void findEmptyCellsUntilWall() {
        for (int x = 0; x < getWidth(); x++) {
            for (int y = 0; y < getHeight(); y++) {
                if (hasObject(WALL, x, y)) {
                    break;
                } else {
                    paintEmptyCells(x, y);
                }
            }
        }
    }

    private void paintEmptyCells(int startX, int startY) {
        for (int x = startX; x < getWidth(); x++) {
            if (hasObject(WALL, x, startY)) {
                break;
            } else {
                add(OBSTACLE, x, startY);
            }
        }

        for (int x = startX; x >= 0; x--) {
            if (hasObject(WALL, x, startY)) {
                break;
            } else {
                add(OBSTACLE, x, startY);
            }
        }

        for (int y = startY; y >= 0; y--) {
            if (hasObject(WALL, startX, y)) {
                break;
            } else {
                add(OBSTACLE, startX, y);
            }
        }

        for (int y = startY; y < getHeight(); y++) {
            if (hasObject(WALL, startX, y)) {
                break;
            } else {
                add(OBSTACLE, startX, y);
            }
        }
    }
}

问题分析与解决方法 #

坐标重叠的核心原因是真实世界坐标转换为网格坐标时的精度丢失，以及画线算法处理连续线段时重复标记同一网格位置。以下是针对性修复方案：

1. 前置去重：过滤转换后的重复端点 #

在生成墙的坐标对前，跳过与前一个位置重复的网格点，避免无效的重复线段：

private void addWall() {
    List<Location[]> coordinatePairs = new ArrayList<>();
    Location prevLoc = null;
    for (int i = 0; i < coordinates.length; i++) {
        Location currLoc = transformCoordinates(coordinates[i][0], coordinates[i][1]);
        // 跳过重复的连续点
        if (prevLoc != null && currLoc.equals(prevLoc)) {
            continue;
        }
        if (prevLoc != null) {
            coordinatePairs.add(new Location[]{prevLoc, currLoc});
        }
        prevLoc = currLoc;
    }
    addWallsBetweenCoordinates(coordinatePairs);
}

2. 优化障碍物填充的重复标记问题 #

添加集合记录已填充的障碍物位置，避免同一网格被多次标记：

// 在类中新增集合
private final Set<Location> obstacleLocations = new HashSet<>();

private void paintEmptyCells(int startX, int startY) {
    // 向右填充
    for (int x = startX; x < getWidth(); x++) {
        Location loc = new Location(x, startY);
        if (hasObject(WALL, loc)) break;
        if (!obstacleLocations.contains(loc)) {
            obstacleLocations.add(loc);
            add(OBSTACLE, loc);
        }
    }

    // 向左填充
    for (int x = startX - 1; x >= 0; x--) {
        Location loc = new Location(x, startY);
        if (hasObject(WALL, loc)) break;
        if (!obstacleLocations.contains(loc)) {
            obstacleLocations.add(loc);
            add(OBSTACLE, loc);
        }
    }

    // 向上填充
    for (int y = startY - 1; y >= 0; y--) {
        Location loc = new Location(startX, y);
        if (hasObject(WALL, loc)) break;
        if (!obstacleLocations.contains(loc)) {
            obstacleLocations.add(loc);
            add(OBSTACLE, loc);
        }
    }

    // 向下填充
    for (int y = startY + 1; y < getHeight(); y++) {
        Location loc = new Location(startX, y);
        if (hasObject(WALL, loc)) break;
        if (!obstacleLocations.contains(loc)) {
            obstacleLocations.add(loc);
            add(OBSTACLE, loc);
        }
    }
}

// 同时修改空单元格遍历方法，避免重复处理同一位置
public void findEmptyCellsUntilWall() {
    Set<Location> processedCells = new HashSet<>();
    for (int x = 0; x < getWidth(); x++) {
        for (int y = 0; y < getHeight(); y++) {
            Location loc = new Location(x, y);
            if (hasObject(WALL, loc)) break;
            if (!processedCells.contains(loc)) {
                processedCells.add(loc);
                paintEmptyCells(x, y);
            }
        }
    }
}

3. 可选：提升坐标转换精度 #

用Math.round替代强制类型转换，减少截断导致的不必要重叠，同时确保坐标在网格范围内：

private Location transformCoordinates(double x, double y) {
    int gridX = (int) Math.round(x0 + x * lonScale);
    int gridY = (int) Math.round(y0 - y * latScale);
    // 限制坐标在网格边界内
    gridX = Math.max(0, Math.min(gridX, getWidth() - 1));
    gridY = Math.max(0, Math.min(gridY, getHeight() - 1));
    return new Location(gridX, gridY);
}

内容的提问来源于stack exchange，提问作者Duda Validator