safe:|

rin · data-oriented design · build an ECS

rin-dod

Build an archetype entity component system from nothing, in fifteen chapters you read, compile and step through: from an entity as a number to a game running on it.

Start with 1.1, an entity is a number

Data-oriented design in rin, in two courses and a dojo:

  1. Build an ECS. Start here. Fifteen chapters that build an archetype entity component system from nothing, in the order of its name: entities, then components, then systems. It ends with a game running on it. Each chapter is a program that compiles on its own, the output it must print, and a guide that builds it step by step.
  2. Advanced: layout and SIMD. Seven lessons, for after. They cover what a loop fetches from memory, aliasing and noalias, what the compiler vectorizes and how to check it in the assembly, and which layout suits which access pattern.
  3. The dojo. The thirteen building blocks an ECS is made of, taken out on their own: a playground to watch each one work and break, and a kata to write it yourself, timed, against a harness, until your hands know it.

There is no renderer, no window and no library: only data, and the loops that stream it.

All of it is written in rin's safe subset. rin checks every program with its memory-safety rules on, the default on its regions branch, and every program prints its expected output and runs clean under AddressSanitizer and UBSan (tools/check.py). Memory is regions: level: region;, fields that say *vec<T> in level, lookups that return option<*T>. What the checker cannot see stays in small unsafe { } blocks and proc[unsafe] kernels: the type-erased byte columns, the noalias promises, and reading argv. The main branch keeps the earlier unsafe version of the course.

Build an ECS

chapterabout
1entities
1.1an entity is a numberids, components as arrays indexed by them, a system as a loop
1.2despawninga free list, reused numbers, and the stale reference they cause
1.3generationshandles that know when they are stale
1.4the entity indexslots, packed rows, swap-remove, kayan_verify
2components
2.1components and signaturescomponent ids, a registry of reflect records, 64-bit signatures
2.2columnsone array of any component, as bytes, viewed as a typed slice
2.3a tablethe entity index and the columns, joined
2.4archetypesa table for every combination, found by signature
2.5typed accesskayan_get<T>, kayan_set<T>; keep handles, borrow pointers
2.6adding and removingmoving between tables, and the archetype graph
2.7inspectingany entity, field by field, from reflection
3systems
3.1queriesthe tables a system runs over, matched once and kept
3.2systemskernels, systems, a schedule, a frame
3.3commandswhy a system cannot change structure, and the buffer that can
3.4a gameturrets, waves, bullets and fire, on everything above

Read each chapter's guide first. It explains the new idea and builds its code step by step, and every sample in it is copied from the chapter's program. Then open the program: it holds everything built so far, with the chapter's new code near the end, so any chapter can be opened in a debugger and stepped through as a whole ECS. Run it and read the output against the code. Each guide ends with exercises, most of them "break this on purpose and watch what happens".

Each chapter's file starts from the previous chapter's, so diffing two neighbours shows exactly what a chapter changed:

git diff --no-index ecs/src/2.components/2.5.typed_access/typed_access.rin ecs/src/2.components/2.6.add_remove/add_remove.rin

The ECS is called kayan, after the C sketch it grew out of.

The dojo

blockwhat it is
1free list and generationshandles that are safe to keep after what they name is gone
2swap-remove and the back-referencevalues packed with no holes, found by id: a sparse set
3the slot map1 and 2 together: handles into packed values
4a type-erased columnan array of any type as bytes, viewed as a typed slice
5a command bufferstructural changes recorded now and applied later
6bitsetsa set of components in a u64: has, all of, none of
7an arenapush, push, clear: memory for things that die together
8index, not pointerlinks that stay right when their storage moves
9interningfind or make, by key: a hash table that hands out dense ids
10memoized edgesa slow lookup done once, then remembered on the edge
11a reflection walkreading, writing and comparing any value through its type's record
12a watermarklooking only at what was added since last time
13a dispatch tablebehaviour as data: the schedule as a list of functions
python tools/dojo.py                      your reps, and which blocks are due
python tools/dojo.py play slot_map        watch it: the playground
python tools/dojo.py start slot_map 2     write it: a kata from level 2, timed
python tools/dojo.py slot_map             check it against the harness

Each block has three levels (one proc, every proc, a blank page) and a few variations, and the runner keeps your times and spaces your reps out. dojo/README.md has the rest. Each course chapter says which blocks it is built from.

Advanced: layout and SIMD

lessonabout
0from kayanwhat was kept from the C kayan, what changed, and why
1aos vs soathe same particles in three layouts, what a loop fetches, and what SIMD needs
2archetype tableone table: columns, rows, spawn, swap-remove, systems over slices
3many archetypesone table type for every archetype: ids, signatures, queries
4entity handlesgenerational handles, slots, moving between archetypes
5inspectorprinting and editing any entity from reflection records
6kayana small game, and deferring structural changes to a command buffer
7access patternsfour layouts under streams and lookups, and how an ECS decides

Lessons 1 and 7 are about memory, aliasing and the code the compiler makes. Lessons 2 to 6 build an ECS again, compressed into five steps, so read them as a recap of the course. docs/README.md has more.

Build and run

Needs a rin compiler built from rin's regions branch (rin.exe with its std beside it, through RIN_HOME or PATH), CMake, Ninja, clang-cl and the Windows SDK.

rin build
build\cmake\ids.exe

Every chapter and lesson is its own program, named after its file, and so is each dojo playground. Or compile one by hand: rin writes C, and any C compiler does the rest, with rin's folder and its std on the include path:

rin compile ecs/src/2.components/2.4.archetypes/archetypes.rin -o archetypes.c
clang -std=c11 -g -I <rin> -I <rin>/std archetypes.c -o archetypes

On Windows that last line warns about fopen; -D_CRT_SECURE_NO_WARNINGS quiets it, as build.rin does.

rin compile refuses a program that breaks a safety rule, so a program that builds has been checked. rin check file.rin does the checking alone.

python tools/check.py finds rin through RIN, then RIN_HOME, then PATH, and its std beside it. It builds every program with clang and warnings as errors, runs it, and compares what it prints with its .expected file. --sanitize adds AddressSanitizer and UBSan, --bless rewrites the expected files after a deliberate change, and a word filters the programs. tools/check_snippets.py checks that every sample in the ECS guides and the dojo's READMEs is in its program:

python tools/check.py ecs
python tools/check.py kayan --sanitize
python tools/check_snippets.py

rin itself builds on Windows: its arena runtime, in extern/haikal, calls VirtualAlloc. The generated C is portable, and the whole course has passed on Linux, gcc and clang, with a test build of rin over a stand-in for those calls, and -Wno-sign-compare added to tools/check.py's flags: an enum compared with its member warns there, harmlessly.

Reading it in a browser

Open website/index.html. It has every chapter's and lesson's guide, its source with line numbers, and the output it must print, with an index on the left. It is generated from the files in this repository, so after changing a program or a guide run python tools/site.py to bring it up to date.

Layout

ecs/
  src/
    1.entities/
      1.1.ids/
        ids.rin             the program
        ids.expected        what it prints
      ...
    2.components/
    3.systems/
    README.md               what the safe subset asks of each part
  docs/                     a guide a chapter: steps, output, exercises
  README.md                 the course on its own
src/                        the advanced lessons, one folder each
  1.aos_vs_soa/
    aos_vs_soa.rin          the program
    aos_vs_soa.expected     what it prints
  ...
includes/
  kayan.rin                 lesson 4's world, used by lessons 5 and 6
docs/                       the advanced lessons' guides
dojo/
  1.free_list/              a block: README, playground, harness, levels, solution
  ...
  README.md                 how the dojo works
  dojo.rin                  what every harness shares
website/
  index.html                everything as one page: guide, code, output
  template.html             its layout and styles
tools/
  check.py                  build, run and compare every program
  check_snippets.py         check every sample in the guides and dojo READMEs is in its program
  site.py                   rebuild website/index.html from the repo
  dojo.py                   start, run and time the dojo's katas
build.rin                   the program list, for `rin build`
task-8910.md                the backlog: lessons 8, 9 and 10

License

MIT. See LICENSE.

rin · data-oriented design · build an ECS

rin-dod

Build an archetype entity component system from nothing, in fifteen chapters you read, compile and step through: from an entity as a number to a game running on it.

Start with 1.1, an entity is a number

Data-oriented design in rin, in two courses and a dojo:

  1. Build an ECS. Start here. Fifteen chapters that build an archetype entity component system from nothing, in the order of its name: entities, then components, then systems. It ends with a game running on it. Each chapter is a program that compiles on its own, the output it must print, and a guide that builds it step by step.
  2. Advanced: layout and SIMD. Seven lessons, for after. They cover what a loop fetches from memory, aliasing and noalias, what the compiler vectorizes and how to check it in the assembly, and which layout suits which access pattern.
  3. The dojo. The thirteen building blocks an ECS is made of, taken out on their own: a playground to watch each one work and break, and a kata to write it yourself, timed, against a harness, until your hands know it.

There is no renderer, no window and no library: only data, and the loops that stream it.

Build an ECS

chapterabout
1entities
1.1an entity is a numberids, components as arrays indexed by them, a system as a loop
1.2despawninga free list, reused numbers, and the stale reference they cause
1.3generationshandles that know when they are stale
1.4the entity indexslots, packed rows, swap-remove, kayan_verify
2components
2.1components and signaturescomponent ids, a registry of reflect records, 64-bit signatures
2.2columnsone array of any component, as bytes, viewed as a typed slice
2.3a tablethe entity index and the columns, joined
2.4archetypesa table for every combination, found by signature
2.5typed accesskayan_get<T>, kayan_set<T>; keep handles, borrow pointers
2.6adding and removingmoving between tables, and the archetype graph
2.7inspectingany entity, field by field, from reflection
3systems
3.1queriesthe tables a system runs over, matched once and kept
3.2systemskernels, systems, a schedule, a frame
3.3commandswhy a system cannot change structure, and the buffer that can
3.4a gameturrets, waves, bullets and fire, on everything above

Read each chapter's guide first. It explains the new idea and builds its code step by step, and every sample in it is copied from the chapter's program. Then open the program: it holds everything built so far, with the chapter's new code near the end, so any chapter can be opened in a debugger and stepped through as a whole ECS. Run it and read the output against the code. Each guide ends with exercises, most of them "break this on purpose and watch what happens".

Each chapter's file starts from the previous chapter's, so diffing two neighbours shows exactly what a chapter changed:

git diff --no-index ecs/src/2.components/2.5.typed_access/typed_access.rin ecs/src/2.components/2.6.add_remove/add_remove.rin

The ECS is called kayan, after the C sketch it grew out of.

The dojo

blockwhat it is
1free list and generationshandles that are safe to keep after what they name is gone
2swap-remove and the back-referencevalues packed with no holes, found by id: a sparse set
3the slot map1 and 2 together: handles into packed values
4a type-erased columnan array of any type as bytes, viewed as a typed slice
5a command bufferstructural changes recorded now and applied later
6bitsetsa set of components in a u64: has, all of, none of
7an arenapush, push, clear: memory for things that die together
8index, not pointerlinks that stay right when their storage moves
9interningfind or make, by key: a hash table that hands out dense ids
10memoized edgesa slow lookup done once, then remembered on the edge
11a reflection walkreading, writing and comparing any value through its type's record
12a watermarklooking only at what was added since last time
13a dispatch tablebehaviour as data: the schedule as a list of functions
python tools/dojo.py                      your reps, and which blocks are due
python tools/dojo.py play slot_map        watch it: the playground
python tools/dojo.py start slot_map 2     write it: a kata from level 2, timed
python tools/dojo.py slot_map             check it against the harness

Each block has three levels (one proc, every proc, a blank page) and a few variations, and the runner keeps your times and spaces your reps out. dojo/README.md has the rest. Each course chapter says which blocks it is built from.

Advanced: layout and SIMD

lessonabout
0from kayanwhat was kept from the C kayan, what changed, and why
1aos vs soathe same particles in three layouts, what a loop fetches, and what SIMD needs
2archetype tableone table: columns, rows, spawn, swap-remove, systems over slices
3many archetypesone table type for every archetype: ids, signatures, queries
4entity handlesgenerational handles, slots, moving between archetypes
5inspectorprinting and editing any entity from reflection records
6kayana small game, and deferring structural changes to a command buffer
7access patternsfour layouts under streams and lookups, and how an ECS decides

Lessons 1 and 7 are about memory, aliasing and the code the compiler makes. Lessons 2 to 6 build an ECS again, compressed into five steps, so read them as a recap of the course. docs/README.md has more.

Build and run

Needs the rin compiler with noalias (rin 5413d4e or later; rin.exe from rin-windows-x64, through RIN_HOME or PATH), CMake, Ninja, clang-cl and the Windows SDK.

rin build
build\cmake\ids.exe

Every chapter and lesson is its own program, named after its file. Or compile one by hand: rin writes C, and any C compiler does the rest, with rin's folder and its std on the include path:

rin compile ecs/src/2.components/2.4.archetypes/archetypes.rin -o archetypes.c
clang -std=c11 -g -I <rin> -I <rin>/std archetypes.c -o archetypes

python tools/check.py builds every program with clang and warnings as errors, runs it, and compares what it prints with its .expected file. --sanitize adds AddressSanitizer and UBSan, --bless rewrites the expected files after a deliberate change, and a word filters the programs. tools/check_snippets.py checks that every sample in the ECS guides is in its program:

python tools/check.py ecs
python tools/check.py kayan --sanitize
python tools/check_snippets.py

The checker also works on Linux. There it relaxes -Wformat only: rin's printfmt and std print write %llu for u64, which is unsigned long on 64-bit Linux.

Reading it in a browser

Open website/index.html. It has every chapter's and lesson's guide, its source with line numbers, and the output it must print, with an index on the left. It is generated from the files in this repository, so after changing a program or a guide run python tools/site.py to bring it up to date.

Layout

ecs/
  src/
    1.entities/
      1.1.ids/
        ids.rin             the program
        ids.expected        what it prints
      ...
    2.components/
    3.systems/
  docs/                     a guide a chapter: steps, output, exercises
  README.md                 the course on its own
src/                        the advanced lessons, one folder each
includes/
  kayan.rin                 lesson 4's world, used by lessons 5 and 6
docs/                       the advanced lessons' guides
dojo/
  1.free_list/              a block: README, playground, harness, levels, solution
  ...
  dojo.rin                  what every harness shares
website/
  index.html                everything as one page: guide, code, output
  template.html             its layout and styles
tools/
  check.py                  build, run and compare every program
  check_snippets.py         check every sample in the guides and dojo READMEs is in its program
  site.py                   rebuild website/index.html from the repo
  dojo.py                   start, run and time the dojo's katas
build.rin                   the program list, for `rin build`

License

MIT. See LICENSE.