Darryl Long

This optimisation project was a project that we received during Studio 2, this was received midway through the second project of Studio 2, Creature Feature. There were many challenges that I encountered throughout the project that will be discussed in this post-mortem. Furthermore, I’m going to discuss how to avoid these problems for next time. The task that was assigned to me was a to optimise the field generation for a tiled map generator, the problem currently was that the map was calculating fields by iterating over all the tiles and calculating fields over all the other tiles this gave an efficiency of O(n^2) and was extremely inefficient.

To optimise this we had to come up with a solution so as not to iterate over every single tile only iterate over tiles that would need to be iterated over. My solution was to implement quadtrees to the project solution, quadtrees work by creating quadrants depending on the number of items within an area, if there are too many items within the area, it is then split into four equal regions. Therefore the items within each quadrant only need to check the other items in its quadrant for potential fields.

My initial implementation of this solution I separated each tile into a quadrant depending on their location and how many other tiles were in their quadrant. This gave weird results and an incorrect display of the fields, where quadrant lines could clearly be seen when generating the fields. This was caused by potential fields of tiles that happened to overlap into other quadrants but wasn’t being calculated within that quadrant. The solution to this problem was to note the tile as an area and not a single point and to distribute and include it into each quadrant that it overlapped into as an area. This worked for the most part but again I ran into another immediate problem where generating the initial data was infinite, this was caused by the code that detects the maximum amount of items allowed in a region and splits the quadrant, where there were cases where the maximum amount of fields overlapped a region and the quadrant kept splitting smaller and smaller but the overlap was not going to change causing it to load infinitely. This was solved by adding a limit to the number of times that the quadrant was able to split.

This process of implementing a solution, detecting the problem and then thinking of a way to solve the problem was a really good exercise in the problem-solving. The initial research into quadtrees helped greatly with understanding the implementation of the solution and understanding how the quadtree system worked, this research stage should be repeated when implementing a system to better understand how the system is meant to work. Another challenge I had was time constraints, the assignment being given to us halfway through another project gave it barriers to when I would be able to work on it, better time management is key for future projects. Finally, the last challenge to overcome was syntax work, after working and concentrating on a project in C#, suddenly working on a project in C++ was difficult, implementing simple systems required rigorous syntax checks, in future projects I hope to either be more familiar with the different languages or try not to work in multiple languages to avoid confusion.

In conclusion, the project went well, was optimised efficiently and delivered by the due date. However, there are notes to take on problem-solving, researching, time management and working in multiple languages over projects.