8
\$\begingroup\$

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

conceptual graphic of what I want to achieve

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.?
\$\endgroup\$
  • \$\begingroup\$ Do you need to be able to view it from different angles? If so, will you want to apply different textures to opposite sides of the same wall? E.G. pink wallpaper on one side, blue on the other? \$\endgroup\$ – jzx Jan 3 '15 at 10:44
  • \$\begingroup\$ I will need ability to rotate the map and to use different kind of paints and materials on both sides of the walls. Now I think that the top part of the wall should also show material inside the wall (e.g., concrete, brick, wood) \$\endgroup\$ – Tchayen Jan 3 '15 at 11:58
7
\$\begingroup\$

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.

Edge coordinates for a square grid

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

Edges surrounding 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:

Tiles surrounding an edge

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I don't think your comment "friendly with A*" really applies, as it assumes the interface ("which tiles are adjacent?") must match the implementation ("tiles store neighbours"). The two could be different, for example if you use a separate data structure for walls as amitp suggests. \$\endgroup\$ – congusbongus Jan 5 '15 at 5:01
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.