search

Taeir / ContextProject-MIGI2

VR Game
0 stars 0 forks source link

Feature maze generation update fixed #402

Closed Diocruel closed 8 years ago

Diocruel commented 8 years ago

And here it is, just a small algorithm to generate maps. It seems that I lost about 94 commits during the “fix” of author, so please, DON’T delete the Maze-generation-update branch, as it contains the commits not counted in this PR!

Firstly, maps are now saved in a different format. In this format each map is a folder with a .cmf file specifying what rooms to load. The folder also contains a map within for each room that can be loaded. The .crf files themselves now have a different layout as well, see the below list for the new notation of the tiles.

Secondly, a lot of extra data structures have been created. These data structures all contain javadoc entailing their purpose, so their purpose won't be explained thoroughly here. The main idea is to transfer the information saved in the .cmf and .crf files in collections of objects, so that the algorithms can easily deal with the data. Remember Datastructures and Algorithms from the first year? Well each algorithm has data structures it can easily deal with, so transforming the .crf files into data structures that are fast and handy greatly improves the algorithm speed.

Thirdly, the algorithm itself is created. There is no real existing algorithm that is widespread and does exactly what we want to do with the maze creation: use predefined rooms with entrances and exits that creates a random cave, in which each exit is connected to an entrance.

The algorithm works in six steps:

  1. Place start and treasure room randomly in space, though ensure some distance between them.
  2. For a number of attempts place random other rooms till desired density has been found, keep track of every room's it's connections and the type of connection (in/out)
  3. Create a connection (edge) from every in-connection to every out-connection that is not in the same room.
  4. Use the Reverse Delete algorithm to create a Minimum Spanning Tree of this connected graph, but enforce extra connectifity such that every exit is connected to an entrance.
  5. For each remaining edge use breadth first search to construct actual corridor in the maze.
  6. Place corridors walls so the maze is closed of.

It seems that this algorithm works cleanly and fast for mazes til about 20 to 30 rooms, after this, the algorithm starts taking a lot of time to complete, since it has to do a ton of comparisons to keep the maze structured. Though mazes of 200 to 300 rooms look stunning and can still be generated in about 1 minute of serious computing time on my laptop.

And finally, All PMD, Findbug and CheckStyle warnings have been dealt with or explained. The test coverage is wel over 80% in all added classes, except for the RandomUtil class, since it only contains two lines, with one being a private constructor....

See for the entire coverage: Coverage of all packages. The coverage in the level package: Coverage of entire level package. The coverage in the level.RoomIO package: Coverage of entire level.RoomIO package. The coverage in the level.util package: Coverage of entire level.util package.

I know it is a lot of lines, so I should have done this in separate pull request perhaps, but it was difficult to envision the entire algorithm before hand, so many changes have been made to it during its creation, which would have cost extra review time on code which was removed later.

Please ask any questions you have about the algorithm or the classes. Make sure you understand the algorithm while reviewing the code!

Thanks!

Almost forgot this Pull Request closes #151, closes #152, closes #153, closes #202, closes #293, closes #293, closes #294, closes #295, closes #296, closes #297, closes #298, closes #299 and closes #395 .

ChielBruin commented 8 years ago

[75 minutes later...] All the code looks good and the result looks great! I have "some" style complaints, after this is updated I am fine merging.

Diocruel commented 8 years ago

Since I accidentally based this PR on master this PR should be closed. There will however be a reference to this PR as all the comments have been addressed.