Skip to content

Instantly share code, notes, and snippets.

@bigjosh
Last active December 22, 2020 18:26
Show Gist options
  • Save bigjosh/dda8fcc93cc7792903e083cfd3bc8d3b to your computer and use it in GitHub Desktop.
Save bigjosh/dda8fcc93cc7792903e083cfd3bc8d3b to your computer and use it in GitHub Desktop.
Counts the number of connected nodes in a distributed and robust way. More info at https://forum.move38.com/t/yadca-yet-another-distributed-counting-algorithm/468
// SimpleCounter demo
// A simple distributed counter example
//
// On startup, blinks are dim BLUE which shows they are in IDLE mode waiting for a master
//
// Button press a blink to make it master of the cluster. The master will show the current count
// using the 0-342 display format decribed below under showNumber()...
//
// While a blink is actively part of a counting cluster, it will show dim GREEN on the face
// that points to its parent. All parent faces eventually lead back to the master.
//
// You can add blinks to and remove blinks from the cluster and the count should update to reflect
// in real time.
//
// A second button press on the master will take it out of master mode and all connected
// blinks should then quickly return to IDLE mode.
//
// Note that pressing the button on a blink that is currently part of a counting cluster
// does nothing, but once the current master is un-masted or removed from the cluster
// then any tile can become the new master with a button press.
//
// It is possible to have two masters either by physically combining two count clusters together
// or by activating two masters at almost the same instant on far apart tiles in the same cluster.
// In either case, the result will show some of the tiles on one master and some on the
// other, and the sum shown on the two masters will equal the total number of blinks in the cluster.
//
// This system should be robust to loops, broken trees, and changing topologies so
// do not be afriad to play around!
//
// Note that it does not do error checking for branches larger than 61 blinks or for
// total groups larger than 342 blinks, but these could be easily added.
void setup() {
// blank
}
// Display a number 0-342 on the LEDs
// The number is shown in base 7 format with red, green,
// and blue being the 1's, 7's, and 49's places respecitively
// A 0 digit is shown as OFF. Digits 1-6 are shown as 1-6 LEDs
// lit with the place color.
//
// 0 = All Off
// 1 = 1 RED
// 2 = 2 RED
// ...
// 6 = 6 RED
// 7 = 0 RED, 1 GREEN
// 8 = 1 RED, 1 GREEN (both on LED 0 so you see yellow)
// 9 = 2 RED, 1 GREEN (you see 1 yellow, 1 red)
// ...
// 48 = 6 RED, 6 GREEN (you see 6 yellow)
// 49 = 0 RED, 0 GREEN, 1 BLUE
// 50 = 1 RED, 0 GREEN, 1 BLUE (you see 1 purpule)
// ...
// 341 = 5 RED, 6 GREEN, 6 BLUE (you see 1 purpule, 5 white)
// 342 = 6 RED, 6 GREEN, 6 BLUE (6 white)
//
// #fin#
void showNumber( unsigned x ) {
// We are the root, so display the accumulated tile count
// Deconstruct the count "digits" into base 7 for display on our 6 LED screen (0 digit=0 LEDs on)
// This also just happens to look nice since we always count ourselves, so count never 0, so screen never totally blank
const unsigned DISPLAY_BASE = FACE_COUNT+1;
byte high = x / (DISPLAY_BASE*DISPLAY_BASE);
byte medium = (x - (high * DISPLAY_BASE*DISPLAY_BASE)) / DISPLAY_BASE;
byte low = x % DISPLAY_BASE;
FOREACH_FACE( f ) {
byte r=0;
byte g=0;
byte b=0;
// Low 1-6 maps to faces 0-5
// When low==0 then no red
// Note that count never is 0 becuase we always count ourselves
// but count can be FACE_COUNT in when case no red, but green with have 1
if ( (f+1) <= low ) {
r = MAX_BRIGHTNESS_5BIT;
}
// Medium 1-6 maps to faces 0-5
// We do not show any medium when count < FACE_COUNT
if ( (f+1) <= medium ) { // Only show G when we go around at least one time
g = MAX_BRIGHTNESS_5BIT;
}
// High 1-6 maps to faces 0-5
// When do not show any high when count < FACE_COUNT^2
if ( (f+1) <= high ) { // Only show blue when it is more than 0 (count>=36)
b = MAX_BRIGHTNESS_5BIT;
}
setColorOnFace( MAKECOLOR_5BIT_RGB( r , g , b ) , f );
}
}
#define TIMEOUT_MS 250
Timer timeout; // Durring this timeout we only can send idle, we will ignore requests
// this prevents loops. This has to be long enough that a message can get
// from the root to the tile farthest from it.
// Values sent on faces:
#define VALUE_REQUEST 0 // We are requesting a downstream count
#define VALUE_IDLE IR_DATA_VALUE_MAX // We are idle
// anything else is the downstream count (including this tile)
// The first time we see a request (0) on a face, then we lock onto that as our master
#define PARENT_FACE_IDLE FACE_COUNT // Waiting to see a request on any face
#define PARENT_FACE_ROOT FACE_COUNT+1 // We are the root
// Anything else is the face that we got a request on
// This is the state, and if the state
// if not IDLE or ROOT then its overloaded to
// hold the face of the parent.
// Should probably make this into a union to be more
// clear. Is there a better way to represent data
// only applicable to one state?
byte parent_face=PARENT_FACE_IDLE;
void loop() {
//----- UI
if (buttonPressed()) {
if (parent_face == PARENT_FACE_IDLE) {
parent_face = PARENT_FACE_ROOT;
} else if (parent_face == PARENT_FACE_ROOT) {
parent_face = PARENT_FACE_IDLE;
timeout.set( TIMEOUT_MS );
}
};
//----- INPUTS
unsigned count=1; // Count all connected tiles (including ourselves)
FOREACH_FACE(f) {
byte v;
if (!isValueReceivedOnFaceExpired(f)) {
v = getLastValueReceivedOnFace(f);
} else {
// Treat an unconnected face as idle
v = VALUE_IDLE;
}
// Check if we can attach to a parent
if ( v == VALUE_IDLE ) {
// Only way we care able an idle is if we see it one what used ot be our
// parent. In that case, we detatch and start the detactment timeout.
if ( f == parent_face ) { // This was our parent, now it is idle
// Lost parent
parent_face = PARENT_FACE_IDLE;
timeout.set( TIMEOUT_MS );
}
} else if ( v == VALUE_REQUEST ) {
// Only connect if we are idle AND the timeout has expired
// The timeout keeps us from instantly connecting to a neighbor
// in a loop after we loose a parent.
if ( parent_face == PARENT_FACE_IDLE ) {
// We do not currently have a parent
if ( timeout.isExpired() ) { // Do not already have a parent
parent_face = f; // We now have a parent
}
}
} else {
// If we get here, then this face is just looking at a downstream tile so we
// should accumulate its count.
count+= v;
}
}
//----- OUTPUTS
if (parent_face==PARENT_FACE_IDLE) {
setValueSentOnAllFaces( VALUE_IDLE );
} else {
FOREACH_FACE(f) {
if (f==parent_face) {
setValueSentOnFace(count,f); // Percolate count back up the chain
} else {
setValueSentOnFace( VALUE_REQUEST ,f); // request count from the downstream tile
}
}
}
//----- UPDATE DISPLAY
setColor(OFF);
if (parent_face == PARENT_FACE_ROOT) {
showNumber( count );
} else if (parent_face == PARENT_FACE_IDLE ) {
setColor( dim( BLUE , 64 ) );
} else {
// Point to upstream parent face with dim green
setColorOnFace( dim( GREEN , 64) , parent_face );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment