Image: Astar progress animation

Description: Illustration of A* search algorithm. The graph is created by uniform square discretization of a 2-dimensional planar region, placing a node in each discretized cell, and connecting each node with its 8 neighbors using bidirectional edges. Cost of edges are same as their Euclidean lengths. The gray shape represents an obstacle. The filled circles in red & green represent expanded nodes (nodes in closed set). The color indicate the g-value (red:lower g-value, green: higher g-value). The empty nodes with blue boundary are the ones in open set. The nodes of the graph are generated on the fly, and nodes falling inside the obstacle are discarded as inaccessible. The objective is to find the least cost path (restricted to the graph) from a given start to a given goal coordinate. The heuristic (consistent) used by a node is its Euclidean distance to goal. That is, ha(n) = |g - n|2, where n represents the Euclidean coordinate of the node n, g is the goal node, and | . |2 is the 2-norm. This is a typical example of motion planning in robotics using A* search algorithm. Created using YGSBPL graph-search library and OpenCV.
Title: Astar progress animation
Credit: Own work
Author: Subh83
Permission: .mw-parser-output .responsive-license-cc{clear:both;text-align:center;box-sizing:border-box;width:100%;justify-content:space-around;align-items:center;margin:0.5em auto;background-color:#f9f9f9;border:2px solid #e0e0e0;border-spacing:8px;display:flex}.mw-parser-output .responsive-license-cc div{margin:4px}.mw-parser-output .rlicense-text div{margin:0.5em auto}@media screen and (max-width:640px){.mw-parser-output .responsive-license-cc{flex-flow:column}.mw-parser-output .rlicense-text{order:1}} This file is licensed under the Creative Commons Attribution 3.0 Unported license. You are free: to share – to copy, distribute and transmit the work to remix – to adapt the work Under the following conditions: attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. https://creativecommons.org/licenses/by/3.0CC BY 3.0 Creative Commons Attribution 3.0 truetrue
Usage Terms: Creative Commons Attribution 3.0
License: CC BY 3.0
License Link: https://creativecommons.org/licenses/by/3.0
Attribution Required?: Yes