Quadtree Spatial Partitioning for Scratch Hi! This is a backpackable/downloadable quadtree spatial partitioning system for Scratch. It helps manage lots of objects efficiently. For a demo, please see here: https://scratch.mit.edu/projects/1187193132/ ________ What is spatial partitioning? Spatial partitioning is a way to divide the screen into smaller areas and store objects based on where they are. Instead of checking every object, you only check the ones inside the area you care about. Why is this useful? * Faster games when many objects exist * Efficient collision checks * Large levels/worlds * Easy object culling (only process what's on screen) ________ Don't worry about the large number of custom blocks, you only need 3 to use this system. Everything else runs automatically. ________ Main Blocks (These are the important ones) ________ [Add object (x) (y) (ID) in quadtree] * Adds an object to the quadtree * Does NOT update your object list * You must: - Add x then y to your object list manually [Update object (ID) to position (x) (y)] * Updates the object's position in: - The object list - The quadtree * Automatically restructures the quadtree * You do not need to update values yourself [Get objects in box x (x) y (y) width (w) height (h)] * Gets all objects inside a rectangular area * Stores results in the (objects_inframe) list * Coordinates start from the lower-left corner, extending right and up * Best used only when needed, not every frame (ex: when the camera nears the edge) This is object culling. ________ Object format: * Odd item = x position * Even item = y position * Object ID = (length of object list) ÷ 2 Use this when adding objects that already exist. Object List Format * Every 2 list items = 1 object * Item 1: x position * Item 2: y position (This format may change later) ________ Advanced (Optional) ________ [Get container x (x) y (y)] * Finds which container exists at an x/y position * Outputs to (found_container) * Mostly for advanced or technical use [FIND C ID (C ID)] * Searches the Container list for an exact container ID * Stops the project if not found (prevents corruption) * Outputs to return C ID * Uses caching for speed (found_container) * Result from Get container - Outputs either 0 or a valid Container ID (limit_per_container) *Sets the maximum number of objects a container can have before it's subdivided. *Prevents nodes from becoming too complex which can also cause lag. *By default the limit is 4. ________ Container List Format Each container uses at least 4 list items: 1. Container ID (header) 2. Box size (in pixels at 100% scale) 3. Number of objects in the container 4. Object IDs... If used please credit MentalBox. Thanks!
