Logic level representation that distinguishes “<<under>> and <<above>> the bridge”

Question

I have an logic level/map representation for a 3D game that uses vector<Area> where:

class Area{
    vector<Point2D> bounding; //determines the shape of the Area, its borders 
    //bounding of Area is like borders of country 
    //(it's easy to test if something is inside area)

    vector<Obstacle> obstacles; //general type for all static objects inside this Area
    //each Obstacle has boundingBox (center, halfSize, rotation)

    vector<Dynamic> dynamicObjects; //same as obstacles, but the use of separated vector
    //for dynamic objects helps with few things

    Player * player = 0; //like Obstacle, but it has special treatment

    vector<Area*> connectedAreas; //I won't went deeper into how Areas are connected.
    //For simplify, let's assume we are working on one Area.
    //Or that when Player leaves Area, all connectedAreas start a test if he entered
    //one of them (it's not the case, but work fine for purposes of that example).
    ...
};

It's quite simple and very low memory-consuming representation for large areas (grid representation would grow and grow with the size of area). I also find it quite good when it comes to some AI algorithms that my game uses. I don't have too advanced collisions in my game (so I don't need to care about them in the level representation). So generally, I'm happy with that representation.

Still, I have one problem: sometimes some parts of the map have "height-levels" - e.g. bridge: you can be either under the bridge or above it (and you can go above only from certain fragments of map). How can I represent that?

For caves or multi-floor buildings I can just use vector<Area> instead of single Area/Area's fragment. That vector<Area> could hold separated Area for each floor.

But when the mesh has kind of "smooth" transitions between levels (bridges, some parts of mountains and any non-separable fragments of map) - it doesn't looks like good solution anymore.

For example, here player is able to go either under the tree or above the trunk:

P.s. I am not asking for the graphic representation. I've separated the game logic and graphic engine as much as possible. The 3D engine uses triangles of course, with much more details then game logic need or want (less data => faster processing).

Answer 1

In my online-game that I'm tinkering on as a hobby, I plan to split the map up into tiles that have only a 2D coordinate inside each tile. The vertical coordinate for a player or NPC inside its particular tile-cube will then simply be decided by the ground level underneath it. Since each tile has arbitrary connections to other tiles in 4 directions, stairs would still be possible to make. Just create a tile with the stair model (blue) at its end:

The player will seem to walk up the stairs because the ground level rises. If we now connect the left edge of the tile to the tile one level up, the user will easily walk up one level. The only downside of this approach is that a character won’t be able to hide under the stairs.

However, if your tiles aren't very tall (E.g. half the height of a typical character), you can have another tile for the area below, that is connected to the other tiles around the stairs, but not the stairs, and thus is drawn and accessible as if it was below. The stairs would be forced to a certain thickness, but apart from that you could have many levels.

Also, your 3D model would not need to include the lower part of the wedge, so it could look like you can walk directly below, while your character's head is just sticking out the top of its tile. I.e. in the above picture, you have the bottom level (white/blue) then the middle level (red) and then one flat tile from the top (green). If you e.g. connect the red tile to the surrounding white tiles, a player could fall off the stairs. If you don't connect them at all, you'd have an invisible wall.

Another advantage of using such tiles is that they can be used for simple collision testing. You can just block an entire tile from being stood on.

Answer 2

I'm struggling to understand what you're asking, but I'll take a shot at it. I'm assuming what you're talking about is an "area graph" or "zone graph", a concept for AI. In an area graph, parts of the map are linked logically in a sparse graph to make it easier for AI to understand what's going on. If that's the case, why not just add a 3rd coordinate to your areas?

class Area{
    vector<BoundingBox3D > bounds;
    vector<Obstacle > obstacles;
    ...
};

Then "above the bridge" merely has a bounding box higher than "below the bridge". If you want something even more generic than bounding box you can do this:

class Area{
    vector<Shape3D > bounds;
    vector<Obstacle > obstacles;
    ...
};

Where "Shape3D" is a generic 3D shape. You can then logically link these things together in a graph.

Answer 3

Why make it any harder then it needs to be? Just add a boolean to the entity state right next to the 2D position.

Then during rendering you will need to offset when try depending on the tile, some logic will also depend on the true false value like line of sight calculation.

But you can mostly short circuit that if you assume the amount of object like that are rare in a level.