Looking for a way to conduct a recursive search in a Javascript object that fits your specific requirements?

Question

Looking for a way to conduct a recursive search in a Javascript object that fits your specific requirements?

Hello there,

I'm currently developing a text-based game using Javascript. In my code, I have a variable called map which is an object containing information about different rooms in the game. I found an algorithm that I would like to modify for my specific needs, but I'm unsure how to do so.

Here is a snippet of my variable:

/**
 *       [003]-[004]
 *         |     |
 * [001]-[002] [007]
 *         |     |
 *       [005]-[006]
 **/     
var map = {
    "001" : {
        "Id" : "001",
        "Name" : "Room 001",
        "Directions" : {
            "N" : "",
            "S" : "",
            "E" : "002",
            "W" : ""
        }
    }, // Other room objects omitted for brevity
};


function findSteps( id, map, array ) {
    if ( ! ( map && "object" === typeof map ) ) { return; }
    if ( map.Id === id ) { return map; }

    for ( var x in map ) {
        if ( Object.hasOwnProperty.call( map, x ) ) {
            map.Id && array.push( map.Id ); //used to exclude undefined
            var result = findSteps( id, map[ x ], array );

            if ( result !== undefined ) {
                return [ result, array ];
            }
        }
    }
}

console.dir( findSteps( "004", map, [] ) );

<p>I want the function to return an array of arrays containing all possible paths in the game. This will help me determine the closest available path later on.</p>

<p>The desired output would look something like this:</p>

<pre><code>output = [
    [ "001", "002", "003", "004" ],
    [ "001", "002", "005", "006", "007", "004" ]
]

I also need the function to accept a starting Id and stop the recursion after a certain number of iterations if no path is found.

If you have any hints or tips, they would be much appreciated.

Thank you for your help!

http://jsfiddle.net/GxZYX/

Edit:

After considering everything, I believe I only need to find the shortest path.

Edit:

http://jsfiddle.net/GxZYX/1/ is where I tested implementing breadth-first search (currently buggy).

javascript algorithm

Answer 1

Answer №1

I am seeking a function that will generate an array of arrays containing all potential paths. These paths will be evaluated later to identify the most efficient route.

Using this approach may not be the most effective way to conduct pathfinding. There are algorithms specifically designed for determining the shortest paths in graphs, and for most 2D games, the preferred method is often the A* algorithm. A* algorithm incorporates a heuristic distance function (h*(x)) to avoid visiting every individual node (room), resulting in significantly lower running time compared to considering every possible path, which could have a time complexity as poor as O( n! ).

For those interested, an implementation in JavaScript is available, but I recommend gaining a solid understanding of the theory behind it before attempting to implement it yourself.

Answer 2

I am seeking a function that will generate an array of arrays containing all potential paths. These paths will be evaluated later to identify the most efficient route.

Using this approach may not be the most effective way to conduct pathfinding. There are algorithms specifically designed for determining the shortest paths in graphs, and for most 2D games, the preferred method is often the A* algorithm. A* algorithm incorporates a heuristic distance function (h*(x)) to avoid visiting every individual node (room), resulting in significantly lower running time compared to considering every possible path, which could have a time complexity as poor as O( n! ).

For those interested, an implementation in JavaScript is available, but I recommend gaining a solid understanding of the theory behind it before attempting to implement it yourself.

Answer 3

Answer №2

If you want to determine the most efficient route between two points in an undirected graph similar to yours, you can simply utilize a Breadth-first-search algorithm.

function findShortestPathTo(destination, currentLocation){
    var path = [];
    while(true){
        path.push(currentLocation);
        if(currentLocation == destination[currentLocation]) break;
        currentLocation = destination[currentLocation];
    }
    return path;
}       

var breadthFirstSearch = function( graph, startNode, endNode ) {

    var destination = {};
    destination[endNode] = endNode;

    var currentLevel = [ graph[endNode] ];

    while( currentLevel.length ) {

        var nextLevel = [];

        for(var i=0; i<currentLevel.length; i++) {
            var currentNode = currentLevel[i];

            if ( currentNode.Id == startNode ) {
                return findShortestPathTo(destination, startNode);
            }

            for( var direction in currentNode.Directions ) {
                var neighborNode = currentNode.Directions[direction]; 
                if( !destination[neighborNode] ) {
                    destination[neighborNode] = currentNode.Id;
                    nextLevel.push( graph[neighborNode] );
                }
            }
        }

        currentLevel = nextLevel;
    }

    return null;
};

var graph = {
    "001" : {
        "Id" : "001",
        "Name" : "Room 001",
        "Directions" : {
            "E" : "002"
        }
    },
    "002" : {
        "Id" : "002",
        "Name" : "Room 002",
        "Directions" : {
            "N" : "003",
            "S" : "005",
            "W" : "001"
        }
    },
    "003" : {
        "Id" : "003",
        "Name" : "Room 003",
        "Directions" : {
            "S" : "002",
            "E" : "004"
        }
    },
    "004" : {
        "Id" : "004",
        "Name" : "Room 004",
        "Directions" : {
            "S" : "007",
            "W" : "003"
        }
    },
    "005" : {
        "Id" : "005",
        "Name" : "Room 005",
        "Directions" : {
            "N" : "002",
            "E" : "006"
        }
    },
    "006" : {
        "Id" : "006",
        "Name" : "Room 006",
        "Directions" : {
            "N" : "007",
            "W" : "005"
        }
    },
    "007" : {
        "Id" : "007",
        "Name" : "Room 007",
        "Directions" : {
            "N" : "004",
            "S" : "006"
        }
    }
};

console.log('shortest path',  breadthFirstSearch( graph, "001", "004" ) );

Answer 4

If you want to determine the most efficient route between two points in an undirected graph similar to yours, you can simply utilize a Breadth-first-search algorithm.

function findShortestPathTo(destination, currentLocation){
    var path = [];
    while(true){
        path.push(currentLocation);
        if(currentLocation == destination[currentLocation]) break;
        currentLocation = destination[currentLocation];
    }
    return path;
}       

var breadthFirstSearch = function( graph, startNode, endNode ) {

    var destination = {};
    destination[endNode] = endNode;

    var currentLevel = [ graph[endNode] ];

    while( currentLevel.length ) {

        var nextLevel = [];

        for(var i=0; i<currentLevel.length; i++) {
            var currentNode = currentLevel[i];

            if ( currentNode.Id == startNode ) {
                return findShortestPathTo(destination, startNode);
            }

            for( var direction in currentNode.Directions ) {
                var neighborNode = currentNode.Directions[direction]; 
                if( !destination[neighborNode] ) {
                    destination[neighborNode] = currentNode.Id;
                    nextLevel.push( graph[neighborNode] );
                }
            }
        }

        currentLevel = nextLevel;
    }

    return null;
};

var graph = {
    "001" : {
        "Id" : "001",
        "Name" : "Room 001",
        "Directions" : {
            "E" : "002"
        }
    },
    "002" : {
        "Id" : "002",
        "Name" : "Room 002",
        "Directions" : {
            "N" : "003",
            "S" : "005",
            "W" : "001"
        }
    },
    "003" : {
        "Id" : "003",
        "Name" : "Room 003",
        "Directions" : {
            "S" : "002",
            "E" : "004"
        }
    },
    "004" : {
        "Id" : "004",
        "Name" : "Room 004",
        "Directions" : {
            "S" : "007",
            "W" : "003"
        }
    },
    "005" : {
        "Id" : "005",
        "Name" : "Room 005",
        "Directions" : {
            "N" : "002",
            "E" : "006"
        }
    },
    "006" : {
        "Id" : "006",
        "Name" : "Room 006",
        "Directions" : {
            "N" : "007",
            "W" : "005"
        }
    },
    "007" : {
        "Id" : "007",
        "Name" : "Room 007",
        "Directions" : {
            "N" : "004",
            "S" : "006"
        }
    }
};

console.log('shortest path',  breadthFirstSearch( graph, "001", "004" ) );

Looking for a way to conduct a recursive search in a Javascript object that fits your specific requirements?

Answer №1

Answer №2

Similar questions

Employing promises for fetching data via XHR results in a promise that is still pending

Is there a way to insert a value into the input field using JQuery or JavaScript?

Identifying text within a paragraph using JavaScript regex, excluding any URLs mentioned

Is it possible to link click and onchange events?

Delete the file containing Mongoose references

What is the formula for determining the REAL innerWidth and innerHeight?

Encountering an issue with JQuery when attempting to create a double dropdown SelectList. Upon submitting the POST request, the output received is always

Does the concept of abstraction come into play when utilizing Javascript array functions that do not change the original data but instead create a new array?

absence of an export called

Loading an Angular app causes Chrome devtools to freeze

Confirm the dimensions of an image prior to uploading using Node, Express, and Multer

Having trouble getting my parallax slideshow to work with jquery preventDefault

What is the best way to retrieve a string from a URL?

Tips for displaying a loading spinner during the rendering of a backbone view

Having difficulty sending emails with Nodemailer

What methods can I use to prevent a number from becoming negative?

I am facing an issue with the Angular signup page that is using ui-router, as it is unable

Preventing a JavaScript timer function from executing multiple times when triggered by an 'in viewport' function

Assign the "this" keyword of App.vue to the Vuex state

transform pixel coordinates to latitude and longitude dimensions