如何高效查找网格中各瓦片的相邻瓦片？A*算法性能优化求助

Oh yeah, that double nested loop is definitely the problem here—O(n²) time complexity gets brutal fast when you’re dealing with thousands of tiles. Let’s break down how to fix this and get your neighbor generation down to seconds (or even milliseconds) instead of minutes.

First: If your tiles are in a regular grid (square/hex aligned, fixed size) #

This is the easiest case to optimize. Instead of checking every tile against every other tile, you can directly calculate which tiles should be neighbors using their coordinates.

First, build a map that lets you look up tiles by their (x,y) position. Then for each tile, check the adjacent coordinate positions (up/down/left/right, or diagonals if you allow 8-way movement) and add any existing tiles as neighbors.

Here’s how that would look in code:

// Step 1: Create a map to look up tiles by their coordinates
Map<String, PathTile> tilePositionMap = new HashMap<>();
for (PathTile tile : pathTiles) {
    // Use a unique key for each (x,y) pair—adjust if your coordinates are floating-point
    String coordinateKey = tile.getX() + "," + tile.getY();
    tilePositionMap.put(coordinateKey, tile);
}

// Step 2: Generate neighbors efficiently
private void generatePathTileNeighbors() {
    // Define direction offsets for 4-way movement (add diagonals for 8-way)
    int[][] adjacentOffsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    for (PathTile currentTile : pathTiles) {
        int currentX = currentTile.getX();
        int currentY = currentTile.getY();
        
        for (int[] offset : adjacentOffsets) {
            int neighborX = currentX + offset[0];
            int neighborY = currentY + offset[1];
            String neighborKey = neighborX + "," + neighborY;
            
            PathTile neighborTile = tilePositionMap.get(neighborKey);
            if (neighborTile != null) {
                currentTile.addNeighbor(neighborTile);
                // Optional: If neighbors are bidirectional, add currentTile to neighborTile's list here too
                // neighborTile.addNeighbor(currentTile);
            }
        }
    }
}

This runs in O(n) time—each tile is processed once, and we only check a fixed number of adjacent positions instead of every other tile. For 3000 tiles, that’s 12,000 checks instead of 9,000,000—huge difference.

Second: If your tiles are irregular shapes/sizes #

If your tiles don’t fit a strict grid, you need a way to avoid checking every tile. The solution here is spatial partitioning: split your game world into larger "cells" and only check tiles that are in the same cell or adjacent cells as the current tile.

Here’s a simple implementation using a grid-based spatial partition:

// First, set up the spatial grid (adjust cellSize based on your average tile size)
private int cellSize = 200; // Pick a size that's roughly 2x your largest tile's width/height
Map<String, List<PathTile>> spatialPartition = new HashMap<>();

// Populate the spatial grid
private void initSpatialPartition() {
    for (PathTile tile : pathTiles) {
        // Calculate which cell the tile belongs to (use center or top-left coordinate)
        int cellX = (int) (tile.getCenterX() / cellSize);
        int cellY = (int) (tile.getCenterY() / cellSize);
        String cellKey = cellX + "," + cellY;
        
        // Add the tile to the cell's list (create the list if it doesn't exist)
        spatialPartition.computeIfAbsent(cellKey, k -> new ArrayList<>()).add(tile);
    }
}

// Generate neighbors using the spatial partition
private void generatePathTileNeighbors() {
    // Check the current cell and all 8 surrounding cells
    int[][] cellOffsets = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};
    
    for (PathTile currentTile : pathTiles) {
        int cellX = (int) (currentTile.getCenterX() / cellSize);
        int cellY = (int) (currentTile.getCenterY() / cellSize);
        
        // Check each adjacent cell
        for (int[] offset : cellOffsets) {
            int neighborCellX = cellX + offset[0];
            int neighborCellY = cellY + offset[1];
            String cellKey = neighborCellX + "," + neighborCellY;
            
            List<PathTile> candidateTiles = spatialPartition.get(cellKey);
            if (candidateTiles == null) continue;
            
            // Only check tiles in this cell for intersection
            for (PathTile candidate : candidateTiles) {
                if (!currentTile.uniqueID.equals(candidate.uniqueID) && currentTile.intersect(candidate)) {
                    currentTile.addNeighbor(candidate);
                    // Optional: Add bidirectional neighbor
                    // candidate.addNeighbor(currentTile);
                }
            }
        }
    }
}

This reduces the number of intersection checks drastically. Instead of checking 3000 tiles per tile, you might only check 10-20 candidates per tile—way faster.

Bonus Tips: #

• Bidirectional Neighbors: If your graph is undirected (A is a neighbor of B, so B is a neighbor of A), you can add the neighbor relationship once instead of twice. For example, when you find that A intersects B, add B to A's list and A to B's list, then skip processing that pair later. This cuts your work in half.
• Floating-Point Coordinates: If your tiles use floating-point positions, avoid using strings as keys—create a Point class that overrides equals() and hashCode() properly, or use a library like java.awt.Point (if you’re using Java).
• Quadtree/Octree: For very large worlds or highly irregular tiles, consider using a quadtree (2D) or octree (3D) instead of a grid-based partition. They’re more efficient at handling sparse or unevenly distributed tiles.

With any of these methods, you’ll see a massive speedup—going from minutes to seconds (or less) even for thousands of tiles.

内容的提问来源于stack exchange，提问作者Casey Pak