The avatar for @lvngd
Christina Levengood
Public
Edited
Jan 31, 2022
1 fork
2 stars
Insert cell
# Maze Generation with Kruskal
Insert cell
{
const svgBackgroundColor = "#081c15",
mazeEnterColor = "#f8961e",
mazeExitColor = "#faedcd",
mazePathColor = "#333d29",
mazeWallColor = "#95d5b2",
mazeWallWidth = 4,
svg = d3.create("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom)
.style("background-color", svgBackgroundColor),
container = svg.append("g")
.attr("transform",`translate(${margin.left},${margin.top})`),
container2 = svg.append("g")
.attr("transform", `translate(${margin.left},${margin.top})`),
numRows = mazeWidth,
numCols = mazeHeight,
y = d3.scaleBand()
.range([0,width])
.domain(d3.range(numRows)),
x = d3.scaleBand()
.range([0, height])
.domain(d3.range(numCols)),


update = (edges, mazeLines,diffIds,borderEdges) => {

//maze lines - actual path lines
let lines = container.selectAll(".mazePathLines")
.data(mazeLines)
lines
.join(
enter => enter.append("path")
.classed('mazePathLines', true)
.attr("d", d => {
let x1 = x(d.source % numCols) + x.bandwidth();
let y1 = y(Math.floor(d.source/numCols)) + y.bandwidth();
let x2 = x(d.target % numCols) + x.bandwidth();
let y2 = y(Math.floor(d.target/numCols)) + y.bandwidth();
return d3.line()([[x1,y1],[x2,y2]]);
})
.attr("stroke", mazePathColor)
.attr("stroke-width", 7)
.attr("fill", mazePathColor)
.style('opacity', .5)
)
//maze walls - perpendicular to maze lines
let walls = container.selectAll(".walls")
.data(diffIds)
walls
.join(
enter => enter.append("path")
.classed('walls', true)
.attr("d", d => {
let x1 = d.source % numCols;
let y1 = Math.floor(d.source/numCols);
let x2 = d.target % numCols;
let y2 = Math.floor(d.target/numCols);
let perps = getPerpendicularLine(x,y,x1,y1,x2,y2);
return d3.line()(perps);
})
.attr("stroke", mazeWallColor)
.attr("stroke-width", mazeWallWidth)

.attr("fill", mazeWallColor)
.style('opacity', .6)
)
let borders = container2.selectAll('.borders')
.data(borderEdges)
borders
.join(
enter => enter.append('path')
.classed("borders", true)
.attr("d", d => {
let x1 = x(d.x1);
let y1 = y(d.y1);
let x2 = x(d.x1);
let y2 = y(d.y1);
switch(d.side){
case "top":
x1 = x1 + x.bandwidth()/2;
x2 = x2 + x.bandwidth()/2 + x.bandwidth();
y1 = y1 + y.bandwidth()/2;
y2 = y2 + y.bandwidth()/2;
break;
case "bottom":
x1 = x1 + x.bandwidth()/2;
x2 = x2 + x.bandwidth()/2 + x.bandwidth();
y1 = y1 + y.bandwidth()/2 + y.bandwidth();
y2 = y2 + y.bandwidth()/2 + y.bandwidth();
break;
case "left":
x1 = x1 + x.bandwidth()/2;
y1 = y1 + y.bandwidth()/2;
x2 = x2 + x.bandwidth()/2;
y2 = y2 + y.bandwidth()/2 + y.bandwidth();

break;
case "right":
x1 = x1 + x.bandwidth()/2 + x.bandwidth();
y1 = y1 + y.bandwidth()/2;
x2 = x2 + x.bandwidth()/2 + x.bandwidth();
y2 = y2 + y.bandwidth()/2 + y.bandwidth();
break;
}

return d3.line()([[x1,y1],[x2,y2]])
})
.attr("stroke", d => d.type == "wall" ? mazeWallColor : (d.type == "exit" ? mazeExitColor : mazeEnterColor))
.attr("stroke-width", d => d.type == "wall" ? mazeWallWidth : 8)
)
// let rects = container.selectAll("rect")
// .data(graph.nodes)
// .join("rect")
// .style("opacity", 0)
// .transition()
// .duration(500)
// .delay((d,i) => i * 500)
// .attr('x', d => x(d.id%numCols) + x.bandwidth()/2)
// .attr('y', d => y(Math.floor(d.id/numCols)) + y.bandwidth()/2)
// .attr("width", x.bandwidth())
// .attr("height", y.bandwidth())
// .attr('fill', "red")
// .style('stroke', 'red')
// .style("stroke-opacity", 0)
// .style("opacity", 1);
}


let rightEdges = d3.range(numRows).map(d => {
return {x1: numCols-1, y1: d, x2: numCols-1, y2: d+1, side: "right", "type": "wall"};
})
let bottomEdges = d3.range(numRows).map(d => {
return {x1: d, y1: numCols-1, x2: d+1, y2: numCols-1, side: "bottom","type": "wall"};
})
let topEdges = d3.range(numRows).map(d => {
return {x1: d, y1: 0, x2: d+1, y2: 0, side: "top","type": "wall"};
})
let leftEdges = d3.range(numRows).map(d => {
return {x1: 0, y1: d, x2: 0, y2: d+1, side: "left","type": "wall"};
})
let borders = rightEdges.concat(bottomEdges,topEdges,leftEdges);
d3.shuffle(borders);

//random enter and exit spots
let enter = borders.pop();
let exit = borders.pop();
enter.type = "enter";
exit.type = "exit";
borders.push(enter);
borders.push(exit);

let maze = kruskalMaze();
let mazeEdgeIds = new Set(Array.from(maze).map(d => d.id));

//subtract maze path edges from the graph edges to get the walls
let diffIds = Array.from(graph.edges).filter(d => !(mazeEdgeIds.has(d.id)))


update(graph.nodes,maze,diffIds,borders);

yield svg.node();


}
Insert cell
getPerpendicularLine = (x,y,x1,y1,x2,y2) => {
let horizontal = Math.abs(x2-x1) > 0 ? true : false;

let xMin = d3.min([x1,x2]);
let yMin = d3.min([y1,y2]);
let xMax = d3.max([x1,x2]);
let yMax = d3.max([y1,y2]);
if(horizontal){
//ys will change, x is midpoint
//x +/- x.bandwidth()/2
y1 = y(yMax) + (y.bandwidth()/2)
y2 = y(yMin) - (y.bandwidth()/2)
x1 = x(xMin) + (x.bandwidth()/2)
x2 = x(xMin) + (x.bandwidth()/2)
}else{
//xs change, y is midpoint
y1 = y(yMin) + (y.bandwidth()/2)
y2 = y(yMin) + (y.bandwidth()/2)
x1 = x(xMax) + (x.bandwidth()/2)
x2 = x(xMin) - (x.bandwidth()/2)
}
x1 = x1 + x.bandwidth();
x2 = x2 + x.bandwidth();
y1 = y1 + y.bandwidth();
y2 = y2 + y.bandwidth();
return [[x1,y1],[x2,y2]];
}
Insert cell
getCellNumber = (x,y) => {
let rowCount = mazeHeight;
let colCount = mazeWidth;

let cell = (x*colCount) + y;
return cell;
}
Insert cell
getXYfromCellNumber = (cell) => {
let x = cell % mazeWidth;
let y = Math.floor(cell/mazeWidth);
return {x: x, y: y};
}
Insert cell
createEdge = (i,j,currentNodeId) => {
let edgeNodeId = getCellNumber(i,j);
let edge = {id: `${currentNodeId}${edgeNodeId}`, source: currentNodeId, target: edgeNodeId};
return edge;
}
Insert cell
createGraph = (width,height) => {
let graph = {};
let x = width,
y = height;
let nodes = [];
let edges = [];

let nodeToIds = {};

let edgeIds = new Set()
d3.range(x).forEach(i => {
d3.range(y).forEach(j => {
let currentNode;
let currentNodeId = getCellNumber(i,j);
if(currentNodeId in nodeToIds){
currentNode = nodeToIds[currentNodeId];
}else{
currentNode = {id: currentNodeId, x: i, y: j};
nodeToIds[currentNodeId] = currentNode;
nodes.push(currentNode);
}
let edgeNodeId;
let edge,
currentEdgeId,
reverseEdgeId;
if(i > 0){
edge = createEdge(i-1,j,currentNodeId);
currentEdgeId = edge.id;
reverseEdgeId = `${getCellNumber(i-1,j)}${currentNodeId}`;
if(!(edgeIds.has(currentEdgeId) || edgeIds.has(reverseEdgeId))){

edges.push(edge);
edgeIds.add(currentEdgeId);
edgeIds.add(reverseEdgeId);
}
};
if(i < width-1){
edge = createEdge(i+1,j,currentNodeId);
currentEdgeId = edge.id;
reverseEdgeId = `${getCellNumber(i+1,j)}${currentNodeId}`;
if(!(edgeIds.has(currentEdgeId) || edgeIds.has(reverseEdgeId))){
edges.push(edge);
edgeIds.add(currentEdgeId);
edgeIds.add(reverseEdgeId);
}
};

if(j > 0){
edge = createEdge(i,j-1,currentNodeId);
currentEdgeId = edge.id;
reverseEdgeId = `${getCellNumber(i,j-1)}${currentNodeId}`;
if(!(edgeIds.has(currentEdgeId) || edgeIds.has(reverseEdgeId))){
edges.push(edge);
edgeIds.add(currentEdgeId);
edgeIds.add(reverseEdgeId);
}
};

if(j < height-1){
edge = createEdge(i,j+1,currentNodeId);
currentEdgeId = edge.id;
reverseEdgeId = `${getCellNumber(i,j+1)}${currentNodeId}`;
if(!(edgeIds.has(currentEdgeId) || edgeIds.has(reverseEdgeId))){
edges.push(edge);
edgeIds.add(currentEdgeId);
edgeIds.add(reverseEdgeId);
}
};
})
})

graph.nodes = nodes;
graph.edges = edges;
return graph;
}
Insert cell
assignRandomEdgeWeights = (graph) => {
let edges = graph.edges;
let weights = edges.map(e => {
e.weight = getRandomInt(1,5);
return e;
});
weights = weights.sort((a, b) => (a.weight > b.weight) ? 1 : -1);
return weights;
}
Insert cell
mazeWidth = 10
Insert cell
mazeHeight = 10
Insert cell
graph = createGraph(mazeWidth,mazeHeight)
Insert cell
kruskalMaze = () => {
//assign random edge weights to each edge of the graph
const weightedEdges = assignRandomEdgeWeights(graph);
//initialize clusters and ranks for each graph node
const clusterRanks = getClustersAndRanks(graph);
const ranks = clusterRanks[1];
const clusters = clusterRanks[0];

//union find algorithm
const find = (u) => {
if(clusters[u] != u){
clusters[u] = find(clusters[u]);
}
return clusters[u];
}
const union = (x,y) => {
x = find(x);
y = find(y);
if(ranks[x] > ranks[y]){
clusters[y] = x;
}else{
clusters[x] = y;
}
if(ranks[x] == ranks[y]){
ranks[y]++;
}
}
let solution = new Set();
for(let edge of weightedEdges){
let x = edge.source, y = edge.target;
if(x != y){
if(find(x) != find(y)){
solution.add(edge);
union(x,y);
}
}
}

return solution;
}

Insert cell
getClustersAndRanks = (graph) => {
const clusters = {};
const ranks = {};
Array.from(graph.nodes).forEach(n => {
clusters[n.id] = n.id;
ranks[n.id] = 0;
})
return [clusters,ranks];
}
Insert cell
width = 400
Insert cell
height = 400
Insert cell
margin = ({top: 10, bottom: 50, left: 10, right: 50})
Insert cell
getRandomInt = (min, max) => {
min = Math.ceil(min);
max = Math.floor(max);
return Math.floor(Math.random() * (max - min) + min);
}
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more