# Speed Optimization for Incremental Updating of Grid-Based Distance Maps
## 1 Introduction  
In the context of collision check and path planning in robotics and game AI, the Distance Map (DM) has been widely used as a consistent model to encode the search space [1; 2; 3; 4; 5]. In a grid-based environment with regions of blocked cells, a corresponding DM can be constructed to provide each cell a maximal clearance value, which registers the distance from itself to the nearest obstacle. Thus, a DM can help an agent (e.g., a Non-Player Character (NPC) in the video game or a robot in the real world) with a certain safety radius to efficiently search out collision-free paths and to avoid obstacles in motion. Figure 1 presents a DM constructed in an indoor environment. In many practical applications, the underlying environments that an agent maneuvers in are often dynamic; therefore, it is necessary to reconstruct their corresponding DMs whenever changes of cell states are observed (e.g., an obstacle is inserted, removed, reshaped, or transferred). Since such changes usually occur within a relatively neighboring area around the agent, only portions of the previously constructed DM need repair. To make use of this localized feature, existing algorithms such as Dynamic Brushfire [6] and its subsequent variants [7; 8] aim to speed up the reconstruction by launching a wavefront from the source of the state changes to incrementally repair the distance values, rather than reconstructing the whole DM from scratch. With such a localized mechanism, only those cells that are actually affected by the wavefront need to be handled; thus, in most cases, the computation costs can be efficiently reduced. However, for all of the previously proposed algorithms, the propagation of the wavefronts simply expands all the neighbors of a processed cell without preference, and then inserts the newly affected neighbors into a priority queue, so as to prepare for the next round propagation. Such indiscriminate expansion results in a much longer priority queue and thus becomes an efficiency bottleneck. In order to reduce the number of elements which need to be sorted by the priority queue, a searching strategy, Canonical Ordering, is introduced by us to systematically choose a single route from the equivalent propagation paths. Figure 2 shows how our algorithm propagates the wavefront form the source blocked cell (denoted as yellow tiles), visiting each affected cell only once (where the red arrows denotes the propagation directions of the wavefronts). We choose the successors of an expanded cell, \(s\), by following two basic rules described in [PERSON] and [PERSON]'s paper [9]. That is, for a cell \(s\), with the propagation direction \(c\) that was previously used to reach \(s\), (1) If \(c\) to arrive at \(s\) is one of the four cardinal directions, the only legal direction at \(s\) for the next round propagation is \(c\); (2) If the \(c\) to arrive at \(s\) is one of the four diagonal directions which can be decomposed into two perpendicular cardinal components \(c_{1}\) and \(c_{2}\), the legal directions at \(s\) for the next round propagation are \(c\), \(c_{1}\), and \(c_{2}\). We name our algorithm Canonical Ordering Dynamic Brushfire (abbreviated to CODB in the rest of this paper). Since a DM stores the maximal clearance for each traversable cell to its nearest obstacle, operations such as collision checks can be simplified to instant look-up queries (As shown in Equation (1)). For instance, if an agent with safety radius \(R>0\) is located on cell \(s\), then the result of the collision check is determined by Equation (1) as below (where 1 denotes collision detected and 0 denotes collision-free):  
\[C(R,s)=\left\{ \begin{array}{ll}1&if\ (R-DM(s))\geq 0\\ 0&if\ (R-DM(s))<0\end{array} \right. \tag{1}\]  
Figure 1: A distance map (DM) constructed from an indoor environment. The yellow regions consist of blocked cells (obstacles). Visually speaking, for each of these traversable cells in the unblocked areas, the father it is away from the nearest obstacle, the higher its brightness is.