Anoda (working title) is a first-person narrative exploration game I'm building solo in Unreal Engine 5, for PC and Steam Deck. You go out on timed runs and bring items back.
Some items don't come free. They can be stuck (rooted, buried, sealed) and need a tool, and some hide a small minigame. One of them is a labyrinth: a 5×5 grid by default, up to 7×7 in the accessibility settings. There is no fail state. The only pressure is the run timer.
Work-in-progress UI, final art pending.
Each placed item is supposed to keep its own maze: retry it, save, quit, come back tomorrow, same puzzle. The code even said so in a comment. It wasn't true, and it took a relaunch to notice.
Carving the maze
Each cell stores its four walls as bit flags. A new cell has all four.
enum class EMazeWall : uint8
{
None = 0,
North = 1 << 0,
East = 1 << 1,
South = 1 << 2,
West = 1 << 3,
All = North | East | South | West
};
The generator is a recursive backtracker, written iteratively with an explicit stack [1]. Start in a corner, step to a random unvisited neighbour, knock down the wall between the two cells, repeat. Nowhere new to go? Step back.
while (Stack.Num() > 0)
{
const FIntPoint Current = Stack.Last();
// ... collect unvisited neighbours into Candidates
if (NumCandidates == 0)
{
Stack.Pop();
continue;
}
const FMazeDirection& Chosen = Directions[Candidates[Rand.RandRange(0, NumCandidates - 1)]];
const FIntPoint Next = Current + Chosen.Delta;
Maze.GetCell(Current).Walls &= ~Chosen.Wall;
Maze.GetCell(Next).Walls &= ~Chosen.Opposite;
Visited[Maze.CellIndex(Next)] = true;
Stack.Add(Next);
}
A wall is shared by two cells, so it's cleared on both sides: Wall on the current cell, Opposite on the next. All randomness comes from one FRandomStream built from a seed. Same seed, same maze. Keep that in mind.
The result is a perfect maze: exactly one path between any two cells, no loops. In graph terms, a tree.
Where to put the entrance
My first version put the start at (0,0) and the exit in the opposite corner. Every maze was a corner-to-corner walk, and that pair is rarely the longest path the maze has.
The fix uses a property of trees. Run a breadth-first search [2] from any cell and take the farthest one: it's an end of the tree's longest path. Search again from there, and the farthest cell is the other end. That path is the tree's diameter [3]. The trick goes back to Edsger Dijkstra, around 1960 [3].
MazeBfsDistances(Maze, CarveOrigin, Distances);
Maze.Start = MazeFarthestCell(Distances, Size);
MazeBfsDistances(Maze, Maze.Start, Distances);
Maze.End = MazeFarthestCell(Distances, Size);
Two searches, and every maze gets the longest solution it can offer. Buck uses the same two-pass trick to make mazes harder [1].
The promise in the comment
This is how an item picked its maze:
// Fixed seed = same puzzle for every instance of this item, across attempts and reloads.
const int32 Seed = (Item->MinigameSeedMode == EItemMinigameSeedMode::FixedPerItem)
? (int32)GetTypeHash(Item->GetFName())
: FMath::Rand();Hash the item's name, use it as the seed. Same name, same seed, same maze. It looks right.
The catch is that an FName isn't a string. It's a reference into a global name table that the engine fills as names get registered. That is what makes FName cheap to copy and compare: the engine compares entries, not text.
GetTypeHash(FName) hashes that entry, not the text. In UE 5.8 the engine is honest about it [4]:
friend uint32 GetTypeHash(FNameEntryId Id)
{
const uint32 UnstableInt = Id.ToUnstableInt();
return HashCombineFast(UnstableInt, UnstableInt);
}ToUnstableInt. Where a name lands in the table depends on the order names were registered while the game started. Within one session it never changes. Across launches, it can.
So inside a session everything held: retries, saves, loads, same maze every time. Every test passed. Quit, launch again, and the same item had a different maze.
Stable for what?
The obvious fix is to hash the text instead of the table entry. But before fixing it, I had to answer a simpler question: stable for what?
The comment said "same puzzle for every instance of this item". Read literally, that's per item type, and the quick fix would hash the item type's ID. There were three ways to read it:
- Per item type. Every cutter in the world shares one maze. Solve it once, you know them all.
- Per placed pickup. Two cutters lying in different spots get two different mazes. Each keeps its own across retries, saves and relaunches.
- Per player. A new save brings new mazes.
I went with the placed pickup. A maze belongs to a thing in the world.
It was also the cheap option. Every placed pickup already has a persistence key: the save system uses it to remember which pickups were collected. The seed hashes that same key. No new ID, nothing new to save.
"Make it stable" isn't a requirement until you say what it belongs to.
The fix
The persistence key is a plain string: an ID I can set by hand on the pickup, or the actor's name if I leave it blank.
FString UPickupComponent::GetPersistenceKey() const
{
if (!PickupId.TrimStartAndEnd().IsEmpty())
{
return PickupId;
}
return GetOwner() ? GetOwner()->GetName() : FString();
}
The seed is a CRC32 of that string:
int32 UPickupComponent::SeedForKey(const FString& Key)
{
// Not GetTypeHash(FName): it hashes the name's slot in the name table, which
// changes between launches. Lowercased because an FName keeps the casing it was
// first registered with, so the same actor name can come back cased differently.
return static_cast<int32>(FCrc::StrCrc32(*Key.ToLower()));
}
Two decisions sit in that one line:
- CRC32, not
GetTypeHash(FString).GetTypeHashexists for hash maps, and a hash map only needs it to agree with itself during one run. CRC32 is a fixed function of the text: same string, same number, on every launch and every machine. - Lowercase first. An actor's name comes from its
FName, and anFNamekeeps the casing it was first registered with. The same actor can come back asBP_Pickup_C_1one day andbp_pickup_c_1the next.
The setting got a new name too: FixedPerItem became FixedPerPickup, so it says what it does. It's the default value, and Unreal doesn't write default values into assets, so no item asset had to change.
Testing "the same on every launch"
There was already a test: generate a maze twice from the same seed, check the walls, start and exit match. It passed, and it was right to pass. The broken part was where the seed came from.
Testing "the same on every launch" from inside one launch is the tricky part. Comparing the engine's output with the engine's output proves nothing: the old code would agree with itself too. So the expected value is worked out once, outside the engine, and written into the test by hand:
bool FAnodaPickupSeedPinnedTest::RunTest(const FString& Parameters)
{
TestEqual(TEXT("the seed of a known key is pinned"), UPickupComponent::SeedForKey(TEXT("bp_pickup_test_c_1")), 2125975711);
return true;
}
If this test ever fails, saved games will open different mazes than before.
What it still doesn't cover
The fix is only as stable as the key, and the key has two weak spots:
- Renaming a placed pickup in the editor changes its maze, unless it has a hand-set ID. The save system's "already collected" flag has the same weakness, since it uses the same key.
- Two pickups with the same actor name in different levels share a maze, and their collected flag too.
Both have the same answer: give hand-placed pickups an explicit ID. For a solo project with a handful of levels, that's a rule I can live with.
Takeaways
- An
FNameis a table entry, not text. Hash its string if the number has to survive a relaunch. - "Make it stable" means nothing until you say what it belongs to.
- A test for "the same on every launch" needs an expected value from outside the engine.
Anoda is in development. More soon™.
References
[1] J. Buck, Mazes for Programmers: Code Your Own Twisty Little Passages. Pragmatic Bookshelf, 2015. Recursive backtracker: ch. 5, pp. 73–77. Longest path: ch. 3, pp. 44–46.
[2] E. F. Moore, "The shortest path through a maze," in Proceedings of the International Symposium on the Theory of Switching, Harvard University Press, 1959, pp. 285–292.
[3] R. W. Bulterman, F. W. van der Sommen, G. Zwaan, T. Verhoeff, A. J. M. van Gasteren, and W. H. J. Feijen, "On computing a longest path in a tree," Information Processing Letters, vol. 81, pp. 93–96, 2002, doi:10.1016/S0020-0190(01)00198-3.
[4] Epic Games, Unreal Engine 5.8 source, Engine/Source/Runtime/Core/Public/UObject/NameTypes.h.