Kevin Santo CappuccioTable of Contents (bolded ones are in this project log)
- General terms - the names I've decided to call things
- What's being stored - how the overall state is stored
- File Parsing - how we fill in those arrays
- Pathfinding - how we find valid paths for each connection
- Controlling the crosspoint switches - how we send that data to the CH446Qs
- LEDs - how we choose unique colors for each net
- The Wokwi bridge app - how we scrape the Wokwi page for updates
Pathfinding
This is the really tricky part. I probably wrote all this code about 4 times, trashed it and started over from scratch with only the lessons learned from the last attempt. Earlier versions would add connections one at a time, but you'd end up in weird states because it has no knowledge of what other paths it needs to make room for. So the final version here clears the connections from the last update, takes in all the connections to be made, and finds paths for the whole board every time you add a new wire. All the old connections usually follow the same paths as last time unless they need to be nudged over to make room for some other path, and the actual connection won't be interrupted at all.
Here's the schematic of just the crosspoints, the Nano header, and the breadboard.
If you look closely, you'll see that there generally 2 connections (I'm calling these 2 connections Lanes between each breadboard chip, except for the chip that is across from it on the breadboard. And every breadboard chip has one connection to each of the special function chips. The pins on the Nano header has a connection to 2 special function chips (interleaved to make it easier to connect continuous pairs of pins to the breadboard).
Here's the high level outline of what NetsToChipConnections.cpp is doing
- Sorts all the paths by Net This sort of sets priority, lower net numbers (so all the special function nets) will be picked first and are more likely to have direct connections chosen
- For each path, find the start and end chips
- If there are multiple candidates (Nano header pins will have 2) store both
- If both start and end chips have candidates in common, choose that chip (this would make it a bounce)
- Assign node and path types (BB to BB, NANO to BB, BB to SF, etc...)
- Sort a list of chips from least to most crowded (by how many connections that chip has used)
- Resolve the candidate chips by going down the sorted list of chips and picking the less crowded chip
- Search for a direct path between those 2 chips
- If there isn't one, swap to the other candidate chips and search again
- If one of the nodes is a special function with multiple options swap the nodes with their equivalents and search again
- If there still isn't a direct path, set the altPathNeeded flag and move on At this point, any paths that have a simple direct connection should be done, now we need to deal with the ones that don't
- Resolve alt paths, if the altPathNeeded flag is set
- Search through all the other chips until you find one that has a direct connection to both the start and end chips
- If one chip is connected to the X inputs and the other the Y inputs, set that connection on chip[2] and x[2] y[2]
- If they're both on X or both on Y, set the sameChip flag and the x[3] or y[3] as -2 to denote that that connection is a bounce and it doesn't matter which pin is chosen, as long as it's available
- Search through all the other chips until you find one that has a direct connection to both the start and end chips
- Resolve uncommitted hops, anything set as -2 gets a random unconnected pin assigned to it at the very end so it doesn't take up connection space
There's a lot more subtlety to this but if I go into any more detail you might as well just read the code itself. It will all be in the file NetsToChipConnections.cpp, and if you're running it on a Jumperless or just an RP2040, you can set the Chip Connections and Chip Connections Alt debug flags and it will show you everything it's doing in a somewhat nicely formatted way. There are comments in the code but there are a lot of nested array things that can get pretty confusing, if you need help understanding what's going on in a particular function, let me know and I'd be happy to walk you through it.
Here's the output with the debug flags on (with some redundant bits removed because it's really long)
sorting paths by net
number of nets: 20
path[0] net: 1
path[1] net: 8
path[2] net: 9
path[3] net: 10
path[4] net: 11
path[5] net: 12
path[6] net: 13
path[7] net: 14
path[8] net: 15
path[9] net: 16
path[10] net: 17
path[11] net: 18
path[12] net: 19
number unique of nets: 26
pathIndex: 13
numberOfPaths: 13
0 [24,GND,Net 1], 1 [D4,14,Net 8], 2 [10,36,Net 9], 3 [D6,40,Net 10],
4 [D7,39,Net 11], 5 [D8,38,Net 12], 6 [D9,6,Net 13], 7 [D10,7,Net 14],
8 [D11,9,Net 15], 9 [D12,8,Net 16], 10 [D3,25,Net 17], 11 [D2,23,Net 18],
12 [D1,45,Net 19],
finding start and end chips
path[0]
nodes [24-100]
finding chips for nodes: 24-GND
node: 1
chip: D
node: 2
special function candidate chips: I J L
Path 0 type: BB to SF
Node 1: 24 Node 2: 100
Chip 1: 3 Chip 2: -1
path[1]
nodes [74-14]
finding chips for nodes: D4-14
node: 1
nano candidate chips: J K
node: 2
chip: B
Path 1 type: BB to NANO
Node 1: 14 Node 2: 74
Chip 1: 1 Chip 2: -1
... [removed for space]
path[11]
nodes [72-23]
finding chips for nodes: D2-23
node: 1
nano candidate chips: J K
node: 2
chip: D
Path 11 type: BB to NANO
Node 1: 23 Node 2: 72
Chip 1: 3 Chip 2: -1
path[12]
nodes [71-45]
finding chips for nodes: D1-45
node: 1
nano chip: I
node: 2
chip: F
Path 12 type: BB to NANO
Node 1: 45 Node 2: 71
Chip 1: 5 Chip 2: 8
paths with candidates:
0,1,3,4,5,6,7,8,9,10,11,
resolving candidates
chips least to most crowded:
C: 0
G: 0
H: 0
J: 0
K: 0
L: 0
I: 1
E: 2
A: 3
B: 3
D: 3
F: 3
sf connections: I1
sf connections: J0
sf connections: K0
sf connections: L0
C: 0
G: 0
H: 0
J: 0
K: 0
L: 0
I: 1
E: 2
A: 3
B: 3
D: 3
F: 3
path[0] chip from D to chip J chosen
sf connections: I1
sf connections: J1
sf connections: K0
sf connections: L0
C: 0
G: 0
H: 0
K: 0
L: 0
I: 1
J: 1
E: 2
A: 3
B: 3
D: 3
F: 3
path[1] chip from B to chip K chosen
... [removed for space]
sf connections: I4
sf connections: J4
sf connections: K3
sf connections: L0
C: 0
G: 0
H: 0
L: 0
E: 2
A: 3
B: 3
D: 3
F: 3
K: 3
I: 4
J: 4
path[11] chip from D to chip K chosen
path[0] net: 1 24 to GND chip[0]: D x[0]: 7 y[0]: 2 chip[1]: J x[1]: 15 y[1]: 3 1 1
path[1] net: 8 14 to D4 chip[0]: B x[0]: 11 y[0]: 6 chip[1]: K x[1]: 6 y[1]: 1 8 8
path[2] net: 9 10 to 36 chip[0]: B x[0]: 8 y[0]: 2 chip[1]: E x[1]: 2 y[1]: 5 9 9
path[3] net: 10 40 to D6 chip[0]: F x[0]: 11 y[0]: 2 chip[1]: J x[1]: 6 y[1]: 5 10 10
path[4] net: 11 39 to D7 chip[0]: F x[0]: 10 y[0]: 1 chip[1]: I x[1]: 7 y[1]: 5 11 11
path[5] net: 12 38 to D8 chip[0]: E x[0]: 1 y[0]: 7 chip[1]: K x[1]: 10 y[1]: 4 12 12
path[6] net: 13 6 to D9 chip[0]: A x[0]: 0 y[0]: 5 chip[1]: I x[1]: 9 y[1]: 0 13 13
path[7] net: 14 7 to D10 chip[0]: A x[0]: 1 y[0]: 6 chip[1]: J x[1]: 9 y[1]: 0 14 14
path[8] net: 15 9 to D11 no direct path, setting altPathNeeded flag (BBtoSF)
path[9] net: 16 8 to D12 no direct path, setting altPathNeeded flag (BBtoSF)
path[10] net: 17 25 to D3 chip[0]: D x[0]: 6 y[0]: 3 chip[1]: I x[1]: 3 y[1]: 3 17 17
path[11] net: 18 23 to D2 chip[0]: D x[0]: 15 y[0]: 1 chip[1]: K x[1]: 4 y[1]: 3 18 18
path[12] net: 19 45 to D1 no direct path, setting altPathNeeded flag (BBtoSF)
alt paths
BBtoSF path: 8
bb: A sfChip: K xMapBB: 0 yMapSF: 0 xStatus: 13
bb: B sfChip: K xMapBB: -1 yMapSF: 1 xStatus: 65
bb: C sfChip: K xMapBB: 4 yMapSF: 2 xStatus: -1
bb: C sfChip: K xMapBB: 4 yMapSF: 2 xStatus: -1
xMapL0c0: 4 xMapL1c0: 2 xMapL1c1: 5 xMapL0c1: 3
8 chip[0]: B x[0]: 4 y[0]: 1 chip[1]: K x[1]: 13 y[1]: 2 15 -1
Found Path!
BBtoSF path: 9
bb: A sfChip: J xMapBB: -1 yMapSF: 0 xStatus: 65
bb: B sfChip: J xMapBB: 2 yMapSF: 1 xStatus: -1
bb: B sfChip: J xMapBB: 2 yMapSF: 1 xStatus: -1
xMapL0c0: 2 xMapL1c0: 0 xMapL1c1: 3 xMapL0c1: 1
9 chip[0]: A x[0]: 2 y[0]: 7 chip[1]: J x[1]: 10 y[1]: 1 16 -1
Found Path!
BBtoSF path: 12
bb: A sfChip: I xMapBB: 0 yMapSF: 0 xStatus: 13
bb: B sfChip: I xMapBB: 2 yMapSF: 1 xStatus: 16
bb: C sfChip: I xMapBB: 4 yMapSF: 2 xStatus: -1
bb: C sfChip: I xMapBB: 4 yMapSF: 2 xStatus: 15
xMapL0c0: 4 xMapL1c0: 10 xMapL1c1: 5 xMapL0c1: 11
12 chip[0]: F x[0]: 4 y[0]: 7 chip[1]: I x[1]: 1 y[1]: 2 19 -1
Found Path!
resolving uncommitted hops
path net node1 type chip0 x0 y0 node2 type chip1 x1 y1 altPath sameChp pathType chipL chip2 x2 y2 x3 y3
0 1 24 0 D 7 2 GND 2 J 15 3 0 0 BB to SF 0
1 8 14 0 B 11 6 D4 1 K 6 1 0 0 BB to NANO 0
2 9 10 0 B 8 2 36 0 E 2 5 0 0 BB to BB 0
3 10 40 0 F 11 2 D6 1 J 6 5 0 0 BB to NANO 0
4 11 39 0 F 10 1 D7 1 I 7 5 0 0 BB to NANO 0
5 12 38 0 E 1 7 D8 1 K 10 4 0 0 BB to NANO 0
6 13 6 0 A 0 5 D9 1 I 9 0 0 0 BB to NANO 0
7 14 7 0 A 1 6 D10 1 J 9 0 0 0 BB to NANO 0
8 15 9 0 B 4 1 D11 1 K 13 2 0 1 BB to NANO 0 C 2 -2 13 -1
9 16 8 0 A 2 7 D12 1 J 10 1 0 1 BB to NANO 0 B 0 -2 3 -1
10 17 25 0 D 6 3 D3 1 I 3 3 0 0 BB to NANO 0
11 18 23 0 D 15 1 D2 1 K 4 3 0 0 BB to NANO 0
12 19 45 0 F 4 7 D1 1 I 1 2 0 1 BB to NANO 0 C 10 -2 4 -1
path net node1 type chip0 x0 y0 node2 type chip1 x1 y1 altPath sameChp pathType chipL chip2 x2 y2 x3 y3
taken connections (-1 is free)
chip 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7
A 13 14 16 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 13 14 16
B 16 -1 16 -1 15 -1 -1 -1 9 -1 -1 8 -1 -1 -1 -1 -1 15 9 -1 -1 -1 8 -1
C -1 -1 15 -1 19 -1 -1 -1 -1 -1 19 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
D -1 -1 -1 -1 -1 -1 17 1 -1 -1 -1 -1 -1 -1 -1 18 -1 18 1 17 -1 -1 -1 -1
E -1 12 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 12
F -1 -1 -1 -1 19 -1 -1 -1 -1 -1 11 10 -1 -1 -1 -1 -1 11 10 -1 -1 -1 -1 19
G -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
H -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
chip 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7
I -1 19 -1 17 -1 -1 -1 11 15 13 -1 -1 -1 -1 -1 1 13 -1 19 17 -1 11 -1 -1
J -1 -1 18 -1 8 -1 10 -1 12 14 16 -1 -1 -1 -1 1 14 16 -1 1 -1 10 -1 -1
K -1 -1 -1 -1 18 17 8 -1 10 11 12 13 14 15 16 -1 -1 8 15 18 12 -1 -1 -1
L -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1
8 same chips: @, @, @, @, @, @, C, C,
9 same chips: @, @, @, @, @, @, B, B,
12 same chips: @, @, @, @, @, @, C, C,
final paths
path net node1 type chip0 x0 y0 node2 type chip1 x1 y1 altPath sameChp pathType chipL chip2 x2 y2 x3 y3
0 1 24 0 D 7 2 GND 2 J 15 3 0 0 BB to SF 0
1 8 14 0 B 11 6 D4 1 K 6 1 0 0 BB to NANO 0
2 9 10 0 B 8 2 36 0 E 2 5 0 0 BB to BB 0
3 10 40 0 F 11 2 D6 1 J 6 5 0 0 BB to NANO 0
4 11 39 0 F 10 1 D7 1 I 7 5 0 0 BB to NANO 0
5 12 38 0 E 1 7 D8 1 K 10 4 0 0 BB to NANO 0
6 13 6 0 A 0 5 D9 1 I 9 0 0 0 BB to NANO 0
7 14 7 0 A 1 6 D10 1 J 9 0 0 0 BB to NANO 0
8 15 9 0 B 4 1 D11 1 K 13 2 0 1 BB to NANO 0 C 2 0 13 0
9 16 8 0 A 2 7 D12 1 J 10 1 0 1 BB to NANO 0 B 0 0 3 0
10 17 25 0 D 6 3 D3 1 I 3 3 0 0 BB to NANO 0
11 18 23 0 D 15 1 D2 1 K 4 3 0 0 BB to NANO 0
12 19 45 0 F 4 7 D1 1 I 1 2 0 1 BB to NANO 0 C 10 1 4 1
path net node1 type chip0 x0 y0 node2 type chip1 x1 y1 altPath sameChp pathType chipL chip2 x2 y2 x3 y3
To be continued with Driving the CH446Qs
Discussions
Become a Hackaday.io Member
Create an account to leave a comment. Already have an account? Log In.