Skip to content

Instantly share code, notes, and snippets.

@davidrobles
Last active March 13, 2018 06:40
Show Gist options
  • Save davidrobles/c6db7c54d002013ba4e5 to your computer and use it in GitHub Desktop.
Save davidrobles/c6db7c54d002013ba4e5 to your computer and use it in GitHub Desktop.
Breadth First Search Game Tree
<!DOCTYPE html>
<meta charset="utf-8">
<html>
<head>
<title>Tic-Tac-Toe Game Tree</title>
</head>
<body>
<script src="http://www.davidrobles.net/js/visualizing-game-trees-with-d3/underscore.js"></script>
<script src="http://www.davidrobles.net/js/visualizing-game-trees-with-d3/backbone.js"></script>
<script src="http://www.davidrobles.net/js/visualizing-game-trees-with-d3/d3.js"></script>
<script src="http://www.davidrobles.net/js/visualizing-game-trees-with-d3/mauler-0.0.4.js"></script>
<script>
var margin = { top: 50, right: 50, bottom: 50, left: 50 },
width = 960 - margin.left - margin.right,
height = 500 - margin.top - margin.bottom,
nodeSize = 45,
counter = 1;
var breadthFirstIteration = function() {
if (queue.length > 0) {
var node = queue.shift();
if (node.parent != node) {
if (!node.parent.children) {
node.parent.children = [];
}
node.parent.children.push(node);
}
var moves = node.game.moves();
for (var i = 0; i < moves.length; i++) {
queue.push({
game: node.game.copy().move(i),
parent: node,
id: counter++
});
}
return node;
}
};
var ticTacToe = new ma.games.TicTacToe({
board: [['O', 'X', ' '],
['O', 'X', ' '],
[' ', ' ', 'X']]
});
var svgView = new ma.views.TicTacToeSVG({
model: ticTacToe,
sideLength: nodeSize
});
var diagonal = d3.svg.diagonal()
.projection(function(d) { return [d.x, d.y]; });
var svg = d3.select("body")
.append("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom)
.attr("style", "background-color: #eeeeee")
.append("g")
.attr("transform", "translate(" + margin.left + ", " + margin.top + ")");
var tree = d3.layout.tree().size([width, height]);
tree.separation(function(a, b) {
return 2;
});
var root = { game: ticTacToe, id: 0 },
nodes = tree(root);
root.parent = root;
root.px = root.x;
root.py = root.y;
var curNode = root;
var queue = [root];
var update = function() {
if (!curNode) {
return clearInterval(timer);
}
nodes.push(curNode);
// Enter nodes
svg.selectAll(".node-group")
.data(tree.nodes(root), function(d) {
return d.id;
})
.enter()
.append("g")
.attr("class", "node-group")
.attr("transform", function(d) {
svgView.model = d.game;
svgView.svg = d3.select(this);
svgView.render();
return "translate(" + (d.parent.px - (nodeSize / 2)) + ", " + (d.parent.py - (nodeSize / 2)) + ")";
});
// Enter links
svg.selectAll(".link")
.data(tree.links(nodes), function(d) {
return d.source.id + "-" + d.target.id;
})
.enter()
.insert("path", ".node-group")
.attr("class", "link")
.attr("d", function(d) {
var o = {
x: d.source.px,
y: d.source.py
};
return diagonal({
source: o,
target: o
});
})
.attr("fill", "none")
.attr("stroke", "#666666")
.attr("stroke-width", 2);
var t = svg.transition().duration(250);
// Update links
t.selectAll(".link")
.attr("d", diagonal);
// Update nodes
t.selectAll(".node-group")
.attr("transform", function(d) {
d.px = d.x;
d.py = d.y;
return "translate(" + (d.x - (nodeSize / 2)) + ", " + (d.y - (nodeSize / 2)) + ")"
});
curNode = breadthFirstIteration();
};
var duration = 250,
timer = setInterval(update, duration);
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment