##################################################################################################################################################### ######################################################################## INFO ####################################################################### ##################################################################################################################################################### """ This program is provided during session 2 of the PyRat project: https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session2/practical/ It is meant to be used to verify the correct implementation of the BFS player and all its components. """ ##################################################################################################################################################### ###################################################################### IMPORTS ###################################################################### ##################################################################################################################################################### # External imports import random import unittest # PyRat imports from pyrat import BigHolesRandomMaze, MazeFromDict from players.BFS import BFS ##################################################################################################################################################### ###################################################################### CLASSES ###################################################################### ##################################################################################################################################################### class BFS_Tests (unittest.TestCase): """ *(This class inherits from* ``unittest.TestCase`` *).* This class tests the methods of the BFS class. For each method, we test it with a few different configurations. """ ############################################################################################################################################# # CONSTRUCTOR # ############################################################################################################################################# def __init__ ( self, *args: object, **kwargs: object ) -> None: """ Initializes a new instance of the class. Args: args: Arguments to pass to the parent constructor. kwargs: Keyword arguments to pass to the parent constructor. """ # Inherit from parent class super().__init__(*args, **kwargs) ############################################################################################################################################# # TEST METHODS # ############################################################################################################################################# def test_traversal_random (self) -> None: """ This method tests the ``traversal(...)`` method. We are going to check the following: - Outputs are of the expected types. - All vertices are visited. - The routing table is a tree, with root corresponding to the start of the traversal. - The found distances are correct, i.e., strictly positive and increasing, except for the start vertex which should be 0. Note that we cannot test that the output is unique, as there are multiple valid outputs, depending on how vertices are explored. We will test the method on several random graphs to make sure it is working properly. Random graphs will be generated using the PyRat class used to create mazes in games. There are several such classes, but we will use the BigHolesRandomMaze class. """ # Constants NB_GRAPHS = 10 WIDTHS = [2, 30] HEIGHTS = [2, 30] CELL_PERCENTAGES = [20.0, 100.0] WALL_PERCENTAGES = [20.0, 100.0] MUD_PERCENTAGE = 0.0 # Test on several graphs for i in range(NB_GRAPHS): # Instantiate the player player = BFS() # Generate a random maze # We use a fixed random seed for reproducibility of tests rng = random.Random(i) maze = BigHolesRandomMaze(width = rng.randint(WIDTHS[0], WIDTHS[1]), height = rng.randint(HEIGHTS[0], HEIGHTS[1]), cell_percentage = rng.uniform(CELL_PERCENTAGES[0], CELL_PERCENTAGES[1]), wall_percentage = rng.uniform(WALL_PERCENTAGES[0], WALL_PERCENTAGES[1]), mud_percentage = MUD_PERCENTAGE, random_seed = i) # Choose a random starting vertex start_vertex = rng.choice(maze.get_vertices()) # Perform the traversal distances, routing_table = player.traversal(maze, start_vertex) # Check the output type for distances # It should be a dictionary with integer keys and integer values self.assertTrue(isinstance(distances, dict)) self.assertTrue(all(isinstance(k, int) for k in distances.keys())) self.assertTrue(all(isinstance(v, int) for v in distances.values())) # Check the output type for the routing table # It should be a dictionary with integer keys and integer or None values self.assertTrue(isinstance(routing_table, dict)) self.assertTrue(all(isinstance(k, int) for k in routing_table.keys())) self.assertTrue(all(isinstance(v, (type(None), int)) for v in routing_table.values())) # All vertices should be visited # Equivalently, the distances should have the same keys as the maze vertices self.assertEqual(sorted(set(distances.keys())), sorted(maze.get_vertices())) # Check that the start vertex is the only tree root self.assertEqual(routing_table[start_vertex], None) self.assertTrue(all(routing_table[v] is not None for v in routing_table.keys() if v != start_vertex)) self.assertEqual(distances[start_vertex], 0) self.assertTrue(all(distances[v] > 0 for v in distances.keys() if v != start_vertex)) # We check that the routing table is a tree # Also we check that associated distances are decreasing as we go to the root for vertex in routing_table: # We check that the parent is closer to the root if routing_table[vertex] is not None: self.assertTrue(distances[routing_table[vertex]] < distances[vertex]) # We ckeck that we can reach the root from any vertex path = [vertex] while routing_table[path[-1]] is not None: self.assertTrue(routing_table[path[-1]] not in path) path.append(routing_table[path[-1]]) ############################################################################################################################################# def test_traversal_fixed (self) -> None: """ This method complements the previous tests by testing the `traversal(...)` method on some controlled examples. To do so, we will use some mazes for which there is a unique routing table. We do not test the output types again, as it has already been done in the previous test function. """ # Constants TESTS = [{"inputs": {"maze": MazeFromDict({4: {5: 1}, 5: {4: 1, 6: 1}, 6: {5: 1, 16: 1}, 7: {17: 1}, 9: {19: 1}, 10: {20: 1}, 11: {12: 1}, 12: {11: 1, 22: 1}, 16: {6: 1, 17: 1, 26: 1}, 17: {7: 1, 16: 1}, 19: {9: 1, 29: 1}, 20: {10: 1, 30: 1}, 21: {22: 1}, 22: {12: 1, 21: 1, 23: 1, 32: 1}, 23: {22: 1}, 24: {34: 1}, 26: {16: 1, 27: 1, 36: 1}, 27: {26: 1, 28: 1, 37: 1}, 28: {27: 1, 29: 1}, 29: {19: 1, 28: 1}, 30: {20: 1, 40: 1}, 31: {32: 1, 41: 1}, 32: {22: 1, 31: 1, 33: 1}, 33: {32: 1, 34: 1}, 34: {24: 1, 33: 1, 44: 1}, 36: {26: 1, 46: 1}, 37: {27: 1}, 40: {30: 1, 41: 1}, 41: {31: 1, 40: 1, 51: 1}, 43: {44: 1}, 44: {34: 1, 43: 1, 45: 1}, 45: {44: 1, 46: 1}, 46: {36: 1, 45: 1, 47: 1}, 47: {46: 1, 48: 1}, 48: {47: 1}, 50: {51: 1}, 51: {41: 1, 50: 1, 52: 1, 61: 1}, 52: {51: 1, 53: 1}, 53: {52: 1, 54: 1}, 54: {53: 1, 55: 1}, 55: {54: 1, 56: 1, 65: 1}, 56: {55: 1, 57: 1}, 57: {56: 1, 58: 1, 67: 1}, 58: {57: 1, 68: 1}, 60: {61: 1}, 61: {51: 1, 60: 1, 71: 1}, 65: {55: 1}, 66: {67: 1}, 67: {57: 1, 66: 1, 77: 1}, 68: {58: 1, 78: 1}, 69: {79: 1}, 70: {71: 1, 80: 1}, 71: {61: 1, 70: 1, 72: 1}, 72: {71: 1, 73: 1}, 73: {72: 1, 74: 1}, 74: {73: 1, 75: 1}, 75: {74: 1}, 77: {67: 1, 87: 1}, 78: {68: 1, 79: 1}, 79: {69: 1, 78: 1, 89: 1}, 80: {70: 1, 90: 1}, 81: {91: 1}, 82: {83: 1, 92: 1}, 83: {82: 1, 84: 1}, 84: {83: 1, 94: 1}, 85: {95: 1}, 86: {96: 1}, 87: {77: 1, 88: 1, 97: 1}, 88: {87: 1}, 89: {79: 1, 99: 1}, 90: {80: 1, 91: 1}, 91: {81: 1, 90: 1, 92: 1}, 92: {82: 1, 91: 1, 93: 1}, 93: {92: 1}, 94: {84: 1, 95: 1}, 95: {85: 1, 94: 1, 96: 1}, 96: {86: 1, 95: 1}, 97: {87: 1, 98: 1}, 98: {97: 1}, 99: {89: 1}}), "start": 55}, "outputs": {"routing_table": {55: None, 54: 55, 56: 55, 65: 55, 53: 54, 57: 56, 52: 53, 58: 57, 67: 57, 51: 52, 68: 58, 66: 67, 77: 67, 41: 51, 50: 51, 61: 51, 78: 68, 87: 77, 31: 41, 40: 41, 60: 61, 71: 61, 79: 78, 88: 87, 97: 87, 32: 31, 30: 40, 70: 71, 72: 71, 69: 79, 89: 79, 98: 97, 22: 32, 33: 32, 20: 30, 80: 70, 73: 72, 99: 89, 12: 22, 21: 22, 23: 22, 34: 33, 10: 20, 90: 80, 74: 73, 11: 12, 24: 34, 44: 34, 91: 90, 75: 74, 43: 44, 45: 44, 81: 91, 92: 91, 46: 45, 82: 92, 93: 92, 36: 46, 47: 46, 83: 82, 26: 36, 48: 47, 84: 83, 16: 26, 27: 26, 94: 84, 6: 16, 17: 16, 28: 27, 37: 27, 95: 94, 5: 6, 7: 17, 29: 28, 85: 95, 96: 95, 4: 5, 19: 29, 86: 96, 9: 19}, "distances": {55: 0, 54: 1, 56: 1, 65: 1, 53: 2, 57: 2, 52: 3, 58: 3, 67: 3, 51: 4, 68: 4, 66: 4, 77: 4, 41: 5, 50: 5, 61: 5, 78: 5, 87: 5, 31: 6, 40: 6, 60: 6, 71: 6, 79: 6, 88: 6, 97: 6, 32: 7, 30: 7, 70: 7, 72: 7, 69: 7, 89: 7, 98: 7, 22: 8, 33: 8, 20: 8, 80: 8, 73: 8, 99: 8, 12: 9, 21: 9, 23: 9, 34: 9, 10: 9, 90: 9, 74: 9, 11: 10, 24: 10, 44: 10, 91: 10, 75: 10, 43: 11, 45: 11, 81: 11, 92: 11, 46: 12, 82: 12, 93: 12, 36: 13, 47: 13, 83: 13, 26: 14, 48: 14, 84: 14, 16: 15, 27: 15, 94: 15, 6: 16, 17: 16, 28: 16, 37: 16, 95: 16, 5: 17, 7: 17, 29: 17, 85: 17, 96: 17, 4: 18, 19: 18, 86: 18, 9: 19}}}, {"inputs": {"maze": MazeFromDict({0: {1: 1}, 1: {0: 1, 11: 1}, 4: {5: 1}, 5: {4: 1, 6: 1}, 6: {5: 1, 7: 1, 16: 1}, 7: {6: 1}, 8: {9: 1, 18: 1}, 9: {8: 1}, 10: {11: 1}, 11: {1: 1, 10: 1, 21: 1}, 14: {24: 1}, 15: {16: 1}, 16: {6: 1, 15: 1, 17: 1, 26: 1}, 17: {16: 1, 18: 1, 27: 1}, 18: {8: 1, 17: 1, 19: 1}, 19: {18: 1}, 20: {21: 1}, 21: {11: 1, 20: 1, 31: 1}, 23: {24: 1}, 24: {14: 1, 23: 1, 25: 1}, 25: {24: 1, 26: 1}, 26: {16: 1, 25: 1, 36: 1}, 27: {17: 1, 28: 1}, 28: {27: 1, 29: 1}, 29: {28: 1, 39: 1}, 30: {31: 1}, 31: {21: 1, 30: 1, 41: 1}, 32: {42: 1}, 36: {26: 1, 37: 1}, 37: {36: 1, 38: 1, 47: 1}, 38: {37: 1, 48: 1}, 39: {29: 1}, 40: {41: 1}, 41: {31: 1, 40: 1, 42: 1}, 42: {32: 1, 41: 1, 52: 1}, 47: {37: 1, 57: 1}, 48: {38: 1, 49: 1, 58: 1}, 49: {48: 1, 59: 1}, 50: {51: 1}, 51: {50: 1, 61: 1}, 52: {42: 1, 62: 1}, 56: {57: 1}, 57: {47: 1, 56: 1}, 58: {48: 1, 68: 1}, 59: {49: 1}, 60: {70: 1}, 61: {51: 1, 62: 1}, 62: {52: 1, 61: 1, 63: 1}, 63: {62: 1, 73: 1}, 70: {60: 1, 71: 1}, 71: {70: 1, 72: 1}, 72: {71: 1, 73: 1, 82: 1}, 73: {63: 1, 72: 1, 74: 1, 83: 1}, 74: {73: 1, 75: 1, 84: 1}, 75: {74: 1, 85: 1}, 76: {77: 1, 86: 1}, 77: {76: 1, 78: 1, 87: 1}, 78: {77: 1, 79: 1, 88: 1, 68: 1}, 79: {78: 1, 89: 1}, 80: {81: 1}, 81: {80: 1, 82: 1}, 82: {72: 1, 81: 1, 92: 1}, 83: {73: 1}, 84: {74: 1}, 85: {75: 1, 86: 1, 95: 1}, 86: {76: 1, 85: 1}, 87: {77: 1}, 88: {78: 1, 98: 1}, 89: {79: 1}, 90: {91: 1}, 91: {90: 1, 92: 1}, 92: {82: 1, 91: 1}, 93: {94: 1}, 94: {93: 1, 95: 1}, 95: {85: 1, 94: 1}, 96: {97: 1}, 97: {96: 1, 98: 1}, 98: {88: 1, 97: 1, 99: 1}, 99: {98: 1}, 68: {58: 1, 78: 1}}), "start": 56}, "outputs": {"routing_table": {56: None, 57: 56, 47: 57, 37: 47, 36: 37, 38: 37, 26: 36, 48: 38, 16: 26, 25: 26, 49: 48, 58: 48, 6: 16, 15: 16, 17: 16, 24: 25, 59: 49, 68: 58, 5: 6, 7: 6, 18: 17, 27: 17, 14: 24, 23: 24, 78: 68, 4: 5, 8: 18, 19: 18, 28: 27, 77: 78, 79: 78, 88: 78, 9: 8, 29: 28, 76: 77, 87: 77, 89: 79, 98: 88, 39: 29, 86: 76, 97: 98, 99: 98, 85: 86, 96: 97, 75: 85, 95: 85, 74: 75, 94: 95, 73: 74, 84: 74, 93: 94, 63: 73, 72: 73, 83: 73, 62: 63, 71: 72, 82: 72, 52: 62, 61: 62, 70: 71, 81: 82, 92: 82, 42: 52, 51: 61, 60: 70, 80: 81, 91: 92, 32: 42, 41: 42, 50: 51, 90: 91, 31: 41, 40: 41, 21: 31, 30: 31, 11: 21, 20: 21, 1: 11, 10: 11, 0: 1}, "distances": {56: 0, 57: 1, 47: 2, 37: 3, 36: 4, 38: 4, 26: 5, 48: 5, 16: 6, 25: 6, 49: 6, 58: 6, 6: 7, 15: 7, 17: 7, 24: 7, 59: 7, 68: 7, 5: 8, 7: 8, 18: 8, 27: 8, 14: 8, 23: 8, 78: 8, 4: 9, 8: 9, 19: 9, 28: 9, 77: 9, 79: 9, 88: 9, 9: 10, 29: 10, 76: 10, 87: 10, 89: 10, 98: 10, 39: 11, 86: 11, 97: 11, 99: 11, 85: 12, 96: 12, 75: 13, 95: 13, 74: 14, 94: 14, 73: 15, 84: 15, 93: 15, 63: 16, 72: 16, 83: 16, 62: 17, 71: 17, 82: 17, 52: 18, 61: 18, 70: 18, 81: 18, 92: 18, 42: 19, 51: 19, 60: 19, 80: 19, 91: 19, 32: 20, 41: 20, 50: 20, 90: 20, 31: 21, 40: 21, 21: 22, 30: 22, 11: 23, 20: 23, 1: 24, 10: 24, 0: 25}}}] # Test on several controlled examples for i in range(len(TESTS)): # Instantiate the player player = BFS() # Get the input and output data maze = TESTS[i]["inputs"]["maze"] start = TESTS[i]["inputs"]["start"] target_routing_table = TESTS[i]["outputs"]["routing_table"] target_distances = TESTS[i]["outputs"]["distances"] # Perform the traversal distances, routing_table = player.traversal(maze, start) # Check that outputs match the expected ones self.assertEqual(sorted(routing_table), sorted(target_routing_table)) self.assertEqual(sorted(distances), sorted(target_distances)) ############################################################################################################################################# def test_find_route (self) -> None: """ This method tests the ``find_route(...)`` method. Here, we want to make sure that the output corresponds indeed to a route from the start to the end. We are going to check the following: - Outputs are of the expected types. - The route is a valid path from the start to the end. The method will be tested on some controlled examples, where we can easily check the validity of the output. """ # Constants INPUTS = [{"routing_table": {0: None, 1: 0, 2: 1, 3: 2, 4: 3}, "start": 0, "end": 4}, {"routing_table": {0: 2, 1: None, 2: 1, 3: 0, 4: 0, 5: 4, 6: 1}, "start": 1, "end": 6}] # Test on several controlled examples for i in range(len(INPUTS)): # Instantiate the player player = BFS() # Get the input data routing_table = INPUTS[i]["routing_table"] start = INPUTS[i]["start"] end = INPUTS[i]["end"] # Find the route route = player.find_route(routing_table, start, end) # Check the output type # It should be a list of integers self.assertTrue(isinstance(route, list)) self.assertTrue(all(isinstance(v, int) for v in route)) # Check that the route is a valid path from the start to the end self.assertEqual(route[0], start) self.assertEqual(route[-1], end) self.assertTrue(all(routing_table[route[j + 1]] == route[j] for j in range(len(route) - 1))) ##################################################################################################################################################### ####################################################################### SCRIPT ###################################################################### ##################################################################################################################################################### if __name__ == "__main__": # Run all tests unittest.main(verbosity=2) ##################################################################################################################################################### #####################################################################################################################################################