# Research

__Proposed format__:
> Title describing area of research:
> * [Link to article](https://some-link.org)
> * Short 1--2 sentence explanation of what the article is about

> A `{*}` in front of a source means it is a scientific article/paper/book that is a trustworthy source (e.g. not a blog, or wikipedia)

[toc]

## ECS as a whole
* {\*} [Advantages and implementation of Entity-Component-Systems](https://trepo.tuni.fi/bitstream/handle/123456789/27593/H%C3%A4rk%C3%B6nen.pdf)
* A literature study of how ECS engines are built and their benefits and downsides
* Can be used as a reference in the report
* {\*} [Simulator X: A scalable and concurrenct architecture for intelligent realtime interactive systems](https://ieeexplore.ieee.org/document/5759457)
* Doesn't explicitly use ECS, but is quite similar in its use of entities. It's implemented using the actor model and message passing, which is unique.
* {\*} [Decoupling the entity-component-system pattern using semantic traits](https://ieeexplore.ieee.org/document/7854098)
* Describes how ECS does not allow for compatibility between differently typed components that contain the same data. Semantic traits are a way of solving this.
* {\*} [Vico: An entity-component-system based co-simulator](https://www.sciencedirect.com/science/article/pii/S1569190X20301726)
* A deterministic single-threaded ECS engine built on the JVM.
* [Options for Entity interaction](https://www.youtube.com/watch?v=KuGRkC6wzMY)
* How to handle entity-to-entity interactions in Unity's DOTS.
* [Adelost - ECS study](https://github.com/Adelost/entity-component-systems-study)
* Study comparing common optimization strategies for allocating and accessing components.

## Scheduling
* {\*} [A review of multiprocessor directed acyclic graph (DAG) scheduling algorithms](http://csjournals.com/IJCSC/PDF6-1/13.%20Shivanii.pdf)
* Great article for finding papers about different scheduling algorithms.
* {\*} [The interactive space-time scheduler](https://www.sciencedirect.com/science/article/abs/pii/016560749090226Y)
* Describes parallel scheduling of algorithms using dependency graphs
* [Wikipedia: Scheduling](https://en.wikipedia.org/wiki/Scheduling_(computing))
* General descriptions of the different types of schedulers that exist
* {\*} [OpenMP task scheduling strategies for multicore NUMA systems](https://journals.sagepub.com/doi/pdf/10.1177/1094342011434065)
* Describes different possible implementations of work-stealing schedulers and compares them against some common ones (e.g. round-robin)
* {\*} [Scheduling parallel programs by work stealing with private deques](https://dl.acm.org/doi/abs/10.1145/2442516.2442538)
* An implementation of a work-stealing scheduler that uses message passing to communicate between the worker threads.

## CPU Caching
* [code::dive conference 2014 - Scott Meyers: Cpu Caches and Why You Care](https://www.youtube.com/watch?v=WDIkqP4JbkE)
* Conference talk about CPU caching and thread memory access, among other things.

## Agile work
* [What is Kanban](https://www.cio.com/article/217626/what-is-kanban-workflow-management-simplified.html)
* Simplified description about Kanban

## Rust
* Low-level high-performance programming with high-level ergonomics ([iterators and closures](https://doc.rust-lang.org/book/ch13-00-functional-features.html), [pattern matching](https://doc.rust-lang.org/book/ch18-00-patterns.html))
* Eliminates entire classes of memory-problems such as dangling pointers, use-after-frees, double-frees and other forms of undefined behavior (UB) -- while matching the performance of memory-unsafe languages such as C/C++
* About 70% of all [CVEs at Microsoft](https://msrc-blog.microsoft.com/2019/07/18/we-need-a-safer-systems-programming-language/) are memory safety issues.
* Two-thirds of [Linux kernel vulnerabilities](https://static.sched.com/hosted_files/lssna19/d6/kernel-modules-in-rust-lssna2019.pdf) come from memory safety issues.
* An [Apple study](https://langui.sh/2019/07/23/apple-memory-safety/) found that 60-70% of vulnerabilities in iOS and macOS are memory safety vulnerabilities.
* [Google estimated](https://security.googleblog.com/2019/05/queue-hardening-enhancements.html) that 90% of Android vulnerabilities are memory safety issues.
* [70% of all Chrome security bugs](https://www.zdnet.com/article/chrome-70-of-all-security-bugs-are-memory-safety-issues/) are memory safety issues.
* [Guaranteed thread safety using the borrow-checker to deny data races at compile-time](https://blog.rust-lang.org/2015/04/10/Fearless-Concurrency.html)
* A robust type-system ([Algebraic Data Types](https://blog.softwaremill.com/algebraic-data-types-in-four-languages-858788043d4e))
* Rust has [advanced generics](https://doc.rust-lang.org/book/ch10-01-syntax.html) and [traits](https://doc.rust-lang.org/book/ch10-02-traits.html) with [type aliasing](https://doc.rust-lang.org/reference/items/type-aliases.html) and [type inference support](https://doc.rust-lang.org/rust-by-example/types/inference.html)
* Built-in high-quality tooling ([cargo](https://doc.rust-lang.org/cargo/) package manager, [clippy](https://github.com/rust-lang/rust-clippy) linter, [rustfmt](https://github.com/rust-lang/rustfmt) formatter, [rust-analyzer](https://rust-analyzer.github.io/) IDE language support)
* [A large ecosystem of concurrency-related packages](https://lib.rs/concurrency)

## Amdahl's Law
* [Wikipedia page](https://en.wikipedia.org/wiki/Amdahl%27s_law) contains all the information you need about Amdahl's law, however I found it not very easy to read through. [This](http://www.umsl.edu/~siegelj/CS4740_5740/Overview/Amdahl%27s.html) short description and the videos below([1](https://www.youtube.com/watch?v=Axx2xuB-Xuo),[2](https://www.youtube.com/watch?v=QutASUpGzbc)) was easier to understand, and should give enough understanding of Amdahl's law.
* S(N)=1/((1-P)+(P/N))
* N: Number of processors
* P: Proportion that is parallelizable
* S(N): The maximum speed up with N processors
* 1-P: The serial part of the process
* When N grows the speed up tends to 1/(1-p)
* For a process where 50% of the execution time is squential the maximum speed up is 2. This is due to only the parallelizable part can be speed up which can at most be 1/(1-0.5)=1/(1/2)=2.
* [Short youtube video(7min)](https://www.youtube.com/watch?v=Axx2xuB-Xuo)
* A short video explaining Amdahl's law in a somewhat easy way. Less general than the wikipedia page
* [Follow up, with examples(10min)](https://www.youtube.com/watch?v=QutASUpGzbc)
* Just a follow up video, going through some actual numbers and use cases for Amdahl's law.

## Downsides of ECS
* [ECS optimization study](https://github.com/Adelost/entity-component-systems-study)
* Seems to be a good overview of the approaches of implementing an ECS. (Object vs Component oriented, dynamic vs static data structures)

* [Intro to ECS](https://programming-guidebook.com/a/introduction-entity-component-system-ecs.html)
* States that the systems iterating over the components might be inefficient during regular applications as opposed to game/sim situations. (Authors note: Grasping at straws here)

* [Component structure pitfall](https://www.quora.com/Are-there-any-downsides-cons-with-the-new-job-System-Entity-component-System-ECS-in-Unity-2018)
* Discusses the presence of mind to create thoughtful components in order to avoid having to rewrite systems accessing these when changed.

## Parts of an ECS engine
* Data-Oriented Design
* [Data-Oriented Design and C++](https://www.youtube.com/watch?v=rX0ItVEVjHc)
* Goes through what data-oriented design means
* [Practical data-oriented design](https://media.handmade-seattle.com/practical-data-oriented-design/)
* How to apply data-oriented design in practice (talks about CPU cache efficiency, etc.)
* [Understanding data-oriented design for entity component systems - Unity at GDC 2019](https://www.youtube.com/watch?v=0_Byw9UMn9g)
* Talks about how data-oriented design is used in an ECS.
* [ECS: under the hood](https://habr.com/en/post/651921/)
* [Sparse / dense component data storage](https://skypjack.github.io/2019-03-07-ecs-baf-part-2/) is important for cache locality
* Solution: [Archetypes](https://ajmmertens.medium.com/building-an-ecs-2-archetypes-and-vectorization-fe21690805f9), but a downside is that adding/removing components on entities requires expensive archetype-changes
* Solution: [Sparse set](https://skypjack.github.io/2020-08-02-ecs-baf-part-9/), but a downside is that it requires more memory
* [Data structures for ES: Contiguous memory](https://t-machine.org/index.php/2014/03/08/data-structures-for-entity-systems-contiguous-memory/)
* A blog-post that goes into depth about the data structures an ECS needs.
* [Data structures for ES: Multi-threading and networking](https://t-machine.org/index.php/2015/05/02/data-structures-for-entity-systems-multi-threading-and-networking/)
* A blog-post that describes how to handle networking and threading in an ECS.
* {\*} [Wait-free hash maps in the entity-component-system pattern for realtime interactive systems](https://ieeexplore.ieee.org/abstract/document/7551583)
* Describes how the use of wait-free hashmaps can be integrated into ECS to increase scalability with the number of concurrently running threads.
* Querying / filtering of entities and components for systems
* Resolving queries
* Dependency graph could be generated using [topological sorting](https://en.wikipedia.org/wiki/Topological_sorting) algorithms
* [Indexing queries](https://devlog.hexops.com/2022/lets-build-ecs-part-2-databases/#indexing-queries): allow systems to query e.g. nearby entities using an octree for spatial-lookup acceleration
* Concurrent scheduling of systems
* {\*} A [dataflow](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=381846)-inspired approach could be used, where systems are "blocks" and components are the data flowing between them (example: [Microsoft's TPL Dataflow library](https://link.springer.com/chapter/10.1007/978-1-4302-5921-3_10))
* {\*} More modern: [A Survey of Pipelined Workflow Scheduling: Models and Algorithms](https://dl.acm.org/doi/pdf/10.1145%2F2501654.2501664)
* {\*} [Mutual exclusion scheduling with interval graphs or related classes](https://www.sciencedirect.com/science/article/pii/S0166218X08001959)
* Describes the problem of scheduling jobs that want mutually exclusive access to the same piece of data
* {\*} [Chromatic optimisation: Limitations, objectives, uses, references](https://www.sciencedirect.com/science/article/pii/S0377221782800027)
* Describes how to use graph coloring to represent scheduling problems and algorithms to solve them
* {\*} [Scheduling Computer and Manufacturing Processes](https://link.springer.com/book/10.1007/978-3-662-04363-9)
* An entire book dedicated to scheduling computer processes
* System execution ordering (similar to [Unity's frame order](https://docs.unity3d.com/Manual/ExecutionOrder.html))
* Serialization of execution state
* Triggered Systems: systems that have a precondition before they will run (e.g. "only run when `W` is pressed" or "only run when connected to server")

## Ethics and Social aspects
* [Code of ethics - International Game development association](https://members.igda.org/page/codeofethics)
* An established code of ethics to follow when developing games. More focused on the work and workplace ethics than the ethics of games themselves.
* [Ethics in the Videogame Industry](https://celiahodent.com/ethics-in-the-videogame-industry/)
* Article written about societal concerns regarding games, written by the director of UX at Epic Games.
* [Accessibility and Entity component system architecture](https://hal.science/hal-02987484/document)
* Paper about how entity component based architecture can help when developing games to make them more accessible for people with a disability.
* {\*} [Accessibility and serious games: What about EntityComponent-System software architecture?](https://link.springer.com/chapter/10.1007/978-3-030-63464-3_1)
* The article is found on pages 18-27.
* The paper looks into if ECS can provide the flexibility needed to add accessibility features late in game development.

## Schedule
* [Gantt chart](https://docs.google.com/spreadsheets/d/1YX_hbfd5mx5tAHCePJGUUfLh62rqDOhf-n_Xrmq-u9s/edit?usp=sharing)

## History of ECS

* [Object System used in Thief: The Dark Project (1998)](http://chrishecker.com/images/6/6f/ObjSys.ppt)
* Objects
* Objects are just ID’s
* Systems
* Data primarily used by a system is stored in the system
* Other systems can access the data using property system

* [Scott Bilas's Component System (CS) first used in Dungeon Siege (2002)](https://web.archive.org/web/20160325222032/http://scottbilas.com/files/2002/gdc_san_jose/game_objects_slides.pdf):
* Entities
* No logic and no data (may include frequently used data like position)
* Components
* Logic and data

* [Adam Martin's Entity Systems (EC) from 2007](https://t-machine.org/index.php/2007/09/03/entity-systems-are-the-future-of-mmog-development-part-1/):
* Entities
* Representing an in-game object
* Have no data and no methods
* Is an unique ID
* Components
* A component for each aspect of any entity
* All data is stored inside components
* Systems
* Each system runs continuously (own private thread)
* Performs global actions on all entities that have a component with the same aspect as the system

## ECS engines
* {\*} [Analysis of entity encoding techniques, design and implementation of a multithreaded compile-time Entity-Component-System](https://www.researchgate.net/publication/305730566_Analysis_of_entity_encoding_techniques_design_and_implementation_of_a_multithreaded_compile-time_Entity-Component-System_C14_library)
* Implementation of ECS in C++

* {\*} [Development of an Entity
Component System Architecture
for Realtime Simulation](https://kola.opus.hbz-nrw.de/frontdoor/deliver/index/docId/1932/file/thesis-2019-09-16-final.pdf)
* Similar to the paper above, less detailed. A bachelor thesis.
* Divided into 3 parts: Established paradigms, Architecture and Implementation.

* [EnTT](https://github.com/skypjack/entt)
* ECS engine built in modern C++
* Has benchmarks

## Different applications of ECS
The main application of ECS is to simulate different types of "physical" systems.

Here is a compilation of different domains that use an ECS engine, as well as what purpose the ECS engine serves in some of the examples.

### Game Development
* [Overwatch Gameplay Architecture and Netcode](https://www.youtube.com/watch?v=W3aieHjyNvw)
* ECS allowed the Overwatch development team to easily decouple the netcode implementation from the rest of the system as a consequence of using ECS.

### Physics simulations
* {\*} [AtomECS: Simulate laser cooling and magneto-optical traps](https://arxiv.org/pdf/2105.06447.pdf)
* An ECS engine was used to simulate the movement of atoms that are affected by laser radiation. They could shown that the simulation agree with theoretical results. This shows that ECS is not only for video games, where realism and accuracy is not the main focus, but that it has potential to be used to perform reliable physics experiments. The repository can be found on [GitHub](https://github.com/TeamAtomECS/AtomECS).

### Military
* {\*} [An Entity-component System Based, IEEE DIS Interoperability Interface](https://scholar.afit.edu/cgi/viewcontent.cgi?article=6360&context=etd)
* Thesis describing how ECS can be used to implement Distributed Interactive Simulations, which are used for military wargaming. Essentially online multiplayer games for military purposes.

### CAD Software
* [A Thought Experiment: Using the ECS Pattern Outside of Game Engines](https://adventures.michaelfbryan.com/posts/ecs-outside-of-games/)
* A blog post describing the benefits of using an ECS over a classical OOP structure to implement a CAD system. The code can be found on [GitHub](https://github.com/Michael-F-Bryan/arcs).

### GUI
* {\*} [Polyphony: Programming Interfaces and Interactions with the Entity-Component-System Model](https://hal.inria.fr/hal-02147180/document)
* The paper explores the applicability of ECS in user interfaces. They concluded that GUI's could benefit from the composability and high performance that ECS provides.

### Possible future applications
* [N-Body simulation](https://en.wikipedia.org/wiki/N-body_simulation)
* N-body simulation is a simulation of astronomical bodies where different physical forces are calculated, such as gravity. See also the [n-body problem](https://en.wikipedia.org/wiki/N-body_problem).