Library Functions

[blakeelias]

We need a variety of functions available that multiple solvers may need to use.

Board Queries:

• [ ] Neighbors to a voxel
• [ ] Neighbors to be Filled
• [ ] Neighbors to be Void
• [ ] Voxel has Filled neighbor?
  • Pseudocode here: https://piratenpad.de/p/icfpc2018-tbd (see has_filled_neighbor(voxel))
• [ ] Voxel has Empty neighbor?
• [ ] Detect hollow spaces
  • Pseudocode here: https://piratenpad.de/p/icfpc2018-tbd (see hollow_areas(model))
• [ ] Surface detection
  • Pseudocode here: https://piratenpad.de/p/icfpc2018-tbd (see outer_surface(hollow_area))
• [ ] Shortest path between two voxels, staying within the model (only using voxels that need to be Filled)

Bot movement:

• [ ] Fill in a region of space
• [ ] Collision prevention algorithm in case robots are close to each other or are trying to cross each other's paths

[Lucus16]

First of all, in order to have bots move around without colliding, I think it's useful if bots can mark cells as reserved for movement: When it needs to go somewhere, it calculates a free path and reserves all the cells on that path and then frees them after it's moved past them.

Similarly, it's useful to be able to reserve cells for filling so that independently acting bots don't try to fill the same space. Marking cells as reserved may also help for avoiding other conflicts.

In that context, the following building blocks seem useful:

• [ ] Calculate a shortest path (in terms of number of move ticks necessary) from a source to a target, given a state, avoiding volatile and reserved cells, using Dijkstra. Output should be a list of moves so the length indicates the number of ticks it takes.
• [ ] Reserve all cells needed for a move or list of moves.
• [ ] Execute a move and free the cells on the next tick.
• [ ] Check if any bot or to be filled voxel has become unreachable in a state, using flood fill or something. Movement reservations are temporary and need to be ignored. Filling reservations should not be ignored, but keep in mind that blocks can be filled diagonally, while bots can't move diagonally.
• [ ] Move the starting bot next to the nearest to be filled voxel on the ground.
• [ ] Split into twenty bots. Optimization is relatively unimportant.
• [ ] Join twenty bots and go home. Optimization is again unimportant.

[manpages]

• [ ] Shard with tunnel thickness threshold t (skeleton algorithm, should break the model in classes of tunnels and blobs, where a tunnel is a Full region with min(dx, dy, dz) <= t; Blob is a region that is connected to a tunnel such that min(dx, dy, dz) >= t. We should know how to merge tunnels and blobs together. Now if the entire model is split into blobs connected by tunnels, we can estimate the costs of filling each entity as well as the amount of robots required).
• [ ] List all the unique wide yarns (a yarn is a connected monovoxular path within a model between a source voxel and destination voxel, a yarn is called unique if there is only one yarn connecting two voxels within a model. This model has a unique yarn. This can be very useful for human analysis of tasks. If the notion of yarns will prove to be useful, we should extend it to t-yarns, which are tunnels, that are exactly t×t in each intersection.)
  • [ ] Create a wormhole in a given hollow (see this writeup for a reference)
  • [ ] "Greedy" filling algorithm that fills as much space as the rules allow at a time. (t-yarns and t-wormholes should be relevant here)

[Vlad-Shcherbina]

FYI C++ pathfinding is here: https://github.com/Vlad-Shcherbina/icfpc2018-tbd/blob/4989afb52149422a9dc7bac6204a03cd71d6f8f9/production/cpp_emulator/tests.py#L65