Implementation:Google deepmind Mujoco Engine Island
| Knowledge Sources | |
|---|---|
| Domains | Physics Simulation, Graph Algorithms, Constraint Solving |
| Last Updated | 2026-02-15 04:00 GMT |
Overview
Discovers and assigns constraint islands (disjoint subgraphs) in the simulation to enable independent parallel constraint solving.
Description
engine_island.c implements the island discovery algorithm for MuJoCo's constraint solver. It identifies disjoint groups of bodies and constraints ("islands") that do not interact with each other, allowing them to be solved independently. The algorithm works by constructing a sparse adjacency graph of kinematic trees connected by constraints, then using a flood-fill (DFS traversal) to assign island indices. Arena memory is allocated for island-related data structures, and constraints and DOFs are reordered to be contiguous within each island.
Usage
Called during the forward dynamics pipeline via mj_island() after constraint construction. Island discovery is used to partition the constraint problem for parallel solving and is controlled by the mjDSBL_ISLAND disable flag.
Code Reference
Source Location
- Repository: Google_deepmind_Mujoco
- File: src/engine/engine_island.c
- Lines: 1-606
Key Functions
// find disjoint subgraphs ("islands") given sparse symmetric adjacency matrix
int mj_floodFill(int* island, int nr, const int* rownnz,
const int* rowadr, const int* colind, int* stack);
// clear island-related arena pointers in mjData
static void clearIsland(mjData* d, size_t parena);
// allocate island arrays on arena
static int arenaAllocIsland(const mjModel* m, mjData* d);
// find edges in the tree-tree adjacency graph
static int findEdges(const mjModel* m, const mjData* d,
int* rownnz, int* edge, mjtByte* tree_tree,
int ntree, int tree1, int tree2);
// main island discovery and assignment
void mj_island(const mjModel* m, mjData* d);
Import
#include "engine/engine_island.h"
I/O Contract
Inputs
| Name | Type | Required | Description |
|---|---|---|---|
| m | const mjModel* | Yes | Physics model with tree and constraint structure |
| d | mjData* | Yes | Simulation state with constraint data |
| island | int* | Yes (floodFill) | Output array for island indices per vertex |
| nr | int | Yes (floodFill) | Number of rows/columns of adjacency matrix |
| rownnz | const int* | Yes (floodFill) | Row nonzero counts for sparse adjacency |
| rowadr | const int* | Yes (floodFill) | Row addresses for sparse adjacency |
| colind | const int* | Yes (floodFill) | Column indices for sparse adjacency |
Outputs
| Name | Type | Description |
|---|---|---|
| d->nisland | int | Number of discovered islands |
| d->island_dofadr | int* | Starting DOF address per island |
| d->island_dofnum | int* | Number of DOFs per island |
| d->island_efcadr | int* | Starting constraint address per island |
| d->island_efcnum | int* | Number of constraints per island |
| d->dof_island | int* | Island index assigned to each DOF |
| d->efc_island | int* | Island index assigned to each constraint |
| return (floodFill) | int | Number of islands found |