4.2. Algorithm overview
In Fig. 10, a simple overview of the algorithm to build the accessibility-based graph is shown with four main functions described in the following sections. The algorithm initializes with the user parameters and geometry objects that remain in a global scope. Overall, the algorithm iterates through a queue of nodes that are continually added to the queue in a breadth-first manner from the starting location 𝜏 within the environment (buildGraph). While checking each item of the queue, getNodes iteratively finds the valid neighbor nodes by calling checkChild on each potential neighbor. The final function in the process, getConnection, determines if an edge can exist between two nodes based on the input parameters, and if so, the type of movement required between the original and potential child node. Once an edge is determined to be possible, the movement type is returned (likewise for all connections for the original queued item). Before the breadth-first process continues to the next item in the queue, the graph is updated with vertices, edges, and weights.
4.2.1. Breadth-first process
The generation of common surface and graph information methods regarding navigation takes into account the entire environment at once. Breadth-first search allows for the fast completion of the graph generation when no accessible locations are found (Appendix A). This feature is particularly useful in the planning and design phase of a building or environment as it offers immediate numerical and visual feedback about the features that are blocking accessibility. The quick ending to the graph generation benefits the calculation time in practical use cases (e.g., the starting location being a ramp that is too steep).
Generating the graph begins with a valid starting location where start point 𝜏 is above a valid surface geometry in 𝛤. The algorithm begins with an empty graph 𝐷 and an ordered set 𝑄 representing the queue of vertices that remain to be checked for validity in 𝑃. At initialization 𝑄 = {𝜏}, with the algorithm completing when 𝑄 = ∅.
Generating the graph can be seen in Algorithm 1 line 8, where a parent node 𝑝 is removed from the queue 𝑄. The valid children nodes are assigned to set 𝐶 and if a child node is not already defined as a parent node, it is added to 𝑄. Once the set of valid children are returned, the weight vector containing step type is stored in the weight set (line 10). This pseudocode shows the method in which weights are calculated during graph construction, and therefore, during the iteration over the child set, a function setEdgeCost() on line 12 calculates a directional edge cost between the two nodes and stores it in 𝑊 . This function can be used to set multiple types of edge costs, such as distance, slope, and energy, as discussed later. After the directed edge of a parent and child is stored, the child node is checked for existence in the parent set. If the node is not in the existing parent set it is added to 𝑄.
Two main functions are defined that determine the validity of a child node within the getNodes() function (called in Alg. 1 and later defined in Alg. 2). The function inter(𝑛𝑖,𝑛𝑗) is defined as returning the distance 𝑛⃖⃖⃖⃖𝑛⃖⃖⃗ intersects 𝐵 in the environment and dst(𝑛 , 𝑛) returns 𝑖𝑗𝑖𝑖𝑗 ‖ 𝑛⃗ − 𝑛⃗ ‖ . 𝑖𝑗
Fig. 11 shows the node evaluation in the (𝑥𝑧) plane where the ray cast direction is −𝑧̂. As the graph is in relation to physical space, −𝑧̂ corresponds to the direction of gravity. The parameters and labels used are those described in 4.1.3. The surfaces illustrated provide examples of a step, faceted surface, and natural topography (e.g., a hill or mountain). When a possible node is invalid, it is not added to 𝑄, and in the simple example within the figure, the graph completes. To simplify the illustration, Fig. 11 is a two-dimensional example is given and only the directed relation from the left to right is discussed.
In 11(a), a ray is cast in −𝑧̂ starting at 𝑛1. As the node found from inter(𝑛3, 𝑛3 − 𝑧̂) < 𝑏𝑢, 𝑛3 is considered valid. When checking 𝑛4, h is reset based on the previous node (𝑛3). To demonstrate the use of 𝛤, three objects, 𝛤 = {𝐵1 , 𝐵2 , 𝐵3 } are represented in the illustration where they are all walkable surfaces. The last node, 𝑛7, is shown in red as inter(𝑛7, 𝑛7 − 𝑧̂) > 𝑏𝑢, ending the graph generation. In the down step case for parameter 𝑏𝑑, 11(b) illustrates the intersection point for 𝑛5 falling outside the threshold. Finally a node 𝑛7 is invalid in 11(c) as the angle created from 𝑛6 and inter(𝑛7, 𝑛7 − 𝑧̂) > 𝑠𝑢. Furthermore, the relative positioning in 𝑍 of parent–child nodes can be seen by the height variation relative to the previous node.
Algorithm 2 implements this process in three-dimensions. The function getNodes(p) takes an input node 𝑝 and tests for its children in the directions contained in a given set of an even grid in the (𝑥, 𝑦) plane (i.e., Fig. 8), represented in the set 𝛷 = {−1, 0, 1} × {−1, 0, 1}. With these directions, a 45 deg angle is a limiting factor for a path connecting nodes. To decrease this angle, 𝛷 can incorporate additional locations, i.e., (−2,−1), which would correspond to node 𝑣3 connecting to 𝑣8 in Fig. 8. An alternative approach to expanding the neighboring nodes could be to iteratively expand while some condition remains true, such as no stepping, through an adaptive highway graph. Algorithm 1 and 2 describe the three-dimensional breadth-first process in general terms. On line 4, a point 𝑐 is composed of the 𝑥, 𝑦, 𝑧 values of 𝑝, offset in the directions of 𝛷.
The process for determining the return value of checkChild(p,c) begins with the description of Fig. 11 and is expanded to define edge weights and determine criteria for an edge connection in the following section.
4.2.2. Determining accessibility
As discussed in the previous section, each (𝑝,𝑐) is checked against a set of parameters and criteria. 𝑁𝐷+(𝑝) is constructed in Alg. 2, represented by the returned set 𝐶. One aspect of accessibility is a minimum width or region a valid path can traverse through. Algorithm 2 can be expanded to force accessible edges in path-finding to only pass through nodes that are connected to at least some user-defined number of neighbors. On line 12 of Alg. 2, rather than returning 𝐶, a check can be done to see if |𝐶| is greater than some minimum connectivity and if not, return an empty set. For example, if 𝛷 is the set of 8 neighboring directions, return 𝐶 ⟺ |𝐶| = 8.
For 𝑐 ∈ 𝐶, 𝑐 is determined to be valid by function checkChild(p,c), shown in Alg. 3. First, the distance to the closest 𝐵𝑖 ∈ 𝛤 is found by inter(𝑐,𝑐 − 𝑧̂). Given no labeled geometry in 𝛤, 𝐵𝑤 is the same set of objects as 𝛤 . For labeled geometry consisting of walkable and non-walkable surfaces, a set of walkable surfaces are defined as 𝐵𝑤 ⊂ R3. If the closest distance is to 𝐵𝑖 ∉ 𝐵𝑤 the node is not valid. The connection type 𝑡 between 𝑝 and 𝑐′ is calculated by getConnection(p, 𝑐′) and if valid, the step and slope parameters are verified. In implementation, the relational information of connection types between the parent and child nodes is stored during the graph construction, and the function returns the connection type (𝑡) and valid node (𝑐′).
The type of connection between two nodes is determined as one of five possible cases (Fig. 12): No Step 12(a), Step Over 12(b), Step Up 12(c), Step Down 12(d), Invalid 12(e). The reference to ''No Step'' is specifically regarding a geometry that protrudes off of the ground surface, which would require a foot, wheelchair, or other aid to lose contact with the ground during traversal. The ''No Step'' is referred to as a direct connection, which works in both flat and inclined ground as the height offset between nodes is also stored. Therefore, future queries of the relationship between nodes (such as defining edge cost) returning both a height offset and direct connection allow for a specific categorization such as an incline instead of a step. This method provides a similar but more detailed approach to determining node connections as the edge culling in [54] or the edge connectivity determination of a visibility graph.
Given the first connection type being false, a second ray, referred to in the figure as 𝑑2, is calculated and used to check for a connection. Depending on the height relationship between 𝑝 and 𝑐, the translated start position of the ray is determined by 𝑏𝑢 or 𝑏𝑑 as the directed edge is either stepping up or down. The special case is for when the two nodes are equal in height with an obstruction between them, requiring a step over the obstruction (Fig. 12(b)), which has a ray start point calculated the same as a step up.
Algorithm 4 demonstrates the process for calculating the rays and connection types. After the connection type and parameters of 𝐶 is determined, the algorithm returns to buildGraph(D,Q) on line 5. At that point, for the given 𝑝 passed to getNodes, the subgraph of 𝑝 can be constructed (𝐷[𝐸𝐷+ (𝑝)]).
4.3. Edge costs
The cost of traveling from one node to another is defined by the mapping of the weights from set 𝑊 as shown in Section 4.1.1. While the significance of the method and resulting graph is the straightforward application to a variety of human factors, a few weight categories previously discussed in the literature will be defined here. Especially at the urban scale, the inclusion of varying ground conditions to walkability analysis can better predict the human experience, with comfort, timing, and fatigue being realized.
Two cases exist for defining the cost of an edge:
1. Cost of mobility along the edge
2. Cost of moving to a node
In the first group, metrics related to mobility itself are included; 𝛹𝑐(𝑒𝑖𝑗) = Cross-slope, 𝛹𝑑(𝑒𝑖𝑗) = Metric Distance, 𝛹𝑠(𝑒𝑖𝑗) = Slope, 𝛹𝑒(𝑒𝑖𝑗) = Energy Expenditure, 𝛹𝑡(𝑒𝑖𝑗) = Step Type.
In the second group, attributes not able to be calculated by the path in isolation, but rather as values calculated cohesively with the built environment are considered. These highly localized parameters are easily missed in maximal edge connected graphs (e.g., [58]) and rely on the dense set of nodes throughout the environment. In this approach, an edge weight is defined by some properties or attributes of the end points (nodes) of the edge. For example, a directed edge with a start node located on concrete and end node located on sand is given a higher cost than the reverse as that node should be avoided. This weight mapping can include 𝛹𝑘(𝑒𝑖𝑗) = Type of Surface the end node is on, with further types; 𝛹𝑙(𝑒𝑖𝑗) = Light Intensity from Opposite Direction, 𝛹h(𝑒𝑖𝑗) = Light Difference Between Nodes, 𝛹𝑓(𝑒𝑖𝑗) = Probability of Falling, 𝛹𝑣(𝑒𝑖𝑗) = Percentage of View to Greenspace, 𝛹𝑤(𝑒𝑖𝑗) = Surrounding Width.
Some edge cost definitions such as the metric distance, 𝛹𝑑(𝑒𝑖𝑗) = |𝑛𝑖 −𝑛𝑗|, are straight forward while others 𝛹𝑙(𝑒𝑖𝑗) are based on the implemented simulation technique. The two most notable costs related to the focus of this paper are 𝛹𝑐 (𝑒𝑖𝑗) and 𝛹𝑒 (𝑒𝑖𝑗) and are therefore defined in full. 𝛹𝑐(𝑒𝑖𝑗) is the mapping of weights to edge costs in the graph relating to the cross slope and 𝛹𝑡(𝑒𝑖𝑗) is the mapping consisting of an identifier for the step type found in Alg. 4.
Calculating the cross-slope score 𝛹𝑐(𝑒𝑖𝑗) is done by considering the edges to 𝑢𝑖𝑗 (using the mapping defined in Section 4.1.1) that are orthogonal in the 𝑥𝑦 plane, denoted by 𝑥𝑦⊥. The maximum difference in height between the nodes of orthogonal edges is used as the score:
Definition 8. equation
The requirement for 𝛹𝑡(𝑒𝑖𝑘) = 𝑡𝙳𝙸𝚁𝙴𝙲𝚃 corresponds to the connection type defined in Alg. 4 line 3 as a direct connection with no step.
Additionally, a function defining energy expenditure3 of walking on slopes as shown in Fig. 4 is used for 𝑤𝑒.