Code Overview 8: Array Exploration

A project log for HEXABITZ - Modular Electronics for REAL

A new kind of electronic prototyping!

HexabitzHexabitz 06/03/2018 at 23:400 Comments

Array exploration is a feature that lets automatically configure your Hexabitz arrays and generate their topology without a sweat. It is particularly useful for large and complex arrays where manually generating the topology is usually cumbersome and error-prone.

Once you assemble your array and program all modules with native firmware, You can invoke the array exploration algorithm via the Explore() API or explore CLI command. The algorithm finds out number of connected modules (N), the topology routing table (stored in array matrix) and which ports are swapped. All of these information are stored either in the emulated EEPROM or a special Flash page so that you don't have to explore again every time you reboot the array. Note that the module you're connected to when invoking the exploration algorithm will be assigned ID #1. Other modules will be assigned sequential IDs based on their relative distance to the master (module #1).

Exploration Algorithm

Here's a detailed step-by-step description of what happens in the exploration algorithm:

  1. The master module (ID #1) swaps all its ports and explores adjacent neighbors by sending them an inquiry message. Neighbors send back a response mentioning which port they heard the inquiry from. 
  2. The master then starts assigning IDs to new modules and updating its topology array:
    1. Assign sequential IDs to neighboring modules (according to master ports they're connected to).
    2. Update the master topology array with IDs and ports of neighboring modules.
    3. Ask neighbors to update their own topology array.
  3. The master asks each new module to explore its neighbors, basically repeating steps 1 & 2. This continues level by level until all modules are explored:
    1. Master asks a given module to swap its ports
    2. Master asks the module to explore its adjacent neighbors.
    3. Master assigns IDs to this module adjacent neighbors.
    4. Master updates its topology array.
    5. Master asks all discovered modules to update their topology array as well. Then the master repeats steps 1 to e asking next module down the list to explore.
  4. The master ensures all connected modules have been already discovered by reissuing exploration commands to all modules and watching out for any new un-IDed modules.
  5. If there are no un-IDed modules, the master generates and distributes appropriate port directions:
    1. Virtually reset the state of master ports to Normal.
    2. Update other modules ports starting from the last one and going backwards to ensure the communication chain is not broken.
    3. The master asks each module to update its port direction.
    4. The master officially updates its ports back to normal.
  6. The master tests new port directions by pinging all modules and recording their responses. It's also displayed on the terminal if the CLI explore command was invoked.
  7. The master asks all modules to save the topology and port directions in specific Flash page (for topology) and emulated EEPROM (for number of modules and port directions).

The following video shows exploration of different arrays with various shapes and complexities. There are generous delays currently in the algorithm making it a bit lengthy (2 minutes for the sphere) but they can be optimized later.

Removing Current Topology

If you want to reconfigure the array in a different shape without erasing and reprogramming modules, you can invoke the CLI command default array to remove topology related information from Flash / emulated-EEPROM. Remember to do that before disassembling your array!