标准BFS二维迷宫寻路无法找到目标节点求助

Let's break down the issues in your BFS maze search code and fix them one by one—these are common pitfalls when implementing pathfinding algorithms:

1. Critical Hash Collision in Coordinate String Keys #

Right now, you’re concatenating x and y directly into a string (e.g., 12 + 3 = "123"). This creates identical keys for completely different coordinates like (12,3) and (1,23), tricking map_seen into marking valid, unvisited nodes as already visited. This is a major bug that will break pathfinding for mazes with double-digit coordinates.

Fix: Add a delimiter (like a comma) between x and y when creating the key:

String key = x + "," + y;

This ensures unique keys for every coordinate pair (e.g., "12,3" vs "1,23").

2. Wrong Timing for Marking Nodes as Visited #

You’re marking a node as visited after dequeuing it. This means multiple copies of the same node can be added to the queue by different paths before it’s marked, wasting memory and processing power, and potentially causing missed paths or infinite loops.

Fix: Mark nodes as visited right before enqueuing them. This guarantees each node is processed exactly once, following standard BFS best practices.

3. Static Variables Cause Cross-Search Contamination #

Your q (queue) and map_seen (visited tracker) are static class variables. If you call searchPath more than once, leftover data from the first search will corrupt the second—old queue entries will be processed, and old visited marks will block valid paths.

Fix: Move these variables inside the searchPath method to make them local. This ensures every search starts with a fresh queue and visited map.

4. Path is Stored in Reverse Order #

Your getPath method builds the path by traversing from the target node back to the start, so the final path list will have coordinates in target → start order, not the expected start → target order.

Fix: Reverse the path list at the end of the getPath method (don’t forget to import java.util.Collections):

Collections.reverse(path);

Fixed Full Code #

Here’s the revised code with all fixes applied, plus a helper method to eliminate repetitive direction-checking code:

import java.util.*;

public class MazeBFS {
    // Box class definition (included for completeness)
    static class Box {
        int x;
        int y;
        Box parent;

        public Box(int x, int y, Box parent) {
            this.x = x;
            this.y = y;
            this.parent = parent;
        }
    }

    public static void searchPath(int[][] maze, int x, int y, ArrayList<Integer> path) {
        // Local variables ensure fresh state for each search
        Queue<Box> q = new LinkedList<>();
        HashMap<String, Boolean> map_seen = new HashMap<>();

        q.add(new Box(x, y, null));
        map_seen.put(x + "," + y, true); // Mark start as visited immediately

        while (!q.isEmpty()) {
            Box p = q.poll();

            if (maze[p.y][p.x] == 9) {
                System.out.println("target found! ");
                getPath(p, maze, path);
                return;
            }

            // Use helper to handle all four directions cleanly
            enqueueNeighbor(maze, p.x + 1, p.y, p, q, map_seen);
            enqueueNeighbor(maze, p.x - 1, p.y, p, q, map_seen);
            enqueueNeighbor(maze, p.x, p.y + 1, p, q, map_seen);
            enqueueNeighbor(maze, p.x, p.y - 1, p, q, map_seen);
        }
        System.out.println("exited reached");
    }

    // Helper to reduce duplicate code for neighbor checks
    private static void enqueueNeighbor(int[][] maze, int x, int y, Box parent, Queue<Box> q, HashMap<String, Boolean> map_seen) {
        String key = x + "," + y;
        if (isFree(maze, x, y) && !map_seen.containsKey(key)) {
            q.add(new Box(x, y, parent));
            map_seen.put(key, true);
        }
    }

    public static boolean isFree(int[][] maze, int x, int y) {
        return (x >= 0 && x < maze[0].length) && (y >= 0 && y < maze.length) && (maze[y][x] == 0 || maze[y][x] == 9);
    }

    public static ArrayList<Integer> getPath(Box node, int[][] maze, ArrayList<Integer> path) {
        while (node != null) {
            path.add(node.x);
            path.add(node.y);
            maze[node.y][node.x] = 2;
            node = node.parent;
        }
        Collections.reverse(path); // Flip to start -> target order
        return path;
    }
}

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