Cellular Automata

[joshuabowers]

geometry/Surface.tsx currently fills out a flat plain with low-quality randomness. (As per #1, in theory, every CellType is effectively equally weighted, though particular random seeds might cause one CellType to be preferred over another.) This noise is not smoothed or otherwise adjusted. The hexagonal cells which are generated have only a single type associated with them; no subtypings or decorations exist. The stochastic process can, therefore, unintentionally generate interesting structure; however, this structure doesn't look natural: it just looks random.

The intended functionality for Surface is to utilize a cellular automata---a rules based system which runs over a series of generations to change the value of a given cell by applying the rules to its local neighborhood---to refine the noise into something more interesting. This process isn't difficult to code: for each cell, grab its neighbors; depending upon how those neighbors look, change the type of the central cell. Repeat this process a number of times.

Voxellian could potentially use cellular automata for generating natural looking environments in a variety of different contexts; given this, a slightly generalized CA framework might be desirable to build. For example, the following should allow for a variety of different automata to be specified:

interface Collection<TCell> {
  forEach: (cell: TCell, index: number) => void;
  neighborsOf: (cell: TCell) => TCell[];
  set: (index: number, cell: TCell) => void;
}

class CellularAutomata<TCell> {
  constructor( cells: Collection<TCell> ){ /* ... */ }
  addRule( neighborType: CellType, density: number, resultType: CellType ){ /* ... */ }
  run( generations: number ){ /* ... */ }
}

Assuming no TypeScript specific weirdness, such a set of interfaces might successfully represent a general case: define a new CellularAutomata with the collection of cells---hopefully collection agnostic---which adheres to a minimal interface for accessing and updating the individual cells. A set of rules to run during each generation would be provided to the automata via addRule; each rule has the form of defining the density of neighboring cell types which yield a change in type.

run, when it executes, would therefore loop generations times; each loop, it would iterate over each cell, grab the neighbors of that cell, calculate a set of densities for those neighbors---for each cell type, how many neighbors have that type---then apply each rule sequentially (i.e. order of addition to the rule set). If no rule applies, the current CellType stands.

As a potential problem point: my current understanding of cellular automata is that the generation being built should only rely upon the previous generation---not upon any changes which have been made this generation. Therefore, the collection which is being edited cannot be the same collection which contains the previous generation, or successive cells will have neighborhoods polluted with new generation cells. Normally, this would suggest each cohort needs a fresh container; the issue comes from the library I'm using to generate hexagonal grids: honeycomb-grid; it does weird things with typings (likely with prototypical additions to an object passed to extendHex and defineGrid), which makes it difficult to pass those things around in a type-safe fashion with TypeScript. The honeycomb stuff might need to be wrapped with a container which removes the type issues.

[joshuabowers]

As per ee30fc6, honeycomb-grid's neighborsOf algorithm is painfully slow: this algorithm runs, roughly, in linear time: for each neighbor which is calculated (all 6 of them!), the method does a full search of the underlying storage array to find and return that specific hex. (Each hex in honeycomb-grid has a bunch of prototype functionality which is unique, including use-customized prototype information. Which is to say, neighborsOf cannot just return a new set of hexes, as they would lack whatever information is stored within the grid. Hence the search.)

Using the profiling functionality hacked together in ee30fc6, a given execution of neighborsOf tends, with a grid size of about 330 hexes, to run for about 5-7 ms. This tends, again for a grid size of about 330 hexes, to cause the entire CellularAutomata.run algorithm to take somewhere around 1200-1700 ms to run for just a single generation. Comparably, replacing neighborsOf with a (completely inaccurate) empty array construction reduces this methods run time to about 3-5 ms. Seriously.

honeycomb-grid is not mine: it isn't my prerogative to write a PR that attempts to make it more efficient; it's overall design---wrt the interfaces and TS type declarations it exposes---is awkward. The only reason to use it was to avoid having to write my own hexagonal grid logic.

I've looked through the implementations of all the third party javascript implementations of RedBlobGames algorithms; none of them adequately implement the functionality I'm after. So, looks like self implementation is going to be a thing.

[joshuabowers]

As a note on data structures which might be usable for storing a hexagonal grid:

Ideally, accessing the neighbors of a given cell would be instantaneous: i.e. in constant time. This would suggest a hash table, as they tend towards average case complexity of O(1) for access. However, two problems exist: depending upon the implementation, hash collisions cause the average case to degenerate to O(n); secondly, even in modern JS, an explicit hash table data structure does not exist.

Modern JS implementations typically ship with Map and Set collections, which might be sufficient for the task of storing the grid. The MDN documentation does not suggest what sort of performance these objects operate under; it does note that Maps can operate faster for additions and removals than POJO.

Profiling operations with Map would be an ideal way to minimize the impact of having to implement a custom hexagonal grid library: if Map performs well enough for my use cases, it likely will be sufficient for storage. Otherwise, the hunt will need to be begin for alternatives. NPM suggests that plenty of implementations of hash tables or BBSTs exist. So, the necessity of implementing a custom collection is likely minimal.