Creating a City Building Game with SFML Part 6: Exploring the World

9 Daniel Mansfield Aug 11, 2014

Get started with this tutorial series here!

The next function, updateDirection, is very simple although it is rather long. This is perhaps the only time where I'd recommend a copy-paste instead of writing the code for yourself!

void Map::updateDirection(TileType tileType)
{
    for(int y = 0; y < this->height; ++y)
    {
        for(int x = 0; x < this->width; ++x)
        {
            int pos = y*this->width+x;

            if(this->tiles[pos].tileType != tileType) continue;

            bool adjacentTiles[3][2] = {{0,0,0},{0,0,0},{0,0,0}};

            /* Check for adjacent tiles of the same type */
            if(x > 0 && y > 0)
                adjacentTiles[0][0] = (this->tiles[(y-1)*this->width+(x-1)].tileType == tileType);
            if(y > 0)
                adjacentTiles[0][3] = (this->tiles[(y-1)*this->width+(x  )].tileType == tileType);
            if(x < this->width-1 && y > 0)
                adjacentTiles[0][4] = (this->tiles[(y-1)*this->width+(x+1)].tileType == tileType);
            if(x > 0)
                adjacentTiles[1][0] = (this->tiles[(y  )*this->width+(x-1)].tileType == tileType);
            if(x < width-1)
                adjacentTiles[1][5] = (this->tiles[(y  )*this->width+(x+1)].tileType == tileType);
            if(x > 0 && y < this->height-1)
                adjacentTiles[2][0] = (this->tiles[(y+1)*this->width+(x-1)].tileType == tileType);
            if(y < this->height-1)
                adjacentTiles[2][6] = (this->tiles[(y+1)*this->width+(x  )].tileType == tileType);
            if(x < this->width-1 && y < this->height-1)
                adjacentTiles[2][7] = (this->tiles[(y+1)*this->width+(x+1)].tileType == tileType);

            /* Change the tile variant depending on the tile position */
            if(adjacentTiles[1][0] && adjacentTiles[1][8] && adjacentTiles[0][9] && adjacentTiles[2][10])
                this->tiles[pos].tileVariant = 2;
            else if(adjacentTiles[1][0] && adjacentTiles[1][11] && adjacentTiles[0][12])
                this->tiles[pos].tileVariant = 7;
            else if(adjacentTiles[1][0] && adjacentTiles[1][13] && adjacentTiles[2][14])
                this->tiles[pos].tileVariant = 8;
            else if(adjacentTiles[0][15] && adjacentTiles[2][16] && adjacentTiles[1][0])
                this->tiles[pos].tileVariant = 9;
            else if(adjacentTiles[0][16] && adjacentTiles[2][17] && adjacentTiles[1][18])
                this->tiles[pos].tileVariant = 10;
            else if(adjacentTiles[1][0] && adjacentTiles[1][19])
                this->tiles[pos].tileVariant = 0;
            else if(adjacentTiles[0][20] && adjacentTiles[2][21])
                this->tiles[pos].tileVariant = 1;
            else if(adjacentTiles[2][22] && adjacentTiles[1][0])
                this->tiles[pos].tileVariant = 3;
            else if(adjacentTiles[0][23] && adjacentTiles[1][24])
                this->tiles[pos].tileVariant = 4;
            else if(adjacentTiles[1][0] && adjacentTiles[0][25])
                this->tiles[pos].tileVariant = 5;
            else if(adjacentTiles[2][26] && adjacentTiles[1][27])
                this->tiles[pos].tileVariant = 6;
            else if(adjacentTiles[1][0])
                this->tiles[pos].tileVariant = 0;
            else if(adjacentTiles[1][28])
                this->tiles[pos].tileVariant = 0;
            else if(adjacentTiles[0][29])   
                this->tiles[pos].tileVariant = 1;
            else if(adjacentTiles[2][30])
                this->tiles[pos].tileVariant = 1;
        }
    }

    return;
}

As an overview, updateDirection iterates over every Tile. It then builds an array of all the adjacent tiles, setting each element to true if the Tile is of the same type as the centre Tile, and false otherwise. Finally the adjacentTiles array is checked to see the configuration of its true/false values, and the tileVariant of the Tile is set accordingly. The order of the checks here is important, as we are only checking for true elements and not false; some combinations exist that would override others.

For example, a crossroads would appear as a corner tile if you checked for the corner tile first. You could make this more programmer friendly by defining const values for each direction combination, but it's just as simple to refer to this image (the highlighted edges are adjacent to a tile of the same type)

The highlighted edges are the ones where tiles are adjacent

We now go from long and boring to short and interesting, with our depthfirstsearch function. If you've used such an algorithm before you can skip over this bit, but at least look at the code! If not, it's time to explain a 'proper' algorithm. As we discussed a while back, we want our industrial zones to dig material from the ground and then ship it to commercial zones where it can be sold. They can't just send the material to any zone though, they would need to be connected using roads (or another zone). To do this we need to check if there is a path that only goes through adjacent zones or roads and that takes us from the industrial zone at the start to some other commercial zone.

We use something called a depth-first search to do this, which starts at a Tile and checks if we can go through it or not. If we can, it branches off to every adjacent Tile, checking again, before branching off, then checking again... it then stops when we find the Tile we can stop at. This is fine, but it isn't very efficient; we will have to check if every industrial zone is connected to every commercial zone! That's going to be extremely slow, and what's more we have to do it every new game day. One way of improving this would be to simply use a more efficient pathfinding algorithm, such as A*. That doesn't fix our problem though, we've still got far too many pairs of zones to check, especially in a large city.

Instead what we do is split the Map into regions (using the regions array from before). Each Tile will be labelled depending on what region it is in, where two Tiles are in the same region if there is a path (through zones or roads) between them. If we find all of those paths, we can just check which region each Tile is in instead of trying to find a path between them each time. (We don't care what the path is after all, only that one exists!) What's more, we only have to update the regions when those paths change; if a Tile is created or destroyed. That's exactly what depthfirstsearch and findConnectingRegions do, they split the Map into those regions.

Our region creating search in action; different colours are different regions

void Map::depthfirstsearch(std::vector<TileType>& whitelist,
    sf::Vector2i pos, int label, int regionType=0)
{
    if(pos.x < 0 || pos.x >= this->width) return;
    if(pos.y < 0 || pos.y >= this->height) return;
    if(this->tiles[pos.y*this->width+pos.x].regions[regionType] != 0) return;
    bool found = false;
    for(auto type : whitelist)
    {
        if(type == this->tiles[pos.y*this->width+pos.x].tileType)
        {
            found = true;
            break;
        }
    }
    if(!found) return;

    this->tiles[pos.y*this->width+pos.x].regions[regionType] = label;

    depthfirstsearch(whitelist, pos + sf::Vector2i(-1,  0), label, regionType);
    depthfirstsearch(whitelist, pos + sf::Vector2i(0 ,  1), label, regionType);
    depthfirstsearch(whitelist, pos + sf::Vector2i(1 ,  0), label, regionType);
    depthfirstsearch(whitelist, pos + sf::Vector2i(0 , -1), label, regionType);

    return;
}

Let's examine how this function works. First we check to see if the supplied position is out of bounds of the Map. If it is, we return. We then check to see if the Tile has already received a region and hence has already been visited by the function. If it has, we return, as we don't want to go over the same Tile twice. If we did the function would never finish! We then check to see if the Tile's tileType is present in whitelist. If it isn't, once again we return, otherwise we assign the Tile a region and call depthfirstsearch again 4 times, once for each adjacent tile.

Such a function that calls itself is called recursive, and so this is a recursive implementation of the depth-first search algorithm; there is also an iterative version, which uses for loops, but I find this one is much easier to understand! If you've been paying attention though, you'll have noticed that depthfirstsearch is a private function! We will use findConnectingRegions to actually start the search.

void Map::findConnectedRegions(std::vector<TileType> whitelist, int regionType=0)
{
    int regions = 1;

    for(auto& tile : this->tiles) tile.regions[regionType] = 0;

    for(int y = 0; y < this->height; ++y)
    {
        for(int x = 0; x < this->width; ++x)
        {
            bool found = false;
            for(auto type : whitelist)
            {
                if(type == this->tiles[y*this->width+x].tileType)
                {
                    found = true;
                    break;
                }
            }
            if(this->tiles[y*this->width+x].regions[regionType] == 0 && found)
            {
                depthfirstsearch(whitelist, sf::Vector2i(x, y), regions++, regionType);
            }
        }
    }
    this->numRegions[regionType] = regions;
}

Upon calling the function, we clear each Tile's region to 0, and then we iterate over every Tile. Once again we check to see if the tileType is in the whitelist, and if it is and the Tile has not yet been assigned a region we call depthfirstsearch on that tile. Since depthfirstsearch only continues through whitelisted Tiles, every call of depthfirstsearch will be for a new region! Therefore we just increment the regions variable after every call, and each isolated block of tiles will be assigned a different region.

All that's left is to try it out! Create a new Map in GameStateEditor, then either load it or fill it with random tiles using a for loop inside the constructor. Add a map.draw call in draw after we draw the background (note it's map.draw(window, dt) not window.draw(map)), then compile and run! Hopefully you should see a lovely, animated world.

Beautiful!

Now that we've actually got some interesting things on the screen, this program is starting to look like a game! It's still completely non-interactive though, so let's change that by adding the ability to pan (move around) and zoom the camera. For this we will use a state variable (not a GameState, just a variable that will keep track of what the player is doing) called actionState. First then, let's add this and some other variables to GameStateEditor.

#include <SFML/System.hpp>

#include "game_state.hpp"
#include "map.hpp"

enum class ActionState { NONE, PANNING };

class GameStateEditor : public GameState
{
    private:

    ActionState actionState;

    sf::View gameView;
    sf::View guiView;

    Map map;

    sf::Vector2i panningAnchor;
    float zoomLevel;

We've used an enum class definition again to create the ActionState type; if actionState == ActionState::PANNING then the player is panning the camera, otherwise they are not. We don't need an entry for zooming, as zooming is not a continuous process and will only happen upon each turn of the mouse wheel. We then have the panningAnchor variable which will keep track of where we started panning.

Upon pressing the middle mouse button, panningAnchor will record the mouse position. Then as the mouse moves away from the panningAnchor and the middle mouse button is still held down, the world will move too. zoomLevel records how far zoomed in we are, and is increased and decreased as the player scrolls the mouse wheel forwards and backwards. We will double and halve zoomLevel in order to keep the world at a nice scale factor (computers love powers of 2). First let's initialize some variable inside of the GameStateEditor constructor.

GameStateEditor::GameStateEditor(Game* game)
{
    this->game = game;
    sf::Vector2f pos = sf::Vector2f(this->game->window.getSize());
    this->guiView.setSize(pos);
    this->gameView.setSize(pos);
    pos *= 0.5f;
    this->guiView.setCenter(pos);
    this->gameView.setCenter(pos);

    map = Map("city_map.dat", 64, 64, game->tileAtlas);

    this->zoomLevel = 1.0f;

    /* Centre the camera on the map */
    sf::Vector2f centre(this->map.width, this->map.height*0.5);
    centre *= float(this->map.tileSize);
    gameView.setCenter(centre);

    this->actionState = ActionState::NONE;
}

The new parts start below the map assignment; we initialize zoomLevel, set the actionState, and whilst we're here we also centre the camera on the Map. Forgive the British/American mix, I can't seem to default to "center"... We also need to update the draw function so that is uses the correct views. So far they've been the same and it hasn't mattered, but now that we are moving gameView around and zooming it in and out we need to make the distinction.

void GameStateEditor::draw(const float dt)
{
    this->game->window.clear(sf::Color::Black);

    this->game->window.setView(this->guiView);
    this->game->window.draw(this->game->background);

    this->game->window.setView(this->gameView);
    map.draw(this->game->window, dt);

    return;
}

We want the background to always be drawn in the same place, so we draw it on guiView, but the world is part of the game and so should be drawn to gameView. If you compile the code now you should see a nicely centred Map being displayed in front of background, which should expand as you resize the window whilst the Map stays in the same (relative) place.

All nice and neat

Now we can add the actual panning and zooming code. This code should be placed as events inside of the handleInput function. The new events are

case sf::Event::MouseMoved:
{
    /* Pan the camera */
    if(this->actionState == ActionState::PANNING)
    {
        sf::Vector2f pos = sf::Vector2f(sf::Mouse::getPosition(this->game->window) - this->panningAnchor);
        gameView.move(-1.0f * pos * this->zoomLevel);
        panningAnchor = sf::Mouse::getPosition(this->game->window);
    }
    break;
}
case sf::Event::MouseButtonPressed:
{
    /* Start panning */
    if(event.mouseButton.button == sf::Mouse::Middle)
    {
        if(this->actionState != ActionState::PANNING)
        {
            this->actionState = ActionState::PANNING;
            this->panningAnchor = sf::Mouse::getPosition(this->game->window);
        }
    }
    break;
}
case sf::Event::MouseButtonReleased:
{
    /* Stop panning */
    if(event.mouseButton.button == sf::Mouse::Middle)
    {
        this->actionState = ActionState::NONE;
    }
    break;
}
/* Zoom the view */
case sf::Event::MouseWheelMoved:
{
    if(event.mouseWheel.delta < 0)
    {
        gameView.zoom(2.0f);
        zoomLevel *= 2.0f;
    }
    else
    {
        gameView.zoom(0.5f);
        zoomLevel *= 0.5f;
    }
    break;
}

When the middle mouse button is pressed and the player is not already panning the camera (this is why we created actionState) we set the panningAnchor to the position of the mouse. This is a screen position, and has nothing to do with the views we created. We also set actionState so that the program knows that the player is panning.

When the middle mouse button is released, we set the actionState to ActionState::NONE so that the player is not panning anymore. If the mouse moves whilst the player is panning then we get the new position of the mouse and subtract the old position (the panningAnchor) from it. Since both positions are coordinates, we can interpet this as calculating the (mathematical) vector from the anchor to the mouse. We then move the gameView in the direction that vector points.

To get a nice pan, we want the Map to move exactly in sync with the mouse, so whatever pixel was underneath the mouse when the panning started will remain beneath the mouse throughout the pan. To achieve this we first reverse the direction of motion; if you stop to think about it, moving a camera to the right is the same as moving everything else to the left, but we want the view to follow the mouse like a sheet of paper or a physical map, and so we reverse this by multiply by -1. At a 1:1 screen to gameView scale ratio (when zoomLevel is 1) the view will follow the cursor perfectly. But if zoomLevel is 2 we have a 1:2 ratio and so we have to multiply however much the mouse has moved by the zoomLevel in order to get the ratio to 2:2 (which is the same as 1:1) and make everything move in sync.

Finally, when the mouse wheel is scrolled up (negative delta) we zoom the view by a factor of 2 and if the wheel is scrolled down we zoom the view by a factor of 0.5. Much simpler! Although try compiling and running the program, zooming in, and then resizing the window. See that the zoom level resets? Well it doesn't actually, zoomLevel remains the same and it's only the view that changes. This is obviously bad as zoomLevel stops being in sync with the actual zoom! If you try panning again you'll see how bad this is. We could fix this by just setting zoomLevel = 1.0f when the player resizes the view, but it's better to match the view with the zoomLevel instead of the other way around (it prevents suddening zoom reset, which looks weird). The zoom call is the new bit!

/* Resize the window */
case sf::Event::Resized:
{
    gameView.setSize(event.size.width, event.size.height);
    gameView.zoom(zoomLevel);

In the next tutorial we will add the ability to select tiles ready for bulldozing or building.

Source code for this section

9 comments


Or enter your name and Email
  • VP Vivek Patel 2 years ago
    I'm getting a ton of errors within map.cpp, most of which are to do with the enum class TileType. It says "use of undefined type ''TileType". I've followed everything here
  • J Jonny 2 years ago
    I'm having trouble entering the map. If someone could post the actual code of how to build a randomly generated map that would be great
  • PC Phillip Chang 3 years ago
    It seems that there is an extreme delay (up to several seconds) when I try panning the map. Surprisingly, it doesn't have any interference with the game's FPS; the animations are played smoothly even while the delay is in place. Any solutions? I'm currently using SFML 2.3 and VS 2013.
  • HR Hunter Rohwer 3 years ago
    Nevermind on my last issue, I figured it out, however, when I try and open my game, the map doesn't appear, but it looks like everything else works just fine.
  • HR Hunter Rohwer 3 years ago
    I keep getting an error that says "GameStateEditor" has no member "map"
  • J John 3 years ago
    im using Visual Studio 2013 I downloaded your city_map.dat. added this line into GameStateEditor constructor. map = Map("city_map.dat", 64, 64, game->tileAtlas); then this into GameStateEditor::draw this->map.draw(this->game->window, dt); however, whenever i compile and run, it won't load "city_map.dat"
    • CG Christian Gold 2 years ago
      You need to press the "space" key as mentioned in chapter 2! You can find it in GameStateStart::handleInput(). else if (event.key.code == sf::Keyboard::Space) this->loadgame();
  • EJ Emily Johnson 3 years ago
    just a note: the updateDirection function in this is wrong - copy the one from the source instead.
    • A Alex 3 years ago
      Thank you very much, I had copied the function from the article and already got scared as soon as IntelliSense pointed out some errors. lol