Thread: Simple recursive maze algorithm & counting steps

  1. #1
    Registered User
    Join Date
    Jun 2013
    Posts
    25

    Simple recursive maze algorithm & counting steps

    Hey,

    issue: my maze algorithm must be able to count total steps. He is not allowed to "jump" from a deadend back to the cross-way he originally came from.

    Code:
    int R2D2Turbo::findIt(Labyrinth* incLab, int x, int y)
    {
        
    
        if ((x == incLab->getExit().x) && (y == incLab->getExit().y))
        {
        return 1;
        }
    
        if (x <=0 || x >= incLab->getSize().x || y <= 0 || y >= incLab->getSize().y)
        {
        return 0;
        }
        
        if (incLab->getPoint(x, y) == '#' || track[y][x] == '+') return 0;
    
        track[y][x] = '+';
        this->steps++;
        
        if ( findIt(incLab, x, y - 1)) return 1;
        if ( findIt(incLab, x + 1, y)) return 1;
        if ( findIt(incLab, x, y + 1)) return 1;
        if ( findIt(incLab, x - 1, y)) return 1;
    
        return 0;
    }
    Give maze:
    Code:
    ### ### 
    # # # # 
    # # # # 
    #     # 
    ##### # 
    #     # 
    ### ###
    Result:
    Code:
    ###x### 
    # #x#x# 
    # #x#x# 
    #  xxx# 
    #####x# 
    #  xxx# 
    ### ###
    Total steps: 11 - he jumps from 5:1 to 5:4 and misses 3 steps.
    The required answere is 14 steps.

    Due to the nature of recursive algoirthms, he jumps instead of moving the way back from the deadend one by one...

    Any suggestion on how to get this solved is appreciated. The only solutions I could think of are way overloaded...

    Thanks in advance!

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Maze solving algorithm - Wikipedia, the free encyclopedia
    Perhaps you should implement "wall follower" and just count how many steps it takes.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jun 2013
    Posts
    25
    Thanks for the input, I already implemented a wall follower with left-hand rule and another with right-hand rule, they work like a charm. I however need a third, simple maze algorithm (as I need a total of 3 different maze algorithms).

    Now using a wall follower algorithm to count steps of my R2D2Turbo is not a satisfying solution, as the wall follower itself already is an own maze algorithm.
    Last edited by coffee_cups; 06-01-2013 at 12:24 PM.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Perhaps you could have your findIt function return the number of steps it has made.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive maze, so close, but something is wrong
    By forensicgeek in forum C Programming
    Replies: 9
    Last Post: 09-16-2009, 10:48 PM
  2. Recursive Stack Algorithm Maze Solver
    By unrestricted in forum C Programming
    Replies: 0
    Last Post: 09-04-2007, 03:11 AM
  3. counting steps
    By muran_pling in forum C++ Programming
    Replies: 6
    Last Post: 12-18-2006, 04:27 AM
  4. Solve a maze recursive
    By BENCHMARKMAN in forum C++ Programming
    Replies: 4
    Last Post: 09-19-2006, 11:33 PM
  5. recursive maze help
    By chad101 in forum C++ Programming
    Replies: 1
    Last Post: 12-15-2005, 02:37 PM