| Latest revision |
Your text |
| Line 1: |
Line 1: |
| − | 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. | + | This page explains the game's process behind spawning enemies in a cave. This is obtained through observation, and is subject to have some parts incorrect. |
| | | | |
| − | {{credits|JHawk}} | + | {{note|Until further notice, this only applies to spawning enemies.}} |
| | | | |
| − | == Summary == | + | ==Process== |
| − | The game...
| + | 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. |
| − | # 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 == | + | ===Main algorithm=== |
| − | 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.
| + | # For each <code>TekiInfo</code> entry in the [[Cave definition file|sublevel's configuration]], in order... |
| | + | ## Store the minimum amount of enemies to spawn. |
| | + | ## Store the spawn coordinate type. |
| | + | ## Do the [[#Spawn algorithm|spawn algorithm]] with this enemy type, amount, and spawn coordinate type. |
| | + | # If the number of enemies hasn't reached <code>{f002}</code> yet... |
| | + | ## For each <code>TekiInfo</code> entry in the sublevel's configuration... |
| | + | ### Grab its random distribution weight and add it to a list. |
| | + | ## While the number of enemies hasn't reached <code>{f002}</code>... |
| | + | ### Randomly decide what enemy to spawn next, using the weighted list built in the last step. |
| | + | ### Store the enemy's type. |
| | + | ### Store the spawn coordinate type. |
| | + | ### Do the [[#Spawn algorithm|spawn algorithm]] with this enemy type, amount of 1, and spawn coordinate type. |
| | + | # Remove every spawned object that is not meant to be there (collected treasures, Candypop Buds that disappear when you have 20+, etc.) |
| | | | |
| − | === Main algorithm === | + | ===Spawn 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. | + | # While the intended amount of enemies hasn't been spawned yet... |
| − | # Run the [[#Spawn type 5, 8, 1 algorithm|spawn type 5, 8, 1 algorithm]] to spawn all "main" category objects of type 5 (seams). | + | ## If all of the possible spawn positions of the intended type have been used up, leave this algorithm. |
| − | # Run the [[#Spawn type 5, 8, 1 algorithm|same algorithm]] to spawn all "main" category objects of type 8 ("special" enemies). | + | ## Pick a random non-dead end spawn coordinate of the intended type (every unit in the cave has [[Cave unit definition file#layout.txt|a set of spawn coordinates]]). |
| − | # Run the [[#Spawn type 5, 8, 1 algorithm|same algorithm]] to spawn all "main" category objects of type 1 ("hard" enemies).
| + | ## If this coordinate is out of bounds, skip it. |
| − | # Run the [[#Spawn type 0 algorithm|spawn type 0 algorithm]] to spawn all "main" category objects of type 0 ("easy" enemies). | + | ## If this coordinate has already been used, skip it. |
| − | # Run the [[#Spawn decorative algorithm|spawn decorative algorithm]] to spawn all "decorative" category objects. | + | ## Decide how many enemies to spawn here, picking randomly between the spawn coordinate's amount limits. |
| − | # Run the [[#Spawn treasure algorithm|spawn treasure algorithm]] to spawn all "treasure" category objects. | + | ## For each one in that amount... |
| − | # Run the [[#Spawn regular dead end algorithm|spawn regular dead end algorithm]] to spawn all regular "dead end" category objects. | + | ### If the number of enemies spawned here surpasses the intended amount, leave this algorithm. |
| − | # Run the [[#Spawn falling dead end algorithm|spawn falling dead end algorithm]] to spawn all falling "dead end" category objects. | + | ### Spawn that enemy in these coordinates (with slight variation). |
| − | # Run the [[#Spawn gate algorithm|spawn gate algorithm]] to spawn all gates. | + | ## Mark this spawn coordinate as used. |
| − | # 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 === | + | ==Weighted distribution== |
| − | 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.
| + | 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 definition has a weight number that goes from 0 to 9. Any object definition with a weight of 0 will not be picked, though. |
| | | | |
| − | # 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).
| + | To know what the chances are of the game picking a given object, all of the weight numbers are summed up, and the chance of that object is <code><object's weight> / <sum></code>. So for example, if you have the following list: |
| − | # 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 ===
| |
| − | * 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><entry's weight> / <sum></code>. So for example, if you have the following list: | |
| | | | |
| | {| class="wikitable" | | {| class="wikitable" |
