"Generate Dungeon" not implemented

[Ghabry]

Name of the game:

Pesadillas con los conejitos saltarines
https://mega.nz/file/Q8NW2YIS#fx9hoHJxRsgrk4bHEpciK5UNO4JyPLvT97zdszLhxeU

Reported via Android bug reporting :) @fdelapena you can answer the user

Describe the issue in detail and how to reproduce it:

Go to bed on the first map, on the 2nd you will softlock out of bounds.

Guess you are as surprised as I am:

The checkbox "[ ] Generate Dungeon" in the Map Properties actually generates a dungeon when loading the map (and overdraws the base map). I always thought this is an editor feature. WTF.

This breaks the mentioned game because it teleports on a space that is not movable in the non-generated dungeon -> softlock.

@CherryDT :)

[CherryDT]

I'm not surprised, I knew this :D To be honest, there is no other way this could work, otherwise the dungeon would be the same every time. The idea is that it's a random dungeon i.e. that it looks different every time you enter it.

The only really confusing part there for me (and probably also for game makers) is how placing events on the map and, as you can see here, teleporting to it works (and does so without messing everything up). It does some magic but I didn't really look into how that works yet.

[Ghabry]

This suddenly moved from "This feature is so useless, who needs random dungeons?" to "Woah, this is amazing!".

It even ensures that the teleport place can reach the rest of the map o_O.

[Ghabry]

I figured out ~50% of the algorithm by now. Pretty sure I can fully replicate this when I stare at it for longer.

[mateofio]

Can't wait to see how many RPG_RT bugs come out of this one..

[Ghabry]

List of maps using this (based on rmarchiv as usual):

Tod_auf_Reisen_Data/Map0057.emu:16:  <generator_flag>T</generator_flag>
Die letzte Schlacht der Elfen VIII (v1.30)/Map0073.emu:16:  <generator_flag>T</generator_flag>
Die letzte Schlacht der Elfen VIII (v1.30)/Map0074.emu:16:  <generator_flag>T</generator_flag>
Eternal Legends 2 (Demo v1.60)/Map0680.emu:16:  <generator_flag>T</generator_flag>
ExcelSagaRPG/Map0122.emu:16:  <generator_flag>T</generator_flag>
HOME/Map0065.emu:16:  <generator_flag>T</generator_flag>
HOME/Map0293.emu:16:  <generator_flag>T</generator_flag>
HOME/Map0294.emu:16:  <generator_flag>T</generator_flag>
Space Drop - the hero myth/Map0051.emu:16:  <generator_flag>T</generator_flag>
Space Drop - the hero myth/Map0052.emu:16:  <generator_flag>T</generator_flag>
Space Drop - the hero myth/Map0053.emu:16:  <generator_flag>T</generator_flag>
Super Pokémon Eevee Edition (v0.9)/Pokemon Eevee/Map0142.emu:16:  <generator_flag>T</generator_flag>
Super Pokémon Eevee Edition (v0.9)/Pokemon Eevee/Map0143.emu:16:  <generator_flag>T</generator_flag>
Super Pokémon Eevee Edition (v0.9)/Pokemon Eevee/Map0169.emu:16:  <generator_flag>T</generator_flag>
Super Pokémon Eevee Edition (v0.9)/Pokemon Eevee/Map0170.emu:16:  <generator_flag>T</generator_flag>
Super Pokémon Eevee Edition (v0.9)/Pokemon Eevee/Map0280.emu:16:  <generator_flag>T</generator_flag>
Super Pokémon Eevee Edition (v0.9)/Pokemon Eevee/Map0287.emu:16:  <generator_flag>T</generator_flag>
Super Pokémon Eevee Edition (v0.9)/Pokemon Eevee/Map0288.emu:16:  <generator_flag>T</generator_flag>
Super Pokémon Eevee Edition (v0.9)/Pokemon Eevee/Map0289.emu:16:  <generator_flag>T</generator_flag>

@rygos

[Ghabry]

Here an incomplete write up of what I figured out by now.

First: In the official code it invokes a gigantic function with ~27 parameters twice. However the parameters are almost not shared. So this is just bad codedesign. I will split it in two functions to make this more clear:

---

Allocations:

• A list of size mapWidth * mapHeight, I call this tilemap. This is not the actual map tilemap, is a temporary array!
• A list of Points of size (mapWidth + mapHeight) / 100 + eventCount + 5. No idea what the w+h/100 is supposed to do. (RPG_RT uses two arrays here, I will use Points). I call this eventPos

---

First step is "GenerateUpperLayer".

Relevant tiles here are "ceiling", "upper wall" and the 12 obstacleTiles (3 obstacles in a 2x2 grid).

1. Initialize the entire map upper layer with 10000
2. When not "Room with Obstacles" as gen mode: End here. Yes, no obstacles for other modes :(
3. Set tilemap to 1 when there is an event at this map location (does not care about hero or vehicles)
4. Go though the entire map, ignoring corners:

// Put obstacle A
if (Rand(32) == 0)
  set_obstacle = 1
if (tilemap at pos > 0) // has event at pos
  set_obstacle = 0
if (the 2x2 area has an event)
 set_obstacle = 0
if (set_obstacle)
  // Put the obstacle on "tilemap"

// Now the code is duplicated for obstacle B and obstacle C
// Only difference is:
B has Rand(64) and C has Rand(128)
// Also when there is aready a A-obstacle then no B is put etc.

5. Copy the data to the real map, updating passability etc (I dont understand that code but it makes sense to just adjust it based on the tile information)

---

Second step is "Lower Layer": BUG 1 to 5 are executed for upper layer even though they are completely useless there.

if (!useFloorB)
  floor_b = floor_a
if (!useFloorC)
  floor_c = floor_a

2. Get X/Y Position of all events and sequentialy write it in the list. When they are at a map border inc/dec by 1 to ensure they are not at a border anymore
3. From evtCount to end of eventPos list: Write random numbers: X = Rand(mapWidth - 2) + 1, Y = Rand(mapHeight - 3) + 2

The elements starting from evtCount in the list are Hero, Boat, Ship, Airship.

4. Store hero pos at eventPos[evtCount]
5. When a vehicle is on the current map store there X/Y location (this overwrites the random number from step 4).
6. Shuffle the event list "eventPos.size" times.
7. Fill the map lower layer with "ceiling tiles"

Now it depends on the generation mode, there are 4:

Single Passage

1. Go through eventPos. When the successor (index + 1) has either:

• Same X pos
• Same Y pos
• Rand(2) is 0
  Then:
  TO BE FIGURED OUT
  Else:
  TO BE FIGURED OUT

Linked Rooms

1. Go through the entire event list, compare cur with next event:
2. Check if (code duplicated across all 4)

• x1 & x2 same row and x2 > x1
• x1 & x2 same row and x2 < x1
• y1 & y2 same col and y2 > y2
• y1 & y2 same col and y2 < y1

3. When one of the 4 is true move in a loop from A to B. Call a function (4.), they won't be considered again for the current event.
4. The called function:

w_upper = max(0, x - (genRoomWidth / 2 +Rand(2)))
h_upper = max(0, y - (genRoomHeight / 2 + Rand(2)))
w_lower = min(mapWidth - 1, x + (genRoomWidth / 2 + Rand(2)))
w_lower = min(mapHeight - 1, y + (genRoomHeight / 2 + Rand(2)))

These tiles are "marked". They won't be considered again for this event loop step.

After the loop:
5. Not fully sure: Create rooms at the event locations using function "4"
6. When a tile is marked replace it with a floorA tile on the tilemap.

Maze

TO BE FIGURED OUT

Open Room with Obstacles

1. Fill the entire map, ignoring borders, with floorA. When "upperWall" is enabled skip the 2nd row

Shared afterwards

1. Update map tile information (passability etc.)
2. When passage granularity is 2: Look for Floor A tiles and make the next tile on the row also a Floor A tile. Same for next cols.
3. TO BE FIGURED OUT

if (hasFloorATile)
  rnd = Rand(16) - 1
  if (rnd < 3)
    // make it a B tile
  else if (rnd - 3 == 0)
    // make it a C tile

5. Upper wall logic: TO BE FIGURED OUT

[mateofio]

Ideal unit / fuzz test:

1. Hook RPG_RT to output the generated map to lcf binary.
2. Seed the RNG with a lot of pre-determined values
3. Run both player and RPG_RT with same RNG seeds and RNG algos. Ensure the output maps match exactly.

Now that the RPG_RT RNG algo is known, maybe it helps to revisit this.

[Heartbleat]

This feature is critical for at least a few games, even if it was seldomly-used.

I was recently asked to port one such game to EasyRPG so non-Windows folks could run it without breaking out Wine.
The main gameplay depends on being able to generate a new dungeon floor from a themed template many times, so it's essentially unplayable as it stands.

Reproducing this in Speo 1.3.3 would just require going through the first room in the game, telling the attendant you're a returning player to skip a textwall, then heading down the stairs to the right.
(It might be a good test specimen for any work on this feature, because nearly every map in the game makes use of it.)