如何在Prolog中探索未知迷宫？基于初始位置与行列数的路径求解

Great question—exploring an unknown maze in Prolog without a fixed endpoint plays perfectly to Prolog's recursive and backtracking strengths. Let's break this down into actionable steps with code you can adapt for your Wumpus/trap/wall/empty terrain checks.

Since the maze is unknown, we can't hardcode a map. Instead, we'll dynamically explore step-by-step:

1. Track our current position and path so far
2. "Sense" the terrain at each new position (simulate or hook into real maze data)
3. Use recursion to try moving in all valid directions, backtracking if we hit a dead end, hazard, or wall
4. Avoid looping by keeping a list of already visited positions

First, we need to represent key elements clearly:

• Positions: Use pos(X, Y) where X = column, Y = row (adjust coordinate system to match your maze)
• Discovered terrain: Store as dynamic Prolog facts (we'll add these as we explore)
• Path/visited: Use lists to track where we've been to avoid loops

We'll use dynamic facts to record what we find—this lets us query terrain instantly without re-sensing the same spot:

:- dynamic wumpus/1, pit/1, wall/1, empty/1.

Let's build the main recursive logic. We'll start with a helper to validate positions (make sure we don't walk outside the maze bounds):

% Check if a position is within the maze's width/height
valid_pos(pos(X, Y), MazeWidth, MazeHeight) :-
    X >= 0, X < MazeWidth,
    Y >= 0, Y < MazeHeight.

Next, a "sensing" predicate to detect terrain (replace this with your actual maze input logic—here we simulate random terrain for testing):

% Simulate sensing terrain at a position (replace with real detection)
sense_terrain(Pos) :-
    random(0, 10, Rand),
    (Rand =< 1 -> assert(wumpus(Pos))   % 10% chance Wumpus
     ; Rand =< 3 -> assert(pit(Pos))    % 20% chance pit
     ; Rand =< 4 -> assert(wall(Pos))   % 10% chance wall
     ; assert(empty(Pos))).             % 60% chance empty

Now the recursive exploration core. We'll use a main entry point, then handle two cases: when we can't explore further (termination), and when we can keep moving:

% Main entry: Start exploring from the initial position
start_explore(StartPos, MazeWidth, MazeHeight) :-
    explore(StartPos, [], [], MazeWidth, MazeHeight).

% Termination condition: No valid unvisited adjacent positions left
explore(CurrentPos, Visited, Path, MazeWidth, MazeHeight) :-
    % Find all reachable, unvisited, safe adjacent positions
    findall(NextPos, (
        adjacent(CurrentPos, NextPos),
        valid_pos(NextPos, MazeWidth, MazeHeight),
        \+ member(NextPos, Visited),
        \+ wall(NextPos),
        \+ wumpus(NextPos),
        \+ pit(NextPos)
    ), []),
    % Output results when exploration finishes
    writeln('=== Exploration Complete ==='),
    writeln('Final Path (from start to end): '), reverse(Path, ReversedPath), writeln(ReversedPath),
    writeln('\nDiscovered Terrain:'),
    findall(W, wumpus(W), Wumpuses), writeln('Wumpus Locations: '), writeln(Wumpuses),
    findall(P, pit(P), Pits), writeln('Trap Locations: '), writeln(Pits),
    findall(Wa, wall(Wa), Walls), writeln('Wall Locations: '), writeln(Walls),
    findall(E, empty(E), Empties), writeln('Safe Empty Spaces: '), writeln(Empties).

% Recursive step: Explore current position and adjacent spots
explore(CurrentPos, Visited, Path, MazeWidth, MazeHeight) :-
    % Only proceed if we haven't visited this position yet
    \+ member(CurrentPos, Visited),
    % Sense the terrain at the current spot
    sense_terrain(CurrentPos),
    (empty(CurrentPos) ->
        % If it's safe, add to our path and visited list
        NewVisited = [CurrentPos | Visited],
        NewPath = [CurrentPos | Path],
        % Try all four adjacent directions (backtracking handles dead ends)
        adjacent(CurrentPos, NextPos),
        valid_pos(NextPos, MazeWidth, MazeHeight),
        explore(NextPos, NewVisited, NewPath, MazeWidth, MazeHeight)
    ;
        % If it's a hazard/wall, mark as visited and backtrack
        NewVisited = [CurrentPos | Visited],
        explore(CurrentPos, NewVisited, Path, MazeWidth, MazeHeight)
    ).

% Define adjacent positions (up, down, right, left)
adjacent(pos(X, Y), pos(X, Y+1)) :- !. % Up
adjacent(pos(X, Y), pos(X, Y-1)) :- !. % Down
adjacent(pos(X, Y), pos(X+1, Y)) :- !. % Right
adjacent(pos(X, Y), pos(X-1, Y)).     % Left

• Backtracking: Prolog's built-in backtracking automatically handles "dead ends"—if one direction leads to a hazard or wall, it'll backtrack to the last safe spot and try another direction.
• Avoiding Loops: The Visited list ensures we never re-explore the same position, preventing infinite loops.
• Customization: Replace the sense_terrain/1 predicate with your actual maze input logic (e.g., reading from a file, or integrating with a maze API).
• Path Format: The path is stored in reverse order (from current position back to start), so we use reverse/2 to print it from start to finish in the termination step.

To run the code, call the main entry point with your starting position and maze dimensions. For example, a 5x5 maze starting at pos(0,0):

start_explore(pos(0,0), 5, 5).

You'll get a full report of the path taken and all terrain discovered during exploration.

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