Code viewer [Ancient Brain]

Code viewer for World: Breadth-first search

// Cloned by Abdelshafa Abdala on 13 Oct 2021 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;
 
  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 
          {
          console.log ("adding neighbour " + n.label + " to queue");
          queue.push(n);
          n.parent = person;
          n.onqueue = true;
          }
        }
        person.searched = true;
       console.log ("end of search of " + person.label);
      }
    }
  }    
//--- end of while ------------------------------------------




}