A* Search: Find a Route Around a Wall

A wall blocks the direct route. How can A* choose a useful next square without already knowing the way? We work through one small map from start to exit, then replay the same decisions in Python. You can find the complete Python algorithm and runnable examples here: https://github.com/bigocast/bigocast-... First, build the remaining-distance estimate by imagining the wall removed. Combine it with the cost so far, keep the other options waiting, and see why a shortest route can briefly move away from the exit. Our complete example returns six legal moves. The Python walkthrough follows heap removal, the cheaper-route comparison, best-cost and parent updates, and route reconstruction. We stop when a current goal entry is removed, then explain why Manhattan distance is safe for four-way movement with one-step costs. For N input squares, we derive O(N log N) worst-case time and O(N) auxiliary space, including heap entries. A returned route of L positions takes O(L) reconstruction time and output space. These bounds describe this implementation and map contract; the estimate is not a promise that A* always runs faster. Sources and further reading Amit Patel, Red Blob Games, Introduction to A*: https://www.redblobgames.com/pathfind... Amit Patel, Red Blob Games, Implementation: https://www.redblobgames.com/pathfind... UC Berkeley CS 188, Informed Search: https://inst.eecs.berkeley.edu/~cs188... Carnegie Mellon 15-281, Search and Games: https://www.cs.cmu.edu/~15281/coursen... Join the newsletter: https://bigocast.com Chapters 00:00 A route around a wall 00:23 Four-way moves and one-step costs 01:06 Build the Manhattan estimate 01:51 Cost so far plus remaining estimate 02:50 Why a useful route can move away 03:44 Finish the search and recover the route 04:58 Give Python the same map 05:54 Initialize and choose a current entry 06:45 Follow one complete neighbor update 07:53 Repeat and reconstruct the path 08:52 Why this estimate gives a shortest route 10:02 Derive time, working space and output cost 11:27 Keep learning with BigOCast 'A Kind Of Hope' by Scott Buckley - released under CC-BY 4.0. www.scottbuckley.com.au https://www.scottbuckley.com.au/libra... https://creativecommons.org/licenses/... Music edited with local looping, crossfades, filtering, mono mixing and speech ducking.