Use placed cables as communication channels

xsebek commented 1 year ago

In #94 it is proposed to add wireless antennas as communication channels. But that sounds a little high-tech and cables are much easier to craft and lay down. As a bonus, more robots can just come to a cable and attach without having an antenna themselves.

Proposed solution

Placed I/O cables (74ad23e322e) will be tracked in the global state as sets of connected cables. (Tip: use Link/cut tree) We will add a command that allows the robot to use a nearby cable as a channel:

attach: dir -> cmd (chan bool)

The idea is that cables are primitive and only allow you to transmit one bit at a time. But on the plus side, any primitive robot can receive that bit.

Alternatives

We could add separate commands for receiving and transmitting through cables, but that sounds unnecessary.

More likely we would want to transmit different types through a cable. If we wanted to make it easy we could fail with an exception if another robot is transmitting and returning () + a when the receiving robot is expecting a different type.

But, we could also make this more interesting by casting the sent type to the received type. So if you are waiting for text but another robot sends an int, we reinterpret it as binary text. This is a bit more real-life and could lead to some interesting algorithms as well as use cases like making a private channel just for casting.

^{Personally, I like the alternative chan a with the casting approach, I am just worried that it will crash the type system. But morally it should work because we can remember all the involved types and produce the values safely.}

xsebek commented 1 year ago

Also, this would be a fun place to figure out how to draw cables as connected. Here is how I imagine it:

two lone cables:
```
@@@
~@~
@@@
```
two connected cables:
```
@@@
╶─╴
@@@
```
three connected cables:
```
@╷@
╶┴╴
@@@
```

To make them distinguishable we could use the heavy versions of the characters for walls. But it would be great not to have to bother with connecting walls properly in mazes.

xsebek commented 1 year ago

To expand on the "private channel for casting" idea, what you could do is:

place "I/O cable";
let attachT: cmd (chan text) = attach down in t <- attachT;
def serialize = \x. build {c <- attach down; broadcast x}; txt <- read t; salvage; return txt end;
y <- serialize ("Hello!", 1234, inr true); say y;

With some other robot listening for the message:

y <- listen;
let attachTIE: cmd (chan (text, int, () + bool)) = attach down in tie <- attachTIE;
def deserialize = \x. build {c <- attach down; broadcast x}; txt <- read t; salvage; return txt end;
x <- deserialize y;

Basically, this would only give you a fast serialization function that you do not have to implement yourself. :smile:

xsebek commented 1 year ago

One other question that I did not address is whether to hardcode this for I/O cable or add some property for the entity that we can set in YAML. I would lean toward the latter, with something like:

- name: I/O cable
  display:
    attr: device
    char: 'Ю'
  description:
  - An I/O cable can be used to communicate with an adjacent robot.
  properties: [portable]
  medium: connectedPlaced  # NEW!

Another value could be "wireless", to pass radio frequencies for antennas around via entities.

valyagolev commented 1 year ago

It's probably good to be able to have separate cable networks that can overlap without intersecting. in e.g. Factorio this is solved by having different network colors.

Also I'm not sure I understand how synchronisation will work. E.g. if my robot walks around and finds a cable, how does it know if the transition hasn't already started?

One solution is to have an abstraction that will use a recognisable header, and the publisher can simply repeat its message forever with a header. Then whoever wants to receive it will wait for the header to start deserialising, and can move on afterwards.

xsebek commented 1 year ago

@valyagolev indeed the Factorio wires are cool and I would love to have something like that in Swarm.

For anyone unfamiliar with Factorio, this is how wires look:

In Swarm, the equivalent signal would be entity -> count map. It is often used to carry around requests and supplies - e.g. green cable connects to chests of iron and a red cable connects to smelters. You can connect the wires to the same power pole which is very convenient and harder to do in Swarm because we only have one entity placed in a location.

We could either let players space the cables one cell apart so they do not connect or create different cable kinds like Factorio. The intersections could either be special entities or you would have to use wireless channels to cross.

Synchronisation is an interesting problem. I guess you could start by having one cable and robots waiting for time slots.

robots send a request to transmit
master controller robot reads requests and sends out a message with assigned time slots
robots read the assigned time slots
the selected robot sends its message (and has to wait for some extra time before requesting again)

You can get time slots by checking the current time modulo 4:

t <- time; return $ t - (t/4)*4

What actually happens during one tick is that if robots A and B are both sending and C, D are receiving is that:

A goes first, sends a
B goes next, and sends b which overwrites a
depending on when C and D are woken up from waiting robots, they will either get:
- a if they are woken immediately after A sends
- b if they are woken next tick or after other not sleeping robots have run

This way you at least don't have collisions, so one robot gets its message across and others just have to try again.

byorgey commented 1 year ago

A lot of really cool ideas here! I really like the idea of laying down I/O cables as a communication network. And the nerd in me is very excited about the prospect of being able to use something fancy like a link/cut tree. :grin: Here are some more of my thoughts/reactions.

General principles

First, I have recently been thinking a lot about the general principle that this game should first and foremost be about programming --- so rather than providing complex features, we should strive for providing simple, composable pieces out of which players can build the features they want. For example, when using communication cables, we could imagine programming in some kind of queueing or synchronization system --- but instead we should just make them very simple, and players can create their own systems for dealing with contention, scheduling, and synchronization.

Crossing cables

As for how different cables can cross each other, following the guiding principle mentioned above, I think we want to provide something as simple as possible, then let players program whatever they want. We can't have more than one entity on the same cell (I mean, in theory we could change that, but I like how it keeps things simple), and I don't like the idea of creating a specialized "cable crossing" entity. But entities already have a color attribute, and once we implement #455 we should have the ability to "paint" entities different colors. What if I/O cables automatically connect to any other I/O cables of the same color anywhere within the neighborhood of 8 cells horizontally, vertically, or diagonally adjacent? Then to have cables cross you could just put four cables in an X pattern, like

RRRGGG
GGGRRR

where R indicates a red wire and G green.

Channels

I don't really like the idea of (ab)using private channels to do serialization, that seems backwards (using a complex mechanism to simulate a simpler one). Besides, we already have the format command which does serialization.

However, I love the idea of reusing the general concept of "channels" from #94. The idea of having cables provide only chan bool is certainly amusing to contemplate, and seems to be in line with the general principle I mentioned earlier --- after all, that's what cables in the real world actually provide, and we have to build communications networks on top of it with serialization and deserialization etc! But I think it might be a bit too low-level and not that much fun (except for those people who are real nerds about network communication protocols).

If we're going to have typed communication channels, then I think we should use them. @xsebek was worrying about breaking the type system, but I think we can take a hint from Haskell's Typeable class. My idea would be something like this:

There's no attach function because I don't know how that would work with moving around. i.e. what happens if you attach, get a channel reference, and then drive away? Can you still listen to messages from the channel? That doesn't really make sense to me.
Instead, there's just read : dir -> cmd (unit + a). You read from a cable in a particular direction; you get inl () if either there is no value available for reading, or if the type of the value on the cable does not match the type you were expecting.
- Relatedly, we could provide a primitive cast : a -> (unit + b), which is basically what read will be doing under the hood. If the input value has the expected type, then you get inr with the value; otherwise you get inl (). (In practice, this means values must carry around their types at runtime. We don't currently do this but it shouldn't be hard to add.)
- The read function itself must also know at runtime what type it was called with, of course. Again, we don't currently have this information available but I think we are going to have to bite the bullet and do it anyway, for other reasons as well.
- This provides a nice mechanism for different robots to be able to "share" a cable, like a bus: as long as they are sending/receiving different types, each will only get the messages intended for them.

Synchronization

As far as synchronization goes, what about providing something like write : int -> a -> chan a -> bool, which works as follows: write k v c will write value v to channel c for k ticks (i.e. any time during those k ticks, any other robots executing read will read that value). If another robot tries to do a write during those k ticks, both writes immediately stop and return false. If the k ticks elapse with no interference, write returns true. You could use this to implement a simple ethernet-like protocol with exponential backoff etc.

xsebek commented 1 year ago

Can you still listen to messages from the channel? That doesn't really make sense to me.

No problem, it would just be a runtime check and we would know where that channel came from. I think that is preferable to having too many specialised functions. In this case you could define them yourselves and afterwards pretend the dangerous attach does not exist. Just like you can define safeMove really.

xsebek commented 1 year ago

I like the diagonal crossing idea, but we would not be able to draw it I am afraid. That kind of makes it less user friendly and could end up too confusing and unexpected.

There is a crossing like character ╫ that looks a bit like taking a different wire under the horizontal one. I think that could be good compromise as general system still be discoverable as new entity that you can craft.

Also I like the color painting idea. 👨🏻‍🎨

byorgey commented 1 year ago

Hmm, re: attach, I guess you are right. It makes sense to have a way to just get a channel value and then you can write general-purpose communication functions that just take a channel as an argument, without having to worry about where the channel came from. So I guess under the hood, channel values will have some extra information specifying when/how you are allowed to use them, like ones you get from attach might be usable only when you are in a specific location. Whereas something like world : chan text will be usable any time.

Why ╫ and not just ┼? Anyway, I am warming up to the idea of having a special "wire crossing" entity. It would have to be a special different color since we can't make the horizontal and vertical lines different colors, and it would look weird if it shared the color of one of the crossing wires but not the other. Also, I am imagining that if a placed cable has more same-color cables adjacent to it in each of the cardinal directions, it would be drawn as ┼, but in the same color. Whereas a special cable crossing entity would be drawn that way too, but in a special color (gold?) and it would work differently, of course, allowing the two different cables to cross over each other without interacting.

xsebek commented 1 year ago

Why ╫ and not just ┼?

So that the cable from the south can be a different colour. :slightly_smiling_face: I imagine that the two lines look like a tunnel through which the crossing cable goes.

We can improve it once we implement this drawing system, it is not too important anyway. :sweat_smile:

valyagolev commented 1 year ago

Relatedly, we could provide a primitive cast : a -> (unit + b), which is basically what read will be doing under the hood. If the input value has the expected type, then you get inr with the value; otherwise you get inl (). (In practice, this means values must carry around their types at runtime. We don't currently do this but it shouldn't be hard to add.)

The read function itself must also know at runtime what type it was called with, of course. Again, we don't currently have this information available but I think we are going to have to bite the bullet and do it anyway, for other reasons as well.

or in a different vein:

values by themselves don't carry around their types
we have a well-defined type equality (purely symbolic is probably fine)
channel is basically a dictionary type => value
send a sets a value, read : dir -> cmd (unit + a) does a lookup by type
it's almost straightforward how to reuse the cable for different uses

xsebek commented 1 year ago

@valyagolev I am not sure what you mean by 2., AFAIK we have type equality because that is how unification works. Once we add type synonyms we could make that more interesting, but for now, the type equality is well-defined. You could relax it to allow e.g. integer to turn to text like with reinterpret_cast.

Making it a dictionary takes away a bit of the challenge. As a player, I would not expect cables* to store an unbound number of values with different types. How long would the values stay there anyway? Would all the sending robots keep sending until a receiving robot for that type comes around? Or would we have to collect them next tick? Or would they stay available indefinitely?

I think that is a really good question to ask, so thanks for bringing that detail up @valyagolev. :+1: Personally I would expect cables to only store one value, with its type and time of sending.

You can still devise a way to encode an arbitrary value including a dictionary of them, so it will be possible to reuse cables but I do not see a reason to make it trivial. Like why would you bother with laying more than one cable if you can just use different types (() * a, () * () * a,...)? :laughing:

^{*) If you have constructed a costly antenna, then I guess you should receive a value with the correct type if there is any, but cable feels too one-dimensional for that.}

swarm-game / swarm