I am playing with allowing face values to be optionally bigger than a byte in the Custom Blinklib. To test it, I set the value to be an int32 (4 bytes) as I was testing for ways to make Blinks always fully aware of their position in relation to each other. For that, currently I would need 3 bytes (for X and Y coordinates, one byte each, and 3 bits on the other byte to keep track of the Blink heading. As there is no 3-byte integral types, I have to round up to 4 which would also make 11 bits of information available for the developer to use as they see fit).
The above is working as expected but transferring 4 bytes of data per-face actually takes a considerable amount of time (it looks like more than 4x the time for some reason I did not dig into) and this delay makes itself pretty visible on games that make heavy use of face values (i.e. most of them).
So, if you are ever doing a Blinks v2 (v3?) please consider a faster IR transceiver if at all possible. I do not need high end megabits/second transfer speeds but it would be really nice if we could transfer arbitrary amounts of data (currently that would be a maximum of 18 bytes for user packets) in a virtually instantaneous way (assuming, of course, the Blink processor could cope with that. But a processor upgrade would also be welcome ).
I would love faster IR transfer too! Makes so many things better!
In an ideal world, we’d have a 200Mhz arm on each face dedicated to driving the IR LED with a charge pumped MOSFET driver, and all clocked with a +/-1ppm temp comp oscillator. We could easily get 1Mb/s full duplex per face out of this setup (these IR LEDs are amazingly fast), but then each blink would probably cost $200 and a CR2032 battery would only last a few minutes.
The limiting factors on the current hardware/software versions are (1) the inherent inaccuracy of the oscillator on the chip, and (2) the amount of flash memory available.
Since IR data is just a stream of pulses, the information is encoded in the timing of those pulses. The current maximum IR speed is limited by the ability of the RX blink to accurately time the TX pulse. Sounds trivial (1us = 0 bit, 2us = 1 bit, done!) but it is actually much harder than that because of limits on how accurately you can measure those timings when there are sampling errors (nyquist) and no shared clock between the two sides of the conversation. Adding an external crystal would help a lot (there can be +/-10% difference in clock speed between units of this chip!), but this adds 3 parts and associated cost.
Upgrading to a bigger chip would give more space for more sophisticated algorithms which would also help some. Initially the IR protocol was noticeably faster, but I ultimately went with a simpler one to leave more room for games since the simpler one seemed fast enough for everything we could throw at it. That said, we have been actively talking about upgrading the chip in future versions since the price difference between the current ATMEGA168 (16Kb flash) and the larger ATMEGA328 (32KB flash) has dropped significantly since the current version was designed.
I understand and appreciate your approach of making high quality, general use tooling. This is at the core of good software design practice, but on a severely resource constrained platform like this sometimes you have to throw away generality and optimize to the specific problem you are trying to solve - or even change the problem to fit the constraints. This can be challenging since it goes against everything we normally do, but I personally often find it rewarding. There have been many times I have been frustrated that my planned approach just would not work on a blink, and that forced me to step back an reexamine the problem and find a totally (often completely ad-hoc) approach that ultimately solved the problem at hand even more elegantly. I think these experiences have made me a better programmer even on big platforms.
Do you have a specific application that is driving the design of this x/y/h mapping system?
Have you considered that the map is basically static except for when the topology of the cluster changes, and there is a pretty low limit to the maximum rate at which the topology can change because these are physical objects? Maybe there is a way to greatly reduce the information moving in the system by only propagating topology diffs? Or even limit the propagation of these diffs only to places where they have effects.
In my experience, when you look at a set of blinks at a high level, there is very little actual “information” in it and that information evolves slowly relative to the clock speed of the MCUs and the IR link data rate. The challenge trying to find a representation that matches the specific problem you are working.
Make sense?
Can you share more about the specific problem motivating this question? (Remember, specific like “A game where…” and not general like “An API that…” )
Well, that is why I said I do not need speeds that fast.
So, if (2) could be solved (by just upgrading to a new processor with more flash) how much do you think this could be improved.
Don’t take me wrong, you are right that within the current design (specially API design), the IR speed is actually ok (it is definitely fine for all existing games). The thing is that I like pushing things to their limit and I am all the time hitting walls because of that (I already hit 99% storage usage with Hexxagon maybe 10 times or so, for example, but I always found a way to find some more space). What I am trying to do now I can get to work and with a game like Hexxagon, the speed would not be an issue. But, of course, I noticed the speed and thought it would be nice to have faster speeds.
Oh, but at this point I already tried lots of stuff and this is already the lowest common denominator I could find for what I want to do. It is not like I tried one thing, it didn’t work and instead of fixing the software I decided the only solution was upgrade the hardware (I am not that kind of software engineer). Still, faster IR speeds would be nice.
Yes. I want to implement “influence distance”. If you had the chance to play Hexxagon, you noticed that during a player’s turn, their pieces light up (on older versions) or pulse (in current versions). If the user clicks a piece that can not be moved because there is no space for it to go, I indicate that with a flash.
I started thinking how nice it would be if I could figure out if a piece could be played or not before hand and only pulse pieces that can be moved.
In the simple case, this is trivial, I can check if I have any empty spaces adjacent to the Blink for the 1 space move case and check if any adjacent blink has least one empty space adjacent to them (and use a single bit of face value to indicate that). This works perfectly, is very simple and I was very proud of having come up with the solution in like 5 minutes after deciding to do it.
But it breaks badly in the same cases that led me to start discussions with you about dealing with “holes” in the middle of the cluster of Blinks. The simple implementation breaks if there is a missing adjacent Blink, there are no empty blinks around the one I am checking and the is an empty space just after the missing Blink. Even this case is relatively simple and I could probably get it working with a bit more effort but, generally I might have a U-shaped blink setup with an arbitrary number of Blinks so I need a way to propagate some meaningful information in a way that I can know if there is an empty space just across a “chasm”.
My current solution for something similar when searching for valid positions to light them up, is to send a message from the origin Blink (because the user selected it) to all Blinks and wait for them to check if they are possible targets and to report back if at least one possible target exists. This works thanks to my message broadcast library.
But now I have no selected Blinks. I have n player Blinks and m empty spaces and I can not send messages from all of the Blink in one of these groups as managing propagation the right way would be a nightmare (if not impossible due to memory constraints). So I ruled out broadcast messages for this and moved to the official way of propagating state: Face values.
So the idea was to use face values to propagate influence. Basically an empty Blink would tell its neighbors they are at an influence distance of 1. Those Blinks would propagate that and tell their neighbors what their distance is. and so on. When a Blink receives more than one possible distance propagating through different faces, it will always propagate only the smaller one that would go out another face. With this, I can just check on all players Blinks if their influence distance is smaller than 3 and if it is, they should be enabled. If not, they should be disabled.
This works on paper but as you noticed with your broken rainbow code, it is non trivial and even with a data intensive solution like yours, we would still need to use all bits in the face value for this and only have a limited reach for the propagation (I currently have 3 bits available in Hexxagon).
So I ignored the constraints and looked at the math. What would I need to do to get this to work?
The first thing I can do to simplify the problem is to make all Blinks know where they are. This is already implemented in Hexxagon although the Blinks do not remember their location. In any case, I can use a 3 bytes single broadcast message to let them know their position and the global heading.
Now all blinks know where they are. What I want to know is the distance from the closest empty space to each of the player blinks. To know that with the information I have, I can simply propagate the X and Y coordinates for each empty blink (They use X, Y and Z coordinates, but X + Y + Z = 0 so I only need to transfer 2 coordinates) with that, computing the distance is trivial. Again, when a blink receives the coordinates of multiple Blinks, it always propagates what would result in the smallest distance in a specific face.
This works great but if I tried using a single byte, the coordinates would have to be limited to -8 to +7 even when using all available 8 bits in a face value (4 bits for X and 4 bits for Y, both signed values). And I only have 3 bits available anyway. So I need more bits.
So now I am at 99% storage again (but I am sure I can go back to, say, 95% just with optimizations) and have around 200 bytes of memory.
If you have some magic idea to solve this in a different way, I am all ears.
Also, I do not need to propagate the heading anymore so that is a plus I guess.
Been there, done that. I am pretty sure entropy is requiring me to use more bits. And I did see your Broken Rainbow example (which is pretty neat but has the problem of using more storage than I can afford).
).