---
# System prepended metadata

title: 'CS422: Code Explanation Report'

---

# 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):
```