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

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).

• You haven't explained what your map data structure actually means, and I can't guess. Sounds to me like you've over-complicated things, though. Sparse grids would allow you use a grid without wasting memory, though even a non-sparse grid scales quite well in terms of memory usage. You can also store your map as a series of static shapes (walls/floors/heightmaps) like most physically-simulated games have to do. – Sean Middleditch Dec 7 '14 at 23:04
• @SeanMiddleditch can you precisely tell me what should I explain more? I'm not trying to be rude or ironic, I just find that structure very small and self-described. But I work with it for some time, so it's very possible I'm missing some info. – PolGraphic Dec 7 '14 at 23:07
• the code you had when I commented didn't have the comments in the code. I think the rest of my comment stands... this representation is quite atypical and I think you're over complicating the problem massively. – Sean Middleditch Dec 7 '14 at 23:15
• @SeanMiddleditch I'm glad that comments helped. I know it's not a typical representation (partly because it's geometrical representation with its pros & cons over grid-based one), but it works for me really good in certain types of games/worlds (in many others, different rep.m like sparse grids you mentioned, would be better, I agree). The reason I've posted that question is I want to know if it's possible to bypass the problem I described for structure I've described. If so, it would be useful in more situations. – PolGraphic Dec 7 '14 at 23:40
• Why not a simple boolean to signify the entity is on a unusual level, then your game logic would need to change to account for the unusual level. But overall it's a simple addition when most of the time it will be false. – ratchet freak Dec 7 '14 at 23:44

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.

• My representation doesn't really use the tiles and it rather use shapes (bounding multi-vertex 2d figures for areas as well as for objects inside of it). I guess there is an more precise name for it (geometric representation?). Anyway, it's an option for tiled-based maps - up-vote for now, thanks for respond (and great illustration!). And I guess I can partly modify that idea to be usable by my structure. – PolGraphic Dec 7 '14 at 23:45
• Yeah, by virtue of being connected to other tiles/areas, both are graphs, in the end, so you should be able to massage the shapes as desired. That said, I generally try to stick with simple rectangular tiles, as they're much easier to work with (intersection, collisions, distance measurement, progressive loading, specifying the player's position inside the tile...). Only the tiles are rectangular, the 3D models don't have to be, so a player will barely notice the limitation. – uliwitness Dec 7 '14 at 23:47
• Indeed. On the other hand, with geometrical representation (when you assume that endless world is empty and you add areas/sectors/obstacles by defining their shapes/borders) you can e.g. find very accurate optimal paths for circular objects quite easy; your map memory consumption is low (and do not grow with the size but with the complexity of objects' shapes). But in most cases, grid-based maps prove to be more useful (I guess that's why they are the majority). – PolGraphic Dec 7 '14 at 23:51

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.

• Adding 3rd dimension is something I would like to avoid. The game is 3d, but the logic/AI is fine with 2D representation (think about strategy/rpg game, not a shooter/flight simulator). The vector<Point2D> in my Area is the shape of Area - it stands for borders of Area (I guess I wasn't clear with that). But your note about linked Areas is absolutely true :) Still, 3D representation is an option (up-vote from me so far), but maybe somebody will point another solution. – PolGraphic Dec 7 '14 at 23:21
• Clearly your AI is not "fine" with a 2D representation, since you want it to go above and below "bridges" -- a 3D concept! However, you can "hack" it to work in 2D by having different "layers" in a 2D region, as you suggest. Just add a single coordinate representing the height. It is an integer coordinate. Add this to all of your obstacles and entities as well to make it clear which "layer" they are in. – mklingen Dec 8 '14 at 0:07
• My AI is "fine" with 2D representation for 99.5% of time (the bridges etc. on the map are very rare and player spends less then 1% of time close to them). That's why I would love to stick with 2D representation and think for something when the "bridge problem" happens (it's true, my AI is not "fine" in that situation). Of course, for some other games, with flying option or anything like that, my approach is not even close to "ok" ;) Thanks for the comment. I will have a hard time deciding which respond should I mark as an answer, because eventually, I've taken something from each of them. – PolGraphic Dec 8 '14 at 0:10

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.

• It's a good point. I've used the adapted approuch of @uliwitness + your "branches" (psuedocode: if(untypicalSituation == true){...}) which saves me from doing any more calculations 99% of time. I had to mark one answer, so up-vote from me. – PolGraphic Dec 8 '14 at 17:48