Top-Down Roguelike Game, some doubts and thoughts.

[gabrieljt]

Hello,

I'm doing some experiments, the idea is to make a simple top down roguelike game. I'm new to game development, but I'm feeling lucky
I've also read the SFML Game Development book, which is great, so I will be using many of it's ideas.

First things first, I wanted to create a Dungeon with Floor and Wall tiles and a movable Character.
So I created my Character and Tile entities and built the Dungeon Scene.

I've found some cool assets http://opengameart.org/content/dawnlike-16x16-universal-rogue-like-tileset-v17 that I will be using for the time being.

Tiles are 16x16, and I'm using a 12x16 TextureRect for the Character.
Right now, the character moves freely in the Dungeon, so I thought it would be better to center the origin of the Character and the Tile to their Sprite centers. Due to this, I had to add an offset to the Tile position for generating a 10x10 Dungeon, like in the first image. I've set the visible area to a 5x5 cells, that's why you are not seeing the entire room. The View zoom is being applied.

Related code so far:

// the following snippet in buildScene() generates a square room with no door and a wall tile at map[3][3]

const auto tilemapSize = 10u;  // 10x10 cells
mDungeonBounds = sf::FloatRect(0.f, 0.f, Tile::Size * tilemapSize, Tile::Size * tilemapSize); //160x160 pixels
       
for (auto x = 1u; x < tilemapSize - 1u; ++x)
        for (auto y = 1u; y < tilemapSize - 1u; ++y)
        {
                if (x != 3u || y != 3u)
                 {
                        Tile::TileID id(x, y);
                        addTile(id, Tile::Type::Floor);
                 }
        }
        addTile(Tile::TileID(3u, 3u), Tile::Type::Wall);
        for (auto i = 0u; i < tilemapSize; ++i)
        {
                Tile::TileID firstRow(i, 0u);
                Tile::TileID lastRow(i, tilemapSize - 1);
                Tile::TileID firstColumn(0u, i);
                Tile::TileID lastColumn(tilemapSize - 1, i);
                addTile(firstRow, Tile::Type::Wall);
                addTile(lastRow, Tile::Type::Wall);
                addTile(firstColumn, Tile::Type::Wall);
                addTile(lastColumn, Tile::Type::Wall);
        }
       
// spawns player at map[5][5]
Tile::TileID tileId(5u, 5u);
mSpawnPosition = sf::Vector2f(tileId.first * Tile::Size + Tile::Size / 2, tileId.second * Tile::Size + Tile::Size / 2);

/*---------------*/

void Dungeon::addTile(Tile::TileID id, Tile::Type type)
{
        std::unique_ptr<Tile> tilePtr(new Tile(type, mTextures, mFonts, id));  
        auto tile = tilePtr.get();
        // Tile has centered origin    
        tile->setPosition(id.first * Tile::Size + Tile::Size / 2, id.second * Tile::Size + Tile::Size / 2);
        mSceneLayers[Main]->attachChild(std::move(tilePtr));
}

void Dungeon::setupView()
{
        auto visibleArea = Tile::Size * 5u; // 5x5 cells
        auto zoom = visibleArea / std::min(mView.getSize().x, mView.getSize().y);      
        mView.setCenter(mSpawnPosition);       
        mView.zoom(zoom);
}
 

1) Drawing the Dungeon

As you may have noticed, I'm attaching all the Tiles as SceneNodes.
Also, each Tile is calling it's own draw method.

At this point you may be thinking that I'm completely lost, but I did read some stuff and I am aware of these problems
But I still have doubts and need help on how to solve them.

First, the drawing problem.
The Tiles share the same Texture, and their TextureRects are initialized in the DataTable.
Is it okay to draw them with the draw calls since they are sharing the same Texture, or should I build a VertexArray?
If i use the VertexArray, what happens if a Tile is destroyed? Can I change the data of the VertexArray at runtime? Or do I need to update the TileMap and rebuild the VertexArray? 

I think it is interesting to make a Tile an Entity.
One direct optimization that could be done is creating a BaseTile that is walkable and has no effects, not even destroyable. If using the VertexArray, this Tile does not even has to be attached to the SceneNode, reducing the number of SceneNodes, which raises my second question:

2) Space Partitioning

Right now, in a 10x10 Dungeon there are 101 SceneNodes, including the Character.
Still runs at 60fps in a 11x11 Dungeon, but when it's 12x12, it's totally unplayable with 1fps.

I'm still reading about Grid and Quadtrees and this topic http://en.sfml-dev.org/forums/index.php?topic=13766.0.

But I do have a design question.
Each SceneNode has a vector with pointers to their children and a pointer to it's parent.
Suppose I want to adapt this to a 4x4 Grid structure, four 5x5 Cells that maps the 10x10 dungeon.
Is it simple as creating 4 SceneGraphs for the 4 Cells of the room and attach nodes to the graphs depending on their positions?
Then i just update the current Cell.
Data Structures are underestimated, I must be missing something  . Haven't tried this yet though.

3) Wall Collisions

Before diving into problems 1 and 2, I've decided to implemented wall collisions, just to fool around the map and see if I could do it.
After struggling many hours I've came to a working solution 

I've tried to keep in mind the axis of least penetration idea, as explained here: http://gamedevelopment.tutsplus.com/tutorials/create-custom-2d-physics-engine-aabb-circle-impulse-resolution--gamedev-6331 (AABB vs AABB)

Here's the collision code:

        if (matchesCategories(pair, Category::Character, Category::UnwalkableTile))
                {
                        auto& character                 = static_cast<Character&>(*pair.first);
                        auto& tile                              = static_cast<Tile&>(*pair.second);
                        auto characterBounds    = character.getBoundingRect();
                        auto characterPosition  = character.getPosition();                     
                        auto tileBounds                 = tile.getBoundingRect();
                        auto tilePosition               = tile.getPosition();

                        // check X axis penetration through left or right
                        auto penetrationX               = std::min(std::abs(tileBounds.left + tileBounds.width - characterBounds.left)
                                                                                                , std::abs(characterBounds.left + characterBounds.width - tileBounds.left));
                        // check Y axis penetration through up or down
                        auto penetrationY               = std::min(std::abs(tileBounds.top + tileBounds.height - characterBounds.top)
                                                                                                , std::abs(characterBounds.top + characterBounds.height - tileBounds.top));
                        auto penetratingAxis    = std::min(penetrationX, penetrationY);
                        auto collideX                   = penetratingAxis < penetrationY;

                        if (collideX)
                        {
                                // Colliding Left
                                if (characterPosition.x > tilePosition.x)
                                        character.setPosition(characterPosition.x + penetrationX, characterPosition.y);
                                // Colliding Right
                                else
                                        character.setPosition(characterPosition.x - penetrationX, characterPosition.y);
                        }
                        else
                        {
                                // Colliding Top
                                if (characterPosition.y > tilePosition.y)
                                        character.setPosition(characterPosition.x, characterPosition.y + penetrationY);
                                // Colliding Bottom
                                else
                                        character.setPosition(characterPosition.x, characterPosition.y - penetrationY);
                        }              
        }
 

Works quite well. Screenshot 2 show character at the corner with LEFT and UP being pressed, and screenshot 3 just after both keys are released.
Character slides smoothely throught when both keys are pressed, however it will get stuck sometimes when near the corners (haven't discovered why yet). Screenshot 4 shows this case.

Character never gets stuck if only one key is pressed, and no bizarre repositionings are happening. Collision with that single block near the corner works perfectly in all directions and with all movement combinations. I'm satisfied with the results for now, but I do want to get rid of that corner stuck situation

Well.... this is it, for now.
Sorry for the long post, and thank you very much for your attention.

Thank you all SFML collaborators, I'm happy learning game development without sticking with those fancy engines full of options. I may put them to good use one day, but I don't think they are adequate for beginners at game development.
I have a CS background (not that it means much xD), and SFML Game Development Book really cleared many things out for me  The coding style and patterns made me give C++ a second chance, and I'm enjoying it a lot! (spent my last years working with IT).

And here is the code so far, you may build the project with CMake.
https://github.com/gabrieljt/Dungeons

- Gabriel

[eXpl0it3r]

1) You should use a VertexArray, it will give you way more frame time, i.e. your performance will be a lot better. Usually you update the tilemap and the update the rebuild the vertex array.

2) With a VertexArray you should already be able to draw grids beyond 12x12 without issues.
I'd have my doubts whether a scene graph is appropriate here. Personally I'd just go with a simple class that generates the tile map and a vertex array for drawing it. The scene graph would be used for entities etc.

3) I'd have to fully understand the collision code, but I don't have enough time...

[gabrieljt]

1) Thanks, now it is more clear to me.

2) But if Tiles are not Scene Nodes, how could I detect collision with Tiles?
Thought of returning the Tiles in the Tilemap based on the character's position.
But I think this will add complexity for handling events between the entities and the tiles.

3) Haha, it's okay. But I think I know whats wrong now.
There are a few cases when colliding with 2 tiles and/or at diagonal position that it doesnt work as expected. I am applying the least penetration axis idea but I think I didn't calculate the penetration as the normal vector, as explained in the artcile.

Thank you

[Cirrus Minor]

Still runs at 60fps in a 11x11 Dungeon, but when it's 12x12, it's totally unplayable with 1fps.

A map so small as 12x12 shouldn't cause this huge slowing 
Why don't you just use, for exemple, a logical and a graphical map ? I'm doing so for my roguelite, it's quite fast and not so complex !

[gabrieljt]

I understand the benefits of using a logical tilemap and drawing it with a Vertex Array, it is the way to go.

I was tempted to make Tile an Entity because of games like Minecraft, Terraria, Starbound... Tiles (Blocks) in those games feels like they are true game objects instead of logical tiles. But they must be using complex data structures to achieve this.

I want the character to move freely in the Dungeon, like an oldschool action rpg (Zelda, Alundra). But it still not clear to me how to handle collisions when using a logical tilemap...

Will do some experiments and research, thanks again

[eXpl0it3r]

I was tempted to make Tile an Entity because of games like Minecraft, Terraria, Starbound... Tiles (Blocks) in those games feels like they are true game objects instead of logical tiles. But they must be using complex data structures to achieve this.

Yes the blocks you can interact with a probably some sort of entities as well, but just look at the background. The background is also built from tiles but it's static as your tile map would be.

I want the character to move freely in the Dungeon, like an oldschool action rpg (Zelda, Alundra). But it still not clear to me how to handle collisions when using a logical tilemap...

The graphical representation doesn't have to have anything in common with the logical representation. For the collision logic you could have a simple std::vector<bool> and every coordinate that is true can't be passed. For more complex systems you could use a vector of your own enum, so you could add/check against nicer names.

[gabrieljt]

thank you for your replies, they were enlightening.

i've had some progress

i made a Tilemap class, which has a std::map<Tile::ID, TilePtr> and a VertexArray.
in its constructor, the map is populated and then the vertex array is built accessing the map for each tile and retrieving the tile texture rect in the tileset texture.

the Tilemap is a SceneNode, and it is attached to the Background SceneLayer. this way it's drawCurrent() method is easily called and even more, i can handle collision properly!

since i have all the tiles in the tilemap and the character's coordinates, i can access O(1) the tile he is on converting his coordinates to a TileID, which is great.
no need to attach the tiles to the scene graph, really xD.

some related code:

// buildScene()
    // Build Map
        std::unique_ptr<Tilemap> tilemap(new Tilemap(mTextures));
        mTilemap = tilemap.get();
        mTilemap->setPosition(0.f, 0.f);
        mSceneLayers[Background]->attachChild(std::move(tilemap));

        // Add player's character
        std::unique_ptr<Character> player(new Character(Character::Player, mTextures, mFonts));
        mPlayerCharacter = player.get();
        mSpawnPosition = mTilemap->getTile(Tile::ID(50u, 50u))->getPosition();
        mPlayerCharacter->setPosition(mSpawnPosition);
        mSceneLayers[Main]->attachChild(std::move(player));

// handleCollision()
    if (matchesCategories(pair, Category::Character, Category::Tilemap))
        {
                auto& character = static_cast<Character&>(*pair.first);
                auto tile = mTilemap->getTile(character.getPosition());
                auto tileID = tile->getID();
        if (tile->isWalkable())
                std::cout << "I'm here: " << tileID.first << " " << tileID.second << std::endl;
        }
 

very nice, im enjoying this!
was able to create a 1000x1000 world that ran with 30fps, just a stress test.
500x500 runs like a charm.

however, i still have a doubt related to C++.

im using a resouce holder that keeps the texture.
the drawCurrent() needs the texture, is it okay to store it in the tilemap like this?

public:
    Tilemap(const TextureHolder& textures);
private:
    const sf::Texture                   mTileset;

Tilemap::Tilemap(const TextureHolder& textures)
: SceneNode(Category::Tilemap)
, mTileset(textures.get(Textures::Tiles))
, mSize(100u, 100u)
, mBounds(0.f, 0.f, mSize.x * Tile::Size, mSize.y * Tile::Size)
, mImage()
, mMap()
{
/* populates mMap and builds mImage */
}

void Tilemap::drawCurrent(sf::RenderTarget& target, sf::RenderStates states) const
{
        // apply the transform
        states.transform *= getTransform();
   
        // apply the tileset texture
        states.texture = &mTileset;

        // draw the vertex array
        target.draw(mImage, states);
}
 

what is happening in the constructor?
am i copying the texture on is it just a reference to the texture holder?
the const thingy is not that clear to me... why some functions have const, like this:

virtual unsigned int    getCategory() const;
 

also, i'm using a shared_ptr to keep the tiles in the map, like this:

public:
    typedef std::shared_ptr<Tile> TilePtr;
private:
    std::map<Tile::ID, TilePtr> mMap;  

void Tilemap::addTile(Tile::ID id, Tile::Type type, const TextureHolder& textures)
{
        // TODO: assert inserted
        TilePtr tile(new Tile(id, type, textures));
        tile->setPosition(id.first * Tile::Size, id.second * Tile::Size);
        mMap[id] = tile;
}

Tilemap::TilePtr Tilemap::getTile(Tile::ID id)
{
        return mMap[id];
}

Tilemap::TilePtr Tilemap::getTile(sf::Vector2f position)
{
        Tile::ID id(position.x / Tile::Size, position.y / Tile::Size);
        return mMap[id];
}
 

at first, i tried to use a std::map<Tile::ID, Tile*>, but it didnt go well.
then i tried the unique_ptr, and i didn't manage to read only the contents of the map, i've had to std::move() and it was breaking the map.
shared_ptr worked fine, but i need to study more about this too... is this fine by now?

thanks again!!!

edit
-------

iv'e used the collision code that i posted before using a if (!tile->isWalkable()) in the collision check and it worked!
but the collision happens only when the character is penetrating more than it should, occupying the cell.
i need to retrieve the neighbors too, but that should be easy.

also, it was a great tip about tile being pure virtual, and now it is not associated to texture anymore

if anyone is interested, just check the repo, i'm all ears.

edit 2
---------

after all this big refactoring, i've finally achieved the same results as in the OP, but with a huge room and various changes in the design.
even that damned collision bug persisted, but it is okay for now.

the screenshots are 1440x900, with a 100x100 dungeon room, 10x10 visible are of 16x16 tiles.
the last one is a 1000x1000 room with zoom out to see it entirely the character is under the 'P' of "FPS".

time to research procedural dungeon generation, i guess.

but i need a break... for now

thanks!

[SeriousITGuy]

Hey gabrieljt,
I am very much doing the same thing, also based on the book SFML Game Development
I'm not as far as your project, I'm still stuck in the basic framework and will start the dungeon topic in a few days hopefully. About the basic framework we are both doing things equally and I'm looking forward to read your dungeon class
Maybe I will fork your project, here is mine if interested https://github.com/SeriousITGuy

Cheers

[gabrieljt]

nice!

i've stopped coding for a while, but the latest version @ github now generates a "random" dungeon with some entities and a general bounds collision since it takes a pair of SceneNodes.

the communication between the game logic layer and the tilemap layer exists, but the Tilemap API requires some refactoring though.

entities outside the view bounds are cleared, but their spawn points are kept if they are still alive, huge dungeons with a nice number of entities can be created.

it's working quite nice, feel free to fork and do whatever you want with it

i'm also studying OpenCL at work, so i might implement parallel collision detection someday for learning purposes.

i am now reading this book:
http://www.artofgamedesign.com/

while coding, i always have the feeling i am making an empty prototype and just learning more about specific techniques instead of making a game, but i will surely come back to coding one day

[xethm55]

Looking through the code, it appears that your collision bug is a result of only handling x or y collisions but never both.  I'd suggest the following fix:

       
        if (matchesCategories(pair, Category::Character, Category::UnwalkableTile))
        {
            auto& character         = static_cast<Character&>(*pair.first);
            auto& tile              = static_cast<Tile&>(*pair.second);
            auto characterBounds    = character.getBoundingRect();
            auto characterPosition  = character.getPosition();        
            auto tileBounds         = tile.getBoundingRect();
            auto tilePosition       = tile.getPosition();

            // check X axis penetration through left or right
            auto penetrationX       = std::min(std::abs(tileBounds.left + tileBounds.width - characterBounds.left)
                                                , std::abs(characterBounds.left + characterBounds.width - tileBounds.left));
            // check Y axis penetration through up or down
            auto penetrationY       = std::min(std::abs(tileBounds.top + tileBounds.height - characterBounds.top)
                                                , std::abs(characterBounds.top + characterBounds.height - tileBounds.top));

            // Only correct if the difference is large enough
            if (penetrationX > 0.05)
            {
                // Colliding Left
                if (characterPosition.x > tilePosition.x)
                    character.setPosition(characterPosition.x + penetrationX, characterPosition.y);
                // Colliding Right
                else
                    character.setPosition(characterPosition.x - penetrationX, characterPosition.y);
            }
           
            // Correct Y if the penetration depth is large enough
            if(penetrationY > 0.05)
            {
                // Colliding Top
                if (characterPosition.y > tilePosition.y)
                    character.setPosition(characterPosition.x, characterPosition.y + penetrationY);
                // Colliding Bottom
                else
                    character.setPosition(characterPosition.x, characterPosition.y - penetrationY);
            }      
        }
 

Edit
Note the 0.05 can be tuned to work, it was just a value I pulled from the ether.

[gabrieljt]

hello and thank you for your answer.

i may try it later.

the latest code is more generic

void handleBoundsCollision(SceneNode& lhs, SceneNode& rhs)
{
        auto lhsBounds                  = lhs.getBoundingRect();
        auto rhsBounds                  = rhs.getBoundingRect();
        // check X axis penetration through left or right
        auto penetrationX               = std::min(std::abs(rhsBounds.left + rhsBounds.width - lhsBounds.left)
                                                                                , std::abs(lhsBounds.left + lhsBounds.width - rhsBounds.left));
        // check X axis penetration through up or down
        auto penetrationY               = std::min(std::abs(rhsBounds.top + rhsBounds.height - lhsBounds.top)
                                                                                , std::abs(lhsBounds.top + lhsBounds.height - rhsBounds.top));
        // the least penetrating axis
        auto penetratingAxis    = std::min(penetrationX, penetrationY);
        auto penetratingX               = penetratingAxis < penetrationY;

        auto lhsPosition                = lhs.getPosition();                   
        auto rhsPosition                = rhs.getPosition();
        // adjust positions, Tile does not have centralized origin
        if (lhsPosition.x == lhsBounds.left || lhsPosition.y == lhsBounds.top)
                lhsPosition = sf::Vector2f(lhsBounds.left + Tile::Size / 2.f, lhsBounds.top + Tile::Size / 2.f);
        if (rhsPosition.x == rhsBounds.left || rhsPosition.y == rhsBounds.top)
                rhsPosition = sf::Vector2f(rhsBounds.left + Tile::Size / 2.f, rhsBounds.top + Tile::Size / 2.f);

        if (penetratingX)
        {
                // Colliding Left
                if (lhsPosition.x > rhsPosition.x)
                        lhs.setPosition(lhsPosition.x + penetrationX, lhsPosition.y);
                // Colliding Right
                else
                        lhs.setPosition(lhsPosition.x - penetrationX, lhsPosition.y);
        }
        else
        {
                // Colliding Top
                if (lhsPosition.y > rhsPosition.y)
                        lhs.setPosition(lhsPosition.x, lhsPosition.y + penetrationY);
                // Colliding Bottom
                else
                        lhs.setPosition(lhsPosition.x, lhsPosition.y - penetrationY);
        }                      
}
 

but i gave up on this game idea, i was just implementing mechanics after all, with no game in mind.

but i've had some inspiration and i already know what i want to do. there is now much planning and work to do, it will take me some time before i start coding.

best regards,

- Gabriel

[Nexus]

By the way, this topic should be moved to projects (if the intent is to present what you've done) or help (if the focus lies on discussing the techniques). Probably the latter.

But it's not a general discussion about SFML.

[gabrieljt]

By the way, this topic should be moved to projects (if the intent is to present what you've done) or help (if the focus lies on discussing the techniques). Probably the latter.

But it's not a general discussion about SFML.

agreed.

sorry for the inconvenience