Editing Cave spawning

This page explains the game's process behind spawning enemies in a cave. This is obtained through code analysis, both of the game code and the [https://github.com/JHaack4/CaveGen CaveGen] project.

{{credits|JHawk}}

== Summary ==
The game...
# Spawns the minimum amounts of objects requested by each [[Cave generation parameters#Entry|entry]] of the main category.
# Spawns random filler objects from the same entries, until it reaches the limit in [[Cave generation parameters#FloorInfo|parameter <code>{f002}</code>]]. The way it picks these entries in particular is complex, but one important note is that different entries have a different chance of being picked, controlled by the [[#Weight distribution|random weight distribution]].
# Spawns the minimum amounts required by entries from the decorative category.
# Spawns the minimum amounts required by entries from the treasure category
# Spawns random filler objects from the same entries (also with weights), until it reaches the limit in parameter <code>{f003}</code>.
# Spawns the minimum amounts required by entries from the dead end category (non-falling and Candypop Buds).
# Spawns random filler objects from the same entries, until it runs out of possible dead ends.
# Spawns the minimum amounts required by entries from the dead end category (all other entries).
# Spawns random filler objects from the same entries, until it runs out of possible dead ends.
# Spawns random filler objects from the gate category (also with weights), until it reaches the limit in parameter <code>{f004}</code>.

== Process ==
Some time after the cave is built out of its [[Cave unit list file|available units]], the game will run this "main algorithm" in order to spawn objects. Note that this outline will only include information about which objects spawn, and how many. It does not have information on ''where'' they spawn, using the "score" mechanic.

=== Main algorithm ===
# Run the [[#Main category allocation algorithm|main category allocation algorithm]] to figure out how many "main" category entries of each spawn type will be spawned.
# Run the [[#Spawn type 5, 8, 1 algorithm|spawn type 5, 8, 1 algorithm]] to spawn all "main" category objects of type 5 (seams).
# Run the [[#Spawn type 5, 8, 1 algorithm|same algorithm]] to spawn all "main" category objects of type 8 ("special" enemies).
# Run the [[#Spawn type 5, 8, 1 algorithm|same algorithm]] to spawn all "main" category objects of type 1 ("hard" enemies).
# Run the [[#Spawn type 0 algorithm|spawn type 0 algorithm]] to spawn all "main" category objects of type 0 ("easy" enemies).
# Run the [[#Spawn decorative algorithm|spawn decorative algorithm]] to spawn all "decorative" category objects.
# Run the [[#Spawn treasure algorithm|spawn treasure algorithm]] to spawn all "treasure" category objects.
# Run the [[#Spawn regular dead end algorithm|spawn regular dead end algorithm]] to spawn all regular "dead end" category objects.
# Run the [[#Spawn falling dead end algorithm|spawn falling dead end algorithm]] to spawn all falling "dead end" category objects.
# Run the [[#Spawn gate algorithm|spawn gate algorithm]] to spawn all gates.
# Remove every spawned object that is not meant to be there (already-collected treasures, Candypop Buds that disappear when you have 20+, etc.)

=== Main category allocation algorithm ===
This algorithm saves how many objects of type 0 we want to spawn, how many of type 1, of type 5, and of type 8.

# Save the number of allocations of spawn type 0 ("easy" enemies) as 0. Repeat for types 1 ("hard" enemies), 5 (seams), and 8 ("special" enemies).
# Save the weight of each spawn type as 0.
# For each "main" category entry in the [[Cave definition file|sublevel's configuration]]:
## Add the minimum amount of that entry to the number of allocations of the relevant spawn type.
## Add the weight of that entry to the weight of the relevant spawn type.
# Repeat until the number of allocations reaches the "main" category limit in <code>{f002}</code>:
## With [[#Weighted distribution|weighted randomness]], pick a spawn type, using the spawn type weights.
## Add +1 allocation to the chosen spawn type.

=== Spawn type 5, 8, 1 algorithm ===
This algorithm spawns objects of types 5, 8, or 1.

# Repeat n times, n being the number of allocations for the spawn type.
## Pick a free spawn point of the given type.
### For type 5, this means picking a free seam. Note that not all seams have the same chance of being picked.
### For types 8 or 1, this means a standard spawn point. Note that some points cannot; see [[#Notes|notes]].
## Run the [[#Regular entry picking algorithm|regular entry picking algorithm]] with all entries of this type, and the number of spawned objects of this type so far.
## If there is no spawn point or entry that can be picked, finish now.
## Spawn one object of that entry on that spawn point.
## Mark that spawn point as used.

=== Spawn type 0 algorithm ===
This algorithm spawns objects of type 0.

# Repeat n times, n being the number of allocations for spawn type 0.
## Pick a free spawn point of type 0. Note that some points cannot; see [[#Notes|notes]].
## Run the [[#Regular Entry picking algorithm|regular entry picking algorithm]] with all entries of type 0, and the number of spawned objects type 0 so far.
## If we picked an entry because we still have minimum amounts to fill, then:
### Save the number of candidates as the number of objects we still have left to spawn of the given entry to meet its minimum.
## Otherwise:
### Save the number of candidates as the number of "main" category objects we can still spawn before meeting the "main" category limit in <code>{f002}</code>.
## Save the maximum number to spawn as the spawn point's maximum amount, or the number of candidates, whichever is smaller.
## If the maximum number to spawn is greater than the spawn point's minimum amount, then:
### Save the number to spawn as a random number between the the spawn point's minimum amount, and our maximum number to spawn.
## Otherwise:
### Save the number to spawn as the maximum number to spawn.
## If there is no spawn point or no entry that can be picked, finish now.
## If the number to spawn is 0, finish now.
## Spawn however many objects we wanted to spawn on that spawn point.
## Randomly move the new objects around the spawn point, using the spawn point's "radius" property.
## Push the new objects around out of the way of each other.
## Mark that spawn point as used.

=== Spawn decorative algorithm ===
This algorithm spawns "decorative" category objects.

# Repeat n times, n being the number of "decorative" category objects that need to be spawned.
## Pick a free spawn point of type 6.
## Run the [[#Regular entry picking algorithm|regular entry picking algorithm]] with all entries of the "decorative" category, and the number of spawned objects of the "decorative" category so far.
## If there is no spawn point or entry that can be picked, finish now.
## Spawn one object of that entry on that spawn point.
## Mark that spawn point as used.

=== Spawn treasure algorithm ===
This algorithm spawns "treasure" category objects. This does not count treasures that are carried inside of enemies in any form.

# Repeat n times, n being the number of "treasure" category objects that need to be spawned as per <code>{f003}</code>.
## Pick a free spawn point of type 2. Note that not all points have the same chance of being picked.
## Run the [[#Regular entry picking algorithm|regular entry picking algorithm]] with all entries of the "treasure" category, and the number of spawned objects of the "treasure" category so far.
## If there is no spawn point or entry that can be picked, finish now.
## Spawn one object of that entry on that spawn point.
## Mark that spawn point as used.

=== Spawn regular dead end algorithm ===
This algorithm spawns regular "dead end" category objects. This means all objects that are not set to fall from the sky, as well as all Candypop Buds.

# Repeat for every dead end cave unit placed in the sublevel, in order.
## If this dead end cannot hold objects, skip to the next.
## If this dead end's spawn point has been used, skip to the next.
## Run the [[#Dead end entry picking algorithm|dead end picking algorithm]] with the regular "dead end" category entries.
## If there is anything to spawn, then spawn either one or two.
## Mark that spawn point as used.
## If it's a Candypop Bud, then:
### Mark the spawn point as used for "dead end falling" purposes.
### If it falls from the sky, then mark it as used for "dead end falling Candypop" purposes.

=== Spawn falling dead end algorithm ===
This algorithm spawns falling "dead end" category objects. This means all objects that are not "regular", as per the [[#Spawn regular dead end algorithm|spawn regular dead end algorithm]].

# Repeat for every dead end cave unit placed in the sublevel, in order.
## If this dead end cannot hold objects, skip to the next.
## If this dead end's spawn point has been used for "dead end falling" purposes, skip to the next.
## Run the [[#Dead end entry picking algorithm|dead end picking algorithm]] with the falling "dead end" category entries.
## If there is anything to spawn, then spawn either one or two.
## Mark that spawn point as used for "dead end falling" purposes.

=== Spawn gate algorithm ===
This algorithm spawns gate objects.

# Repeat n times, n being the number of gates to spawn as per <code>{f004}</code>.
## Pick a gate entry using [[#Weighted distribution|weighted randomness]], using the weights of the gate entries.
## Pick a spawn point for the gate. While this takes place in seams, the process the game uses for picking is very complicated.
## If there is no spawn point or entry that can be picked, finish now.
## Spawn one gate of that entry on that spawn point.
## Mark that spawn point as used.

=== Regular entry picking algorithm ===
This algorithm picks an object entry from a given set, and chooses an entry for the purposes of spawning. It checks how many of the set's type have been spawned so far to decide which one to pick next.

# If we haven't spawned all necessary minimum amounts for objects of the set, then:
## Pick an entry whose minimum amounts haven't been met yet. Prioritize the order in the sublevel configuration file.
# Otherwise, if weight is a thing, and there are entries in the set with any weight, then:
## Pick an entry in the set using [[#Weighted distribution|weighted randomness]], using the weights of the entries in the set.
# Otherwise:
## Pick none.

=== Dead end entry picking algorithm ===
This algorithm picks an object entry from a given set, and chooses an entry for the purposes of spawning. It checks how many of the set's type have been spawned so far to decide which one to pick next.

# If we haven't spawned all necessary minimum amounts for objects of the set, then:
## Pick an entry whose minimum amounts haven't been met yet. Prioritize the order in the sublevel configuration file.
## If the entry is of the "type" 0, and if we can spawn two of these without going over the entry's minimum amount:
### Pick this one, returning 2 as the amount.
## Otherwise:
### Pick this one, returning 1 as the amount.
# Otherwise, if there are entries in the set with any weight, then:
## Pick an entry in the set using [[#Weighted distribution|weighted randomness]], using the weights of the entries in the set.
## If the entry is of the "type" 0, pick this one, returning 2 as the amount.
## Otherwise, pick this one, returning 1 as the amount.
# Otherwise:
## Roll the RNG once for no reason.
## Pick none.

=== Notes ===
{{todo|Confirm that 0-radius claim.}}
* If a spawn coordinate has a radius of 0, all objects to spawn will be placed in the same spot, and will physically push each other apart. Otherwise, the objects will be forced to maintain a fixed minimum distance from one another, even if that distance will push them beyond the spawn coordinate's radius.
* If an object would spawn out of bounds, it will fail to spawn. This can happen if its spawn point is out of bounds, if it got pushed out of bounds due to the [[#Spawn type 0 algorithm|spawn type 0 algorithm]], etc.
* A spawn point for "main" objects of types 0, 1, or 8 can only be picked if all of the following are true:
*# It is in a "room" type cave unit.
*# It has not been used already.
*# It is far enough away from the ship's pod (300 units).
*# It is far enough away from the hole (N/A for type 0, 200 units for type 1, 150 units for type 8).
*# It is far enough away from the geyser (N/A for type 0, 200 units for type 1, 150 units for type 8).

{{credits|[[User:Espyo|Espyo]], [[User:Jimble|Jimble]]}}

== Weighted distribution ==
Some types of object may come up more often than others. For instance, a developer could want a cave where the enemy slots are filled randomly, with each one having a 90% chance of being a Red Bulborb, and 10% chance of being a Wollywog. This is known as weighted random distribution. The way ''Pikmin 2'' does this is that every object entry has a weight number that goes from 0 to 9. Any object entry with a weight of 0 will not be picked, though.

To know what the chances are of the game picking a given entry, all of the weight numbers are summed up, and the chance of that entry is <code>&lt;entry's weight&gt; / &lt;sum&gt;</code>. So for example, if you have the following list:

{| class="wikitable"
|-
! Object || Weight
|-
| Red Bulborb || 4
|-
| Wollywog || 7
|-
| Water Dumple || 3
|}

The chances of spawning a Red Bulborb are 28.5% (4 in 14), the chances of a Wollywog are 50% (7 in 14), and the chances of a Water Dumple are 21.4% (3 in 14).

[[Category:Pikmin 2]]
[[Category:Algorithms]]