Tilemaps can be a great way to keep track of our game world. While a simple array of tile data at their core, they can be much more than that. Today I will look into the concept of directions in a tilemap, how we can perform local steps between tiles easily, and what more we can do once we are that far.
Neighbours and directions
The generic tilemap class we implemented last week came with the following small helper struct which represents a reference to a particular tile in a tilemap.
struct Tile<T>
{
private readonly Tilemap<T> tilemap;
public int X { get; }
public int Y { get; }
public Tile(Tilemap<T> tilemap, int x, int y) : this()
{
this.tilemap = tilemap;
this.X = x;
this.Y = y;
}
public T Value
{
get { return this.tilemap[this.X, this.Y]; }
}
}
Given such a type, I think it would be great to be able to retrieve all tiles next to it. We can of course do this easily, by constructing further instances of the reference struct with offset coordinates.
We could for example add the following property.
public IEnumerable<Tile<T>> Neighbours
{
get
{
yield return new Tile<T>(this.tilemap, this.x + 1, this.y);
yield return new Tile<T>(this.tilemap, this.x + 1, this.y + 1);
yield return new Tile<T>(this.tilemap, this.x, this.y + 1);
yield return new Tile<T>(this.tilemap, this.x - 1, this.y + 1);
/* etc. */
}
}
This works, but it feels somewhat hard-coded, and not very flexible.
Something else that we may want to get from a tile is just a specific neighbour, say the one to its right. Writing a method for this is difficult, since we have no good way of representing ‘one tile to the left’. Instead we could write properties for all the eight directions, but that again results in a lot of inflexible code.
Direction enumerator
Instead, let us represent the concept of ‘direction’ in the tilemap using a enumerator.
enum Direction : byte
{
Unknown = 0,
Right = 1,
UpRight = 2,
Up = 3,
UpLeft = 4,
Left = 5,
DownLeft = 6,
Down = 7,
DownRight = 8,
}
Given this, we can write a method with the signature Tile<T> Tile<T>.Neighbour(Direction direction) which is much better.
Before we can implement that method however, we need a way to translate directions to actual x,y offsets in the tilemap.
Let us write another small helper type for this.
struct Step
{
public readonly sbyte X;
public readonly sbyte Y;
public Step(sbyte x, sbyte y)
{
this.X = x;
this.Y = y;
}
}
I do not often expose the fields of structs directly, but in this case it really does not matter much.
With this type, I would ideally like to write a method on Direction to convert a given direction to a Step value. enums do not allow for methods however, but we can use an extension method instead.
static class Extensions
{
internal static readonly Step[] DirectionDeltas =
{
new Step(0, 0),
new Step(1, 0),
new Step(1, 1),
new Step(0, 1),
new Step(-1, 1),
new Step(-1, 0),
new Step(-1, -1),
new Step(0, -1),
new Step(1, -1),
};
public static Step Step(this Direction direction)
{
return DirectionDeltas[(int)direction];
}
}
Note that instead of using a number of if else clauses, I instead use an array as a direct access table. We could also use a switch statement which may be compiled even more efficiently.
Using a direct access table like this is possible in the first place because we made sure to assign the values of Direction consecutive indices.
With this in place, we can now write the following method in Tile<T>.
public Tile<T> Neighbour(Direction direction)
{
return this.neighbour(direction.Step());
}
private Tile<T> neighbour(Step step)
{
return new Tile<T>(this.tilemap, this.X + step.X, this.Y + step.Y);
}
Whether or not to expose the functionality of Step publicly is up to you. I consider it an implementation detail and hide it in our library.
Simplifying the original code
With these helper types in place, we can now simplify our original property, enumerating all neighbours of a tile.
public IEnumerable<Tile<T>> Neighbours
{
get
{
for (int i = 1; i < 9; i++)
{
yield return this.Neighbour(Extensions.DirectionDeltas[i]);
}
}
}
Note how we skip the first element (index 0) of the array. That element corresponds to Direction.Unknown and has a step of 0,0 which would simply return the same tile.
Another improvement we can make is adding another property that checks if the neighbours we are returning are actually valid tiles. That will prevent us from accidentally accessing tiles outside the tilemap.
public IEnumerable<Tile<T>> ValidNeighbours =>
{
get
{
for (int i = 1; i < 9; i++)
{
var tile = this.Neighbour(Extensions.DirectionDeltas[i]);
if (tile.IsValid)
yield return tile;
}
}
}
A simple enough change.
Representing multiple directions in a single value
There are more things we can do with our Direction type. What I have found useful for path-finding is to be able to know what directions are open, and which are blocked when moving from tile to tile.
For this purpose we could keep a list of our Direction type above for each tile, but I find it nicer to create an actual type representing a combination of directions.
To keep things light we can simply use another enum, however this time instead of using consecutive values, we will use only powers of two as values.
That allows us to use bit-wise unions and intersections to represent and work with combinations of multiple directions.
[Flags]
enum Directions : byte
{
None = 0,
Right = 1 << (Direction.Right - 1),
UpRight = 1 << (Direction.UpRight - 1),
Up = 1 << (Direction.Up - 1),
UpLeft = 1 << (Direction.UpLeft - 1),
Left = 1 << (Direction.Left - 1),
DownLeft = 1 << (Direction.DownLeft - 1),
Down = 1 << (Direction.Down - 1),
DownRight = 1 << (Direction.DownRight - 1),
All = Right | UpRight | Up | UpLeft | Left | DownLeft | Down | DownRight,
}
Note how we make use of the existing Direction type and the binary shift operator << to make sure the values of our distinct directions are correct.
Further, this well defined conversion from Direction to Directions allows us to easily check if one is contained in the other as follows.
public static bool Includes(this Directions directions, Direction direction)
{
return directions.HasFlag(direction.toDirections());
}
private static Directions toDirections(this Direction direction)
{
return (Directions)(1 << ((int) direction - 1));
}
Note how we use the same bit manipulating formula to convert the value as when initialising them above.
Further, we can also add and remove individual directions from a Directions value.
public static Directions And(this Directions directions, Direction direction)
{
return directions | direction.toDirections();
}
public static Directions Except(this Directions directions, Direction direction)
{
return directions & ~direction.toDirections();
}
Note how most of this comes down to simple bit-wise operators and manipulation.
Enumerating directions
Of course, the purpose of our Directions type was to use it as a sort of collection of directions. Let us implement the enumeration of the type.
Unfortunately, there is no easy to way to extract the contained directions directly, however we can loop over the few directions we have and check if each of them is included. If it is, we return it.
private static readonly Direction[] directions =
{
Direction.Right,
Direction.UpRight,
Direction.Up,
Direction.UpLeft,
Direction.Left,
Direction.DownLeft,
Direction.Down,
Direction.DownRight,
};
public static IEnumerable<Direction> Enumerate(this Directions directions)
{
foreach (var direction in Extensions.directions)
{
if (directions.Includes(direction))
yield return;
}
}
Directions as a set
While we are thinking of the type as a collection, or more precisely a set (it does not allow for duplicate elements), we can of course also implement basic set operators and similar checks.
Here are some that I came up with, I am sure more are possible.
public static bool Any(this Directions direction)
{
return direction != Rectangular.Directions.None;
}
public static bool Any(this Directions direction, Directions match)
{
return direction.Intersect(match) != Rectangular.Directions.None;
}
public static bool All(this Directions direction)
{
return direction == Rectangular.Directions.All;
}
public static bool All(this Directions direction, Directions match)
{
return direction.HasFlag(match);
}
public static Directions Union(this Directions directions, Directions directions2)
{
return directions | directions2;
}
public static Directions Except(this Directions directions, Directions directions2)
{
return directions & ~directions2;
}
public static Directions Intersect(this Directions directions, Directions directions2)
{
return directions & directions2;
}
Note how all of these are implemented using simple bit-wise operators which makes them very efficient, especially compared to possible implementation using actual lists or other collections of Direction.
For a commented version of these and other operations, feel free to check the full implementation on GitHub.
Conclusion
Starting from wanting to enumerate the tiles neighbouring another one, we designed and implemented simple binary types representing individual and sets of directions respectively.
Using specialised types allows us to work with directions effortlessly, while the implementation as simple enumerators gives us great performance.
If you found this interesting, make sure to share the post on your favourite social media.
Make sure to check back next week when we will take a look at coordinate systems and how to embed our tilemap inside our game world.
Enjoy the pixels!