34:null 35:["$","title",null,{"children":"Metro Stations as Network Diagrams | Rick Martin | Observable"}] 3b:T1374, md` # Metro Stations as Network Diagrams ## A naive and computationally expensive approach There are a few libraries out there for drawing Metro maps or Tube maps. None of them quite fit my use case, so I felt the need to make another. Every other library I have seen creates charts using locations and lines that are passed in from an external source. In order to create one of those charts, I would need to hardcode the locations of each station and line. My data updates daily, and the chart is expected to stay up-to-date. I cannot dedicate my life to rebuilding the same chart with new information. **So what information do we get? A list of stations, and a list of lines**, which hold unordered collections of stations. That's it. All visuals must be generated from this information. This presents a few challenges: Placing stations on the map in a way that makes sense, finding the best order for each line to visit those stations, and routing lines. Lines need to be readable, but they also must resemble a metro map. There are also a few bonus thoughts and considerations: - Each station may also have a label, which should avoid interacting visually with the inputs and outputs if possible. - Each metro line is a path through 2D space, between two or more stations. - In order to enable pathfinding between stations, Everything should be rendered on a 2D grid. - If at all possible, we want to avoid having lines cross. In our pathfinding, we will allow them to cross, but assign a high cost to doing so. - The order in which we place lines will most likely influence the outcome. Shortest first? Longest? - If the order of the stations matters, things are easier to program, but the results will most likely be messier. For my specific use case, Order doesn't matter as much as aesthetics, so we'll do it the hard way. ## Methodology 1. Start with a list of **stations** and a list of **lines**. - Stations should have a name and an id. - Lines should have a name, a collection of station ids in no particular order, and a color. ### Place Stations in 2D space. 2. Create a D3 Force-directed graph, and place your stations into the graph as nodes. - Apply a charge force to push stations away from each other. - For each pair of stations in each line, apply a pulling force between the two stations. 4. Run the simulation until it settles. 5. Snap each station into a 2D grid. ### Figure out which order to connect Stations in. 6. For each line, find the shortest path that visits all of the stations on the line. - This is a Travelling Salesman problem. This imlementation uses Ant Colony Optimization to solve for a decent line. - This should result in a list of **transitions** from station to station. Each transition contains a "source" and a "target" station. - A line may resolve to a list such as [[1, 7], [7, 5], [5, 8]]. This would result in a line starting at station 1, travelling through station 7, then station 5, and ending at station 8. - With this information, we could draw a network diagram, however we don't want our lines to overlap. This means pathfinding along every transition in every line. ### Pathfind along each line. 7. Create a 2DArray to represent the cost of pathfinding. If a path wants to move across a cell in the 2DArray, it will cost a certain amount. We can raise the cost of moving near stations to discourage paths from going near them unnecessarily. We can also raise the cost of crossing existing paths. This way, our paths will avoid overlapping each other. - Fill the array with 1s as a starting cost. - Increment the cost near each station by some amount. 8. Pathfind along every transition. - This implementation uses A*. - Start at the location of the source station. Travel across the 2DArray to the target station. - When pathing is complete, increase the "cost" of every cell that the path has crossed. ### Draw. 9. Create an svg with 3 groups: - Lines: Lowest z value. For each path in each line, append a path. Use the path as the path's d value. - Stations: Draw each station, as a rounded rect, at their given location. - Information: Highest z value. Draw station names on this layer, adjacent to each station. ## References - [Harry Beck's London Tube map](https://tfl.gov.uk/corporate/about-tfl/culture-and-heritage/art-and-design/harry-becks-tube-map) - [More modern London TFL standards](https://content.tfl.gov.uk/tfl-line-diagram-standard.pdf) - [New York Underground design standards](https://standardsmanual.com/products/nyctacompactedition) - [Tips for PCB trace routing](https://engineering.purdue.edu/ece477/Resources/T3-EagleTips.pdf) - [Circuit Routing Using Monte Carlo Tree Search and Deep Neural Networks](https://arxiv.org/pdf/2006.13607.pdf) - [Implementation of A*](https://www.redblobgames.com/pathfinding/a-star/implementation.html#troubleshooting-ugly-path) - [This Google search](https://www.google.com/search?q=spaghetti&tbm=isch) `3c:T1957,metroStations = { const gridSize = 8; const textSize = 10; const customWidth = 800; // Use a multiple of gridSize for best results. const customHeight = 512; // Use a multiple of gridSize for best results. const arrWidth = customWidth / gridSize; const arrHeight = customHeight / gridSize; const gridVector = new Victor(gridSize, gridSize); const paddingGrids = 32; const lineAvoidance = 4; const lineSelfAvoidance = -2; // Make it cheaper for a line to double back on itself. const stationAvoidance = 3; const stationRadius = 2; const octolinearPathing = false; const useOrderedLinks = false; const useStringPulling = true; const stringPullingLookahead = 16; const stringPullingShortcutThreshold = 0; const drawLines = true; const drawStations = true; const drawStationNames = false; const svg = d3.create('svg').attr('viewBox', [0, 0, customWidth, customHeight]); // Create links / nodes from simulationData. const nodes = simulationData.stations.map(d => Object.create(d)); var linkPairs = []; for (let lineIndex = 0; lineIndex < simulationData.lines.length; lineIndex++) { for (let start = 0; start < simulationData.lines[lineIndex].stations.length - 1; start++) { if (useOrderedLinks) { // Only create links between stations in the order they are listed. linkPairs.push({ source: simulationData.lines[lineIndex].stations[start], target: simulationData.lines[lineIndex].stations[start + 1] }); } else { // Create links between every station in every line. for (let end = start; end < simulationData.lines[lineIndex].stations.length; end++) { linkPairs.push({ source: simulationData.lines[lineIndex].stations[start], target: simulationData.lines[lineIndex].stations[end] }); } } } } const links = linkPairs.map(d => Object.create(d)); // Run a simulation until it settles. const simulation = d3.forceSimulation(nodes) .force("link", d3.forceLink(links).id(d => d.id)) .force("charge", d3.forceManyBody()); simulation.restart(); for (let i = 0; i < 1000; i++) { simulation.tick(); if (simulation.alpha() < 0.005) { break; } } simulation.stop(); // Create a bounding box around the resulting nodes. var top = Number.MAX_VALUE; var bottom = 0; var left = Number.MAX_VALUE; var right = 0; for (var i = 0; i < nodes.length; i++) { var d = nodes[i]; if (d.y > bottom) bottom = Math.round(d.y); if (d.y < top) top = Math.round(d.y); if (d.x > right) right = Math.round(d.x); if (d.x < left) left = Math.round(d.x); } top -= paddingGrids; bottom += paddingGrids; left -= paddingGrids; right += paddingGrids; // Create a cost array. const arr = new Array2D(arrWidth, arrHeight, 1); arr.defaultValue = 1000; // Place each station within the cost array. for (var i = 0; i < nodes.length; i++) { var d = nodes[i]; let index = simulationData.stations.findIndex(function(station) {return station.id == d.id}); let x = Math.round((d.x - left) / (right - left) * arrWidth); let y = Math.round((d.y - top) / (bottom - top) * arrHeight); simulationData.stations[index].position = new Victor(x, y); arr.incrementBox(simulationData.stations[index].position, stationRadius, stationAvoidance, true); } // This is the expensive part. Generate curves to define each line. for (var i = 0; i < simulationData.lines.length; i++) { var line = simulationData.lines[i]; var stationsOnLine = []; for (var j = 0; j < line.stations.length; j++) { var station = simulationData.stations.find(function(station) { return station.id == line.stations[j] }); stationsOnLine.push(station); } var antColony = new AntColonyOptimization(stationsOnLine) var lineSegments = antColony.simulateColony().path; // Pathfind for each of the paths in this line. const curve = d3.line().curve(d3.curveBundle.beta(1)) var allPointsOnLine = []; for (var j = 0; j < lineSegments.length; j++) { let start = simulationData.stations.find(function(station) { return station.id == lineSegments[j].source }); let end = simulationData.stations.find(function(station) { return station.id == lineSegments[j].target }); try { let pointsOnSegment = arr.pathfind(start.position, end.position, octolinearPathing); // Optimize the path a little bit before continuing. var optimizedPoints = pointsOnSegment; if (useStringPulling) { optimizedPoints = arr.stringPull(pointsOnSegment, stringPullingLookahead, stringPullingShortcutThreshold); } arr.incrementList(optimizedPoints, lineSelfAvoidance, true); for (let i = 0; i < optimizedPoints.length; i++) { allPointsOnLine.push(optimizedPoints[i].clone()); optimizedPoints[i] = optimizedPoints[i].multiply(gridVector).toArray(); } // Go ahead and draw the curve while we're looping through the line. if (drawLines) { svg .append('path') .attr('d', curve(optimizedPoints)) .attr('stroke', line.color) .attr('stroke-width', 6) .attr('fill', 'none') .attr('stroke-linecap', 'round'); } } catch(e) { console.warn("Pathing failed between", start.name, "and", end.name); } } arr.incrementList(allPointsOnLine, lineAvoidance, true); } // Draw all of the stations and station names. for (var i = 0; i < simulationData.stations.length; i++) { var station = simulationData.stations[i]; if (drawStations) { svg.append('circle') .attr('fill', '#ffffff') .attr('stroke', '#2c2c2c') .attr('r', 8) .attr('stroke-width', 4) .attr('cx', station.position.x * gridVector.x) .attr('cy', station.position.y * gridVector.y) if (drawStationNames) { svg.append('text') .attr('x', station.position.x * gridVector.x) .attr('y', station.position.y * gridVector.y + 16) .attr('dy', '.35em') .attr('text-anchor', 'middle') .attr('font-family', 'helvetica') .attr('font-weight', 'bold') .attr('font-size', textSize) .attr('fill', '#2c2c2c') .text(station.name.toUpperCase()); } } } return svg.node(); }3d:T574,simulationData= JSON.parse('{ "stations": [ { "id": 1, "name": "Scottsdale" }, { "id": 2, "name": "Magnolia" }, { "id": 3, "name": "Concord" }, { "id": 4, "name": "Aspen" }, { "id": 5, "name": "New Haven" }, { "id": 6, "name": "Wilmington" }, { "id": 7, "name": "Saint Augustine" }, { "id": 8, "name": "Fort Valley" }, { "id": 9, "name": "Waimea" }, { "id": 10, "name": "Sun Valley" }, { "id": 11, "name": "Freeport" }, { "id": 12, "name": "New Castle" }, { "id": 13, "name": "Newton" }, { "id": 14, "name": "Garden City" }, { "id": 15, "name": "Lexington" }, { "id": 16, "name": "Alexandria" }, { "id": 17, "name": "Farmington" }, { "id": 18, "name": "Rockville" }, { "id": 19, "name": "Lowell" }, { "id": 20, "name": "Ironwood" } ], "lines": [ { "color": "#FCD34D", "name": "Brightline", "stations": [10,18,7,9,15,1,2,3,19,17,14,16] }, { "color": "#A7F3D0", "name": "Metra", "stations": [3,2,5] }, { "color": "#A5B4FC", "name": "Caltrain", "stations": [7,2,20,13,6] }, { "color": "#F9A8D4", "name": "Amtrak", "stations": [6,20,7,5,18,1,13,3,19,8] }, { "color": "#F87171", "name": "SunRail", "stations": [3,1,18,11,13,7,16,10] }, { "color": "#A78BFA", "name": "Union Pacific", "stations": [8,15,7,6,3,12,1,4] } ] }');3e:T1ab3,class Array2D { constructor(width, height, defaultValue) { this.arr = []; this.width = width; this.height = height; this.defaultValue = defaultValue; for (let x = 0; x < width; x++) { this.arr[x] = []; for (let y = 0; y < height; y++) { this.arr[x][y] = defaultValue; } } } // start and end are both Victors, since we'll need some vector math. pathfind(start, end, octolinear) { var frontier = new PriorityQueue(true); frontier.push(start.clone(), 0); var cameFrom = {}; var costSoFar = {}; cameFrom[start] = null; costSoFar[start] = 0; var bestHeuristicSoFar = Number.MAX_VALUE; var bestPositionSoFar = start; var currentPosition; const MAX_ROUNDS = 4096; var rounds = 0; while (frontier.size() > 0 && rounds < MAX_ROUNDS) { rounds += 1; currentPosition = frontier.pop(); if (currentPosition.toString() == end.toString()) break; var directions = [ currentPosition.clone().add(Victor(-1, 0)), currentPosition.clone().add(Victor(1, 0)), currentPosition.clone().add(Victor(0, -1)), currentPosition.clone().add(Victor(0, 1)), ]; if (octolinear) { directions = directions.concat([ currentPosition.clone().add(Victor(-1, -1)), currentPosition.clone().add(Victor(1, 1)), currentPosition.clone().add(Victor(1, -1)), currentPosition.clone().add(Victor(-1, 1)) ]); } for (let i = 0; i < directions.length; i++) { var direction = directions[i]; var directionCost = Math.max(this.getv(direction, true), 1); if (directionCost < 1000) { // Stations and walls have a value of 1000. var newCost = costSoFar[currentPosition] + (directionCost); if (!costSoFar.hasOwnProperty(direction) || newCost < costSoFar[direction]) { costSoFar[direction] = newCost; var heuristic = this._getPathfindingHeuristic(direction, end); if (heuristic < bestHeuristicSoFar) { bestHeuristicSoFar = heuristic bestPositionSoFar = direction } var priority = newCost + heuristic // lowest is better. frontier.push(direction.clone(), priority); cameFrom[direction] = currentPosition; } } } } return this._backtracePath(cameFrom, bestPositionSoFar); } _getPathfindingHeuristic(position, end) { return Math.abs(position.x - end.x) + Math.abs(position.y - end.y); } _backtracePath(cameFrom, end) { var currentPosition = end; var path = [end]; const MAX_ROUNDS = 1024; var rounds = 0; while (cameFrom[currentPosition] != null && rounds < MAX_ROUNDS) { rounds++ var nextPosition = cameFrom[currentPosition]; path.unshift(nextPosition); currentPosition = nextPosition; } return path; } stringPull(path, lookahead, threshold) { var pulledPath = [...path]; for (var i = 0; i < pulledPath.length - 1; i++) { var maxLookaheadIndex = Math.min(path.length - 1, i + lookahead); for (var j = maxLookaheadIndex; j > i + 1; j--) { if (this._isCardinalTo(pulledPath[i], pulledPath[j])) { var currentPathSegment = pulledPath.slice(i, j+1); var straightPathSegment = this._getStraightPath(pulledPath[i], pulledPath[j]); if (this._getPathCost(straightPathSegment) < this._getPathCost(currentPathSegment) + threshold) { // Replace currentPathSegment with straightPathSegment. Array.prototype.splice.apply(pulledPath, [i, currentPathSegment.length].concat(straightPathSegment)); break; } } } } return pulledPath; } _isCardinalTo(positionA, positionB) { if (typeof positionA === 'undefined' || typeof positionB === 'undefined') return false; if (positionA.x == positionB.x || positionA.y == positionB.y) { return true; } if (Math.abs(positionA.x - positionB.x) == Math.abs(positionA.y - positionB.y)) { return true; } return false; } _getStraightPath(start, end) { var newPath = []; var currentPosition = start.clone(); var round = 0; const MAX_ROUNDS = 20; while (currentPosition.toString() != end.toString() && round < MAX_ROUNDS) { round++; // Step directly toward end from start. newPath.push(currentPosition.clone()); var xDiff = Math.max(Math.min(end.x - currentPosition.x, 1), -1); var yDiff = Math.max(Math.min(end.y - currentPosition.y, 1), -1); var diff = new Victor(xDiff, yDiff); currentPosition.add(diff); } newPath.push(currentPosition.clone()); return newPath; } _getPathCost(path) { var cost = 0; for (var i = 0; i < path.length; i++) { cost += this.getv(path[i], true); } return cost; } getv(vector, safe) { if (!safe || this.isValidPosition(vector)) { return this.arr[Math.round(vector.x)][Math.round(vector.y)]; } else return this.defaultValue; } setv(vector, value, safe) { if (!safe || this.isValidPosition(vector)) { this.arr[Math.round(vector.x)][Math.round(vector.y)] = value; } } incrementRadius(vector, radius, value) { for (var x = vector.x - radius; x < vector.x + radius; x++) { for (var y = vector.y - radius; y < vector.y + radius; y++) { let position = new Victor(x, y); let distance = Math.max(vector.clone().subtract(position).length(), 1); if (this.isValidPosition(vector) && distance < radius) { this.incrementv(position, Math.floor(value/distance), true); } } } } incrementBox(vector, radius, value) { for (var x = vector.x - radius; x < vector.x + radius; x++) { for (var y = vector.y - radius; y < vector.y + radius; y++) { let position = new Victor(x, y); if (this.isValidPosition(vector)) { this.incrementv(position, value, true); } } } } setList(vectors, value, safe) { for (let i = 0; i < vectors.length; i++) { this.setv(vectors[i], value, safe); } } incrementv(vector, value, safe) { this.setv(vector, this.getv(vector, safe) + value, safe); } incrementList(vectors, value, safe) { for (let i = 0; i < vectors.length; i++) { this.setv(vectors[i], this.getv(vectors[i], safe) + value, safe); } } isValidPosition(vector) { return vector.x > 0 && vector.x < this.width && vector.y > 0 && vector.y < this.height; } print() { var value = ""; for (let y = 0; y < this.height; y++) { for (let x = 0; x < this.width; x++) { value += String(this.arr[x][y]); } value += "\n"; } return value; } }3f:Ta20,class AntColonyOptimization { constructor(stations) { this.stations = new Object(); for (var i = 0; i < stations.length; i++) { this.stations[stations[i].id] = stations[i]; } this.pheromoneMatrix = new Matrix2D(Object.keys(this.stations), 1); this.costMatrix = new Matrix2D(Object.keys(this.stations), 0); for (var i = 0; i < stations.length; i++) { for (var j = 0; j < stations.length; j++) { let movementCost = stations[i].position.clone().subtract(stations[j].position).length(); this.costMatrix.set(stations[i].id, stations[j].id, movementCost); } } } getRecommendedColonySize() { const MAX_ANTS = 120; const MIN_ANTS = 4; return Math.floor(Math.max(Math.min(Object.keys(this.stations).length * 8, MAX_ANTS), MIN_ANTS)); } simulateColony(ants) { if (typeof ants === 'undefined') ants = this.getRecommendedColonySize(); var bestAttempt = { cost: Number.MAX_VALUE, path: [] }; for (let i = 0; i < ants; i++) { let attempt = this.simulateAnt(); this.applyPheromone(attempt.path); if (attempt.cost < bestAttempt.cost) { bestAttempt = attempt; } } return bestAttempt; } simulateAnt() { var unvisitedStations = [...Object.keys(this.stations)]; var startIndex = Math.floor(seededRandom() * unvisitedStations.length); var currentLocation = unvisitedStations.splice(startIndex, 1)[0]; // A station ID. var cost = 0; var pathSoFar = []; for (var i = 0; i < Object.keys(this.stations).length -1; i++) { let newId = this.pickStation(unvisitedStations, currentLocation); cost += this.costMatrix.get(currentLocation, newId); pathSoFar.push({ source: currentLocation, target: newId }); currentLocation = unvisitedStations.splice(unvisitedStations.findIndex((s) => {return s == newId}), 1)[0]; } return { path: pathSoFar, cost: cost }; } pickStation(pickFrom, currentLocation) { var bag = new WeightedBag(); for (var i = 0; i < pickFrom.length; i++) { let cost = this.costMatrix.get(currentLocation, pickFrom[i]); let pheromone = this.pheromoneMatrix.get(currentLocation, pickFrom[i]); let weight = pheromone / cost; bag.addEntry(pickFrom[i], weight); } var target = bag.getRandom(); return target; } applyPheromone(path) { for (var i = 0; i < path.length; i++) { let step = path[i]; this.pheromoneMatrix.increment(step.source, step.target, 1); this.pheromoneMatrix.increment(step.target, step.source, 1); } } }40:[] 39:{"id":"a68247ea8f51f7e8","slug":"in-progress-metro-stations-as-process-diagrams","title":"Metro Stations as Network Diagrams","thumbnail":"cf149a1f5e8a59cb3c7085eced2a006693ee4757408850982b6b866932421583","access_level":"public","create_time":"$D2021-03-30T23:41:50.367Z","update_time":"$D2025-03-24T14:44:37.950Z","view_time":null,"first_public_time":"$D2021-03-31T20:09:31.854Z","has_unpublished_edits":null,"fork":false,"stars":46,"starred":false,"owner":{"type":"team","id":"3d7535b4ad979a57","login":"martin-pi","name":"Rick Martin","avatar_url":"https://avatars-next.observableusercontent.com/a13d596c4e162d5af1526a474e6cf6db62a235aec2094a699c2329df5200fa0c","tier":"starter_2024","bio":"","following":false},"version":1050,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"09a9ff3d030f86ac","login":"martin-pi","name":"Rick Martin","avatar_url":"https://avatars-next.observableusercontent.com/a13d596c4e162d5af1526a474e6cf6db62a235aec2094a699c2329df5200fa0c","tier":null,"bio":"","following":false}],"members":[{"type":"individual","id":"09a9ff3d030f86ac","login":"martin-pi","name":"Rick Martin","avatar_url":"https://avatars-next.observableusercontent.com/a13d596c4e162d5af1526a474e6cf6db62a235aec2094a699c2329df5200fa0c","tier":null,"role":"editor"}],"comments":[{"id":"efedcf7440460f07","reply_to_id":null,"content":"can you name this cell? I'd love to be able to remix it without having to fork :^)","create_time":"$D2021-12-23T04:56:29.613Z","update_time":null,"resolved":false,"user":{"type":"individual","id":"5bb83a6e9493ea1d","login":"mjbo","name":"Max Bo","avatar_url":"https://avatars-next.observableusercontent.com/05ae9baba40510a4a22fa7d179f29dd4ffd85fcff859c54a31d42e166ae61dfa","tier":null}},{"id":"b7908774fea44f14","reply_to_id":"efedcf7440460f07","content":"Absolutely! It should be named now.","create_time":"$D2021-12-23T05:02:26.756Z","update_time":null,"resolved":false,"user":{"type":"individual","id":"09a9ff3d030f86ac","login":"martin-pi","name":"Rick Martin","avatar_url":"https://avatars-next.observableusercontent.com/a13d596c4e162d5af1526a474e6cf6db62a235aec2094a699c2329df5200fa0c","tier":null}}],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":16,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Metro Stations as Network Diagrams","cells":[{"id":0,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":300,"value":"$3c","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"Victor = require('https://bundle.run/victor@1.1.0')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"d3 = require('d3');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":283,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":92,"value":"$3e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":122,"value":"// Returns the lowest priority item first.\nclass PriorityQueue {\n constructor() {\n this.elements = [];\n }\n \n pop() {\n var nextElement = this.elements.shift();\n return nextElement.v;\n }\n\n // Sort by priority on element insertion.\n push(value, priority) {\n var newElement = { v: value, p: priority };\n for (let i = 0; i < this.elements.length; i++) {\n if (newElement.p < this.elements[i].p) {\n this.elements.splice(i, 0, newElement);\n return\n }\n }\n this.elements.push(newElement);\n }\n \n size() {\n return this.elements.length; \n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":456,"value":"class WeightedBag {\n constructor() {\n this.elements = [];\n this.totalWeight = 0;\n }\n \n getRandom() {\n var selection = seededRandom() * this.totalWeight;\n for (let i = 0; i < this.elements.length; i++) {\n if (selection < this.elements[i].w) {\n return this.elements[i].v;\n } else {\n selection -= this.elements[i].w;\n }\n }\n return undefined;\n }\n\n addEntry(value, weight) {\n if (weight > 100) weight = 100;\n var newElement = { v: value, w: weight };\n this.totalWeight += weight;\n this.elements.push(newElement);\n }\n \n size() {\n return this.elements.length; \n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":589,"value":"$3f","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":592,"value":"class Matrix2D {\n constructor(options, defaultValue) {\n this.defaultValue = defaultValue;\n this.dict = new Object();\n for (var x = 0; x < options.length; x++) {\n this.dict[options[x]] = new Object();\n for (var y = 0; y < options.length; y++) {\n this.dict[options[x]][options[y]] = this.defaultValue;\n }\n }\n }\n \n set(optionA, optionB, value) {\n this.dict[optionA][optionB] = value;\n }\n \n get(optionA, optionB) {\n return this.dict[optionA][optionB];\n }\n \n increment(optionA, optionB, value) {\n this.dict[optionA][optionB] += value;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":653,"value":"SeedRandom = require('seedrandom@3.0.5/seedrandom.min.js')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":665,"value":"seededRandom = new SeedRandom('SeedGoesHere');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W40","stdlib":"1"}} 3a:"$39:body"