Category Archives: Programming

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); 
pResult->RegisterComponent(); 
pResult->SetStaticMesh(floor); 
pResult->SetFlags(RF_Transactional); 
this->AddInstanceComponent(pResult);

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

Finally:

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)
     {
       pFloor->AddInstance(t);
     }
     else
     {
       pPillar->AddInstance(t);
     }
   }
 }

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

man11

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.

Options:
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.

Sentinel Menus Almost Done

Sentinel Mission Select screen

Sentinel Mission Select screen

 I’m at the point where I’m working away trying to turn the various bits into a coherent whole, level design, weapon upgrades, etc. Too much too soon and the fun is removed. Too little too late and the game just becomes really hard or boring.

Adding Physics to Sentinel using Jitter

This post will hopefully be one of many.

First things first. Go download Jitter (I’m using 0.1.7). The official web site is here http://jitter-physics.com/

Jitter is a little short on documentation but has an excellent set of demostration scenes. It is worthwhile having a look and a quick play.

The tutorial PDF (included in the package) sums up the basics.

  1. Create a Collision system (I use the CollisionSystemSAP).
  2. Create a physics World and pass the collision system.
  3. Create a shape
  4. Create a RigidBody – using the Shape just created
  5. Add the body to the world
  6. Every update loop ask the physics engine to step forward a small amount of time.

That’s pretty painless and pretty easy to get going. The Jitter libraries are very well designed, the code is well encapsulated and loosely bound.

I’m still playing with the physical properties and other parameters to get a world that “plays right”. Not too hard, not too easy but essentially realistic enough that the gamer can become immersed in shooting the baddies and protecting the oil refinary!

 

Sentinel game development – terrain and shadows

The terrain is based on Riemer’s excellent “multitextured terrain” tutorial. This is strongly recommended for any developer looking at clever multitexture techniques. http://www.riemers.net/eng/Tutorials/XNA/Csharp/Series4/Multitexturing.php

The code is a little old, it predates the XNA 4.0 framework so some bits need tweaks to enable it to compile.

Simple control added with the ability to control the pitch and yaw of the guns.

Fixing Garbage Collection issues when developing for XNA and XBOX 360

The easiest way for a small indie company or hobbyist developer to develop for the XBox 360 is using the XNA tools from Microsoft. Microsoft have spent a substantial amount and time on the XNA product set.

The XNA framework is a low barrier way to games development. XNA development makes use of a XBox specific version of the .NET compact framework. However, this framework does of course have its issues. The libraries aren’t as complete as the non-compact version, etc.

The way memory works in the .NET framework and the Garbage Collector, the generations of collection, heap allocations and similar are well discussed in a number of locations (not least of which is the MSDN library) and so I shall not discuss those specifics here.

This post is about one specific issue – stalls due to garbage collection events firing off at an inconvenient time. At this point I would strongly recommend reading two excellent articles: Steve from StevePro Studios suggested that I investigate garbage collection when I was developing a game called “flap”. A simple sprite game that would stall every few seconds. Go check out Steve’s original articles . There are other articles out there that explain a fair bit of the inner workings of managed code. Boxing and unboxing is especially interesting.

Once you have read Steve’s original article you will understand that there are generally three values in the remote performance monitor to look out for.

  • Managed String Objects Allocated
  • Managed Objects Allocated
  • Boxed Value Types

So you understand how to use the remote performance monitor, you can see that a static scene is allocating 2000 strings each time it updates – what do you do now?

At this point go back to first principles. When you don’t know where the problem lies profile it. Sometimes, and I will admit this, you can guess where the problem is “oh yeah its because I have spriteBatch.DrawString(font,string.Format(“You have killed {0} baddies”,score, … ) in my main draw code”. But I’m becoming an old hand at this – I get surprised way more than I predict. My recommendation is nothing more than dust down the old CLRProfiler.

The current CLRProfiler is available here: http://www.microsoft.com/en-us/download/details.aspx?id=16273

The technique is very simple.

  1. [To find a scene to target for our investigation we do some precursor steps]
  2. Create a Xbox version of the game.
  3. Deploy to the XBox and use the remote performance manager to run the game.
  4. Find a scene that is static enough (e.g. a simple spinning of the camera around the Y axis) that you shouldn’t expect any allocations.
  5. Find, using the performance manager that there are in fact allocations and GC cycles occuring.
  6. You have now a specific and very targeted problem to solve. This is the key, bite off small chunks and solve them one at a time.
  7. Create a debug windows version of your game.
  8. Start the CLRProfiler.
  9. Set the working directory correctly.
  10. Set the “Profile Allocations” to be true.
  11. Set the “Profiling Active” to false.
  13. At this point you are ready to go.
  14. Launch the application.
  15. Now, navigate to the same point as “4” above.
  16. Click on the “Profiling active” checkbox.
  17. Collect some data for a few tens of seconds.
  18. Uncheck the “Profiling Active” checkbox.
  19. At this point use the call graph to see what objects are being allocated and where.