Merged
Conversation
This got merged into Archipelago 0.6.2, so this commit was duplicating the change. This reverts commit e1b0375.
…hipelagoMW#3872) Reduces the duration of progression fill by about 40% on average. For smaller generations, the size of the reduction can vary. A large performance cost in fill_restrictive is sweeping to create the maximum exploration state because it sweeps from base_state every time. This patch breaks up fill_restrictive to fill in batches of items at a time. Each batch creates its own base state, and additionally a sweep state created from the batch's base state. The advantage to this is that the maximum exploration state can be created from the batch's sweep state rather than having to sweep from base_state. As a small bonus, the batch's sweep state can sometimes also be used to create a swap_state, increasing swap performance. A successful swap will sometimes destroy the batch's sweep state and require it to be re-created, but because swap sweeps to create a swap_state for every location it checks, occasionally adding a single extra sweep on a successful swap is negligible. There are no expected changes to the contents of the output of generations with this patch.
This reverts commit edc4548.
Increases the performance of sweeping state in `CollectionState.sweep_for_events()` and `MultiWorld.can_beat_game`, without changing the generated output (at least for supported games with their template yamls). `CollectionState.sweep_for_events()` takes up a significant amount of generation time, mostly from filling progression items, and the majority when not generating a playthrough, so improvements to its performance can have a noticeable effect on generation duration. Similarly, `MultiWorld.can_beat_game()` takes up a significant amount of playthrough calculation time from culling spheres. This patch reduces the duration of both and refactors them to use the same sweeping code. This patch has been split from ArchipelagoMW#3688 to focus only on the sweep itself, and has been simplified to not require any additions to the existing world API. ### Make better use of region accessibility caching Region accessibility is cached per-player and the cache for that player becomes stale whenever an item is collected or removed for that player. The original sweeping implementations make use of this by only collecting items once all reachable locations have been found for all players. This patch changes to the sweep to find reachable locations per-player, collect the items from those locations and then move onto the next player. This keeps region accessibility cached as before, but has the advantage that if a player's reachable locations contain an item that gives a later player access to more locations, it will take fewer iterations for all reachable locations to be collected from. ### Skip checking location accessibility for locations belonging to a player which did not receive any advancement in the previous iteration If no advancement items belonging to a player were collected in the previous sweep iteration (after the point at which their reachable locations were found), then it is assumed that player should have zero newly reachable locations, so checking for their reachable locations can be skipped. While almost all worlds only logically depend on only their own items/locations etc., it is possible for a world to logically depend on a part of another world. To account for this, once the sweep runs out of accessible locations, the locations of all players are checked to confirm that the sweep is indeed finished. My previous idea to account for worlds logically depending on other worlds was to require all worlds to specify which worlds they logically depended on. Performing extra sweeps to confirm will be slower than this previous idea, but it is simpler and does not require any changes to the existing world API.
To determine if an item in a sphere is required, playthrough calculation would remove the item from its location and then use can_beat_game to sweep through locations until either the game can be beaten (the item is not required) or until the sweep runs out of reachable locations (the item is required). This patch changes how it is determined if an item is required. The advancement locations in each higher sphere that have already been culled must be reached for the game to be beatable, so iterate through the advancement locations in each higher sphere after attempting to cull an item. If all locations in a higher sphere and all unreachable locations carried over from a lower sphere are unreachable, then the game is unbeatable and the item is therefore required to beat the game. For items which are required to beat the game, this aborts faster than exhausting all reachable locations to determine that the game is unbeatable. For items which are not required to beat the game, the locations which should be reachable from the current sphere are known in advance, so this only has to check reachability of the locations in the closest higher sphere, and any unreachable locations carried over from lower spheres, before moving onto the next closest sphere, rather than repeatedly checking all filled locations which have yet to be reached. This results in a faster playthrough calculation that also scales better than the previous implementation as the number of advancement items in the multiworld increases. Playthrough calculation duration averaged over 5 generations of the same seed recorded before/s -> after/s. 57 unique games: 671.2 -> 179.5 (73.3% reduction) 28 unique games: 149.2 -> 47.8 (68.0% reduction) 14 unique games: 7.0 -> 4.2 (39.4% reduction) 7 unique games: 4.6 -> 3.4 (26.8% reduction) Because the spheres are re-arranged and new spheres are added while iterating, there is no longer a need to calculate the final spheres because the result is already in its final spheres. The type hint in create_paths has been changed from List[Set[Location]] to Collection[Set[Location]] to allow passing it a deque.
Eijebong
pushed a commit
that referenced
this pull request
Feb 8, 2026
Eijebong
pushed a commit
that referenced
this pull request
Feb 24, 2026
* Fix progressive bombchu bag * Add descriptive comment so this doesn't happen again * Update Items.py * Fixes as per aMannus review * Oops * Make Epona just an event item * Attempt to prefill dungeon rewards before shops * Revert "Attempt to prefill dungeon rewards before shops" This reverts commit 7cafd11. * Fix dungeon rewards prefill hopefully for real this time * Remove unused helpers * Minor fixes * change display name * Fix minor issues * Swap to StrEnum * Swap to modern typing * Fix remove * Fix a bunch of broken locations * Fix overfilling item pool * More logic fixes * Move filler item pool to after prefills * Update __init__.py * Fix missing has_item for bombchu bowling * Fix shop items and wallets * Revert "Move filler item pool to after prefills" This reverts commit 2a0fa4c. * Add missing option groups * Fix more broken locations * Minor changes around slot data * Fix can buy item strings and shuffle shop descriptions * Add tests for collect and remove * Update comment * Make it also check that you don't erroneously have the next rank * Remove Unused DMC_VOLCANO_VENT Exclude HC_GARDEN from regions when skip_child_zelda option is enabled. * Commented out MQ regions from Regions class. * Implement min/max shop price options * Implement randomized scrub prices * Create archipelago.json * Apply pep8 code styling to entire apworld * Add protection against too many triforce pieces * Shorten subtraction * All locations sending correctly in Ship! * Rescued * Update to what we talked about over discord * fix my dumbness * Add rounding to the Triforce Hunt Completion Event Calc Update Some stray strings to the Enum equivilent * do the thing * requested changes * Move pre_fill stuff to create_items * Make Jabu Jabus Belly Boss Exit accessible * Fix some stuff that should've been changed to enums * Change the rest of the ones in this file to enums too cause why not * requested change and some cleanup * forgot to actually update the total option * Comment out Jabu * Remove debug print * Fix missing ocarina requirement * Comment out a MQ location that shouldn't have been there * Comment out another MQ location that shouldn't have been there * testing * LLR Lon Lon Ranch GS Tree * more testing * Pass apworld version in with slot data * Fix triforce pieces * Fix triforce pieces * Why the hell is this the fix * presets * Fix errors * hopefully final fixes * update ocarina * Various minor item pool fixes * Change to using pre-fill again * Revert "Various minor item pool fixes" This reverts commit edca351. * Fix item pool maybe for real now * Re-order init.py and add get_pre_fill_items * Add shop items to the pre_fill_items * Move triforce piece creation and filler items to create_items * Fix shop item count * Update Preset Names * Make pre_fill faster * LLR GS Tree broke * Comment out visualize_regions * Reorganize init * Fix can_play_song and skip epona race name * Put in good UT support * Remove unused import * Fix item_group_count * Fix can_play_song * Put placeholder in for tricks_in_logic * Rename ut_stuff.py to UniversalTracker.py * Update __init__.py * Remove comment * Fix master sword issue with starting age as adult * Push version number * Implement get_filler_item_name * Remove debug thing * this sucks but it works I guess * Scrub Option text * add missing logic * this sucks but it works I guess * Fix connection in forest temple * Remove bombchu bag as a progressive item * Remove age exclusive checks * Remove legacy Ages.BOTH enum and instances * Fix and simplify bombchu helpers * Update version * Make dungeon rewards and vanilla shop items random * Fix for King Dodongo Fight logic * Fix shop item price rules * Version to 0.0.4 * Fix minor issue in the connection between ZD and LH * Update Castle Entryway connection * add parenthesis * Add unit test * Add unit test as a double check * Make item names strings * Add location_name_groups to init * Add location_name_groups * Add Boss Souls item group * True no logic option * Test that age rules work * Add the no logic-only locations * Remove the .values from Locations.py * Also add it to the UT thing * Optimize bottle_count since it's only used once * Rename bottle_count to has_bottle_count * Don't calculate early in has_projectile * Just directly use has_projectile for can_use_projectile * Remove unused variable assignments, clean up can_standing_shield * Flip check in can_get_nighttime_gs to early out on a quicker to calculate part * More misc cleanup * Remove unused function, can_hit_switch * Remove unnecessary arg from can_hit_at_range in can_kill_enemy * Use can_use_any a lot in can_kill_enemy * Make has_boss_soul shorter * Clean up can_pass_enemy * Use a dictionary for has_key_ring instead of an if tree * More cleanup * Cache hearts * Remove the old version that was commented out * Remove unused imports * Final cleanup * Further simplify small_keys * Make skulls depriority * Remove piece of heart from heart count function * Remove pieces of heart from heart test * Remove pieces of heart from logic helpers * Pull the heart stuff out * Heart stuff * Added can_reach override to SohLocation to differentiate between child and adult reachable locations * Add settings name to description * Update check for no logic locations to include checking if trees and crates are actually enabled * Resolve LogicHelper.py errors and remove can_live * Add back tree that was removed by accident * Revert age specific skulls * Fix graveyard gossip stone fairy rule * update deku torch room to water back * Deku Tree Entrance * Fix deku theater GS rule * Update test_time.py * Update Locations.py * I had one job (fix parenths) * Fix location name group * Add switch event * Update version to 0.0.5 * Minor default option changes * Implement time of day events * Fix zora's river grass logic * Fix sun check logic * Prepare readme * Small update to the setup guide * More minor doc changes * Added credits to readme * Formatting changes * Forever reformat * Ice cavern refactor * Fixes * Update doc links to new fork * Format ice cavern and fix KOKIRI_SHIELD -> DEKU_SHIELD * Update version to 1.0.0 * Add slingshot ammo to filler items --------- Co-authored-by: Scipio Wright <[email protected]> Co-authored-by: Tzuf <[email protected]> Co-authored-by: Hunter Marshall <[email protected]> Co-authored-by: BootsinSoots <[email protected]> Co-authored-by: mattman107 <[email protected]> Co-authored-by: Tzuf <[email protected]> Co-authored-by: Jerom Venneker <[email protected]> Co-authored-by: Eric Hoey <[email protected]>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Reverted e1b0375, this is already included in AP 0.6.2, so the commit had added the
__iter__method a second time.adbc879: Re-squashed and cherry picked from ArchipelagoMW#3872
Ignored b5db7ac because it is already included in AP 0.6.2.
Ignored 0075445, instead reverted edc4548 and re-squashed and cherry picked from ArchipelagoMW#3812 because it includes the changes in 0075445
499b2f1: Re-squashed and cherry picked from ArchipelagoMW#3890
507a9a5 has already been applied as 8343271, so there was nothing to do