Dark Chronicle, also known as Dark Cloud 2 in North America, was originally released for the Playstation 2 in 2002. I played it a long time ago and was always curious about how its levels were generated. In order to accomplish this, I had to dive into the underlying machine code. Thankfully the final release of the game contained debug symbols which made it easy to locate relevant functions and paired with Ghidra’s Decompiler which transformed the machine code to C, this difficult task was became a lot easier. So I dove in and took took away the core principles and reimplemented them in Rust.

This post contains an overview of the generator with a demo and details about the path I took achieve this understanding.

Overview

Level generation is performed on a 2D region of tiles. A tile is either set or unset. A set tile has a owner, connections up, right, down, or left, and a boolean to determine if the tile is a tunnel. A tile’s owner refers to either a room id or a tunnel id.

A random room template along with random coordinates are choosen. Check that the chosen location is empty and large enough for the template to prevent any half placed rooms and allow recover if an error occurs in a later stage. Perform this process again so that two rooms are placed and dig a tunnel to connect them.

This setup allows us to make the assumption that whenever we place a new room and begin tunnelling towards another room we can connect to any other tile that does not belong to the just placed room and our current tunnel. This satisfies the constraint that a path between each room, leaving no rooms orphaned.

Now place 4 to 6 additional rooms with random templates. As mentioned whenever the room is place we create a tunnel from the new room towards an existing room. Once all rooms are placed, put 1 to 4 connections between two random rooms.

Create 1 to 3 dead-end tunnels and create 3 tunnel branches which leaves us with a completed level.

Tunnelling

Tunnelling requires a starting position, a target position, and a owner.

  1. Calculate the between difference between each axis and take the absolute value. The absolute value can be though as the number of steps required for each axis.

  2. Begin by travel along the axis with the largest difference in magnitude for a random amount of steps.

  3. When we move one step we check the tile and if it unset, set it with the supplied owner, set connections to the direction that we came from and update the previous tile’s connections to the direction we moved in. If the tile is already set, update connections as mentioned previously and check the owner. If the owner is not equal to supplied owner we can finish tunnelling.

Once we travel the random amount of steps, start again from (1.).

Dead-ends

As the name suggests this creates a tunnel that only has a room at it’s endpoints.

  1. Random select a unset tile with neighbours that are also unset.

  2. Pick a random room and determine it’s center tile.

  3. Begin tunnelling from the unset tile towards the center to the randomly chosen room.

Tunnel Branches

This creates tunnels that branches off other tunnels and creates additional dead-ends that aren’t connected to rooms.

  1. Randomly select a tunnel tile that contains a neighbour that is unset. Similar to tunnelling, step in the direction of the unset tile and set the tile with relevant data and update both tile’s connections properties.

  2. Generate a random number between 1 to 2, which will be the number of iterations for the following procedure.

  3. Randomly select a neighbour that is unset. If one does not exist terminate. If one does exist, generate a target number of steps to take in the range of 1 to 3.

  4. Check if tile in the current direction is unset and is a valid location. If the step is valid then set with relevant data and update connections for both tiles. If the next step is not valid goto (5.) otherwise continue this procedure until the number of steps to take is zero.

  5. If the number of iterations performed is equal to the number generated you are done. Otherwise goto (3.)

Demo

Demo source code

Specifics

This is a high level overview of generator so some details are omitted. Some dungeons do not use the generator and are considered fixed. There are few parameters used

List of tools were used:

  1. Ghidra
  2. Ghidra Emotion Engine
  3. A patched version of Dark Cloud Packer to make it compatible with Linux

I originally has some issues since Ghidra relocated some address locations. I compared the instructions decoded by Ghidra with the ones located in the binary and noticed they were different and after further investigation determined that Ghidra was the cause. From there, I begun searching searching debug symbols for keywords such has ‘Dungeon’, ‘Map’, ‘Level’ which led me to ‘Build__11CAutoMapGenFv’.

I quick scan revealed calls to another function called ‘RandomMapMainProc__11CAutoMapGenFv’ which raised my confidence that I located the correct region and quickly began assigning names to local variables and created stuctures to improve readability of the decompiled code. Access patterns can help determine the size of a structure and its memebers. When a structure is contained within an array and scan of the array is performed then the size is given away by pointer arithmetic. For the members of structure, their size is hinted by the instructions that operate on it. In some cases compiler optimizations made some memory access patterns harder to read requiring further work.

The overall level generator is the same as described in the overview. Levels are either fixed or random levels which have dimensions of either (14, 14) or (20, 16). There is a minimum of 6 and maximum of 8 rooms. Once all rooms are placed 0 to 3 additonal tunnels are built between two random rooms. Another number from 0 to 3 is generated and a function called ‘CreateDummyRoot’ is called which are the dead-ends tunnels mentioned early. Three calls to ‘CreatTermParts’ are made which are simillar to tunnel branches.

‘SetPartsIndex’ is called which is responsible for assigning a tile id for Tunnel tiles and Tunnel terminators. Is is accomplished by visting each tile and checking if it is a Tunnel tile or Tunnel Terminator and if it is the entire ‘PartsInfoData’ is scanned for for a tile that matches the flag and it’s connections.

Each visible tile will now have an id. Some extra features are than placed in the following order: Level entrance, Door room, Health pool, and all exits. The 3D representation of the level is built and tiles with an id of -1 are used for scenery.

Room Templates

For each dungeon style there is a corresponding configuration file which contains various room templates. Each template contains information about its dimensions (width and height), a probability, a boolean called FIXED, and the corresponding data which is a 2D array containing a pair of numbers for each tile. The first element of the pair is a tile id and the second marks the accessiblity of the tile. A tile that is unaccessible is for aesthetics and must not be reachable by the player also monsters and chests cannot be spawned on the tile. This flag is only used for the third region of the game, Starlight Canyon.

Here’s an sample of a configuration file. The full configuration files can be found in ‘data.hd2/dungeon/cfg_file’

VER 1.01;
GRID_SIZE 320.000000, 320.000000;

ROOM_ID 0;
ROOM_SIZE 3,3;
ROOM_RATE 100;
ROOM_FIXED 0;
RD 60,0,52,0,61,0;
RD 55,0,76,0,53,0;
RD 63,0,54,0,62,0;
ROOM_END;

Each tile is an index for an array called ‘PartsInfoData’ whoose elements are 24 bytes long. The most notable members of this structure is the element which is a pointer to constant string that contains the name of the tile, tile flags, and the direction in which the tile is connected to.

PARTS "room01";
   FAR_CLIP 1400,0;
   LIGHT_FLAG 0,0;
   MOVE_FLAG 0,0,1,0;
   PIECE "d00r01_1-m.mds",1;
       PIECE_NAME "d00r01_1-m0";
       PIECE_POS 0,0,0;
       PIECE_ROT 0,-1.2708,0;
       PIECE_SCALE 1,1,1;
       PIECE_COL_TYPE 0,0;
       PIECE_TIME 0,0;
   PIECE_END;
   FUNC_POINT 1;
       FUNC_DATA "pos",1;
           FUNC_NAME "point";
           FUNC_FLAG 0, 0, 0,0;
           FUNC_POS -80,40,80, 0,-1.5708,0, 1,1,1;
       FUNC_DATA_END;
   FUNC_POINT_END;
PARTS_END;