Skip to content

Latest commit

 

History

History
40 lines (40 loc) · 2.78 KB

README.md

File metadata and controls

40 lines (40 loc) · 2.78 KB
Raw

Maze Problem

Here is the 10x10 maze problem that is solved by A* algorithm.
This little project has 2 files ("main.py" and "maze_class.py") that "main.py" is just a fast test for the main written algorithm ("maze_class.py").

main.py

Just run this file by python3 main.py to see how the algorithm works.

maze_class.py

Our main code is here.
I declared 7 diffrent classes that are like this:

  • Environment Class
  • Maze Class
  • Node Class
  • Position Class
  • Direction Class
  • State Class
  • Colors Class

Environment Class

The biggest class in the project.
This class involves the solving algorithm using A*.
There are two functions named "start_solve" and "solve" that "start_solve" is an initialization for A* Algorithm and after initialization "start_solve" starts "solve" function.
"solve" function returns one of the two States of State Enum Class(State.Failure or State.Victory) to determine if A* found any answer for the maze or the autogenerated maze is not solvable.

Maze Class

Maze Class is the second biggest class after Environment Class.
This class has a 10x10 dictionary named "nodes" with keys like (x, y) and values of Node object.
Also with printing a maze object, you can see the actual graphical autogenerated maze and if the maze is solved, you can see the answer path too.
This class will generate blocks and creates a random maze with just calling "block" function that will be called in initialization of Environment Class automatically.

Node Class

This class is used to have some functions like "set_f" to set the heuristic of that node based on goal's location using previous "g" 's node variable. (I mean "g" attribute of the parent node that extended this one)
"g" attribute of every node means the cost until arriving to the node.
"f" attribute of every node equals to (("g" attribute of previous node + 1) + returned value of "h" function in the node) that this functionality is handled in "set_f" function in every node.
"h" function of every node returns predicted cost of the node until it arrives to goal.
Every node is limited in actions and these limited actions are recorded in "blocked_directions" attribute of every node.

Position Class

This class is used for start and goal position of algorithm.
There are two global variables named "me" and "goal" that are objects of this class.

Direction Class

Used as an Enum Class to determine where side of a node is blocked or where is permitted to go and where to go to find our goal.

Colors Class

An Enum Class that has some color codes used for beauty of maze.

State Class

Used as an Enum Class to determine if the algorithm result was successful or not.