Java Maze programming help

so i’m in a data systems class right now. and the latest assignment we have has me stumped. totally. This is what it is:

In the Maze game, the maze is represented by a rectangular grid. at each point of the grid, where are four directions to move: Up, Down, Left and Right. some directions may be blocked by a wall. Suppose you enter the maze with a computer. you have no knowledge of the maze and there is no light in the maze. when you move, each step moves you from one grid to another
(a.) Please design the data structures for

  • the Grid of the game
  • the storage of all the previous steps

(b.)Based on the data structures you proposed, find an algorithm which can guide you into the Maze and get yourself out

Okay, so i know what elements i need for this to work out, because we’ve used them in class: 2d arrays, linked lists, and elements like that, all with different data functions. im just stuck as far as where to start on this.

And it’s all in java. i dont like java.

someone lend me a hand? i’ll bake you cookies. i swear.

Well, I don’t know Java (have looked into it, but didn’t like what I saw the last time I tried), but I would approach it as:

Data structures: use a 2D array to store the map. Use a linked list to store your current path. Use another 2D array to store failed paths (dead ends, and the like) (or create a class to store in the original array that has all the necessary attributes)

Since we don’t know anything about the map, I don’t think Dijkstra’s or A* will work (somebody may be able to correct me on this, though). I’m sure there’s a better algorithm out there, but it might go something like:

1.) From current position pick a direction (make sure current position is stored in the linked list).
2.) If that direction is a wall, mark that tile in the dead end path and return to (1) picking a new direction and mark the chosen direction as dead/wall.
3.) If its not a wall, then move to that square, and add the new position to the linked list.
4.) Continue this (perhaps in one direction) until you hit a wall. You can then back track through the linked list until you hit a square that has unsearched directions (be sure to remove dead squares from the linked list and mark them in the 2D array so they won’t be searched again).
5.) Continue to repeat this general algorithm, but consider some of the special cases like how do you make sure you aren’t in a cycle (looking at the same squares over and over), what constitutes a truly “dead” square, etc. These will be a major determinant of what data structures you need exactly to be efficient here (think about costs for searching data structures, etc.).

You could probably do this recursively if you needed to (though, there’s no reason you can’t loop it). Most of it will be very generic programming anyways, so I doubt it will require more knowledge than functions/classes, data structures, for/while, loops, etc. (basic functionality).

When you find the “Goal” square all you have to do is read out your linked list to get the path from start to end. It didn’t say anything about shortest path, or the possibility of there being multiple paths through the maze, so I assume only one iteration is necessary. If not, I trust you know how to deal with those.

In general its not “right” to post for homework help, since it won’t help you in the long run, so I strongly suggest that you figure out the rest and make absolutely sure you understand what’s going on in case this pops up again in some incarnation. I don’t feel toooo bad since I just went over general concepts, though.

Probably the teacher wants you to implement a depth-first search. If you reach a wall, you go back until the last position with option of direction you can go.
You take another option and go on and on, always keeping track of the places you already visited, so you don’t have to visit them again.

A good starting point of these kind of tasks could be a visual grid painted with Gimp:
http://www.eonido.org/bildoj/grid30px002.png
Then you’ll have a clear coordinate system and something where you can go on with smaller steps.

heres what ive got so far. its incredibly rough and missing peices, but ive got some kind of results. and they compile. ha, so that works.

public class Maze
{
public static void main (String[] args)
{
    Grid2d maze2d = new Grid2d (20,20);
    
    while (maze2d.xpos != maze2d.maxx || maze2d.ypos != maze2d.maxy)
    {
        if (maze2d.xpos<maze2d.maxx)
            maze2d.moveRight();
        else
        if (maze2d.ypos<maze2d.maxy)
            maze2d.moveUp();
        else
        if (maze2d.ypos<maze2d.maxy)
            maze2d.moveDown();
        else
        if (maze2d.xpos<maze2d.maxx)
            maze2d.moveLeft();
    }
    
}
}

public class Grid2d
{
    private int[][]grid;
    private int[]nElems;
    public int x;
    public int y;
    public int xpos;
    public int ypos;
    public int maxx;
    public int maxy;
    public StepLog steps;
    
    public Grid2d(int x, int y)
    {
        grid = new int [x][y];
        xpos = 0;
        ypos = 0;
        nElems =  new int [x];
        for (int i=0; i<x; i++)
        {
            nElems[i] = 0;
        }
        maxx = x;
        maxy = y;
    }
    
    public void moveUp()
    {
        ypos = ypos+1;
        steps.add ("up" + xpos + ypos);
        if (grid [xpos][ypos]==0)
            grid [xpos][ypos]=1;
        else
            grid [xpos][ypos]++;
    }
    public void moveDown()
    {
        ypos = ypos-1;
        steps.add ("down" + xpos + ypos);
        if (grid [xpos][ypos]==0)
            grid [xpos][ypos]=1;
        else
            grid [xpos][ypos]++;
    }
    public void moveLeft()
    {
        xpos = xpos-1;
        steps.add ("left" + xpos + ypos);
        if (grid [xpos][ypos]==0)
            grid [xpos][ypos]=1;
        else
            grid [xpos][ypos]++;
    }
    public void moveRight()
    {
        xpos = xpos+1;
        steps.add ("right" + xpos + ypos);
        if (grid [xpos][ypos]==0)
            grid [xpos][ypos]=1;
        else
            grid [xpos][ypos]++;
    }    
 
    
}


public class StepLog
{
    private Node head;
    private int stepCount;
    
    public StepLog()
    {
        head = new Node(null);
        stepCount = 0;
    }
    
    public void add(Object data)
    {
        Node temp = new Node(data);
        Node current = head;
        while(current.getNext() != null)
        {
            current = current.getNext();
        }
        current.setNext(temp);
        stepCount++;
    }
    
    public void add(Object data, int index)
    {
        Node temp = new Node(data);
        Node current = head;
        for(int i = 1; i < index && current.getNext() != null; i++)
        {
            current = current.getNext();
        }
        temp.setNext(current.getNext());
        current.setNext(temp);
        stepCount++;
    }
    
    public Object get(int index)
    {
        if(index <= 0)
            return null;
        
        Node current = head.getNext();
        for(int i = 1; i < index; i++)
        {
            if(current.getNext() == null)
                return null;
            
            current = current.getNext();
        }
        return current.getData();
    }
    
    public boolean remove(int index)
    {
        if(index < 1 || index > size())
            return false;
        
        Node current = head;
        for(int i = 1; i < index; i++)
        {
            if(current.getNext() == null)
                return false;
            
            current = current.getNext();
        }
        current.setNext(current.getNext().getNext());
        stepCount--; 
        return true;
    }
    
    public int size()
    {
        return stepCount;
    }
    
    public String toString()
    {
        Node current = head.getNext();
        String output = "";
        while(current != null)
        {
            output += "[" + current.getData().toString() + "]";
            current = current.getNext();
        }
        return output;
    }
    
    private class Node
    {
        Node next;
        Object data;
        

        public Node(Object _data)
        {
            next = null;
            data = _data;
        }
        
        public Node(Object _data, Node _next)
        {
            next = _next;
            data = _data;
        }
        
        public Object getData()
        {
            return data;
        }
        
        public void setData(Object _data)
        {
            data = _data;
        }
        
        public Node getNext()
        {
            return next;
        }
        
        public void setNext(Node _next)
        {
            next = _next;
        }
    }
}