# CS422: Code Explanation Report
## system.py
### Directory: /Sources/system.py
### Overview
* This is the main program for the project to navigate between frontend, backend and other class.
### Code Explanation
The main class of this code is **SystemController** class with the following main attributes and methods:
* The attribute consists a dictionary with format: {map's name: map's content (3D List)}
```python
def __init__(self):
self.mapLists = {}
```
* This function uses to write the solution to json file for frontend to show the algorithms's path:
```python
def writeSolutionJsonFile(self, mapName, agentPath, algorithm):
```
* The usage of this function is to solve a choosed map with name: **mapName** parameter with corresponding algorithm by **algorithm** parameter:
```python
def solving(self, mapName, algorithm):
```
* In this function, the system solve all maps with **algorithm** parameter choosed by users (For example: **bfs, dfs**)
```python
def solvingAllMap(self, algorithm):
for mapName in self.mapLists:
self.solving(mapName, algorithm)
```
### How to use (Flow)
* Declare an object for **SystemController** class
```python
system = SystemController()
```
* Put your map's file in .txt format to Map folder on directory /Map
* Call the following code for the system to read all existent map in Map folder
```python
system.readFolderMap('Map')
```
* Choosing the algorithm to solve all maps by the following code (**Note:** The **algorithm** **parameter** is one of four algorithms: **dfs**, **bfs**, **ucs**, **a***):
```python
system.solvingAllMap('dfs')
```
* Run the following code in command line
```cmd
python system.py
```
## algorithms.py
### Directory: /Sources/level1/algorithms.py
### Overview
* This is the main **algorithm** program for the project to solve each level with corresponding map.
### Algorithm Explanation
In first 3 levels, the algorithm use the following basic idea:
* Frontier firstly add the initial state.
* In each step, the algorithm check the current state is goal state or not. If it is goal state, return the results and stop the algorithm.
* Then find the successor function for next state and check if it is possible for next step or not. In detail, there are 2 impossible cases: the position of agent is not inside the map, the agent do not have key to open door.
* Add all possible state in the succesor function to frontier.
* Continue until get to the goal state or print **No solution** if the map do not have any path from initial state to goal state.
**Note:** Our algorithm use a better way to save key state of the agent in each state instead of saving a list of all keys for that agent. I will explain in detail in the following paragraph:
* Assume there are **N** keys.
* To save all keys' state of the agent, we use **bitmask** technical. In other word, key can be save in binary representation in order to reduce memory and complexity.
* Denote **keyState** be the key state in binary representation.
* Denote **keyStateDec** be the key state in decimal representation.
For example: N = 5, the current agent has lists of key: [1, 2, 5], then **keyState = 10011** and **keyStateDec = 19** (from **keyState** convert to decimal).
* Hence, for a state, we use variable **self.key** to save key state in decimal representation which has the same meaning as **keyStateDec** mention above.
* To check if the agent has key **X**, we can use the following bitwise operation (**Note:** key index start from 0):
```python
# Return true if agent has key X
def isKey(self, X, keyState):
return keyState & (1 << X) != 0
```
* To add a key **X** to a new key state, we use the following function to update key **X** to new key state:
```python
keyNext = self.key
# This mean update bit X to 1
keyNext |= (1 << X)
```
* In summary, we use the traditional search algorithm such as **BFS** or **DFS**, but add **self.key** attribute and related function to control the current key state. To understand more deeply, read the next section, especially **Constructor** and **Successor** function.
### Code Explanation
The main class of this code is **MazerSolverLevel1** class with the following main attributes and methods:
* The constructor of the class (**I will explain each parameters in the following code**):
```python
def __init__(self, mazer, nRow, mCol, nLayer = 1):
# 3D Matrix of map state (X, Y, Z)
self.mazer = mazer
# Number of row in map state (Y)
self.nRow = nRow
# Number of column in map state (Z)
self.mCol = mCol
# Number of layer in map state (X)
self.nLayer = nLayer
# Key bitmask state of map state
# (Detail in algorithm explanation)
self.key = 0
# The direction of an agent's move which consists 8
# directions corresponding to UP, RIGHT, DOWN, LEFT, UP LEFT,
# UP RIGHT, DOWN LEFT, DOWN RIGHT
self.dx = [-1, 0, 1, 0, -1, -1, 1, 1]
self.dy = [0, 1, 0, -1, -1, 1, -1, 1]
```
* The following function is to get the agent in current map state with **agentName** parameter. This function returns a tuple **(X, Y, Z)** corresponding to floor Z, row X, column Y:
```python
def agentPosition(self, agentName):
```
* To check an agent's state is inside the map or not, use this function.
```python
# Return true if inside the map
# Else return false
def inside(self, xCor, yCor, layer):
```
* To check an agent can move to another state or not
```python
def canMove(self, xCor, yCor, layer, key):
if not self.inside(xCor, yCor, layer) or not self.isValid(xCor, yCor, layer, key):
return False
return True
```
* The successor function and its explanation:
```python
# successor function return a list of possible state in next step
def succesor(self, xCor, yCor, layer, key):
# successor list
succ = []
# Try 8 direction from current position :(xCor, yCor, layer)
for i in range(8):
xNext = xCor + self.dx[i]
yNext = yCor + self.dy[i]
layerNext = layer
keyNext = key
# If next position is Up Stair
if self.mazer[layer][xCor][yCor] == 'U':
layerNext += 1
elif self.mazer[layer][xCor][yCor] == 'D': # Similar to Down start
layerNext -= 1
# If next position is Key X, the bit X in binary representation of keyNext will update to 1
if self.mazer[layer][xCor][yCor][0] == 'K':
keyNext |= (1 << int(self.mazer[layer][xCor][yCor][1:]))
# If next position is possible for agent to move, push it to successor list
if self.canMove(xNext, yNext, layerNext, keyNext) and self.isValid(xCor, yNext, layer, key) and self.isValid(xNext, yCor, layer, key):
succ.append((xNext, yNext, layerNext, keyNext))
return succ
```
* To call DFS algorithm, use the following function:
```python
# dfs algorithm to solve mazer
# start parameter: tuple of position of agent 1.
# For example: (1, 1, 0)
# goal parameter: tuple of position of goal 1
# For example: (m, n, 0)
def dfs(self, start, goal, key = 0):
```
* Similarly, BFS algorithm can be used:
```python
def bfs(self, start, goal, key = 0):
```
Sign in with Wallet
Connect another wallet