Icontem

astar: Implement the Pathfinding algorithm in JavaScript

Recommend this page to a friend!
  Info   View files View files (5)   DownloadInstall with Composer Download .zip   Reputation   Support forum   Blog    
Last Updated Ratings Unique User Downloads Download Rankings
2014-05-16 (5 years ago) RSS 2.0 feedNot enough user ratingsTotal: 135 All time: 357 This week: 9Up
Version License JavaScript version Categories
astar 1.0Freeware1.0Geography, Algorithms
Description Author

This object can implement the Pathfinding algorithm in JavaScript.

It can take a start point and destination point on a grid map of a given size and finds the path to go from one point to the other.

The object can render on a HTML page the grid map and the path between the grid nodes as the path is being found.

Innovation Award
JavaScript Programming Innovation award nominee
May 2014
Number 3
Finding the path between two points is a problem that often appears in mapping applications.

This object provides a solution to that problem and provides a visual representation of the paths that it finds

Manuel Lemos
  Performance   Level  
Name: Andoitz Jordan Marmolejo <contact>
Classes: 2 packages by
Country: Spain Spain
Age: 29
All time rank: 955 in Spain Spain
Week rank: 10 Up1 in Spain Spain Up
Innovation award
Innovation award
Nominee: 2x

Winner: 1x

Details
A* Pathfinding Algorithm Example

Algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes.

A* Algorithm Pseudocode

function A*(start,goal)
    closedset := the empty set    // The set of nodes already evaluated.
    openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
    came_from := the empty map    // The map of navigated nodes.
 
    g_score[start] := 0    // Cost from start along best known path.
    // Estimated total cost from start to goal through y.
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)
 
    while openset is not empty
        current := the node in openset having the lowest f_score[] value
        if current = goal
            return reconstruct_path(came_from, goal)
 
        remove current from openset
        add current to closedset
        for each neighbor in neighbor_nodes(current)
            if neighbor in closedset
                continue
            tentative_g_score := g_score[current] + dist_between(current,neighbor)
 
            if neighbor not in openset or tentative_g_score < g_score[neighbor] 
                came_from[neighbor] := current
                g_score[neighbor] := tentative_g_score
                f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                if neighbor not in openset
                    add neighbor to openset
 
    return failure
 
function reconstruct_path(came_from, current_node)
    if current_node in came_from
        p := reconstruct_path(came_from, came_from[current_node])
        return (p + current_node)
    else
        return current_node
		

For more information and downloads visit:

http://www.andoitz.com/proyectos/programacion/34-proyectos/programacion/87-astar-pathfinding-algorithm-example.html
  Files folder image Files  
File Role Description
Accessible without login Plain text file a_star.css Data CSS style
Accessible without login Plain text file a_star.html Example Main html
Plain text file a_star.js Class aStar jQuery Library
Plain text file jquery-1.11.0.min.js Class Jquery Library
Accessible without login Plain text file Readme.txt Doc. Readme document

 Version Control Unique User Downloads Download Rankings  
 0%
Total:135
This week:0
All time:357
This week:9Up