2 Replies - 1197 Views - Last Post: 15 November 2012 - 01:20 PM Rate Topic: -----

#1 oyyou  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 184
  • Joined: 26-April 10

Maze - Depth First, Breadth first

Posted 29 January 2012 - 02:36 PM

Okay so I've been given an assignment to program a bot to find the quickest route around a maze of nodes.
The tutor has explained to me how to use these methods, Depth and Breadth. I understand that, but I haven't be taught how to implement it with code. I've just had a bunch of code thrown at me and I'm expected to do this..
I want to show you what I've got for my bot so far,

package Bot;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

import java.util.ArrayList;

import Maze.*;

public class Challenge1Bot extends Bot
{
    private Map<ResourceAdjustment> map;
    
    private Set<String> visited = new HashSet<String>();
    
    private ArrayList<String> selectedRoute = new ArrayList<String>();
    
    private int number;
    
    public Challenge1Bot(BotFamily family) {
        super(family);
        number = 0;
    }
    
    /**
     * Enter node traces the bots arrival, and leaves the maze if the node is an exit node.
     */
    public void enterNodeActions() throws MapError, UserError {
        trace("Arrived at " + getLocationName());
        map = getMap();
            
        if (isAtExitNode()) {
            leave();
        }
    }
    
    public String chooseNextNode() throws MapError {                
        if(selectedRoute.isEmpty()){
            doSomething(getLocationName(), new ArrayList<String>());
        } else {
            number++;
            return selectedRoute.get(number);
        }
        return "";
    }
    
    public void doSomething(String currentNode, ArrayList<String> route) throws MapError
    {
        route.add(currentNode);
        if(!map.isExitNode(currentNode)){
            for(String neighbour: map.getNeighboursNames(currentNode)){
                doSomething(neighbour, route);
            }
        } else 
            if(selectedRoute.isEmpty() || route.size() < selectedRoute.size())
            selectedRoute = route;
    }
    
    /**
     * Trace the exit from the node
     */
    public void leaveNodeActions() throws MapError {
        trace("Leaving " + getLocationName());        
    }
    
    /**
     * Trace entry into the maze.
     */
    public void enterMazeActions() throws MapError {
        trace("Entered the maze.");        
    }
    
    /**
     * Trace the exit from the maze
     */
    public void leaveMazeActions() throws MapError {
        System.out.print("Leaving the maze. It took ");
    }
    
    /**
     * Notify death
     */
    public void deathbedActions() throws MapError {
        trace("Aargh, I'm dying.");
    }
}



That isn't all of the code, but that's the code I've done myself.
The error I'm getting is a Stack overflow. I think I'm getting close to the end.. But I'm really not sure.

Any help with be much appreciated.

Is This A Good Question/Topic? 0
  • +

Replies To: Maze - Depth First, Breadth first

#2 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Maze - Depth First, Breadth first

Posted 29 January 2012 - 06:06 PM

since you got a stackoverflow then you probably have infinite recursion somewhere. Anyways I took a look at your do something method, and I am guessing the problem is you're not checking if you had already visited a node, that way you can end up going around in circles.
Was This Post Helpful? 0
  • +
  • -

#3 hazel69  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 15-November 12

Re: Maze - Depth First, Breadth first

Posted 15 November 2012 - 01:20 PM

I have the same project,did you done it. In that case can you helps me to understand.
Thanks anyways.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1