Random Dungeon Generation UE4 C++

In the previous post, I started programming using the Unreal Engine for the first time. I learnt the basics of projects, some of the UE4 class Hierarchy (useful) and I randomly generated floor or wall. A good start but a long way away from random dungeon layout.

To create a dungeon layout I want to reset all the floor, create some rooms, determine which rooms should connect to which other rooms and then finally carve some corridors between them.

void InitialiseBlocks(); 
void CreateRooms(); 
void ConnectRooms(); 
void CarveCorridors();

The CreateRooms is where it starts to get interesting. There are some really fascinating articles on the Internet about different approaches to go for. The Quadtree approach basically uses quadtrees to divide the area into the various levels of recursion and randomise room creation at each level.

I wrote a quick quadtree class to help me do this. Really it is a room generator that uses quadtrees to prevent overlapping rooms from being generated. It is a badly named class.

The Quadtree is initialised with an axis aligned bounding box (AABB) and then asked to generate rooms. Each Quadtree can either:

  1. Generate room
  2. Subdivide (and then in turn ask each of the child quadtrees to recursively perform the same function)
  3. Stop because the depth of recursion would make any resultant rooms a bit small.

My rules are:

  1. The first two levels (0 = whole, 1 = quarters) quadtrees can’t turn into a room and will always subdivide.
  2. Then the percentage chance of creating a room is 30%, 45% and 65%. This seems to work well. The maximum depth actually disallows this last size but the maximum depth is really a property of the absolute size of the dungeon. This may need some tweaks if I start supporting very large dungeon sizes.
  3. Each room that should be generated is then placed into the quadtree AABB. The width is between 1/2 and 2/3 of the AABB width (and similarly for the height). This guarantees that rooms won’t overlap but adds variety to the sizes and also the “centres” of the room. Filling the quadtree AABB gives far too much uniformity to the rooms.
  4. Any room that is less than 5 in width or height is inflated slightly.

The rooms then need to be connected.  Ian Shadden suggested a simple algorithm. Start with first room and connect it to the nearest room that doesn’t already have a connection. When you get to the last room it won’t have anybody that it can connect to.

This is a simple idea but pretty effective. Then all you have to do is carve the corridors between the connected rooms. Simple!

Simple Random Dungeon Generating in UE4 C++

Unreal Engine Technical Writer Ian Shadden created a very complex blueprint code to generate a random dungeon (it does a lot more than just generate a dungeon!) This post just details my first time experiences working out how to create a simple C++ class to generate something similar. I’ll start by aiming to replicate the first 16 minutes of this video. This bit wasn’t too complicated in the blueprint!

If I can do that then I think I will have gained a bit more understanding of how UE4 class libraries plug together. Others have done similar but nothing like doing it yourself to understand!

Steps this blog will go through:

  1. Create project
  2. Copy Mesh content
  3. Create AWallGenerator class (derived from AActor)
  4. Override OnConstruction
  5. Load two static meshes (one for walls and one for floor)
  6. Add UInstancedStaticMeshComponents (x2) to the AWallGenerator actor
  7. Iterate and add instances to the instanced static meshes
  8. Logging messages
  9. Attach a debugger and step through code

The end result looks a bit like this:

The list above took me a few hours to work out! Luckily there are some great resources out there for UE4.

I started with a blank C++ project. File –> New Project –> C++ –> Basic Code

Where to start? I know that the thing I want to create is an actor. Something I can place “in the world” and it can do things.

File –> New C++ Class –> Actor base class

I shall create an actor class that will then generate instance static meshes. This is a common technique from other engines (where you basically just change a transform and render another copy of the same mesh).

I’ve also copied the “wall_pillar” and “floor” content from the blueprint tutorial – just so I can get it working quickly.

The blueprint example gives plenty of hints as to the way forward. I need to override the “OnConstruction” function so that I can have behaviour in the editor and at “game” time.

First problem – what is the signature of “OnConstruction”? I just looked in the base class header (Actor.h). You can right click a #include and visual studio context menu includes “Open Document”.

virtual void OnConstruction(const FTransform& Transform)

The UE4 engine has an UInstancedStaticMeshComponent (components are things that can be added to actors). The UInstancedStaticMeshComponent has a UStaticMesh and a set of Instances (basically a big list of transforms).

Classes in UE4 code base have to be correctly named or the header parser doesn’t work correctly. I’ve tried (by misnaming the odd class) and they do indeed cause some wierd compilation bugs. Anyway; this is well documented: https://docs.unrealengine.com/latest/INT/Programming/Development/CodingStandard/

In my “OnConstruction”, I iterate over two indices (for the XY plane directions), roll a random number and create an instance of a wall or a floor.

We need to physically load a mesh and bind it. The trickiest bit was working out the folder structure to load the meshes.

 UStaticMesh* floor = Cast<UStaticMesh>(StaticLoadObject(UStaticMesh::StaticClass(), NULL, TEXT("/Game/Meshes/Floor")));

Once the mesh is loaded we can create the UInstancedStaticMeshComponent.

UInstancedStaticMeshComponent* pResult = NewObject<UInstancedStaticMeshComponent>(this); 

I created two of these – one to hold floors and one to hold walls.

About this time I was struggling to see if the meshes were loading and whether or not I had managed to create the components correctly. Two debugging techniques spring to mind at this point – streaming data to an output log and interactive debugging. The UE_LOG macro can be used (and it is pretty straight forward to use). https://wiki.unrealengine.com/Logs,_Printing_Messages_To_Yourself_During_Runtime#Within_Editor_.28Play-In-Editor.29

Logs are great but debugging is better. https://answers.unrealengine.com/questions/253091/how-do-i-debug-c-code.html


Loop and add instances at random:

 for (int i = 0; i != _maxX; ++i)
   for (int j = 0; j != _maxY; ++j)
     FTransform t(FVector(i*_tileSize, j*_tileSize, 0));
     if (FMath::RandRange(1, 10) <= 5)

Converting 2 bit CGA sprite sheets to bitmaps

Dungeon used compiled QBASIC to switch to CGA graphics mode (320x200x2bpp) and render sprites using the PUT method. The PUT command was a pretty fast method to poke a set of bytes into screen RAM and draw a sprite. It couldn’t cope with clipping (going out of bounds of the screen), transparency or a host of other issues but it was pretty fast.

It was substantially faster than PSET (pixel set) command in a loop.

The PUT command took an x,y pair and an array of data. The equivalent GET command took the sprite from screen (where you can render it with PSET) and stuffed it into the array, also storing the width and height in the first two short elements of the array.

To speed up loading the sprites I created a sprite sheet (texture atlas) in an offline program, and use BSAVE to save the screen directly to disk. I would only save the amount of scanlines required to cover the height of the spritesheet.

This technique worked really well, it had a small downside. CGA screen RAM is actually interlaced. To go from line 1 to line 2 is actually a jump offset and not simply the next byte along. The main upside is the fact that all sprites can be dealt with in a single load command (followed by lots of get commands of course) which is substantially faster than opening and closing lots of files. This is why I don’t BSAVE the sprites directly but in fact create an on screen sprite sheet. File loading speed was a very big factor when the files were on floppy disk.

I actually issued a pair of BSAVE commands, offset by a magic constant which equates to a single line down the screen (because of the interlacing). When you load with BLOAD, the same offset is incorporated and the sprites stitch themselves back together and GET commands can be used to fetch from screen RAM to the program memory (which in turn can be used in PUT commands).


Converting a 30 year old game

30 years ago, or there about, I wrote a Dungeon bash game. I called it Dungeon. It was turn based with up to four local players sharing the keyboard and taking it in turns to move their piece, then the monsters had a go and back to start until the mission completed or all the players died.

There were five classes of character, fighter, cleric, wizard, dwarf and elf. The classes set the default and maximum attributes for the player piece.

My brother used to play this game until reasonably recently, as long as you could boot to DOS and run in CGA mode (2 bit graphics – 4 colours), then the game would work.

It is time for a conversion. I am going to try extending my IntelliJ experiments to create a Windows Java version as well as an Android version.

In my subsequent posts I shall talk about the conversion topics as they come up….starting with the fact I can’t “see” the game anymore…

Android with Intellij and Tesco Hudl- week 2

There have been a small number of minor issues to overcome to get up and running.

Issue one: Figuring out how to turn on developer’s mode on the latest Android operating system. Not too big a problem – press the about / build info in settings 7 times. A message popped up but no developer’s menu appeared…

(See various links, youtube clips etc for this). Or here.

Issue two: developer menu only appears if you are logged in with the first account to be created on a device. I tried it with a second account. Doh, a few minutes of frustration with a small lightbulb moment!

Issue three: Tesco’s view is that the HUDL is not a developer platform and hence no USB drivers. This is a little short sighted of them to be honest. Luckily the Samsung drivers work just fine. Thanks Samsung. If I had tried with my Galaxy S3 first on this laptop I may not have even known there was such an issue. (I used Samsung USB driver 1.5.33 which works nicely with the HUDL).

Issue four: Don’t forget to install JRE, Java, git, ant, etc but more importantly go and setup all the appropriate environment variables. (See set or setx commands under Windows).

Everything was now buildable and deployable to my Android device. Yay!

Starting Android Game Development…going for Intellij

Tomlin Games have decided to develop some Android games and apps. Our experiences so far have been somewhat limited using an older ADK and Eclipse. Things have moved on…so we’re going to try some new techniques out and post about what we find.

1) Use C#, MonoGame and Visual Studio with Mono for Android.
2) Java based development using Eclipse
3) Java based development using Android Studio
4) Java based development using IntelliJ IDEA.

Time to try something new – trying option 4!

We’re also going to use libgdx and I am following this post here.