Steps to nodes again

p5.js Coding Questions
1

https://editor.p5js.org/paulgoux/sketches/eiY8BkMUm

So I’m trying to calculate the steps in between each node, and this is working seemingly ok, however some will be out by about 1-5 steps. I don’t understand whats causing this. The main sketch is above and this is the function used to travel from node to node.

Please note, nodefinder and nodebackup are populated once you press generate nodes, however you need to wait for the maze to have completed first. Nodefinder identifies a node based on its number of neighbours, a node is a node if it does not have 2 neighbours. Then this.findnode populates the this.parents if a cell if not a node using some if statements.

The nodefinder function uses nodefinder[i] as a starting point, uses a function called next to check if its neighbouring cell has open walls and updates the neighbouring cells “array” value with its id and a boolean true, so it knows that that node has visited that cell.

So far so good. However when I updated the steps it generates approximately correct steps but with some errors.

var count = 0;

function findnode(){
  var step = 0;
if(findnodes.toggle===1){

for(var i=0;i<nodefinder.length;i++){

    var a = nodebackup[i].oid.toString();
    var b = nodebackup[i].oid
    nodefinder[i].array[b] = true;
    var next = nodefinder[i].newNeighbour(b);
    nodefinder[i].highlight();

    var steps = nodebackup[i].steps;
    //count ++;
    if(next){
      count++;
      //nodefinde
      nodebackup[i].steps[0] ++;
      nodebackup[i].steps[1] ++;
      if(next.node){
        var a = nodefinder[i].parent[0]
        var b = nodefinder[i].parent[1]
        if(a ===nodebackup[i]){
          nodebackup[i].c1[nodebackup[i].c2][1] = nodefinder[i].parent[1];
          nodebackup[i].c1[nodebackup[i].c2][0] = steps[1];
        }
        else if(b === nodebackup[i]){
          nodebackup[i].c1[nodebackup[i].c2][1] = nodefinder[i].parent[0];
          nodebackup[i].c1[nodebackup[i].c2][0] = steps[0];
        }
        if(nodestack[i].length>0){
        nodefinder[i] = nodestack[i].pop();
        nodebackup[i].c2 ++;
        nodebackup[i].steps = [0,0];
      }
    }

      else{

      nodestack[i].push(nodefinder[i]);

      var a = next.parent[0]
      var b = next.parent[1]
      if(a ===nodebackup[i]){

        nodebackup[i].c1[nodebackup[i].c2][1] = next.parent[1];
        nodebackup[i].c1[nodebackup[i].c2][0]  = steps[1];
      }
      else if(b === nodebackup[i]){
        nodebackup[i].c1[nodebackup[i].c2][1] = next.parent[0];
        nodebackup[i].c1[nodebackup[i].c2][0]  = steps[0];
      }

      if(!next.c1[0][1] ){
      next.c1[0][0] = steps[0];
      next.c1[0][1] = nodebackup[i];
      }
      else{
        next.c1[1][0] = steps[1];
        next.c1[1][1] = nodebackup[i];
      }
      nodefinder[i] = next;
    }
    }

    else if(nodestack[i].length>0){
      nodefinder[i] = nodestack[i].pop();
      if(nodefinder[i] === nodebackup[i]&&count>0){
        nodebackup[i].c2 ++;
        nodebackup[i].steps = [0,0];
      }
    }}
}
};
1 Like
2

Wow finally cracked this one. Now to add A* search. it currently has a Djistra like search algorithm using pathfinder 1. Pathfinder 2 counts steps from any node given in the script, then a* can be implemented. Note for pathfinder 2 you need to click on generate nodes then find nodes first, I will streamline this late to be just one operation.

First press start to generate map. Please note unless the number of players is set to 1, there’s a chance the map may not be fully integrated. The players will each generate their own maze with the unvisited space, then create two connections to other maze clusters, currently its unable to identify which maze cluster its made a connection with so it can create two connections with the same neighboring cluster and therefore isolate itself.

Then press Generate Nodes. This populates an array for cells which do not have 2 neighbors.

Then press Findnodes, this will call a function which starts from all the nodes in the populated array and seeks its neighboring nodes, and retrieves their distance to itself. Note this only travels a distance of 1 node, marks it as visited, steps back to its origin and then if it has other unvisited neighbors will expand its search until it finds another node and so on till all neighbors have been visited.

Then finally, press Pathfinder2. This calls the same type of function as before apart from this time, each node travels to every-other node on the map, not just every neighboring node. It then assigns that node a distance from itself which is saved in the array this.dist_to_node, or grid[number]dist_to_node.

Voila.

This was tough and hopefully some of you can make use of it, as I said, it should now be possible to implement the a* search as every distance is known.

1 Like