// Cloned by Ethan Kavanagh on 10 Oct 2023 from World "Breadth-first search " by "Coding Train" project
// Please leave this clone trail here.
// Breadth-first search
// Port from:
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// Modified to do random graphs with random labels
// Find path from start to destination
// Looks at nearest nodes first
// then at nodes 1 level beyond each of those
// ...
// Finds a (joint) shortest path
// random number of nodes each time round
var NONODES = AB.randomIntAtoB ( 5, 15 );
var NOCONNECTIONS = NONODES * AB.randomIntAtoB ( 1, 2 ) ;
var graph;
var queue = [];
// "rest distance" between nodes
const springLength = 200;
//=== graph.js ================================================================
// This is the graph object
function Graph() {
// It has an object to store all nodes by label
this.graph = {};
// It has a redundant array to iterate through all the nodes
this.nodes = [];
// Start and end
this.start = null;
this.end = null;
}
// Set start
Graph.prototype.setStart = function(node) {
this.start = node;
}
// Set end
Graph.prototype.setEnd = function(node) {
this.end = node;
}
// Add a node
Graph.prototype.addNode = function(label) {
// Create the node
var n = new Node(label);
// Keep track of it
this.graph[label] = n;
this.nodes.push(n);
// Return a reference back
return n;
}
// Draw everything
Graph.prototype.show = function() {
for (var i = 0; i < this.nodes.length; i++) {
this.nodes[i].showEdges();
}
for (var i = 0; i < this.nodes.length; i++) {
this.nodes[i].show();
}
}
// Simulate some physics!
Graph.prototype.simulate = function() {
// First node always in center
this.nodes[0].pos.set(width / 2, height / 2);
// Look at every node against every other node
for (var i = 1; i < this.nodes.length; i++) {
var node1 = this.nodes[i];
for (var j = 0; j < this.nodes.length; j++) {
// Nodes don't interact with themselves!
if (i == j) continue;
var node2 = this.nodes[j];
// A vector that points between the nodes
var force = p5.Vector.sub(node1.pos, node2.pos);
var dist = force.mag();
// What is spring force?
var spring = 0;
var k = 0.06;
// If they are connected calculate
if (node1.isConnected(node2) || node2.isConnected(node1)) {
spring = k * (springLength - dist);
}
// All nodes need their own space even if not connected
var separate = 1 / (dist * k);
// Apply the force!
force.setMag(spring + separate)
node1.vel.add(force);
// Slow down velocity so that it dampens over time
node1.vel.mult(0.95);
}
}
// Add velocity to position for all nodes
for (var i = 0; i < this.nodes.length; i++) {
var node = this.nodes[i];
node.pos.add(node.vel);
}
}
//=== node.js ================================================================
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// An object for an individual node
function Node(label) {
// Nodes have physics now!
this.pos = createVector(random(width),random(height));
this.vel = createVector();
// And a color
this.col = color(0);
// The "label" or "value"
this.label = label;
// An array of edges
this.edges = [];
// Parent
this.parent = null;
// Searched?
this.searched = false;
// on queue?
this.onqueue = false;
}
// Is this node connected to another node?
Node.prototype.isConnected = function(neighbor)
{
var index = this.edges.indexOf(neighbor);
return (index >= 0);
}
// Draw!
Node.prototype.show = function() {
textAlign(CENTER);
var w = textWidth(this.label);
stroke(255);
fill(this.col);
ellipse(this.pos.x, this.pos.y, w * 2, w * 2);
fill(255);
noStroke();
text(this.label, this.pos.x, this.pos.y);
}
// Highlight!
Node.prototype.highlight = function() {
this.col = color(0, 150, 0);
}
// Draw connections as lines
Node.prototype.showEdges = function() {
noFill();
stroke(255);
for (var i = 0; i < this.edges.length; i++) {
line(this.pos.x, this.pos.y, this.edges[i].pos.x, this.edges[i].pos.y);
}
}
function connect ( n, m )
// connect two Nodes
// connect both ways
// do not do duplicate connections
{
if ( ! n.isConnected ( m ) ) n.edges.push(m);
if ( ! m.isConnected ( n ) ) m.edges.push(n);
};
//=== sketch.js ================================================================
// Based on
// Grokking Algorithms
// http://amzn.to/2n7KF4h
function setup()
{
createCanvas ( ABWorld.fullwidth(), ABWorld.fullheight() );
graph = new Graph();
var start = graph.addNode('START'); // graph.nodes[0]
var dest = graph.addNode('DEST'); // graph.nodes[1]
var i,c,d;
// add (NONODES-2) further random nodes
for ( i = 2; i <= NONODES-1; i++)
{
var s = Math.random().toString(36).substring(9);
// https://stackoverflow.com/questions/1349404/generate-random-string-characters-in-javascript
graph.addNode(s);
}
// random connections
// connect start and end to 2 random nodes
for ( i = 1; i <= 2; i++)
{
c = AB.randomIntAtoB ( 2, NONODES-1 );
connect ( graph.nodes[0], graph.nodes[c] );
}
for ( i = 1; i <= 2; i++)
{
c = AB.randomIntAtoB ( 2, NONODES-1 );
connect ( graph.nodes[1], graph.nodes[c] );
}
// make some random other connections
for ( i = 1; i <= NOCONNECTIONS; i++)
{
c = AB.randomIntAtoB ( 2, NONODES-1 );
d = AB.randomIntAtoB ( 2, NONODES-1 );
connect ( graph.nodes[c], graph.nodes[d] );
}
graph.setStart(start);
graph.setEnd(dest);
bfs();
}
function draw() {
background(51);
graph.simulate();
graph.show();
}
function highlightPath (n)
// just found goal node - now highlight path back to start
{
var subclock = 0;
n.highlight();
while (n != graph.start)
{
// guard against infinite loop - useful while debugging so tab does not crash
if (subclock > 1000) break;
subclock++;
n = n.parent;
n.highlight();
}
}
function bfs()
{
var clock = 0;
var i;
var found = false;
var destNotFound = true;
queue.push(graph.start);
//--- start of while ------------------------------------------
while (queue.length > 0)
{
// guard against infinite loop
if (clock > 10000) break;
clock++;
var person = queue.shift();
if ( ! person.searched )
{
console.log ("======" );
console.log ("start of search of " + person.label);
if (person == graph.end)
{
console.log ("found goal node");
highlightPath (person);
found = true;
break;
}
else
{
console.log ("checking neighbours of " + person.label);
for ( i = 0; i < person.edges.length; i++)
{
var n = person.edges[i];
if ( ! n.onqueue ) // do not add twice
{
if (n.label == "DEST") {
console.log("Found DEST")
destNotFound = false;
break;
}
if (destNotFound) {
console.log ("adding neighbour " + n.label + " to queue");
}
queue.push(n);
n.parent = person;
n.onqueue = true;
}
}
if (!destNotFound) {
break;
}
person.searched = true;
console.log ("end of search of " + person.label);
}
}
}
//--- end of while ------------------------------------------
if ( ! found )
console.log ("No path found");
}