Ask Question, Ask an Expert


Ask Programming Language Expert

Consider the space for a maze as being a large grid of cells with each cell holding four 'walls'. Starting with a random cell, the computer randomly chooses a neighboring cell. The computer removes the walls between two cells and adds the initially, randomly chosen cell to a stack. Once a cell has at least one wall removed, it is considered to have been visited. The computer continues this procedure. Any cell that has no unvisited neighbors’ is considered a dead-end. When at a dead-end the computer backtracks through the path by popping the stack till it reaches a cell with at least one unvisited neighbor, and continues the path generation by visiting this new, unvisited cell. This process continues till every cell has been visited. This depth-first search approach is captured in the subsequent algorithm:

1. Randomly choose an initial cell

2. While there are neighboring cells with all four walls intact

i. Randomly select one of the unvisited neighbors’
ii. Push the selected cell to the stack
iii. Remove the wall between the current cell and the chosen cell

3. Pop a cell from the stack and make it the current cell

4. Repeat from step 2 until all cells have been visited
Follow the instructions below to prepare the program that will create a representation of a maze by using the depth-first search algorithm.

1. Make the following ADTs.

(a) prepare constructor function makestk, predicate function emptystk and mutator functions pushstk and popstk:

i. makestk returns a new stack in form of a tagged tuple: ('stack',[]).

e.g. >>> cellstk=makestk()
>>> cellstk
('stack', [])

ii. emptystk returns True or False depending on whether the given stack is empty or not.

e.g.  >>> emptystk(cellstk)

iii. pushstk accept a stack and an element, and adds the element to the stack at position 0 (see part (b) below for the creation of cell0).

e.g. >>> pushstk(cellstk,cell0)
>>> cellstk
('stack', [('cell', (0, 0), ['t', 'b', 'r', 'l'])])

iv. popstk eradicates the element at position 0 of the given stack.

e.g. >>> popstk(cellstk)
('cell', (0, 0), ['t', 'b', 'r', 'l'])
>>> cellstk
('stack', [])

(b) prepare a constructor function called makecell, accessor functions getx, gety and getwalls, and mutator functions removetw, removebw, removerw, removelw.

i. make cell accept a tuple which consists of the x and y co-ordinate of the cell being created. It returns a cell in the form of a tagged tuple:

The list represents the four walls of the cell: top, bottom, left and right.

e.g. >>> cell0=makecell((0,0))
>>> cell0
('cell', (0, 0), ['t', 'b', 'r', 'l'])

ii. getx and gety return the x and y co-ordinates (correspondingly) of a given cell.

e.g. >>> getx(cell0)

iii. getwalls returns the list of walls that are intact for the given cell

e.g. >>> getwalls(cell0)
['t', 'b', 'r', 'l']

iv.  remove removes the associated wall from the list of walls of a given cell.

e.g. >>> removetw(cell0)
>>> cell0
('cell', (0, 0), ['b', 'r', 'l'])

2. prepare the function makegrid. This function accepts a width and height and creates a grid/matrix of cells. The width gives the number of columns and the height the number of rows of the grid that must be created.

e.g. >>> makegrid(4,5)
[('cell', (0, 0), ['t', 'b', 'r', 'l']), ('cell', (0, 1),
['t', 'b', 'r', 'l']), ('cell', (0, 2), ['t', 'b', 'r', 'l']),
('cell', (0, 3), ['t', 'b', 'r', 'l']), ('cell', (0, 4), ['t',
'b', 'r', 'l']), ('cell', (1, 0),['t', 'b', 'r', 'l']),
('cell', (1, 1), ['t', 'b', 'r', 'l']), ('cell', (1, 2), ['t',
'b', 'r', 'l']), ('cell',(1, 3), ['t', 'b', 'r', 'l']),
('cell', (1, 4), ['t', 'b', 'r', 'l']), ('cell', (2, 0), ['t',
'b', 'r', 'l']), ('cell', (2, 1), ['t', 'b', 'r', 'l']),
('cell', (2, 2), ['t', 'b', 'r', 'l']), ('cell', (2, 3), ['t',
'b','r', 'l']), ('cell', (2, 4), ['t', 'b', 'r', 'l']),
('cell', (3, 0), ['t', 'b', 'r', 'l']), ('cell', (3, 1),['t',
'b', 'r', 'l']), ('cell', (3, 2), ['t', 'b', 'r', 'l']),
('cell', (3, 3), ['t', 'b', 'r', 'l']), ('cell',(3, 4), ['t',
'b', 'r', 'l'])]

3. Given a cell, we should discover its neighbouring cells i.e. those with which it shares a wall. In the diagram given below, the cells with an x are the neighbours of the cell c. prepare the function getneighbours that admitted a cell, the width and height of the grid, and returns all
neighbours of the given cell.

942_cell layout.jpg
e.g. >>> getneighbours(cell0,4,5)
[('cell', (0, 1), ['t', 'b', 'r', 'l']), ('cell', (1, 0),
['t', 'b', 'r', 'l'])]

4. We must also be capable to remove common walls between two cells. prepare the function removewalls that accepts two cells and removes the wall that is common between the two (hint: any cell will have at most, one wall in common with another).

e.g. >>> cell1=makecell((0,1))
>>> removewalls(cell0,cell1)
>>> cell0
('cell', (0, 0), ['t', 'r', 'l'])
>>> cell1
('cell', (0, 1), ['b', 'r', 'l'])

5. We also want to know, given a cell, which of its neighbours has all of its walls intact. prepare the function wallsintact that accepts the grid and a list of neighbouring cells and returns those whose four walls are integral.

e.g. >>> intact=wallsintact(grid,neighbours)
>>> intact
[('cell', (2, 3), ['t', 'b', 'r', 'l']), ('cell',
(3, 2), ['t', 'b', 'r', 'l']), ('cell', (3, 4),
['t', 'b', 'r', 'l'])]

6. Lastly, prepare function createmaze which accepts a width and height as the dimension for a maze and returns the maze represented as a list of cells. Use depth-first algorithm,

ADTs and functions you created in steps 1-5 above (Hint: Keep track of number of cells visited)

>>> createmaze(4,5)
[('cell', (0, 0), ['t', 'r', 'l']), ('cell', (0, 1), ['b', 'l']), ('cell',
(0, 2), ['t', 'l']), ('cell', (0, 3), ['r', 'l']), ('cell', (0, 4), ['b',
'l']), ('cell', (1, 0), ['t', 'r', 'l']), ('cell', (1, 1), []), ('cell',
(1, 2), ['r']), ('cell', (1, 3), ['b', 'r', 'l']), ('cell', (1, 4), ['t',
'b']), ('cell', (2, 0), ['t', 'l']), ('cell', (2, 1), []), ('cell', (2,
2), ['b', 'r', 'l']), ('cell', (2, 3), ['t', 'r', 'l']), ('cell', (2, 4),
['b']), ('cell', (3, 0), ['t', 'b', 'r']), ('cell', (3, 1), ['t', 'b',
'r']), ('cell', (3, 2), ['t', 'r', 'l']), ('cell', (3, 3), ['r', 'l']),
('cell', (3, 4), ['b', 'r'])]

1087_maze correct path.jpg
Represents maze and correct path(S=start, E=end):

Programming Language, Programming

  • Category:- Programming Language
  • Reference No.:- M91627

Have any Question? 

Related Questions in Programming Language

Business app programmingwrite the following programwrite a

Business App Programming Write the following Program: Write a Java program to the form below. The program must work with decimal numbers and each button must work correctly. The result must be done in a popup window. The ...

Evaluate a formula for data in a filewe consider the

Evaluate a formula for data in a file We consider the formula y(t) = v0t - 0.5gt2 and want to evaluate y for a range of t values found in a file with format v0: 3.00 t: 0.15592 0.28075 0.36807889 0.35 0.57681501876 0.213 ...

The air pollution level of a city on a given day is a

The air pollution level of a city on a given day is a function of the time of day (in hours). As an environmental specialist, you have collected carbon dioxide level readings at different times. An example of one day of ...

Assignmentwrite a program that calculates the intersection

Assignment Write a program that calculates the intersection of two sets of numbers. The sets can be represented using arrays. The general idea is that A!=0 if i is in the set and A==0 if it is not. Array element A can th ...

Programming languages assignment write the following as

Programming Languages Assignment Write the following as Prolog rules:  1. Implement a rule "dogEnthusiast". Someone is a "dogEnthusiast" if they own AT LEAST TWO dogs. Assume that the only types of facts available are: " ...

The car classdefine a class called car that implements the

The Car Class Define a class called "Car" that implements the parameterized Comparable interface. Each object of this class represents a type of car. Your class must provide all the methods in the public interface. Be su ...

A theater-seating chart is implemented as a two-dimensional

A theater-seating chart is implemented as a two-dimensional array of ticket prices, like this: ROW 6: 10 10 10 10 10 10 10 10 10 10 ROW 5: 10 10 10 20 20 20 20 10 10 10 ROW 4: 20 20 20 20 20 20 20 20 20 20 ROW 3: 20 20 3 ...

Write a program which1 asks the user to enter a letter

Write a program which: 1. Asks the user to enter a letter grade (A, B, C, D, F) or (a, b, c, d, f) 2. Validates that the entry is a letter grade (A, B, C, D, F) or (a, b, c, d, f) 3. The program then asks the user to ent ...

Assignmentindent code and insert comments to document your

Assignment Indent code and insert comments to document your program. Program must be implemented and run as instructed Solve question 11 on page 974 using the following modifications: Design and implement the class myArr ...

Write a lex program that converts a le to pig latin

Write a Lex program that converts a le to Pig Latin." Specially, assume the le is a sequence of words (groups of letters) separated by whitespace. Every time you encounter a word: 1. If the First letter is a consonant, m ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro