Skip to content

A* Search algorithm implementation. A* Search algorithm is one of the best and popular technique used in path-finding and graph traversals. Using Vanilla JS and p5.js for visualization. (Random generate map ) Practise.

Notifications You must be signed in to change notification settings

NemesLaszlo/A-Star_Search_Algorithm

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

A-Star_Search_Algorithm

A* Search algorithm implementation. A* Search algorithm is one of the best and popular technique used in path-finding and graph traversals. Using Vanilla JS and p5.js for visualization. (Random generate map ) Practise.

Sources and other links:

https://en.wikipedia.org/wiki/A*_search_algorithm

https://www.geeksforgeeks.org/a-search-algorithm/

https://github.com/NemesLaszlo/A-Pathfinding-Visualization

Pseudocode from the first link: (Wikipedia)

function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        total_path.prepend(current)
        current := cameFrom[current]
    return total_path

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
    // The set of discovered nodes that may need to be (re-)expanded.
    // Initially, only the start node is known.
    openSet := {start}

    // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start to n currently known.
    cameFrom := an empty map

    // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
    gScore := map with default value of Infinity
    gScore[start] := 0

    // For node n, fScore[n] := gScore[n] + h(n).
    fScore := map with default value of Infinity
    fScore[start] := h(start)

    while openSet is not empty
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        openSet.Remove(current)
        for each neighbor of current
            // d(current,neighbor) is the weight of the edge from current to neighbor
            // tentative_gScore is the distance from start to the neighbor through current
            tentative_gScore := gScore[current] + d(current, neighbor)
            if tentative_gScore < gScore[neighbor]
                // This path to neighbor is better than any previous one. Record it!
                cameFrom[neighbor] := current
                gScore[neighbor] := tentative_gScore
                fScore[neighbor] := gScore[neighbor] + h(neighbor)
                if neighbor not in openSet
                    openSet.add(neighbor)

    // Open set is empty but goal was never reached
    return failure

About

A* Search algorithm implementation. A* Search algorithm is one of the best and popular technique used in path-finding and graph traversals. Using Vanilla JS and p5.js for visualization. (Random generate map ) Practise.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published