Measuring Distance
The Distance class provides ways to measure the distance between two points, using various distance calculation algorithms.
Like many grid-related classes, the Distance class cannot be instantiated, but instead provides pre-existing static class instances that represent the three possible methods of calculating distance -- Manhattan, Chebyshev, and Euclidean.
- Table of Contents
- Code Examples
- Distance Calculations
- Calculating Distance
- Implicit Conversions
- Explicit Conversions
Code examples in this section show only code in the Main function. The code provided assumes that the following "using" statements are at the top of the code file:
using GoRogue;
using GoRogue.MapGeneration;
using GoRogue.MapGeneration.Generators;
using GoRogue.MapViews;
using GoRogue.Pathing;
using System.Collections.Generic;
using System.Linq;There are generally 3 ways we can measure the distance between two points. Each method defines space in a different way, affecting not only the distance between two specific points, but as a result, the shape of a "radius" around any given point -- eg. which tiles are within x units of a given position.
The Manhattan distance calculation measures grid distance in terms of only horizontal and vertical movement. The most direct path between two points is the shortest one that moves only in horizontal or vertical steps.
In the image below, the red square represents an arbitrary starting location. The blue squares indicate locations within 1 distance unit of the starting location, according to Manhattan distance. Similarly, the grey squares indicate those locations within 2 units, and the black squares represent those within 3:
The radius, in turn, ends up forming in the shape of a diamond. Manhattan distance is generally a useful distance measurement in games that only allow 4-way movement, since the distance measurement by definition aligns with possible movement directions.
The Chebyshev distance calculation, commonly known as the "maximum metric" in mathematics, measures distance between two points as the maximum difference over any of their axis values. In a 2D grid, for instance, if we have two points (x1, y1), and (x2, y2), the Chebyshev distance between is the max(y2 - y1, x2 - x1).
On the above grid, the difference in the x-value of the two red points is 2-0=2, and the difference in the y-values is 3-0=3. The maximum of 2 and 3 is 3, and thus the Chebyshev distance between the two points is 3 units.
Practically, on a grid, Chebyshev distance represents distance measured as if the shortest path between two points can take steps in any of the 8 directions at equal cost. In the image below, the red square represents an arbitrary starting location. The blue squares indicate locations within 1 distance unit of the starting location, according to Chebyshev distance. Similarly, the grey squares indicate those locations within 2 units, and the black squares represent those within 3:
The resulting shape of the radius formed is a square. Thus, by definition, Chebyshev distance is generally a useful distance measurement in games that allow unrestricted 8-way movement, where moving diagonally costs no more than moving in a cardinal direction.
The Euclidean distance measurement is the most common definition of distance according a mathematical (Euclidean) coordinate plane. Distance between two points is defined as the length of a line segment connecting them. In 2D, given 2 points (x1, y1) and (x2, y2), Euclidean distance is sqrt((x2-x1)^2 + (y2-y1)^2).
In the image below, the red square represents an arbitrary starting location. The blue squares indicate locations within 1 distance unit of the starting location, according to Euclidean distance. Similarly, the grey squares indicate those locations within 2 units, and the black squares represent those within 3:
Note that the diagonal neighbors of the starting location are considered to be approximately 1.41 units away from the starting location, while cardinal neighbors are 1 unit away. Thus, the radius shape formed by Euclidean distance is a circle (or in the case of a integer-grid, a close approximation). While Euclidean distance does not generally match a particular movement scheme on an integer-grid, it can be useful in any case where straight-line distance is desired.
GoRogue representations of these distance calculation methods are straightforward. The Distance.MANHATTAN instance represents the Manhattan distance calculation, Distance.CHEBYSHEV represents the Chebyshev distance calculation, and Distance.EUCLIDEAN represents the Euclidean distance calculation.
Using the existing Distance instances, one can calculate the distance between two points given either 2D or 2D points, or the change in x, and y (and z in 3D) values between two points:
Coord start = Coord.Get(0, 0);
Coord end = Coord.Get(2, 3);
// We get the distance by using 2 Coords, and 4 integer values (x1, y1, x2, y2)
double dist = Distance.MANHATTAN.Calculate(start, end);
double dist2 = Distance.MANHATTAN.Calculate(0, 0, 2, 3);
// We can also use 3d points (x1, y1, z1, x2, y2, z2)
double dist3 = Distance.CHEBYSHEV.Calculate(0, 0, 0, 2, 3, 0);
// We can also calculate distance using delta-x and delta y values
double dist4 = Distance.EUCLIDEAN.Calculate(2, 3);
// Or delta-x, delta-y, and delta-z values in 3D
double dist5 = Distance.EUCLIDEAN.Calculate(2, 3, 0);Because of the relationship between the Distance, Radius, and AdjacencyRule classes, a number of implicit conversions involving the Distance class are defined
Because specifying a Distance calculation method clearly implies a single associated AdjacencyRule, an implicit conversion exists from Distance to AdjacencyRule instances. Distance instances convert as follows:
- Distance.MANHATTAN -> AdjacencyRule.CARDINALS
- Distance.CHEBYSHEV -> AdjacencyRule.EIGHT_WAY
- Distance.EUCLIDEAN -> AdjacencyRule.EIGHT_WAY
The following code example demonstrates that Distance instances are implicitly converted to AdjacencyRule instances:
// Create a map that consists of one single rectangle -- see
// Map Generation documentation for details.
ArrayMap<bool> testMap = new ArrayMap<bool>(10, 10);
RectangleMapGenerator.Generate(testMap);
// Finds all distinct (un-connected) areas of a map.
// See Map Generation documentation for details, however in short
// as its second parameter, this function takes an AdjacencyRule
// that specifies which locations are considered adjacent.
// Note that in this case a Distance instance is passed, but no error
// occurs -- the conversion is done automatically.
List<MapArea> areas = MapAreaFinder.MapAreasFor(testMap, Distance.EUCLIDEAN).ToList();Furthermore, because specifying a radius shape, by definition, implies the distance calculation that creates that shape, an implicit conversion exists from Radius to Distance. Radius instances convert as follows:
- Radius.CIRCLE or Radius.SPHERE -> Distance.EUCLIDEAN
- Radius.SQUARE or Radius.CUBE -> Distance.CHEBYSHEV
- Radius.DIAMOND or Radius.OCTAHEDRON -> Distance.MANHATTAN
The following code example demonstrates that Radius instances are implicitly converted to Distance instances:
// Create a map that consists of one single rectangle -- see
// Map Generation documentation for details.
ArrayMap<bool> testMap = new ArrayMap<bool>(10, 10);
RectangleMapGenerator.Generate(testMap);
// Create an AStar-based pathfinder -- see Pathfinding documentation for details,
// however in short, as the second parameter to its constructor it takes a Distance
// instance specifying how to measure distance. Note that in this case a Radius instance
// is passed, but no error occurs -- the conversion is done automatically.
AStar pather = new AStar(testMap, Radius.SQUARE);
var path = pather.ShortestPath(0, 0, 1, 2);As made evident by the implicit Radius to Distance conversion in the Implicit Conversions section, specifying a radius shape implicitly specifies the distance calculation that creates that shape. Because GoRogue Radius instances exist for both 2D and 3D shapes, specifying a Distance instance does not directly imply a radius shape, as there is no way to determine whether the 2D or equivalent 3D shape should be returned. However, since most commonly the 2D shape is desired, an explicit conversion that defaults to the 2D shape does exist. The conversion values are exactly like ones for Radius to Distance implicit conversion. Distance instances convert as follows:
- Distance.EUCLIDEAN -> Radius.CIRCLE
- Distance.CHEBYSHEV -> Radius.SQUARE
- Distance.MANHATTAN -> Radius.DIAMOND
The following code example demonstrates that Distance instances are explicitly (but not implicitly) convertible to Radius instances:
// We manually cast, and retrieve Radius.DIAMOND
Radius r = (Radius)Distance.MANHATTAN;
// Distance instances are NOT implicitly convertible -- this line of code,
// if uncommented, will generate an error:
// Radius r = Distance.MANHATTAN;