JavaFx Project based on Mazes -- 2

1 Project Description

In this assignment you will be tasked with implementing several algorithms for maze generation

as well as maze solving. For maze solving you will have to utilize multithreading in

your algorithms.

Requirements

1. Must use JavaFX for all visualizations

2. Must strive for code reuse

• For example you should only have a single notion of a board

• Should only have a single notion of a cell on the board

3. Each generation algorithm must animate as it makes progress

4. Must choose a random point on a wall that will act as the starting point of the maze

5. Must choose a random end point on the opposite wall to the starting point to act as

the end point of the maze

6. Must implement the randomized depth first search generation algorithm

7. Must implement the randomized Kruskal’s algorithm

8. All solving algorithm need to visually show where each solving agent is in the maze as

it is solving the maze

9. Must implement the random mouse solving algorithm

10. Must implement the wall follower algorithm

11. Must use no more than 1000 threads at any one time

12. Must augment the random mouse solving algorithm to use multithreading

• Start at the beginning of the maze

• The mouse should not backtrack

• When the ”mouse” encounters a junction in the maze it must create a copy of

itself for each available path

• Each copy must proceed on its own thread while the original mouse dies

• When one mouse reaches the end of the maze all other mice (threads) must be

killed

13. Must augment the wall follower algorithm to use multithreading

• Start a wall follower at the beginning of the maze

2

• Also start a wall follower at the end of the maze on a di↵erent wall

• Both wall followers must be on their own threads

14. Must implement an additional generating algorithm from the list above

15. Must implement an additional solving algorithm from the list above

16. If you implement an additional generating/solving algorithm you can receive extra

credit but only once

17. If you make the board look visually appealing you can receive extra credit

5 Mandatory Generation Algorithm Descriptions

Randomized Depth First Search:

1. Choose the initial cell, mark it as visited and push it to the stack

2. While the stack is not empty

(a) Pop a cell from the stack and make it a current cell

(b) If the current cell has any neighbours which have not been visited

i. Push the current cell to the stack

ii. Choose one of the unvisited neighbours

iii. Remove the wall between the current cell and the chosen cell

iv. Mark the chosen cell as visited and push it to the stack

Randomized Kruskal

1. Create a list of all walls, and create a set for each cell, each containing just that one

cell.

2. For each wall, in some random order:

(a) If the cells divided by this wall belong to distinct sets:

i. Remove the current wall.

ii. Join the sets of the formerly divided cells.

6 Program Inputs

Your program must accept a file name as a command line argument. The file will have the

following format:

{window size}

{cell size}

{generator}

{solver}

3

Where:

• {window size} is an integer that determines the length and width of the window. Min:

100 Max: 900

• {cell size} is an integer that determines the length and width of each cell. You can

assume that cell size will divide evenly into window size. Min 10: Max: 20

• {generator} is one of the following:

– dfs

– kruskal

– prim

– aldous

– rec

• {solver} is one of the following:

– mouse

– mouse thread

– wall

– wall thread

– pledge

– tremaux

– routing

– astar

For example a file might look like this:

900

10

kruskal

mouse_thread

This means your window needs to be 900 x 900, each cell is 10 x 10, uses kruskal’s algorithm

to generate the maze and the random mouse algorithm with multithreading to solve it.

Java JavaFX

Nº du projet : #29896560

À propos du projet