My take on network messages

Software Resources
#1

Warning: I do not have any Blinks yet, so everything on this post is about completely untested code. All I can talk about it is that it compiles (I compile, therefore I am). :slight_smile:

I want to implement a specific game using Blinks and I would need some type of network flood algorithm to use so I can do network validation and synchronization. @jbobrow pointed me to the code by @gapMindful (that helped a lot, specially considering I do not have any Blinks to test). In he end, I thought it could be implemented in an easier way (and with a slightly simpler algorithm) so I went ahead and gave it a go. Here is the result:

If any of you with Blinks could try it and let me know if it does anything useful (again, it might not even work), that would be great.

Limitations:

  • It handles a single message going through the network at a time (it tries to simply ignore anything unexpected like 2 messages running at once).
  • Payload is currently hardcoded to being a single byte (hey, this is better than the 64 values in the ValueOnFace API :slight_smile: ). It can be extended to have more bytes as the payload but I wanted to keep it simple and small.

Here is the API:

// Prototype for functions that want to change the payload of a
// message that is being propagated. Any modifications to payload
// will be seen by upstream nodes. This can be used for, for
// example, add some type of routing information (counting hops
// is what I had in mind).
typedef void (*ForwardHandler)(byte* payload);

// Prototype for functions that want to change the payload of a
// message reply being sent back to the parent. Any modifications
// to payload will be seen by downstream nodes. The local_payload
// parameter should be used to keep track of the progress so far
// (as we potentially receive replies from multiple faces. For
// example, if we are creating a sum of something, we would have
// code similar to this:
//
// void sum(byte* payload, byte* local_payload) {
//   *local_payload += payload;
// }
typedef void (*ReplyHandler)(byte* payload, byte* local_payload);

// BroadcastMessage sends the given message to all available
// neighboors so it can be propagated through the network.
// The forward_handler callback is called whenever a new
// message being routed reaches the current node and the
// reply_handler callback is called for any replies that
// reaches the it.
bool BroadcastMessage(
  const Message& message, ForwardHandler forward_handler,
  ReplyHandler reply_handler);

// Loop updates the status of the NetworkMessageManager. If it
// returns true (this should ever only happen in the node that
// originally sent the message), then result will contain the
// actual result of the network query made. If it returns false,
// then teh result value is meaningless. This should be called
// at every loop iteration.
bool Loop(byte* result);
1 Like
#2

There is a glaring issue with the code that I completely overlooked so do not bother trying it as it will need a considerable redesign before it does what it is supposed to. Anyway, a fellow Blinker (is this a thing?) is sending me a full set of Blinks for development so I will be able to actually see how broken my code is before trying to make it generally available. Sorry for the noise. :slight_smile:

1 Like
#3

Ok. I fixed the glaring issue (I guess. Again, can not test). There are probably others. :slight_smile:

1 Like
#4

Ok, the current code actually works now. It needs some cleanup as I added some ad-hoc stuff to get it to work but it shows the general idea at least.

I made virtually zero effort to reduce its size (this will be the step after the cleanup), Let me know what you think.

@bigjosh this is what I am thinking about using to solve the problem we were talking about in the other thread. I just need to expose the source/destination faces to the ForwardHandler and I will be able to do something like this:

1 - Set payload to be 3 bytes.
2 - Each byte represents a face (or direction) and its opposite face.
3 - Use the source/destination ports to figure out what is the “direction” I am going (obviously in a relative way, not by trying to use anything like directly mapping a face to a direction, which would be the naive non-working approach :slight_smile: ).
4 - For each direction byte, I increase its value by 1 if I am going in the positive direction or subtract otherwise.
5 - At each node the message gets to, I check if the absolute direction value is < 3. If it is, this is a target.

#5

Now you are thinking like a blink! :slight_smile:

I think the increment/decrement ends up being slightly more complicated, but I’m sure you’d quickly get that once it is coded.

This is actually a very interesting problem you’ve framed. I spent a shower thinking about it and I am about 85% sure it can be done without datagrams using just statefull ‘setValueSentOnFace()’. Here are some hints to what I am thinking…

Screenshot_20200708-170420
Screenshot_20200708-1704201440×3040 758 KB

I’ll try and code something up in the next day or two and post it (if it works).

1 Like
#6

I will take that as a compliment. :wink:

In my mind, it sounds correct, but I did not try to implement it yet. :slight_smile:

Just to make sure we are on the same page, here is what I am using as a table test:

Blinks
Blinks960×720 18.6 KB

Light blue is the origin.
Greens are all possible and valid targets.
Reds are not targets.

The problem only gets interesting because of all the gaps in the graph (it is still fully connected but not always through a shortest path).

Now imagine you have, say, 1000 Blinks. shaped like an U where the 2 ends of it are the origin and a valid target (this will never happen in practice in a game, even if you have 1000 Blinks, but I am solving for the general problem).

That will be interesting to see. Good luck.

#7

Actually, I will need 4 bytes instead of 3. The last one I will treat as a signed int8 and it will be used to indicate the current direction (-3 to 3) that map to to other 3 buckets that count the steps in that direction. But other than this, my idea should work.

#8

@bigjosh Ah! Got it working beautifully! I will clean up the code and submit it but, generally speaking, I am using a coordinate system with 3 axis. and I keep track of the (normalized) face the message came through. Then it is actually pretty trivial as I only need to do something like this: (indexes 0, 1 and 2 are x, y and z respectively):

> void set_payload_for_face(byte* payload, byte f) {
>   switch (f) {
>     case 0:
>       payload[1]--;
>       payload[2]--;
>       break;
>     case 1:
>       payload[0]--;
>       payload[1]--;
>       break;
>     case 2:
>       payload[0]--;
>       payload[2]++;
>       break;
>     case 3:
>       payload[1]++;
>       payload[2]++;
>       break;
>     case 4:
>       payload[0]++;
>       payload[1]++;
>       break;
>     case 5:
>       payload[0]++;
>       payload[2]--;
>   }
> }

The fun thing about this is that now each blink can actually know where they are in the world (coordinates will be relative the the Blink that sent the message). This solves my problem and basically sorts up the biggest mechanic in my game but, also, I think it generally opens up some interesting possibility for games.

Let me know what you think. I will update when I submit the code.

#9

Ok, here it is:

Note I am using a 3 dimension coordinate system but because there is a constraint that z+y+z=0, I can actually get by with only 2 coordinates which would reduce memory and storage pressure. I will implement it eventually.

#10

So here is the best I could come up with…

It uses only ‘setValueSentOnFace()’ (and only 56 of the possible 63 values) to be able to detect the as-the-blink-flies distance away from the center for contiguous groups of tiles with a radius of 5 or less.

I do not have enough blinks to exactly make your example pattern, but hopefully this shows that it works correctly (white=0, blue=1,green=2,red=3)…

2020-08-01 20.35.20
2020-08-01 20.35.202016×1512 794 KB

Here is more complicated arrangement (4=yellow, cyan=5)…

2020-08-01 20.44.03
2020-08-01 20.44.031732×2309 320 KB

To get it to work, I had to take advantage of two insights:

  1. There is perfect 6-fold symmetry around the center, so yyou only need to know where you are inside a single 1/6th sector of the full area.

  2. In the rings that are a distance of 1 and 2 away from the center, there must be a direct path to the center so no need to cover indirect back-tracking paths.

Here is a map of the symbols (i.e. values) sent on each face…

image
image969×1162 388 KB

…where the first number is the distance out (“ring”), the second number is the distance away from the radial (“step”), and the decimal is the relative orientation (“face”). Note how when the step gets to the next radial, it effectively just jumps back to the 1st step.

I am pretty happy with this solution, but my gut tells me that there is an even better one just beyond my grasp. I feel like there must be some way to take advantage of the additional symmetries as you get farther away from the center. Or maybe there is some completely different way of viewing the problem that is much, much better than keeping track of positions and orientations. If you find a better solution (one that uses fewer symbols for a given radius) please, please let me know because this problem has been gnawing at me for a long time!

3 Likes
#11

Yes, this is very cool! You could make some very cool looking global patterns/animations that would still work even with gaps and missing pieces. Maybe also somehow use this technique to make a jigsaw puzzle like game!

1 Like
#12

Nice one! I guess the only drawbacks are really using most of the available face values and the limited (but totally reasonable) radius. I guess my solution is more general (as blinks can actually know exactly where they are) but also more expensive so it depends on what you want to optimize for. :slight_smile:

#13

Agreed, this is just a toy solution - but I do think that I discovered some things working it out that will lead me to better solutions on other problems in the future. And I do not think I would have come up with this approach if I was thinking using normal aysnc programming models. This is why I was drawn to the blinks platform in the first place, and I think that working on these simple/hard programs has made me a better programmer generally.

I can tell that you are not a “Mediocre Man” programmer so I really think you’d enjoy dipping your toes in the blinks way of seeing the problems. (I am still struggling to fully jump in- ask Jonathan! :slight_smile: ). If you have time, I’d love to see you come up with a solution that uses this shared-values model, but gets the job done with fewer symbols and/or handles bigger groups. I bet it will look very different than something you’d have come up with for a more standard-looking platform.

#14

I am all for creative solutions to problems. Usually I deal with the other end of the spectrum in terms of resources but I will eventually wrap my head around Blinks. Also, I want to make 2 things clear in case they are not:

1 - I do think you did an amazing job considering the resources available. I am certain I would not be able to easily come up with the same solution you did simply because I am not used to the limitations that now are a fact of life for this platform. :slight_smile: ).
2 - When I “complain” (really, they are not complaints but I am sure they sound like it), it is because I wanted the platform to be better than it is. Even if what I think is better is misguided considering everything.

I most certainly will. But first I need to figure out a way to get my game to work. Datagrams are the soul of the game and they are definitely sent in a higher quantity than the average Blinks game does (I am also using face values, so it is not like I am trying to use datagrams for everything :slight_smile: ).

2 Likes