Maze Generation: Recursive Backtracker

This article is inspired by Jamis Buck’s presentation(Algorithm is not a 4-letter word). I’ve talked before about Maze Generation and its importance in acmASCIS blog, it’s great and interesting topic. In this post we’ll talk about a technique of generating a perfect maze, it’s Recursive Backtracking . Recursive backtracking is an algorithm for solving and generating perfect mazes. This algorithm is fast, easy to understand and straightforward to implement, but the maze is still biased(check Jamis Buck’s Presentation about Biased Maze Concept). Recursive backtracker performs a drunkard’s walk from the starting point by randomizing the visited child node at each level, but with some modifications on the drunkard’s walk ,as  it pushes each visited node onto a stack and when it reached a dead-end it pops the nodes off the stack until it finds one that it can continue walking from instead of doing O(n) Search. Algorithm Steps from Jamis Buck’s Blog:

  1. Choose a starting point in the field.
  2. Randomly choose a wall at that point and carve a passage through to the adjacent cell, but only if the adjacent cell has not been visited yet. This becomes the new current cell.
  3. If all adjacent cells have been visited, back up to the last cell that has uncarved walls and repeat.
  4. The algorithm ends when the process has backed all the way up to the starting point.

    you can check the animation introduced by Jamis Buck (here).

Implementation:

Here’s my Implementation in C#.

  1. publicoverridevoid GenerateMaze()
  2.         {
  3.             while (NumOfVisitedCells < TotalCells)
  4.             {
  5.                 ArrayList adjcentCells = this.GetNeighborsWithWalls(currentCell);
  6.                 if (adjcentCells.Count > 0)
  7.                 {
  8.                     int randomCell = Cell.theRandom.Next(0, adjcentCells.Count);
  9.                     Cell aCell = ((Cell)adjcentCells[randomCell]);
  10.                     currentCell.KnockDownWall(aCell);
  11.                     cellStack.Push(currentCell);
  12.                     currentCell = aCell;
  13.                     numOfVisitesCells++;
  14.                 }
  15.                 else
  16.                 {
  17.                     currentCell = (Cell)cellStack.Pop();
  18.                 }
  19.             }
  20.         }

you can try simple .exe file Maze Generation.exe.

Advertisements

Object Oriented Programming Project

C++ Emulator :

Team Members:

  1. Islam Ibrahim
  2. Anas Awad
  3. Ahmed Sakr

Project Idea:

  • Project idea based on emulating C++ language and implement features of text editors(Syntax highlighting ,word wrapping ..etc)

Project Features :

  1. Text Editor Features
    • C++ syntax Highlighter
    • Basic features ( create  project , Open , Remove ,…..etc)
  2. Emulator Features
  • this C++ Emulator can run C++ Code till recursive functions (loops , nested loops , if  & switch statements  ,nested if , arrays , functions ,

    recursive functions)

  • some libraries such as and are involved ,that support built in functions.

Implementation :

  • Programming language : Java, You can find the source code (here)
  • about syntax  highlighter : after implementing lexical analyzer for using programming language , I’ve implemented a syntax highlighter that  highlights each token based on its type if keyword or string literal……. etc.
  • about concepts of emulating you can find them Here  

Problems:

  1. if your written code contains “cin” and you opened the console and didn’t enter the required data ,  the console will crash if you try to open it again.
  2. If your code contains error and you run it for another time the console will not be editable.

all if these problems just in first version.

Recommendations:

  •  We Hope in next version we finish implement of some features of text editor such as indentation.

Project Experience Acquired:

  • learn more about Compilers “How to build compiler or interpreter”.
  • I’ve implemented lexical analyzer and Parse tree.
  • Make me interested in new area which is programming languages Industry and Engineering compilers.
  • How to apply OOP , OOA and OOD concepts.

Certifications : this project is certified from Dr.Gahada Nasr and got 2nd place with another project implemented by (Bassem Modar , Karim Magdy , Noran abo Doma , Hagar el Fiky) rest of our team members.

Thank You :

  • Dr.Ghada Nasr .. OOP course instructor ..
  • Dr.Mohammed Samy .. Teacher Assistant in my college .. His videos about interpreters were really helpful.
  • Mohammed Hesham .. (acmASCIS) president .. he directed me to the starting point.
  • Noran , Bassem , Hagar, karim … The rest of team members they were working on  (connect4 with 3D) graphics.

Thanks all of you, You were really helpful.