Path generation

Overview

PathGenerator.java, FindPath.java and CheckConnectivity.java find and generate connected paths between buildings. PathGenerator takes an instance of BuildingGenerator which contains all the information about the city and building placements, and attempts to generate paths between buildings until paths form a connected graph. FindPath and CheckConnectivity each take an instance of the PathGenerator. The PathGenerator works by reading and modifying the char[][] data structure obtained from BuildingGenerator.getCharMap()

Class diagrams

Debugging

For any suspected PathGenerator bugs, helpful debugging functionality has been included. It can be activated with the following:

1. Navigate to game/area/MapGenerator/pathBuilding/PathGenerator.java
2. Set the debug flag to true
3. Set the debugFilePath variable to the folder you want to store the resulting debug text file. Ensure the path begins from your root directory and ends in a slash
4. Run the game
5. A cityMap.txt and debugInfo.txt file will be created in the directory specified in debugFilePath. If it is not one of the following has probably happened:

• The debugFilePath is incorrect.
• The line in PathGenerator where the debug information is written was never hit (See PathGenerator.PathGenerator(BuildingGenerator bg, int buildingBuffer)). In this case you can move when debug info is outputted to wherever you like.

cityMap.txt outputs the char[][] data structure PathGenerator uses. N represents wall buffer space, * represents empty space, P represents a path tile, D represents a door position and all other characters represent different types of buildings.

debugInfo.txt outputs useful information regarding which paths it attempted to generate between which coordinates and how many iterations it had to complete before a connected path graph was formed.

Testing difficulties

There are difficulties testing PathGenerator works optimally. It was decided against unit testing whether it returns a fully connected graph of paths due to the following:

• A fully connected path system is not crucial for game functionality, it is only a visual element.
• PathGenerator relies heavily on the BuildingGenerator algorithm to work correctly, so unforeseen behaviour or changes made to that class will propagate to PathGenerator and potentially cause irritating, misleading build errors. The scope of variability that will affect whether PathGenerator will always return connected paths is too high to expect it to consistently perform perfectly.
• The most important one is that verifying PathGenerator returns a connected path system in a unit test would require a second search algorithm within the unit test, which would also require its own verification.

Thus aspects of PathGenerator are inspected visually, and it has been tested thoroughly through the included debug functionality and multiple runs of the game with different parameters set, and has found to return a perfectly connected path system almost the entire time.

---

PathGenerator.java

Testing

PathGenerator functionality is verified through both unit testing and visual inspection. Unit testing can be found in PathGeneratorTest.java, which tests that PathGenerator is capable of initialising the char[][] data structure for path finding. A failure here usually indicates a deeper issue elsewhere. The unit tests:

noPathsThroughBuildingsTest() verifies that PathGenerator does not place a path tile through any buildings. An issue here could mean that there was an issue with the path finding algorithms themselves, or more likely that PathGenerator initialised the char[][] structure wrong due to incorrect buildingSpecification.json info

shouldPlaceADoorForEveryBuilding() verifies that PathGenerator initialises the char[][] structure correctly by giving every building a door position. Failure to do this means that a path will not be generated to all the buildings, or they will be generated incorrectly causing the algorithms to fail

shouldPlacePathAfterDoor() verifies that PathGenerator initialises the char[][] structure correctly and places paths starting from the door tile. If it does not do this it either indicates a deeper issue with the algorithm, or incorrect values were given to buildingSpecification.json

---

FindPath.java

Testing

FindPath is a helper class for PathGenerator, and is verified visually and through the included debug functionality. Visual & debugger checks:

• Every building can be reached from any given building.
• All paths end at a building.
• debugInfo.txt does not report a 'No solution' for a path between two given points.

Future plans for testing include adding more unit testing entry points in the generator classes.

---

CheckConnectivity.java

Testing

CheckConnectivity is a helper class for PathGenerator, and is verified visually and through the included debug functionality. Visual & debugger checks:

• There is only one path system.
• Every building can be reached from any given building.
• debugInfo.txt reports that CheckConnection found no unconnected buildings.

Future plans for testing include adding more unit testing entry points in the generator classes.