Tilemaps
The purpose of this assignment is to prepare you to think about your game’s architecture before things start to get too complex. We have sketched out a basic application for you, but you need to fill in a lot of the details. The application is a tool for generating simple tile maps. As you will see below, one of the applications of a such a tool is procedural content generation. We will talk about this type of content later in the course.
However, procedural content generation is not the primary focus of this lab. Instead, you will learn how to architect a complex application with non-trivial scene graphs. You will begin by filling in partialy-completed CRC cards to help you understand the project. You will then implement functions in a project structured using a made-up programming pattern we call ‘CMV’ (Controller-ModelView). Afterward you will convert this to a real programming pattern MVC (Model-View-Controller).
However, despite our use of the word real we want to emphasize that it is not necessarily the case that one is better than the other. As you will see from your development, both have their advantages and disadvantages. And in fact, we will see problems with both of them when it comes to performance. The only thing that matters when you design your game is that you all agree on the architecture that you are going to use.
IMPORTANT: The code for this lab is much more straight-forward than for the previous lab. However, to complete this lab you need to have a strong understanding of scene graphs. You will particularly need to understand the class PolygonNode, which is a scene graph node for drawing polygonal shapes, including tiles.
Table of Contents
Project Files
Download: Tilemap.zip
You should download the project for this assignment. This is a self-contained project just like all of the ones available from the demos page. You can program in XCode, Visual Studio, or Android Studio. For this assignment, you will only be using XCode or Visual Studio. See the engine documentation for how to build and run on your desired platform.
The Configuration File
There are quite a few important differences about the project configuration file that we
want to highlight. First of all, you will notice that the assets folder is empty. This
is an asset-less project; everything is procedurally generated. However, CUGL still needs
an asset folder even if it is empty (this is a bug that we were not able to fix in time
for the semester start). So do not remove the folder or the reference in the configuration
file.
Next, the code is no longer all in the same directory. It is now spread out over multiple
subdirectories. These subdirectories need to be specifically mentioned in the sources
entry in the configuration file. This guarantees that when other people on your team
try to compile on a different platform (such as Windows vs macOS), all of the source code
files will be properly included.
Related to this, some of the source code files have to include headers in other directories.
This is the purpose of the angle-bracket includes in those source code files. Angle
brackets refer to a non-local header. They use a search path to find them. The
search path is specified as the includes entry in the configuration file. So in this
case, the angle brackets are all relative to the root folder source.
For example, look at the file GameController.cpp. Near the top, you will see these four
lines:
// This is in the same directory
#include "GameController.h"
// This is NOT in the same directory
#include <Input/InputController.h>
The header GameController.h is in the same folder, and is included using quotes. The
other header is included using angle brackets, specifying the path from the root.
With this in mind, you should run the CUGL script to make the project files for Visual Studio and/or XCode before continuing.
The Project Structure
Upon opening this project you’ll notice many folders and 3 top-level files: main,
App.cpp, and App.h. These files have been modified from the original files in
HelloCUGL to include the bare minimum necessary for this project. As this project
has no assets, there is no initialization of an AssetManager in TileApp.cpp.
You will also notice the initialization
_randoms = std::make_shared<std::mt19937>(seed);
in TileApp.cpp. std::mt199337 is a random number generator that is identical
on all platforms. This is crucial for testing purposes. When testing your
implementations, there are tilemap templates for random and procedurally generated
tiles that you should compare against our versions. Since we generated the templates
using the seed 42, the same sequence of random numbers will be generated each time
the project is run. This is psuedo-randomness. If you want the generated templates to
look different upon each project run, you should seed with the current time by inputting
time(0).
The folders are organized by the name of the module whose files they contain and a model, view, and controller. In the MVC sense, models store the game state, views display the state, and controllers calculate the state that is stored in the model and communicated to display to the view. This will be delved into deeper in the sections below when you are implementing code.
There are exceptions to this structure. The clearest exception are the CMV and MVC
folders which contain the Tilemap and Tile modules. These modules are written
inside namespaces conveniently named CMV and MVC to allow us to define the same
class in different files for your convenience (all you need to do to switch between
your implementations is including the files and using the namespace of the implementation
you want to test under GameController).
The other, more subtle, exception is that not all modules have all the components of MVC. This is because not all of your modules will need to store state or display information to the screen. In contrast, you’ll notice that all modules have at least a controller.
You may also notice that while controllers and views are (almost) always accompanied by
.cpp along with their .h files, models only have headers. This was an architecture
choice for this project to resemble the Entity-Component model where models are as
lightweight as possible. In this project, that means that your the models are only meant
for getting and setting values so including a .cpp for more complexity is unnecessary
compared to inlining functions within a header. In your game, it may make sense to include
helper functions for data transformation within the models.
The Basic Application
To get a better understanding of this project, take a look at the Input and Game
modules. One notable difference with this project and other CUGL project examples is
that the InputController no longer maintains state. The InputModel maintains states
we want to know about the mouse such as whether it was clicked, if it’s held down, and
where its last position was (useful when dragging). All variables are public to allow
for getting or setting them.
The InputController header has many sections. The first are its Internal References
which are either its models or views (if any). Notice that the reference to the
InputModel is a unique pointer. This is a smart pointer that can only exist in one
place. Since we want to convey the relationship that a model is communicated to only
by its respective controller, this is a great way to convey this ownership (i.e. the
InputController owns the InputModel). If we want to transfer ownership for any
reason, this is when we would use the std::move function to ‘move’ the pointer to
another place.
Next are its External References. While the Keyboard and Mouse are related to Input,
we separate these responsibilities. You can think of these classes as other modules whose
functionality we can use by communicating with its controller as a sub-controller. Strictly
speaking, however, looking at these classes reveals that state is maintained within them
so they do not follow MVC.
The Main Functions section is similar to in the InputModel. It has a constructor, as well
as functions related to the game flow, such as update, dispose, and reset. But while
InputController has a constructor, it is intended to be a singleton, meaning that only
one instance of it can exist. Therefore, the getInstance function is the intended way for
creating and retrieving it. The update function for this controller is intended
to align the inputs detected with the input callbacks (under the Input Callbacks section)
with the game frames. In particular, we need this method to buffer key presses so that they
are not lost if our framerate drops too low.
Finally, the Input State Getters section is where other controllers can interact with
the Input modules functionality. This, along with the Main Functions are the public
interface which define the relevant parts of this module that your team needs to know
in order to interact with all Input related things.
Now that you understand the basic structure of the application, you should compile and run
it. When you run this lab, a black square should appear on the bottom left of your screen
against a light background. This is the default TileMap that you will be implementing
in this assignment along with the Tile objects that will be placed on it. While there
are numerous inputs in this lab for testing purposes, they won’t do anything just yet
because you have functions to implement first.
NOTE: Actually, we mispoke. The black rectangle will only appear when you define the getters/setters of the model classes. You do not need to define the constructors or update/modify methods. But you do need the getter/setter methods.
CRC Cards
In this section you will learn more about how this project works. You will also fill out
partially filled Class-Responsibility Collaboration (CRC) cards inside the README.md
included in the project. For those new to the Game Design courses, you will fill out
CRC cards when doing your Architecture Specification.
Responsibilities
When working with classes, we often talk about the responsibilities of a class or
interface. These are the relevant parts of the module that your team needs to know in
to interact with them. For example specifications for the Main Functions and
Input State Getters outline the responsibilities of the Input module.
It is good for a team member to know about a module’s responsibilities so they understand
how it works when they using. It is also good for them to know about responsibilities that
may not be directly usable but do important work. For example, the InputController has
the responsibility to set up the mouse callbacks. Since the callback functions are
implemented as separate helper functions and the callbacks are setup in the initializer,
it takes multiple functions to satisfy this responsibility. In particular, this shows that
responsibilities and the functions that satisfy them won’t always be one-to-one mappings).
It is important to know this responsibility so a team member does not attempt to redudantly
set up mouse callbacks in a different module.
We will distinguish between these with the terms interface responsibilities and internal responsibilities respectively. The interface responsibilities should be clear from the public functions in the header (functions other modules can do things with) but the internal responsibilities may be subtler and be spread across multiple functions or consist of a single line of code like a controller initializing it’s respective model and view.
CRC Refresher
When creating your CRC cards for your game you are dividing responsiblities into organized modules. Each of these modules may have a model or view but always a controller in them. Since CRC cards follow the MVC pattern, there must always be a controller since the controller communicates with the model and the view. The model never directly communicates with the view.
The most important information about CRC cards are listing the responsibilities and collaborators.
In the case of the Input module, its Input State Getters section lists all of the
responsibilities. Looking at the implementation of these functions, it is very clear what
the collaborators for each responsibility should be based on where the data being returned
was retrieved from.
Before you get started with the next sections, check the README.md and fill out the CRC cards
for the Input and Game modules. It would also be a good idea to fill out the Tilemap,
Tile, and Generator cards before starting too. You should be able to figure out the
interface responsibilities through the header files but the internal responsibilities will
be provided and you should fill out the collaborators. You can always change these as you are
doing the assignment if you realize that you may have included an extra unnecessary collaborator
or if it’s necessary to have a collaborator to carry out a responsibility. This is a good skill
to train so you can plan out your architecture first before coding to understand how everything
connects together. This also helps when delegating work to members so you understand the order
in which things must be completed.
CMV Pattern
Before we start coding, we need to understand the CMV pattern. The CMV pattern is made up
(by us) and very similar to MVC except for one thing: it purposely violates the separation
between models and views. Why would we want to do this? Sometimes your code always has a
one-to-one relationship between models and views (scene graph nodes). In that case, the
extra separation may be unnecessary overhead. But in cases where there is no
one-to-one mapping (like SpaceDemo, which
uses ship movement to adjust several layers in parallax), it is less than ideal. The purpose
here is to get you to think about several ways of organizing your code.
In the CMV pattern we have 3 components: the controller, the model, and the view. The controller communicates with the model whenever state needs to be updated. The model will then communicate directly with the view whenever it is updated. The view will update itself based on whatever it receives and doesn’t communicate with any other component. Per our discussion in class, the view is at the bottom of the dependency DAG.
Game Module Structure
Before delving into the contents of the CMV folder, take a look at the Game module. This
module has been implemented for you and it is what you will use to verify your implementation
is working and what we’ll use to test your implementation. That is why it is important to avoid
overwriting anything here (feel free to add more later). You’ll notice some functions that
modify the tilemap you will be implementing. There are 5 of these functions, referred to as
templates, which can be accessed through the number keys 1 to 5. The first template generates
a yellow smiley face with a black smile. The second template generates randomly colored tiles
based on the provided probability. The third to fifth templates generate tiles using Perlin
noise and will be explained in more depth later in this assignment. In this section, you will
be using the first and second templates to test your implementation.
In addition to generating templates, you can modify them as well. Here is the control scheme
- The
-and=keys halve or double the size of the tilemap and its tiles. - The
[and]keys decrease or increase the number of columns in the tilemap by one. - The
;and'keys decrease or increase the number of rows in the tile map by one. - The
\key inverts the colors of the tilemap and its tiles - The
skey resets the random number seed, providing new random content.
All operations should keep the tilemap centered about its original position (the center of the screen for the provided templates). In addition, the operations that decrease the number of rows and columns should delete any tiles in the row or column.
The final important thing to note about the Game module are the include and using
statements. The MVC statements should be commented right now since you are working on
the CMV portion. When you move to the MVC portion of the assignment, comment out the
CMV include and using statements and uncomment the MVC statements. We will be doing
this to verify both that both of your implementations work.
Tilemap and Tile Modules
Open up the CMV folder and note the presence of the Tilemap and Tile modules. You will
be implementing functions whose bodies are marked with // TODO: IMPLEMENT ME. The function
headers will provide enough information for you to implement these functions. Make sure to
look both inside the .h and .cpp (if exists) files since some functions you need to
implement may be inline (implemented within the header file). Specifically, you will modify
the following files:
CMVTileModel.hCMVTileController.hCMVTilemapModel.hCMVTilemapController.cpp
For simplicity, we there is nothing for you to do in CMVTilemapController.h.
Some functions have already been implemented for you, particularly within the class
TilemapController. We recommend that you look at the methods
initializeTileMapclearMap
as they will give you some hint on how everything fits together. The method initializeTilemap
is a particularly good example of how to initialize a vector of unique pointers, since it is
very easy to get this wrong. If you come across any issues about a deleted copy constructor
when working with these pointers, look at how this function uses std::move.
There are an awful lot of methods to implement, but the vast majority of them are quite short.
For anything other than a constructor or the methods updateTileSize and updateDimensions,
you should rethink your implementation if it is longer than 5 lines.
The hardest functions are the last two controller methods in TilemapController: updateTileSize
and updateDimensions. Here our solutions are 10-15 lines long (and the functions modifyDimensions
and modifyTileSize use these functions as helpers). You will want to implement those
after you have confirmed that the basic templates work.
Testing
You should first make sure that you can get template #1 working. That template creates a smiley
face, as shown below. To get this far, you will need to implement all of the methods in
the *.h files. For TilemapController, you need to implement the Main, Model,
and View methods, but for the Controller Methods, you can ignore everything after
addTile. Once again, most of these functions are intended to be short.
Once that works, complete the final methods of TilemapController. You will then be able to
create more interactive images. Compare your implementation against these images generated by
our solution. For example, we generated the smiley shown below using template 1. We inverted
the colors, doubled its size, and increased the number of rows by 5. So the order opeations is
- Key
1for template number 1 - Key
\to invert the colors - Key
=to double the size - Key
'pressed 5 times to add more rows
We generated the random tiles below from template 2. In this case, we halved the size, decreased the numbers of rows and columns by 3, and then increased the number of columns by 3. This time to the order of operations is
- Key
2for template number 2 - Key
-to halve the size - Key
[pressed 3 times to remove columns - Key
;pressed 3 times to remove rows - Key
]pressed 3 times to add more columns
For the latter image, ensure that your seed has been unmodified and is still 42 and that
this is the first template you selected after launching the application.
MVC Pattern
Now that you have finished implementing CMV we will be working with the MVC folder and
refactoring your code to satisfy MVC. Once you have verified that your CMV implementation
works, do not modify those files again.
You still have the same Tilemap and Tile modules but you’ll notice a new file for the
Views. This was done to store all nodes inside of their own file. As we say in that file,
technically these classes do not do much more than a SceneNode, so it is not clear that
we needed this extra class, but it does help us understand the organization.
The more important variation with this pattern is that theModels no longer have a reference
to a scene graph node. This is so we can satisfy the MVC constraint that models and views
should never communicate with one another. So even if our view was just a simple PolygonNode,
that controller would now collaborate with the node, and not the model.
To complete this section, you should just be copying over your code and moving things
around so that the Controller passes the Model and View data. Remember to comment the
CMV include and using statements and to uncomment the MVC statements to test your refactor.
Otherwise you are only testing your CMV implementation. You should test your refactor the
same way you tested your CMV implementation, since they should behave exactly the same.
Submission
Due: Thu, Feb 02 at 11:59 PM
This assignment should be fairly easy to complete now that you have been working with C++ for two weeks. In addition, much of this lab is really about thinking about architectural issues, and not algorithmic issues.
Once again, you should limit what you send to use to reduce the burden on CMS. We want you to ZIP together the following:
- The
CMVfolder - The
MVCfile - The
README.mdfile
Anything else is not necessary for your submission. The file README.md should tell us if
you worked in Visual Studio or in XCode to help us grade your work. In addition, you should
have filled out the CRC cards with the desired information.
Submit this zip file as lab3code.zip to CMS
–
Appendix: Procedural Content
One of the hot topics in game development these days is procedural content generation (PCG). We will have a dedicated lecture on this later in the semester. To understand how this lab fits in with PCG, it is instructive to look at some recent examples.
PCG is often used to create randomized terrain in games like Minecraft. Roguelike games like Spelunky generate smaller levels on the fly that satisfy constraints (e.g. open path to exit, damsel on each level) but whose levels all look different.
Another roguelike game, The Binding of Issac, has fixed room templates, but the arrangement of the rooms are procedurally generated. Hades does much the same thing. These games show you do not need a fully PCG game to make each level fun and unique. Just adding tiny touches of PCG here and there can be enough to make your game very replayable. Check out this video from Florian Himsl, one of the developers of The Binding of Issac describing the ad-hoc nature of the level generation.
Now that we have implemented the Tilemap and Tile code, we can finally learn about
procedural generation. To get some myths out of the way, there is no standard way to use
a procedural content generation (PCG) method to solve a specific solution. Instead, you
will need to see what these methods are good for and repurpose them for your game.
In addition, PCG does not mean that you don’t need to think about level design. In fact
you will actually need a much stronger grasp of it to generate good levels. Let’s get into
it!
You will notice a commonality with all these games – they utilize grid systems. You have just implemented a tilemap. This means that you could use it to create procedurally generated content.
Perlin Noise
The code for this project has a module called Generator. This is used to implement
Perlin noise, a popular technique used in PCG. It is the technique that Minecraft
uses to generate its terrain. Though if if you take a
look at the official wiki for how
Perlin noise is used, you will notice how modified it is. There is no free lunch when
working with PCG, and each game has to modify algorithms to fit is specific style of
play.
Perlin noise is a type of gradient noise which works with interpolated random gradients as opposed to value noise which works with interpolated random values. Below we have examples of white noise (uniformly randomly distributed black and white pixels), value noise, and Perlin noise.
In our application, templates #3 - #5 all use the noise2D function in the
Generator module to lay out the tiles. Try it a few times. Press the s key
to get a new random tile. The debug output will display the random number
seed that generated that tilemap.
Performance Considerations
Something you should already understand is that PCG can take a long time to finish. The generator takes about a second to generate template #5, which is a 500 by 500 tilemap performing 8 octaves of fBM. That means a total of 2 million Perlin noise calculations need to be made. PCG is expensive. If you were to use this in your game, you need to use it in an intelligent way. In Minecraft the world is generated asynchronously in chunks as you move around which are despawned as you move away which is time and space efficient.
Another issue with procedural content generation is rendering it. Once again,
template #5 is a 500 by 500 tilemap. That means it has 250,000 scene graph nodes.
CUGL is performant, but that is a little much. When you select template #5, you
will note that the framerate drops to 6 fps (not 60 fps). Indeed, that is why
we had to design the InputController like we did – so it did not drop key presses
when the game slowed down.
An actual implementation would have a view for the tilemap, but not the individual
tiles. The tilemap would be represented as a
[Mesh