Git Product home page Git Product logo

another-astar's Introduction

another-astar

Yet another javascript library with implementations of A* and IDA* algorithms.

Usage

npm install git://github.com/miguelcarrasco/another-astar.git#0.1.2

Use findPathAstar method to get a path from start to goal using A* algorithm, it will return an optimal path if the heuristic cost estimate is admissible for every evaluated node.

let astar = require('another-astar');

let path = astar.findPathAstar(
    {
        // start and goal can be any object
        start: start,
        goal: goal,
        heuristicCostEstimate: function (node) {
            // it should return a heuristic estimate
            // of the cost from node to goal, for example:           
            return someHeuristicCostEstimateNumber;
            // This heuristic should be "admissible" 
            // i.e. the estimate must not be greater than the real cost 
            // to guarantee an optimal path.
        },
        getNodeIndex: function (node) {
            // it should return a string representing the
            // node object for indexing purposes, for example:
            return node.toString();
        },
        getNeighbors: function (node) {
            // it should return an array that contain all the neighbors nodes from the
            // specified node.
            return [node1, node2, ..., etc]; 
        },
        getDistance: function (node1, node2) {
            // it should return the real cost from node1 to node2
            // note that node2 is always a neighbor of node1
            return realCostNumber;
        }
    });

If you want to use IDA* algorithm instead, you can use the method findPathIDAstar instead, it expects the same object as in findPathAstar:

let path = astar.findPathIDAstar({ ... });

Notes

IDA* algorithm memory usage is lower than in A*, but unlike ordinary iterative deepening search, it concentrates on exploring the most promising nodes and thus does not go to the same depth everywhere in the search tree.

Unlike A*, IDA* does not utilize dynamic programming and therefore often ends up exploring the same nodes many times.

This is a work in progress, performance will be improved in future versions.

another-astar's People

Contributors

miguelcarrasco avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.