Geek Answers Handbook

Java solution to the maze with recursion problem

I have a task in which I have to show the path of the labyrinth from entrance to exit, and I got it to work to a certain extent, but when the labyrinth becomes more complicated with dead ends and the program goes into infinite recursion. If you could give me any help to point me in the right direction, that would be very appreciated.

The current Mu theory can be found in the Room class.

Here is the class of the room where links are stored to each room connecting the maze, sort of like a linked list connected in 6 directions, north, south, east, west, up and down.

import java.util.ArrayList;

public class OurRoom
{
    private OurRoom exits[];
    private String name;
    private static ArrayList<OurRoom> list;

    public OurRoom()
    {
        this(null);
    }

    public OurRoom(String name)
    {
        this.name = name;
        this.list = new ArrayList<OurRoom>();
        exits = new OurRoom[Direction.values().length];
        for(OurRoom exit : exits)
        {
            exit = null;
        }
    }       


    public void connectTo(OurRoom theOtherRoom, Direction direction)
    {
        exits[direction.ordinal()] = theOtherRoom;
        theOtherRoom.exits[direction.getOpposite().ordinal()] = this;
    }

    public OurRoom getExit(Direction direction)
    {
        return exits[direction.ordinal()];
    }

    public boolean lookExit(Direction direction)
    {
        return exits[direction.ordinal()] != null;
    }

    public String getName() {
        return name;
    }

    public OurRoom solveRecursively(OurRoom exit) {
        list.add(this);
        if(this == exit) {
            return this;
        }else { 
            OurRoom temp = null;            
            if(lookExit(Direction.east)) {
                temp = exits[Direction.east.ordinal()].solveRecursively(exit);              
            }   
            else if(lookExit(Direction.up)) {
                temp = exits[Direction.up.ordinal()].solveRecursively(exit);
            }
            else if(lookExit(Direction.south)) {
                temp = exits[Direction.south.ordinal()].solveRecursively(exit);             
            }           
            else if(lookExit(Direction.down)) {
                temp = exits[Direction.down.ordinal()].solveRecursively(exit);
            }
            else if(lookExit(Direction.west)) {
                temp = exits[Direction.west.ordinal()].solveRecursively(exit);      
            }   
            else if(lookExit(Direction.north)) {
                temp = exits[Direction.north.ordinal()].solveRecursively(exit); 
            }
            return temp;
        }
    }

    public ArrayList<OurRoom> getList() {
        return list;
    }

}

Here is a listing of directions

public enum Direction
{
    north, south, east, west, up, down;

    public Direction getOpposite()
    {
        switch(this)
        {
            case north:
                return south;
            case south:
                return north;
            case east:
                return west;
            case west:
                return east;
            case up:
                return down;
            case down:
                return up;
            default:
                return this;
        }
    }
}

And here is an example of how the maze is built.

import java.util.ArrayList;
import java.util.Iterator;

public class OurMaze
{
    private OurRoom entrance, exit;

    public OurMaze()
    {
        this(1);
    }

    public OurMaze(int mazeNumber)
    {
        entrance = null;
        exit = null;
        switch(mazeNumber)
        {
        case 0:
            break;
        case 1:
            this.buildMaze1();
            break;             
        default:
        }
    }

    public OurRoom getEntrance()
    {
        return entrance;
    }

    public OurRoom getExit()
    {
        return exit;
    }

    public Iterator<OurRoom> findPathRecursively() {
        entrance.solveRecursively(exit);
        ArrayList<OurRoom> list = entrance.getList();       
        return list.iterator();
    }

    private void buildMaze1()
    {
        OurRoom room1, room2;

        room1 = new OurRoom("Room 1");
        room2 = new OurRoom("Room 2");
        room1.connectTo(room2, Direction.north);

        entrance = room1;
        exit = room2;
    }

    public static void main(String[] args) {
        OurMaze maze = new OurMaze(1);      
    }
}
+5
4

, , , .

duffymo, , - , , , , , .

, solveRecursively, , . , , - , if-else .

, (.. ) , "" , .

( , /. , , , , if , . BFS, , )

+2

, , : .

, ( , ).


http://en.wikipedia.org/wiki/Flood_fill
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search

.

    void dfs(int i, int j) {
        if cell(i, j) is outside of maze or blocked {
            return
        }
        if visited[i][j] {
            return
        }
        visited[i][j] = true;
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }

, , visited, , . , ( ).

var end = exit_point;
while (end != start_point) {
   print end;
   end = came_from[end];
}


, , . .
, - .

+6

, - , , .

, , , , . ?

, , - . IBM , . - . , , . .

+1

6- , node , . .

This page describes various solutions for finding paths through graphs that are structured as such. Your schedule is simpler than those that describe real-world maps, since the cost of moving around any edge is equal to the cost of moving around any other edge.

Be especially sure to watch Dijkstra's algorithm .

+1
source

More articles:


All Articles