"Worms" solver

[manpages]

Deleted obsolete issue description, see next comment for the writeup

[manpages]

Bottom-up low harmonics N-Sharded construction with wormholes

Abstract

Here we define an approach to implementing a naive solver that emphasizes construction in low harmonics mode. To achieve this we need the following algorithms implemented:

1. Surface detection, to use in other algorithms
2. Closed space detection, to detect hollow spaces
3. Shortest path detection, to determine trajectories for bots that need to Fill matter along a path in order to complete filling a layer
4. Expected value function, to fuzzily determine how many bots should build a given model
5. Sharding algorithm, to determine into which classes to break a given model
6. Collision prevention algorithm in case robots are close to each other or are trying to cross each other's paths
7. The actual filling algorithm
8. Wormhole generation algorithm

Below is a preliminary write up that describes how to tie all of this together.

Bottom-up low harmonics

We want to be able to construct everything in low harmonics mode, that by itself is an ambitious enough goal for the lightning round. Currently, the approach envisioned is the following – we fill in layers as long as the things we want to fill in are grounded, then if there are voxels within the layer that needs to be filled, but is ungrounded, we determine a path within the model to reach it, fill it and then go proceed to the next layer.

We call a monovoxular connected trajectory a yarn.

We call a yarn that lies within a model such that there is another yarn within the model that connects starting and ending voxel non-unique yarn.

This is how we work with construction (one-bot example, scale to N-bot case using N-Sharding described further):

1. The bot moves to the center of any grounded subspace of the current layer.
2. The bot fills in the grounded subspace of the current layer.
3. For each ungrounded subspace of the current layer the bot: a. Determines the highest point reachable by building a vertical non-unique yarn [what about http://nn.lv/snwo?] b. From the destination point, it computes the shortest path to each of the ungrounded subspace c. Repeat (3) for the ungrounded subspaces that remain
4. Given travel plan made in 3, travel to the given subspaces in an optimal order and fill ungrounded subspaces on given layer
5. Proceed to the next layer and execute (1)

N-Sharded

Since it's extremely likely that using as many bots working at the same time as possible is the correct approach (notice that we want all the bots to work as much as possible), we propose a naive way of separating the concerns between the bots in the following way: divide the entire space into classes in such way that every bot has as equal as possible volume to fill (call those shards), then have bots perform bottom-up low harmonics algorithm (or any other solver for that matter, naive sharding should be solution-agnostic) in each of their shards. If there is no way to fill the layer entirely (see angled umbrella as a motivational example), the bot must issue wait command until there is a way to finish filling the layer.

Here's how we shard models:

1. Starting from vertical sector sharding: a. Rotate sharding around the x and y axis in the best effort to keep each shard grounded
2. With angled sector sharding: a. Rotate it around own axis (that used to be z axis in (1)) in the best effort to distribute voxels to be filled evenly across sectors.

Wormholes

By construction of shards, bots can't wall-in each other in this approach[Proof?], however they can get walled in due to hollow parts of the model:

-----------
|    |    |
|    |    |
|    |    |
|_________|

To prevent this, we ensure that every bot has a way to run away through a wormhole. A wormhole is a modification of initial model that preserves validity of a model, but reduces the amount of hollow subspaces (we call those hollows) by one.

Here's how we work with wormholes: We do surface detection, determining hollows, then we pick the outermost hollow and topmost outermost point within it, attempting to build a wormhole, following the procedure described below. A wormhole is valid if it replaces Filled voxels with Void voxels, while having bottom layer connected with the top layer:

 ..
 w.
  .

good

...
 w.
 .

bad

Now since we dig wormholes independently, based on the initial model, we are sure that we don't make our modified model non-grounded.

If a wormhole doesn't exist at a given point in a given outward direction, we switch to an adjacent Void point, after we exhaust points in this direction, we attempt to create a wormhole in another outward direction. If we have exhausted candidates, we go one level lower.

If an outward wormhole doesn't exist, we go inward, which is guaranteed to exist since the model is grounded.

For our simple idea when we divide space into subspaces for N robots, we should count hollows that are shared by more than one robot and make enough wormholes for all of them to be able to escape.

[manpages]

Google Docs version of the previous comment: https://docs.google.com/document/d/1LnlwVXcH0uWrVhiRLuNXNCEZKb2Jg8apvnKUXGtaL80/edit?usp=sharing

[manpages]

I went to sleep. I've updated Google Docs (see comment before) with the latest version of the write-up, please criticize, propose relevant algos for naive sharding.

[blakeelias]

Pseudocode for wormholes here: https://piratenpad.de/p/icfpc2018-tbd (see wormholes(model))

Currently, it just finds the top-most point on the outside surface of a hollow region.

[manpages]

Most likely irrelevant with 1x1 pillar solver idea by @lars and @kevroletin