Replace IslandGrid nested TreeMap with spatial hash#2840
Merged
tastybento merged 1 commit intodevelopfrom Mar 13, 2026
Merged
Conversation
…ding The nested TreeMap implementation had O(n²) complexity during island loading due to full-grid scans in removeFromGrid() and headMap() overlap detection. This caused servers with many islands to hang at "Loading islands from database.." (fixes #2838). Also fixes a correctness bug in getIslandStringAt() where the floorEntry() approach could miss large islands at lower X keys when smaller islands existed at closer X coordinates — critical for arbitrary island positions (Stranger Realms). Replaces internals with a cell-based spatial hash (HashMap<Long, Set<String>>) giving O(1) average-case point lookups, O(c×k) insertion with overlap detection, and O(c) removal. Replaces getGrid() with getAllIslands() and getIslandsInBounds() and updates AdminPurgeRegionsCommand accordingly. Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>
cfa114f to
7292b3e
Compare
|
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
1 participant
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.
Summary
TreeMapinternals ofIslandGridwith a cell-based spatial hash (HashMap), reducing island loading from O(n²) to O(n) — fixes Bentobox 3.11.1 not loading on paper 1.21.8 #2838 where servers with many islands hang at "Loading islands from database.."getIslandStringAt()where thefloorEntry()approach missed large islands at lower X keys when smaller islands existed at closer X coordinates — critical for Stranger Realms arbitrary island positionsgetGrid()withgetAllIslands()andgetIslandsInBounds(), updatingAdminPurgeRegionsCommandaccordinglyTest plan
./gradlew clean build— all existing + 8 new IslandGrid tests should passrelates to #2838