Javascript Nightmare [closed]

I am new to javascript and wanted to convert my python A* algorithm to a js version so I can use it in a website.

I have tried to copy it over however I have run into an issue seen here:

Uncaught RangeError: Maximum call stack size exceeded  script.js:34 
    at Array.includes (<anonymous>)
    at Graph.add_edge (script.js:34)
    at Graph.add_edge (script.js:40)
    at Graph.add_edge (script.js:40)
    at Graph.add_edge (script.js:40)
    at Graph.add_edge (script.js:40)
    at Graph.add_edge (script.js:40)
    at Graph.add_edge (script.js:40)
    at Graph.add_edge (script.js:40)
    at Graph.add_edge (script.js:40)

Please see my code here https://pastebin.com/4gTm3enA

I am running the JS through a blank website with a button to call the start up function

EDIT: here is my code pasted in here instead of Pastebin –

class Node {
    constructor(name, g, h) {
        this.name = name;
        this.g = g;
        this.h = h;
        this.f = 0;
    }

}

class Edge {
    constructor(n1, n2, w) {
        this.node_1 = n1;
        this.node_2 = n2;
        this.weight = w;
    }
}

class Graph {
    constructor(start, end) {
        this.start = start;
        this.end = end;
        this.edges = new Array();
        this.nodes = new Array(start, end);
    }
    add_node(node) {
        if (this.nodes.includes(node)) {
            console.log('This node is already in the graph');
        } else {
            this.nodes.push(node);
        }
    }
    add_edge(n1, n2, w) {
        if (!(this.nodes.includes(n1))) {
            this.add_node(n1);
        }
        if (!(this.nodes.includes(n2))) {
            this.add_node(n2);
        }
        this.add_edge(n1, n2, w);
    }
    get_edges() {
        return this.edges;
    }
    get_nodes() {
        return this.nodes;
    }
}
function start_up(){
    console.log('running');
    var sn = new Node('a', 4, 4);
    var mn = new Node('b', 2, 2);
    var en = new Node('z', 0, 0);

    var e1 = new Edge(sn, mn, 2);
    var e2 = new Edge(mn, en, 2);

    var g = new Graph(sn, en);

    g.add_edge(sn, mn);
    g.add_edge(mn, en);

    a_star(g, new Array(), new Array(), sn);
}

function a_star(graph, visited, path, current) {
    var edges = graph.get_edges();
    var nodes = graph.get_nodes();

    if (current != graph.end) {
        visited.push(current);
        path.push(current.name);

        console.log("Current Node: " + current);
        console.log('Visited Nodes: ' + visited);

        c_from_c = new Array();
        for (i = 0; i < edges.length; i++) {
            if (current.name in edges[i]){
                tmp = edges[i].replace(current.name, '');
                c_from_c.push(tmp);
            }
        }
        var available_nodes = new Array();
        for (i = 0; i < c_from_c.length; i++){
            var f = parseInt(c_from_c[i][0]);
            for (j = 0; j < nodes.length; j++){
                if (nodes[j].name == c_from_c[i][0]){
                    f += nodes[j].h;
                    nodes[j].f = f;
                    available_nodes.push(nodes[j]);
                }
            }
        }
        var f_val = new Array();
        for (j = 0; j < available_nodes.length; j++){
            f_val.push(available_nodes[j].f)
        }
        var index = available_nodes.findIndex(Math.min(f_val));

        var current = available_nodes[index];

        a_star(graph, visited, path, current);
    }
    else {
        visited.push(current);
        var shortest = new Array();
        for (i = 0; i < visited.length; i++){
            shortest.push(visited[i])
        }
        console.log(shortest);
    }
}

Answer

Your add_edge is recursively calling itself. This leads to an infinite call stack that the program just can’t put up with, thus throwing the stack overflow error (not to be confused with the company Stack Overflow 🙂 ).

I don’t know what exactly you want with this, nor can I read your mind on what you want done here, but definitely don’t call it recursively like that.

If you find yourself needing it call itself again and again, then there are better alternatives, like window.setInterval or window.requestAnimationFrame that don’t blow the stack.

Otherwise, add a “return” statement before the recursive callback if a certain condition is met, or put the callback statement in a conditional that will/won’t execute if a certain condition is met.

Leave a Reply

Your email address will not be published. Required fields are marked *