current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite

Given any map such as the one below, 1 for path and 0 for walls, can you guys review my code and see what I am doing wrong. My code is supposed to return an arrayList of the positions that it passed by on the map. But my code is not returning any positions and I'm confused on how I can record the "WINNING" positions. Please help, I would truly appreciate it. How can I return an arraylist of winning positions, please help? Please consider that the Path is declared as an instance variable.

An example would be GetPath from point (0,0) to (0,5) and the array returned should contain (0, 5) (1, 5) (2, 5) (3, 5) (4, 5) (4, 4) (4, 3) (4, 2) (3, 2) (2, 2) (1, 2) (0, 2) (0, 1) (0, 0).

 int[][] Map = new int[][]{
        { 1, 1, 1, 0, 0, 1 },
        { 0, 0, 1, 0, 0, 1 },
        { 0, 0, 1, 0, 0, 1 },
        { 0, 0, 1, 0, 0, 1 },
        { 0, 0, 1, 1, 1, 1 },
        { 0, 0, 1, 0, 0, 1 },
};

The recursive method is 

private ArrayList<Point> GetPath(Point CurrentPosition, Point EndPosition, int[][] Map)
{ 
    int x = (int) CurrentPosition.getX();
    int y = (int) CurrentPosition.getY();
    int x2 = (int) EndPosition.getX();
    int y2 = (int) EndPosition.getY();
    System.out.println("CurrentPosition: "+ x + "," + y);
    Path.add(CurrentPosition);

    if (x == x2 && y == y2) //base case
    {
        return Path;
    }


    Map[x][y] = 0; //Will keep track of positions that have been visited.
    ArrayList<Point> recursion;

    if (x + 1 < Map.length && Map[x+1][y] == 1) //checking down
    {
        recursion = GetPath(new Point(x + 1, y),EndPosition, Map);
        if (recursion != null)
        {
            Path = recursion;
            return Path;
        }

      }

       if (x-1 >= 0 && Map[x-1][y] == 1) //checking up
    {
        recursion = GetPath(new Point(x-1, y),EndPosition, Map);
        if (recursion != null)
        {
            Path = recursion;
            return Path;
      }
     }

    if (y+1< Map.length && Map[x][y+1] == 1) //checking right
    {
        recursion = GetPath(new Point(x, y+1), EndPosition, Map);

        if (recursion != null)
        {
           Path = recursion;
            return Path;
        }
      }
    if (y -1 >= 0 && Map[x][y-1] == 1) checking left
    {
        recursion = GetPath(new Point(x, y-1),EndPosition, Map);
        if (recursion != null)
        {
            Path = recursion;
            return Path;
      }
     }


     return null;
    }
share|improve this question

closed as off-topic by ChrisW, rolfl, amon, Jamal♦ Mar 9 '14 at 21:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question must contain working code for us to review it here. For questions regarding specific problems encountered while coding, try Stack Overflow. After getting your code to work, you may edit this question seeking a review of your working code." – rolfl, Jamal
If this question can be reworded to fit the rules in the help center, please edit the question.
    
possible duplicate of Solving a Recursive Maze method – ChrisW Mar 9 '14 at 20:51
    
What is the problem you are trying to solve? Given any map, and ..? – abra Mar 9 '14 at 20:55
    
Given any map with the starting position at (0,0), and also given the End Position, I would like to save the maze and return the points that have been passed through – Roy Kesserwani Mar 9 '14 at 20:57
1  
CodeReview is for improving working code, not for fixing broken code. This question is off-topic. – rolfl Mar 9 '14 at 21:15

1 Answer 1

up vote 1 down vote

It seems to me your Path object will end up containing every node ever visited. As you mention, Path is an instance variable, and as far as I can tell, you add to it in every call to GetPath (in the line Path.add(CurrentPosition)), but you never reset it or remove points from it.

Maybe if you tried only adding nodes when you've found the path? That is, don't add to Path on every call, only in the base case:

if (x == x2 && y == y2)
{
    Path.add(CurrentPosition);
    return Path;
}

Otherwise add to the path only when you come back successful from the recursive call:

recursion = GetPath(new Point(...), EndPosition, Map);
if (recursion != null) 
{
    recursion.add(0, CurrentPosition);
    return recursion;
}

You have to add to the front of the list (hence the 0) because you're working back from the target now.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.