RogueLike - Map and Entities - how to store it?

Question

Started to write my own RL, and already fell into analysis (paralysis?) when implementing map class.

My TILE class looks like:

class CMapTile
{

public:

    enum eMapTileType
    {
        E_UNKNOWN = 0,
        E_FREE,
        E_WALL,
        E_ALL
    };

    CMapTile();
    virtual ~CMapTile();
    uint8_t GetType();
    uint8_t IsBlocking();
    uint8_t GetSymbol();

protected:
    uint8_t m_uiType;
    uint8_t m_uiBlocking;
    uint8_t m_uiSymbol;


};

Then i wrote a class for the map itself

#include "CMapTile.hpp"

class CMap
{
public:

    CMap();
    void Init(const uint8_t& ruiWidth, const uint8_t&  ruiHeight);
    void Generate();
    void Print();
    CMapTile GetTile(const uint8_t& ruiX, const uint8_t& ruiY) const;

private:

    uint8_t m_uiWidth;
    uint8_t m_uiHeight;

    std::vector<CMapTile> m_vTiles; 
};

And here is me thinking. With the design above, Map has no idea about entities. Entities have no idea about map.

So when i want to move Player RIGHT given above i will have to make two checks (totally separated). A check for map if tile is blocking and a check in a vector of entities if there is any entity on that position (X+1).

// Obtain tile to the right
CMapTile *pTile = m_Map->GetTile(pPlayer->GetPosX()+1, pPlayer->GetPosY());

// Obtain entity to the right
CEntity *pEntityToRight = m_EntitiesManager.GetEntity(pPlayer->GetPosX()+1, pPlayer->GetPosY());

// Check if blocking
if(pTile != NULL && pTile->IsBlocking() == false)
{

    // Check if any entity there and blocking
    if(pEntityToRight != NULL && pEntityToRight->IsBlocking == false)
    {
        // Update Player Pos to Tile position
        pPlayer->SetPosition(pTile->GetPosX(), pTile->GetPosY());

        // Update Map Entity Id for this Tile
        _Tile->SetEntityId(pPlayer->GetID());
    }
}

Maybe instead i should have an integer in the CMapTile storing an id of an entity, like below:

class CMapTile
{

public:

    enum eMapTileType
    {
        E_UNKNOWN = 0,
        E_FREE,
        E_WALL,
        E_ALL
    };

    CMapTile();
    virtual ~CMapTile();
    uint8_t GetType();
    uint8_t IsBlocking();
    uint8_t GetSymbol();
    int     GetEntityID();
protected:
    uint8_t m_uiType;
    uint8_t m_uiBlocking;
    uint8_t m_uiSymbol;
    int     m_iEntityID; // <<<<<<<-----

};

Thanks to which i can make a simple call to CMap like this to check if i can move player Right:

  // Obtain tile to the right
CMapTile *pTile = m_Map->GetTile(pPlayer->GetPosX()+1, pPlayer->GetPosY());

// Check if blocking
if(pTile->IsBlocking() == false)
{
    // Update Player Pos to Tile position
    pPlayer->SetPosition(pTile->GetPosX(), pTile->GetPosY());

    // Update Map Entity Id for this Tile
    _Tile->SetEntityId(pPlayer->GetID());
}

With the above CMapTile::IsBlocking would have to know about Entity class, to figure out if entity is a blocking type or not.

Questions This sounds simple but that initial design has an effect on later development. Examples:

What happens later when for an example NPC would have to attack player?

How from the NPC class the logic knows where is the player located or if he (NPC) can move right ? - having no idea about the map.

Should i pass the MAP pointer to the AI logic ?

Which is the proper way to go to separate the logic and make all of the above simple in future stages of development ?

Answer 1

I don't see a problem with the representation of your tilemap in memory. I think I can simplify it by make a tilemap a simple vector<uint8_t> but as we don't know what features you need let's not touch that topic now, as there isn't really a specific way of doing this.

About tile walkability: different entities may interact with tiles in different ways. Example: a ghost may pass through walls. Consider having a single uint8_t to represent a tile_type, and let logic for different entities to decide if they can walk or no walk a tile. For example, birds can pass over a tree tile, the player's character can't. This way you can have ghosts and birds. Do not ask the tile if it is blocking, ask the entity if it can walk a tile.

If you don't like logic in entities, ask the engine if a given entity can walk a tile. If you are using Entity/Component/System approach, ask the relevant system if a given entity can walk a tile.

Should i pass the MAP pointer to the AI logic? I would have a globals::MAP, but this depends on which design patterns you want to follow. You can, it isn't either correct or incorrect. Tip: I found myself requiring map at different functions in graphical RPGs, that's why I prefer globals. If you are working alone no need to overprotect your map, you know where you may modify it or not.

About storing entities IDs in tilemap: again, it isn't incorrect, and for text-based probably not overkill performance wise, as long as you are aware that this makes your tilemap also an scene grid. An scene grid is a form of scene partitioning, either for physics or for rendering. In this case, you are using the grid to easy check if near squares contain an entity.

One question you must ask yourself: Do you need more than a single entity in an square at a given time? Most graphical RPGs don't allow it and for the rare "cutscenes" where there may be special cases they just code them as scripted animations (suspending game "physics" temporarily), so you may very well be fine by having your tilemap being your scene grid with a single field for an entity ID. Problems start if the answer is "yes, I need more than a single entity".

Possible solutions are:

• Replace the entity ID field for a vector (required memory will skyrocket, but depending on your bigger map worst case you may not care).

• Don't store entities IDs in the tilemap, just store them in a separate vector/list and when you want two entities to interact search for suitable entities by iterating through the whole list. This forces you to think in advance in your worst possible case, the problem is that you may change your mind later, so this doesn't scale. Take this as a premature optimization for the specific scenario of allowing a very small number of entities alive at the same time.

If you already know that you only need 100 entities at the time, and that your maps will be big, 1000x1000. You can estimate like this:

• a list with 100 entities ids, with 32 bit per element, is only 400 Bytes. I calling it an entity list, but you probably want to use a vector<>. For a linked list there is extra data.
• a 1000x1000 tilemap, with a 32 bit field for entities ids is 4 MB only for the entities references, doesn't matter if their are set to 0 or reference an actual alive entity, I didn't add the other fields the tile structure contains. Yes, bigger than the list approach, but still a joke for today's hardware.

You must also think in list traversal time vs scene grid near square checking. Of-course the grid beats the list, but at what memory cost. All depends on the number of entities you expect and the size of maps you may want to have.

Some notes: I said "very small number of entities" but for today machines it may be thousand of them (the simpler their interactions are the more you may have). The list strategy plays well with an entity spawn strategy where you load a bunch of entities when entering a certain room/going near a certain zone, and unload them when they no more pursuit you. But if you want an honest open world simulation, and load/unload entities are a no go for you, entity lists aren't your friend (except that your big open world map only requires 100 entities in total, then any strategy would do).

If you can't decide on an strategy, just test them with a fabricated worst possible case (a really big map with thousands entities). Maybe you don't know yet how many you will need for the worst map your final game will have, but you may have an idea, just use bigger numbers than in your worst possible imagined case.

The only value you obtain from this answer is to help you think in some problems now. Problems you will hit eventually anyway while advancing the project.

Need help deciding? Go for the scene grid and single entity per square. Because it's simpler to code. Also, force yourself to think in things like max possible entities at a given time smells to premature optimization. The bigger possible map is not only limited by their size in memory, but also by the time you need to expend in creating them, so I don't expect them to be very big (of-course, there is the case of procedural generation, that makes big maps cheaper to create).

Tip: you are already using getters, and that's OK. By having a proper wrapping interface, if you switch strategies at some point, while your getters prototype doesn't require to change, the rest of the code doesn't require any change either, you will only have to rewrite the getters inner code.

In brief:

• Ask the map the type of tile of a given coordinate.

• Ask the entity/system if a given entity can walk that type of tile.

• Use scene grid because is simpler to code, until you hit the horizon where it won't work for you anymore (and probably you won't hit it)

• Be smart with wrapper functions prototypes in case you decide to switch strategies in the future.

Possible optimization: for most possible scenarios, you only need a tile to be a uint8_t value, and nothing more. The value determines everything, including the symbol used to render it (if that is what the symbol member is for in your code). But I can think of a case where this is not valid, if you want to have secret passages, then you may disguise a passable tile with the symbol of a wall, but note that that can be solved too by having another tile value for the passable wall tile.

tile 23, renders as ¤ and not passable by player.

tile 24, renders as ¤ but passable by player.

¤¤¤¤¤¤¤¤¤¤
¤¤¤T¤¤¤¤¤¤
¤¤¤¤¤¤¤¤¤¤
¤¤¤¤¤¤¤    ££
¤¤   ¤¤  £££
          £E
   P    E  £

Above, the two ¤ are tile 24, while all the others are tile 23, the player can move to T by walking over those two tiles. The presence of T gives the hint that there is a secret passage.