Storing walls that are between tiles

Question

I am writing isometric engine in c++. I decided to take a more realistic approach and make walls occupy space between two tiles, not a single whole tile, as shown in the picture below (just like in The Sims).

My problem is that I have no idea how to store the tile map related data in something that is not grid. In this situation I guess I will need to make it A* friendly, so there will be nodes and edges between tiles not divided by walls. Here is another picture showing what I want to achieve:

So here is the question(s):

How should I:

• store the whole map, both tiles and walls
• optimize it for rendering
• use it for A* and other algorithms rather straightforward to implement on a simple grid but now using walls (edges) to determine visibility, collision etc.?

Answer 1

I start with coordinate systems — the coordinates for grid locations are (x,y) but as Krom mentioned in a different answer, for walls there can be up to two walls for each grid location. That leads to a second coordinate system, for edges between tiles. In this article I used West and South so the edges can be (x,y,West) or (x,y,South), but you can pick two as long as you're consistent.

These two coordinate systems (grid tiles and edges) are related. You'll want to ask: which four edges surround a tile?

For pathfinding, A* wants to know which tiles are neighbors (B) of the current tile (A). Instead of returning all four adjacent tiles, you can check the four edges. You include tile B as a neighbor only if there's no wall between A and B.

Instead of storing two walls for each tile, as Krom suggests, I usually keep the walls in a separate data structure: a set of edge coordinates. When A* wants to know whether B is a neighbor of A, I will check whether that edge is in the set. If it is, then I don't return B.

You probably don't need this for A*, but for other things you'll probably want to know for any edge, which two tiles are connected to it:

See the “Algorithms” section of the page for the calculations for these two operations.

Also note: for some types of maps, you'll actually want to store four edges per grid tile, so that you can support one-way moves.

Answer 2

In each tile you can store walls it has on North and East. That way each tile needs to store only 2 more booleans (or ints, if you want to store wall type). Downside is that tiles along South and West edges cannot have walls on South and West unless you add a one more row of hidden tiles that will have them.

Answer 3

In each tile, it could store the neighbours (or connectivity) that it has access to. Perhaps as a bitmap. The walls are where the two adjacent tiles are not connected. This is very friendly with A*.

The second approach is to store the connectivity of tile as a enumeration. For example, a fully open tile is 0, a tile with wall to north and rest open is 1, a tile with wall to south and rest open is 2, and so on until you covered all possible combinations.

Answer 4

Hopefully this C# is okay for you - my c++ is very rusty:

abstract class MapFeature
{
    public void Draw();
    public bool IsWall();
}
enum Direction
{
    North, South, East, West
}
class Wall : MapFeature
{
    public bool IsWall() { return true; }
    public Tile Front, Back; // Tiles on either side of the wall, otherwise null.

    #region Implementation of MapFeature

    public void Draw()
    {
        // Wall specific drawing code...
    }

    #endregion
}
class Tile : MapFeature
{
    public bool IsWall() { return false; }

    public MapFeature North, South, East, West; // Tiles/Walls on each side, otherwise null

    public bool CanGo(Direction direction)
    {
        switch (direction)
        {
            case Direction.North:
                return !North.IsWall();
            case Direction.South:
                return !South.IsWall();
            case Direction.East:
                return !East.IsWall();
            case Direction.West:
                return !West.IsWall();
            default:
                throw new ArgumentOutOfRangeException("direction");
        }
    }

    #region Implementation of MapFeature

    public void Draw()
    {
        // Tile specific drawing code...
    }

    #endregion
}

You can add wall-specific information to the Wall class, Tile specific information to the Tile class, and further refine conditions in the "CanGo" method. For example, when a wall is actually a locked door - say, a Door class.

In order to draw this, you would start with some arbitrary tile - say the tile in the middle of the current camera position. Then move toward and to the left of the camera according to the size of the tiles. Then do a breadth-first traversal of the IMapFeature nodes, drawing each wall/tile in the order encountered.

A* will work on this structure, though you would obviously need some modifications to handle something like locked doors.

If you wanted to, you could also maintain a spatial index of the tiles, which would implicitly include the walls, in order to find out which tiles were within camera bounds.

You'd still only need to pick a starting tile and a distance to traverse based on tile size.