Normally a tile map displays spaces which can be defined in finite terms using a piece of paper. A hypermaze, however, can be defined using a piece of paper, only, if you use a graph to describe how the pieces fit together. This is true for my hypermaze, and I suspect it should hold true for most other hypermazes. A tile map is a lot like a piece of paper, only a lot less powerful; thus in relation to a tile map you should consider the space of hypermaze to be undefined. You can’t measure it, because it doesn’t have a concrete form in 2 dimensions. You might have success defining it in three dimensions, but then you’ll be unable to translate it to the tile map.

So how can a tile map be used to draw an undefined space?
The answer I found was: little by little.

Instead of throwing the entire environment into the tile map from t=0, push parts of the maze into it as they are needed. The purpose of a maze is to figure out how to correctly navigate it, yet most 2D mazes show you the path. Mind you the correct path is shown along with all the false paths. A less friendly maze would only show you the path you’re on, and only up to the point you are at. With my hypermaze project nothing else was even, truly, possible. I wanted a top down maze to navigate, so I had few choices in how to display the maze.

The way it works is that you start at the “Root Node” in the maze graph. This is just a room with some doorways as far as you’ll ever see, unless you dig into the source code. I’ve broken down the navigation code into the following bullet points.

• Nodes have doorways.
• Obviously you need to choose a door, and move through it.
• When you exit the room, ie. walk through the door, you’ll enter a “Node Link”.
• One end of a node link will always be “where you’re from” and the other end will be somewhere else. (sometimes “somewhere else” is the other side of the same room)
• Every time you enter a Node Link or a Node the Maze looks up the associated pointer, if it doesn’t find a space for that construct it makes one right there and then.
• Constructing a space is a matter of interpreting a Node and its connections. The space needs to fit doorways on all the correct walls.
• Send the space to the Tile Map to be rendered.

A couple things need to happen for the rendering of this process to go smoothly.
First: Entering new Nodes, specifically Nodes and not Node Links, requires calculating the offset for the correct doorway in that new Node. Then the Tile Map coordinates for that space are offset accordingly.
Second: The Tile Map is made from Tile Chunks, 32×32 tile regions. In order to ensure a space is fully rendered calculations need to be made to ensure the space is offset correctly inside the Tile Chunk, and then any parts that spill into other Tile Chunks need to be accounted for.

That probably doesn’t really sound like a lot, but all of that really kicked my ass! It took a couple weeks for me to write, debug, rewrite, debug, and debug it some more. The process has taught me a valuable lesson: start with the coordinate systems and translations between them. That might just save me from frustration next time I am dynamically creating and rendering scenes in Unity, as well as any C++ projects I work on in the future.

An Expanding Tile Map

So then, what about the all important Tile Map? If it can’t take a terrain space and stream it to one or multiple Tile Chunks you’re dead in the water. You could be standing just a couple tiles away from a Tile Chunk boundary, so you need to account for spillover. In theory a space may need to be rendered across 9 Tile Chunks, how do you cope with that in your placement algorithm?

Well I’ve already explained a lot of what goes on, so I will just post the code for the Tile Map. The “important” code.

#define LOWBITS 5
#define terrain_index( a, b )  ( ( ( b ) * terrain_width ) + ( a ) )
#define chunk_index( a, b )  ( ( ( b ) * width ) + ( a ) )

inline uint32 ChunkLocalCoord( uint32 value )
{
	return GetLowBits<uint32>( value, LOWBITS );
}

inline uint32 MapLocalCoord( uint32 value )
{
	return GetHighBits<uint32>( value, 32 - LOWBITS );
}

//The coordinate systems are Bottom-Left oriented and so is Place()
void TileMap::Place( Terrain* t, uint32 starting_tile_x, uint32 starting_tile_y )
{
	debugger::Instance().Terrain = (uint64)t;
	debugger::Instance().Terrain_SX = starting_tile_x;
	debugger::Instance().Terrain_SY = starting_tile_y;
	uint32 increment = IncrementAtBit<uint32>( 0, LOWBITS + 1 );
	const coordinate Starting_Chunk( MapLocalCoord( starting_tile_x ), MapLocalCoord( starting_tile_y ) );
	const coordinate Starting_Chunk_Offset( ChunkLocalCoord( starting_tile_x ), ChunkLocalCoord( starting_tile_y ) );

	const uint8 c_cw = TileChunk::width; //Width of a Chunk
	const uint8 c_ch = TileChunk::height; //Height of a Chunk
	const uint16 c_ChunkColumns = (uint16)ceil( ( Starting_Chunk_Offset.x + t->width ) / (float)c_cw );
	const uint16 c_ChunkRows = (uint16)ceil( ( Starting_Chunk_Offset.y + t->height ) / (float)c_ch );

	coordinate Current_Chunk;
	coordinate Current_Chunk_Offset;
	coordinate Current_Chunk_Offset_Tile;
	coordinate Current_Terrain_Offset;

	TileChunk* chunk = nullptr;
	for ( uint32 r = 0; r < c_ChunkRows; ++r )
	{
		for ( uint32 c = 0; c < c_ChunkColumns; ++c )
		{
			Current_Chunk.x = Starting_Chunk.x + ( c * increment );
			Current_Chunk.y = Starting_Chunk.y + ( r * increment );

			Current_Chunk_Offset.x = ( c == 0 ? Starting_Chunk_Offset.x : 0 );
			Current_Chunk_Offset.y = ( r == 0 ? Starting_Chunk_Offset.y : 0 );

			Current_Chunk_Offset_Tile.x = Current_Chunk.x + Current_Chunk_Offset.x;
			Current_Chunk_Offset_Tile.y = Current_Chunk.y + Current_Chunk_Offset.y;

			Current_Terrain_Offset.x = Current_Chunk_Offset_Tile.x - starting_tile_x;
			Current_Terrain_Offset.y = Current_Chunk_Offset_Tile.y - starting_tile_y;

			uint64 key = MergeIntegers( Current_Chunk.x, Current_Chunk.y );
			auto it = m_Map.find( key );
			if ( it == m_Map.end() )
			{
				chunk = new TileChunk();
				chunk->m_TileSet = m_TileSet;
				it = m_Map.emplace( key, chunk ).first;
			}
			else
			{
				chunk = it->second;
			}
			chunk->SetTiles( t, Current_Chunk_Offset, Current_Terrain_Offset );
		}
	}
}

void TileChunk::SetTiles( Terrain* t, coordinate Chunk_Offset, coordinate Terrain_Offset )
{
	auto &terrain_width = t->width;
	auto &TValues = t->m_TileValues;
	uint16 c_endX = width - Chunk_Offset.x - 1;
	uint16 t_endX = t->width - Terrain_Offset.x - 1;
	uint16 c_endY = height - Chunk_Offset.y - 1;
	uint16 t_endY = t->height - Terrain_Offset.y - 1;

	uint16 endX = t_endX < c_endX ? t_endX : c_endX;
	uint16 endY = t_endY < c_endY ? t_endY : c_endY;
	for ( uint16 y = 0; y <= endY; ++y )
	{
		for ( uint16 x = 0; x <= endX; ++x )
		{
			m_Region[chunk_index( Chunk_Offset.x + x, Chunk_Offset.y + y )]
				= TValues[terrain_index( Terrain_Offset.x + x, Terrain_Offset.y + y )];
		}
	}
}