motsgar/carcassonne-map-generator

Carcassonne map generator / WFC visualizer

This is a tool to visualize the process of wave function collapse to generate maps for the board game Carcassonne. The project is available at https://carcassonne.motsgar.fi

---

This project is created as a project for the course Datastructures and algorithms in the University of Helsinki.

Usage instaructions

The control panel is mostly self explanatory. Only the buttons that can be pressed at whatever time are enabled.

A few examples of what can be done:

• To show the full process of creating a maze and limiting it to a map and then collapsing that map, press the upper most Start animation button. The animation will run until the map is collapsed or it is stopped.
• To generate a maze or map without maze limitation press Start animation under the respective section. The animation will run until it is done or until you press Stop animation.
• To resize the canvas reset everything and change the size of the canvas.

Uploading a custom tilemap

The tilemap json defines the tiles that are used in the map generation. The tiles are defined in order from top left to bottom right one row at a time. The tilemap json is accompanied by a tilemap image that contains the images for the tiles.

After uploading the tilemap json and image, the tilemap is automatically loaded and the map reset to be able to generate a map with the new tilemap.

{
    "width": 6, // The width of the tilemap in tiles,
    "height": 5, // The height of the tilemap in tiles,
    "tileSize": 200, // The size of a single tile in pixels,
    "tiles": [ // Array of tile objects
        { // Each side is a string that tells what type of side it is.
          // It can be either "Road", "City", "Field" or "Water"
            "top": "Road",
            "right": "Water",
            "bottom": "Road",
            "left": "Water"
        },
        ...
    ]
}

Running locally

To run the project locally, clone the repository and run npm install and npm start. The project will be available at http://localhost:8080

Documentation

• Definition document
• Testing document
• Implementation document

Week reports

• Week report 1
• Week report 2
• Week report 3
• Week report 4
• Week report 5
• Week report 6

tile image credits

https://en.wikipedia.org/wiki/Carcassonne_(board_game)

Default tile images taken from wikipedia (CC BY-SA 4.0) Images made by Mliu92

carcassonne-map-generator's Issues

Peer review

Hi! Noticed you've got no peer reviews for some reason, so here's a quick voluntary one.

Project was downloaded at 11:04 PM @ October 16th. There's no user guide (wasn't required), but since there's a web version, it was straightforward to test the project. I have no TS background myself, for context.

First - tests look great. Very high coverage, and they seem to be testing meaningful things.
About the code:

• The syntax is very Rusty 🤔
• several functions are fairly long (assuming we're going at least roughly by the ohte standards here, although I can't help but disagree with them), especially this
• Startpeice -> Startpiece
• propaganation -> propagation
• Could OldCellStates be a 2D array rather than a Map of Maps? I don't know about the performance numbers, and maybe this is an insignificant part of it considering how fast maps are, but maps do have fairly high overhead, especially memory overhead, and since the generated map is a dense grid, it seems like it could be easy to use a 2D array instead. This would allow to avoid this kind of checks as well
• I don't know TypeScript but can you set reverse: undefined here to avoid the hack?
• My understanding of WFC is too basic to judge here, but you have 4 Sets per MapTile, which adds up really fast. I'm used to always being wary of CPU caches in Rust/C++, and just maybe this doesn't matter at all, but I had to at least bring this up. You are indeed making use of the O(1) contains of Sets though, but since there are only 5 types of Sides, these Sets won't have more than 5 elements each either, and for such small datasets a linear search can even be faster.
• Especially here, the same tile is being fetched many times. Readability thing mainly, reader has to check that they actually are all getting the same tile.
• Looking at this function a lot because it's at the core of the WFC, so likely hot; here, possibleTiles is a list, so this is O(n*m) where n=tileList.len(), m = possibleTiles.len().
• Could this repeated "sort() + get first" be replaced with a priority queue (binary heap f.e)? You could trade O(n log n) to O(log n). I'm not sure what sort implementation is used though, but even if it finishes in linear time, a binary heap isn't only better in time complexity but also fast in practice, unlikely to lose.
• "event1" and "event2" could probably be named better.. Looks like they aren't used anywhere in the code (along with MazeEvent/MazeEventCallback since this function doesn't make use of them either)
• Very much a personal preference but it'd be nice if you added links to the references used at the functions for maze generation / WFC

Overall, I find the code very readable! Consistent & I very much like the formatting. Data seems like it has been split up int their own uh, types? appropriately and comments like this were appreciated.

No UI yet (still?), but I like the console output especially for the maze. At this rate this'll be the only visualization though, seems like the actual UI has been put off for a while?

So all in all, looks pretty good to me (most of what I brought up were about performance/memory, not exactly the core priority here I assume). UI looks like it should be the first priority now if the algorithms are finished, or perhaps even if they aren't given how close we're to the presentation (which seems likely to be on monday 24th).

Keep it up :-)