Java实现A*寻路算法遇性能问题求助：复杂路径卡顿

Hey there! Let's break down why your A* implementation is getting stuck with huge closedSet sizes and slow performance, plus fix that wall-checking logic you're unsure about.

First: The Wall Check Logic Issue #

You mentioned that wall results can vary depending on which direction you enter a tile—and that's absolutely contributing to your problems. Let's look at your wall function:

boolean wall(int x, int y, int x_, int y_){
 Tile tileS = getTile(x, y);
 Tile tileCurr = getTile(x_, y_);
 if(abs(tileS.altitude - tileCurr.altitude) > 1 || tileS.altitude < 1){
 return true;
 }else{
 return false;
 }
}

The problem here is that you're checking if the starting tile's altitude is <1, not the target tile. This creates one-way passability:

• If tile A has altitude 0, you can't move from A to any adjacent tile, but you can move into A from adjacent tiles (as long as altitude difference is ≤1).

A* works best with consistent, bidirectional movement rules. Fix this by checking the target tile's validity and the mutual altitude difference:

boolean wall(int fromX, int fromY, int toX, int toY){
 Tile fromTile = getTile(fromX, fromY);
 Tile toTile = getTile(toX, toY);
 // Ensure target tile is walkable (altitude ≥1) and altitude difference is ≤1
 if(toTile.altitude < 1 || abs(fromTile.altitude - toTile.altitude) > 1){
 return true;
 }
 return false;
}

This way, movement between two tiles is allowed or blocked in both directions consistently, preventing the algorithm from wasting time exploring one-way dead ends.

The Big Culprit: Duplicate Nodes in closedSet/openSet #

Your closedSet is blowing past 70000 nodes on a 54x46 grid (only 2484 total tiles!) because your Spot class doesn't override equals() and hashCode(). Right now, closedSet.contains(s) and openSet.contains(s) check if the object reference matches, not if the coordinates are the same. So you're adding hundreds of duplicate Spot objects for the same grid tile to your sets.

Fix 1: Override equals() and hashCode() in Spot #

Add these methods to your Spot class to compare tiles by their coordinates:

class Spot{
 int x, y;
 int f, g, h = 0;
 Spot parent;
 Spot(int x_, int y_){
 x = x_;
 y = y_;
 }

 @Override
 public boolean equals(Object o) {
 if (this == o) return true;
 if (o == null || getClass() != o.getClass()) return false;
 Spot spot = (Spot) o;
 return x == spot.x && y == spot.y;
 }

 @Override
 public int hashCode() {
 return Objects.hash(x, y);
 }
}

Now, contains() will correctly identify if a tile's already been processed or is in the open set.

Fix 2: Replace closedSet with a HashSet #

ArrayList.contains() is O(n)—slow when your set gets big. Swap it for a HashSet<Spot> for O(1) lookups:

HashSet<Spot> closedSet = new HashSet<>();
// Then add to it like:
closedSet.add(current);
// And check with:
if (!closedSet.contains(s) && !wall(s.x, s.y, current.x, current.y)) {

Fix 3: Track openSet nodes with a HashSet #

PriorityQueue.contains() is also O(n). Add a separate HashSet<Spot> openSetTracker to track which nodes are already in the priority queue:

Queue<Spot> openSet = new PriorityQueue<>(fComparator);
HashSet<Spot> openSetTracker = new HashSet<>();
// When adding to openSet:
if (!openSetTracker.contains(s)) {
 openSet.add(s);
 openSetTracker.add(s);
}
// And when checking if s is in openSet:
if(tempG < s.g || !openSetTracker.contains(s)){

This avoids redundant checks and duplicate entries in the priority queue.

Other Small Optimizations #

• Precompute Successors: Instead of parsing the JSON array every time you generate successors, precompute a list of (x,y) delta pairs once at startup. Parsing JSON in the pathfinding loop adds unnecessary overhead.
• Initialize g Properly: Right now, Spot.g starts at 0. For the start node, set start.g = 0, but for other nodes, initialize g to a very large value (like Integer.MAX_VALUE) so the first time you calculate tempG, it will always be smaller than s.g. This avoids relying on the !openSet.contains(s) check to update the g value.
• Avoid Clearing Successors Every Loop: Instead of creating a new ArrayList<Spot> and clearing it each iteration, reuse a single list to reduce object creation overhead.

Final Notes #

Once you fix the Spot equality checks and wall logic, your closedSet size should drop to a reasonable number (far less than 2484 for most paths). The performance hit from duplicate nodes and slow lookups is almost certainly the main cause of your卡顿.

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