Make It Tile User's Manual

Topology Traversal |

Traversing across topology elements is a common need when working with tiles. Make It Tile provides a path finder utilizing the A* algorithm, and vertex and face visitation utilities for processing recursively adjacent elements in a desired order.

This topic contains the following sections:

Path Finding

The PathFinder class provides a simple but flexible means to using the A* algorithm to find optimal paths between pairs of vertices or faces. In many cases, it is sufficient to find the shortest path according to an ordinary measure of distance. If this is so, then FindEuclideanPath will automate the details required by the core A* algorithm. Or if your surface is spherical and you want to use true spherical distance and not just straight-line approximations, you can use the similar FindSphericalEuclideanPath.

If you need a more nuanced cost measurement system than mere distance, you'll need to supply the core path finding function FindPath with the two delegates required by the A* algorithm. The first is the heuristic function which estimates the total cost between to elements (which are typically not adjacent to each other). The second is the actual cost function which returns the cost to traverse a single edge. In many cases, you can pre-compute the cost of each edge and store this data in an edge attribute collection, which makes the cost delegate a simple lookup. The implementation of the heuristic function will be more dependent upon the details of your particular case.

Note |
---|

Ideally, the heuristic should never overestimate the cost, or else the paths that the algorithm will find will not be guaranteed to be optimal. However, an overly optimistic heuristic which tends to radically underestimate the cost is likely to exhibit poor computational performance. To improve performance, you want to make the heuristic as pessimistic as possible while still finding acceptable paths. Preferably, your world is designed such that most actual optimal paths are not that much higher in cost than the theoretically most optimal paths. For an example of a design that goes against this recommendation, consider a world in which most tiles cost 100 to cross, but road tiles, which occur very infrequently, only cost 3. The theoretically optimal path between any two tiles will be the tile count of the path times 3, if every tile in between is a road. But since this rarely happens, most actual optimal paths are around the tile count times 100, a radically larger value. This will force the A* algorithm to search really hard before it is convinced that it has found the optimal path. |

Paths come in a few varieties. By default, implementations of IVertexEdgePath and IFaceEdgePath are produced by the path finder. These are essentially ordered collections of vertex edges and face edges, respectively. If it is more natural to work with a ordered collections of vertices or faces in a particular case instead, you can use AsVertexPath and AsFacePath to get instances of IVertexPath and IFacePath. These latter paths will have one more vertex or face than the number of edges in the paths from which they were derived (akin to the situations in which the fencepost error arises).

Note |
---|

The PathFinder class and the paths that it returns are designed to be reusable, so that you can reduce pressure on the garbage collector. An instance of the path finder will keep its internal storage around for use with future requests for a path, and the path classes can likewise be handed to the path finder for it to write the resulting path into a previous path's internal buffer. |

Find a Euclidean path between two faces

Topology topology = ...; // Create a topology. IFaceAttribute<Vector3> facePositions = ...; // Create face positions. var pathFinder = new PathFinder(); var path = pathFinder.FindEuclideanPath(topology.faces[10], topology.faces[43], facePositions); Debug.LogFormat("Starting from Face {0}", path.source.index); foreach (Topology.FaceEdge edge in path) { Debug.LogFormat("Through Edge {0}, to Face {1}", edge.index, edge.face.index); }

Find a custom-cost path between two faces

Topology topology = ...; // Create a topology. IFaceAttribute<Vector3> facePositions = ...; // Create face positions. IEdgeAttribute<float> travelCosts = ...; // Create travel costs between faces. float minTravelCost = ...; // Determine cheapest travel cost between any two adjacent faces. float maxAdjacentDistance = ...; // Determine the maximum distance between any two adjacent faces. var pathFinder = new PathFinder(); PathFinder.FaceCostHeuristicDelegate heuristic = (Topology.Face source, Topology.Face target, int pathLength) => { float distance = (facePositions[target] - facePositions[source]).magnitude; float minFaceCount = Mathf.Ceil(distance / maxAdjacentDistance); return minTravelCost * minFaceCount; }; PathFinder.FaceCostDelegate cost = (Topology.FaceEdge edge, int pathLength) => { return travelCosts[edge]; }; var path = pathFinder.FindPath(topology.faces[10], topology.faces[43], heuristic, cost); Debug.LogFormat("Starting from Face {0}", path.source.index); foreach (Topology.FaceEdge edge in path) { Debug.LogFormat("Through Edge {0}, to Face {1}", edge.index, edge.face.index); }

Topology Visitation

Topology visitation algorithms are useful when you need to process a single element at a time, starting at a root element, and recursively expanding outward through edges to neighboring elements. Make It Tile includes utilities for doing this according to various ordering schemes, such as breadth-first, depth-first, and even a uniformly random order, through the utility class TopologyVisitor.

The overall structure of visitation is to provide a delegate to the visitation algorithm that will be called for each visited element. That delegate will receive as a parameter a reference to a stateful visitor object, allowing access to the current element being visited, plus other details concerning the current state of visitation, such as how many edges have been traversed in reaching the current element from the root element.

Within that delegate, you are responsible for informing the visitor of the current element's neighboring elements, which it will then push into its queue to be visted at a later time. This gives you an opportunity to filter neighbors however is appropriate for your use case, as well as to expand the concept of adjacency, such as by using outer edges to treat diagonal connections as adjacent.

You can also perform other tasks with the visitor, such as terminating visitation immediately, or treating the current visit as though it never happened, allowing the current element to be visited again at a later time, possibly from a different direction. (Elements will only be visited exactly once, if you don't explicitly override this behavior either through ignoring a visit or telling the visitor to revisit an element even if it has already visited it before.)

If order does not matter beyond that dictated by the recursively expanding pattern of all visitation methods, you can use one of the VisitVertices or VisitFaces overloads. Because order is free to be arbitrary, these algorithms are more efficient than the rest described further down. In addition to the choice between visiting vertices or faces, there are a few other options available to you:

You can pass an optional state object, which will be passed in return to the visit delegate that you supply. This can be used for whatever state-tracking purpose you need.

If cummulative distance (whether that is spatial distance, movement cost, or any other scheme you might have) is relevant to your use case, you can use one of the distance-based overloads to keep track of distance from root for each element visited. (Note that you'll be responsible for informing the visitor of the distance between each neighbor you tell it to visit, since it does not know how to calculate these distances itself.)

If you want to not only know which vertex or face is being visited, but also the edge through which it was added to the queue, you can pass an edge as the root object, and a visit delegate with the corresponding signature for handling an edge visitor.

If you want to start at multiple roots simultaneously, pass an enumerable collection of root elements instead of just a single one. Combining this with a bread-first or random order (see below) can be a useful way to divide a topology into multiple regions.

If the order of visitation does matter, then you have a few different choices, which combine with the same selection of options that are listed above for arbitrary-order visitation.

Breadth First: VisitVerticesInBreadthFirstOrder and VisitFacesInBreadthFirstOrder will perform a breadth-first traversal of the topology, starting from the root element(s). The depth is based purely on the number of edges traversed since starting at the root, and so elements in the queue to visit which were reached through the fewest number of edges are prioritized. Cummulative distance can be tracked, but does not affect traversal order.

Depth First: VisitVerticesInDepthFirstOrder and VisitFacesInDepthFirstOrder will perform a depth-first traversal of the topology, starting from the root element(s). Just as with breadth-first traversal, depth is based on the number of edges traversed, except that elements in the queue to visit which were reached through the most number of edges, rather than the least, are prioritized.

Shortest Distance First: VisitVerticesInShortestDistanceFirstOrder and VisitFacesInShortestDistanceFirstOrder are much like the breadth-first traversal, except that it will use distance instead of number of traversed edges as the measure of depth. As such, you are required to use one of the cummulative distance tracking forms. Note also that only distances of types int, uint, float, and double are supported.

Longest Distance First: VisitVerticesInLongestDistanceFirstOrder and VisitFacesInLongestDistanceFirstOrder, like shortest distance, are the distance-based variant of the depth-first traversal, and similarly requires use of one of the cummulative distance tracking forms. It is also limited to the same numeric types.

Custom Order: VisitVerticesInOrder and VisitFacesInOrder can be used when neither shortest distance nor longest distance are an option, such as when working with an unsupported numeric type. To use these functions, you need to supply your own delegate that allows the priority queue to determine the priority between pairs of queue items.

Random Order: VisitVerticesInRandomOrder and VisitFacesInRandomOrder will pull elements from the queue at random, with no bias for or against closer elements, nor for or against elements inserted more recently into the queue. (In contrast, the arbitrary-order overloads first discussed, are likely to exhibit strong biases, depending on the underlying implementation.)

Performing a limited flood-fill of vertices from a single root vertex

Topology topology = ...; // Create a topology. IVertexAttribute<Color> vertexColors = ...; // Create vertex colors. var rootVertex = topology.vertices[17]; var originalColor = vertexColors[rootVertex]; var targetColor = new Color(0.1f, 0.4f, 0.8f, 1f); // Maximum edge count from root vertex to perform flood fill. // int maxDepth = 10; // Maximum number of vertices to re-color before terminating early. int maxVertexCount = 108; int recoloredVertexCount = 0; TopologyVisitor.VisitVerticesInBreadthFirstOrder(rootVertex, (VertexVisitor visitor) => { vertexColors[visitor.vertex] = targetColor; ++recoloredVertexCount; if (recoloredVertexCount >= maxVertexCount) { visitor.Break(); } if (visitor.depth < maxDepth) { foreach (var edge in visitor.vertex.edges) { if (vertexColors[edge] == originalColor) { visitor.VisitNeighbor(edge.vertex); } } } }); }

See Also