Scanning Algorithms

BFS (Breadth First Search)

• O(V + E).

• Good for 'unweighted graphs'.

• "Good for finding the shortest path".

• Explanation (1) .

• Explanation (2) .

DFS (Depth First Search)

• O(V + E).

• "Not ideal for finding the shortest path."

• Explanation (1) .

• Explanation (2) .

Angular Sweep (Angular Sweep)

• "The central idea of Angular Sweep is to sweep a specific angle around an origin point (such as the player) and determine which cells in the grid are visible and which are blocked by obstacles. The sweep can be done over an arc (limited field of view) or a full circle (full 360° field of view)."

• "From the origin point, the sweep is done in angular increments, sweeping an arc or a full circle. At each angular increment, a "ray" is cast from the origin point, moving in a direction corresponding to the current angle."

Bresenham's Line Algorithm

• Draw a line on a grid / pixel grid.

Midpoint Circle Algorithm / Bresenham’s Circle Algorithm

• "The algorithm is often used to draw precise circles or arcs in 2D games."

• "The algorithm is specific to circles and therefore cannot be used directly for other geometric shapes."

• "It is a fundamental technique in computer graphics and remains relevant for game development and graphical applications."

• ~It divides the circle into octants (1/8) and sweeps each arc.