JP runners should try to understand the cave generation algorithm. It's interesting, let's you see the game in a different way, and can help you play faster.
I include a writeup here (for someone to translate), but the best way is to read the code in CaveGen.java createRandomMap().

The terrain is generated on a grid system, and is made up of "map units" which are attached at "doors".
There are 3 types of map units:
Rooms: these are the largest, and usually contain most of the objects
Corridors: these are hallways, 3-ways, and 4-ways. (usually don't contain any objects)
Alcoves: these are 1x1 units and only have 1 door

The map units each have pre-defined "spawnpoints" of different types, which is where the objects in the game are placed.
Objects in the game fall into 3 categories: Item, Gate, and Teki.
Items are treasures not inside of an enemy. Gates are just gates.
Teki refers to pretty much every other object (enemies, candypops, eggs, hazards, etc...).
Spawnpoints have the following types: door teki, easy teki, hard teki, special teki,
decorative teki, alcove teki, falling alcove teki, item, hole/geyser, pod.
Any teki can fall into any of these spawnpoint types, depending on the sublevel.

High-level algorithm for sublevel generation:
1) Create the terrain by placing mapunits
1a) Place all of the rooms (and maybe some corridors)
1b) Generate hallways
1c) Place alcoves
2) Place the PoD in the first mapunit
3) Place the hole based on score
4) Place the door teki, special teki, hard teki, and easy teki
5) Place the decorative teki
6) Place the treasures (that are not contained inside enemies) based on score
7) Place the tekis that appear in alcoves
8) Place the gates

To generate the terrain for a sublevel, the game reads in map unit files which defines which map units are availible.
Each map unit has a file indicating which type it is, and where its doors + spawnpoints + waypoints + waterboxes are.
During the terrain generation, the game keeps track of 3 queues of map units, one each for rooms, corridors, and alcoves.
The queues hold 4 versions of each map unit availible, one for each of the possible rotations.
The terrain is generated iteravely, one unit at a time.
In the intermediate phases, the doors of map units can be "open" if they do not yet attach to a door from another map unit.

The initial ordering of the queues is sorted from smallest to largest, with ties broken by fewer doors.
The game applies a shuffling algorithm randBacks() to each of the queues.
Then, the game picks the first map unit in the queue of rooms that has a pod spawnpoint, and places it as the first unit.
(As a result of randBacks, if there are multiple possible spawn rooms, the smallest one will be chosen first ~85% of the time, the 2nd smallest ~14%, and the 3rd smallest ~1%)

Each time a map unit is placed, the game will recompute the open doors, and shuffle the map unit queues.
The queue of rooms is shuffled such that it is sorted where the rooms that have been placed least frequently appear at the top.
The queue of corridors is shuffled such that if there are <4 open doors, 4-way corridors are prioritized. If there are >9 open doors, 2-way corridors are prioritized.

After the first unit is placed, the terrain generation moves to the next phase.
The game picks an open door uniformly at random.
Then, the game will decide to prioritize placing a room or a corridor, based on the parameter CorridorVsRoomProb and the type of the map unit attached to the selected door.
From there, the game try to place each map unit in the queue in the order of the queue.
For each map unit, it will try to attach each door of that map unit (in a random order) to the previously selected existing door.
If the doors are correctly oriented and the map unit fits, then the map unit will be placed there. If not, the game will try the next map unit until one that fits is found.
(As a result of this process, it is possible for certain rooms to not spawn, if they cannot fit at a selected door)

Once the specified number of rooms have been placed, the game will move on to hallway generation.
The important parameter here is CapVsHallProb, which determines for each open door if a hallway will try to generate there.
Hallways will be generated when an open door has another open door in the 19x10 space in front of it.
The hallways are generated 1 unit at a time, and the process is quite complicated. Some weird things can happen.

After there are no more hallways to be placed, the game will close off any doors that are still open with alcoves.
If an alcove doesn't fit, it will use the appropriately fitting corridor piece.

After this, the game does two more special things. If there is a corridor behind an alcove, the alcove is deleted and replaced with a hallway.
Also, if 2 1x1 straight hallways are together, they will be replaced with a 1x2 hallway.

After this, the game moves into the object generation phase.

The pod is placed in a uniform random spawnpoint in the first map unit that was placed.

At this point, we need to discuss the most important part of this algorithm: SCORE.
Each item spawnpoint and hole spawnpoint is given an integer score.
Suppose that our sublevel has four map units: P, Q, R, S.
The pod is in room P. Suppose there is a treasure spawnpoint in room S, and the shortest path to the pod is S->R->Q->P.
The score of the treasure spawnpoint is comprised of a few components that are summed up:
The "door-link distance" of map units Q and R (very important - the distances in S and P don't matter)
The "enemy score" of map units P, Q, R, S and the doors PQ, QR, RS
1 bonus point since S is not the pod room

"door-link distance": Within a single room, the game defines the distance between any pair of doors.
This distance is generally defined along the waypoint graph. The best way to understand these is -drawDoorLinks in CaveGen.
A general rule of thumb is that 1 unit of distance is 17 points of score.
"enemy scores": For each easy teki, 2 points of score, for each hard teki, 10 points, and for each door teki, 5 points.
These are applied to the entire map unit, regardless of where the enemy appears within the map unit.
Note that when a hole is placed, there are no enemies yet, so pretty much only "door-link distance" matters

The hole is placed based on score. In story mode, the location is chosen randomly from the set of spawnpoints with the highest score.
The hole is placed before the geyser when both are availible, so the score of the hole will always be greater than or equal to that of the geyser.
In challenge mode, the location is weighted random, where weight = sqrt(score) + 10.

The door teki are placed next. They are placed on random doors (doors between two rooms are most likely).
The special teki are placed next. They are placed uniformly random on spawnpoints that are far enough away from the pod and hole.
The hard teki are placed next. They are placed uniformly random on spawnpoints that are far enough away from the pod and hole.
The easy teki are placed next. They are placed uniformly random on spawnpoints that are far enough away from the pod and hole. These enemies can spawn in groups.
Note, this means that treasures that appear in teki are placed pretty randomly.
The decorative teki are placed next. They are placed uniformly random on spawnpoints.
These and special teki don't contribute to enemy score.

Within each type of object, the order in which they are spawned is set in the file. If at some point there are not any empty spawnpoints left,
the object will not spawn. This can cause objects to be missing.
If an object has a weight property, the game will continue to spawn it until the maximum number of teki is reached, or there are no locations left.

Then the items (treasures) are placed based on score. In story mode, the location is chosen randomly from the set of spawnpoints with the highest score.
If there are aleady n treasures in a room, the score is multiplied by 1/(n+1).
Again, the treasures have an order! So, the first treasure will take the highest scoring spot, and the second treasure will take the second highest scoring spot, and so on.
(This can be used to infer the location of one treasure from another, and can be very helpful for buried treasures)
In challenge mode, the location is weighted random, where weight = 1 + score / num_spawn_points_in_this_unit for rooms
and 1 + score * 10 for alcoves.

The (candypops + not falling) alcove teki are placed next, in the order that they appear in the file.
They are not placed randomly. Instead, they are placed in alcoves in the order that the alcoves were placed in. (generally closer rooms first)
Afterwards, the falling alcove teki are placed. They can be spawned on top of many other teki, but not candypops or holes/geysers.
(This ordering rule is very important for some sublevels. e.g. the mitites on HoB4 or TCT become predictable)

Finally, the gates are placed. First, the gates will priorities covering grounded alcove teki and holes in alcoves. If there is already a teki on the door, the gate will not be placed.
After these are all covered, for each room that is not the pod, the door closest to the pod is covered if there is not already a teki there.
After that process is done, the gates are placed randomly, where closer to the pod is more likely.
(This gate behavior is very important to understand, as it can help you locate buried objects. In some cases, you can infer that gates on alcoves must have something behind them)

And that's it!

In order to gain an understanding of a sublevel, you can look at a cave info report.
It shows you all of the sublevel's parameters, the cave units, and the spawnpoints in each unit.
These are color coded to correspond with the teki that can spawn. For objects, m2 means that the game
will try to spawn a minimum of 2 of this object. w1 means that if there are extra slots availible, the
weight for this object to fill one of the extra slots is 1.
The order that the teki appear in is always the order that they will be spawned in.

You can try to answer the quiz to test your understanding.

Reply · Report Post