ComputingComputer ScienceAlgorithmsComputational GeometryPath PlanningHeuristic SearchObstacle AvoidanceRoutingBubble FormationExpansionMaze RouterMaze RoutingMaze SolvingPathfinding Algorithms
The paper proposes a method for generating a path between two points in a cellular array with obstacle cells. The method first performs a line search toward the target, and when an obstacle is encountered it applies a Lee‑type expansion to bubble around the obstacle before resuming the line search. The approach is fast and highly effective on boards with ample free space.
This paper describes a method of generating a path between two points of a cellular array, with some cells being specified as obstacles. The method combines two techniques: A line search is first directed toward the target. This is a fast and extremely effective method on boards with plenty of space. When the line search hits an obstacle, an expansion technique typical for the Lee-type algorithms is then used to “bubble” around the obstacle. The line search can then continue toward the target again.