Skip to content

Grid Positions

Jump to bottom
Chris3606 edited this page Jan 23, 2019 · 15 revisions

The Coord class provides a convenient system for storing and dealing with grid positions.

Table of Contents

Code Examples

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 System.Collections.Generic;

Creating a Coord

Coord instances cannot be created using a constructor and instances cannot be modified -- instead, call the Get function:

// Gets coord representing position with x-value 2, and y-value 5
Coord c1 = Coord.Get(2, 5);
// They also provide overloaded ToString operators - prints (2, 5)
System.Console.WriteLine(c1);

Or, if you already have a Coord instance, you can use its Translate function to retrieve a new Coord with the given dx and dy difference:

Coord c1 = Coord.Get(2, 5);
c1 = c1.Translate(1, 2);

System.Console.WriteLine(c1); // Prints (3, 7)

Why the Get Function?

Why force the use of read-only coordinates and a Get function, compared to a constructor? Simply put, because in garbage-collected languages such as C#, memory allocation is expensive. In an algorithm where Coords are instantiated often, this can produce substantially slower code just due to allocation/deallocation overhead. While making Coord a C# struct would solve this problem, structs are non-nullable (value-types) and thus can produce odd interactions that can complicate code (NOTE: struct syntax and usability has come a long way, and as a result, Coord will be a struct in v2.0!)

Instead, to solve the problem of expensive memory allocations, the Coord class has a pre-allocated pool of Coord instances representing each position from (-3, -3) to (255, 255) (coordinates most commonly used in 2D games). If the coordinate requested is within this range, the Get function returns the pre-allocated instance (avoiding memory allocation). Otherwise, it returns a new instance. Thus, retrieving Coords in the specified range is much faster than it could otherwise be.

Operations on Coords

While a given Coord instance can't be modified, there are numerous operations provided that return new Coord instances.

They can be added to or subtracted from each other as if a Coord was a 2D Vector:

Coord c1 = Coord.Get(2, 5);
Coord c2 = Coord.Get(4, 1);

System.Console.WriteLine(c1 + c2); // Prints (6, 6)
System.Console.WriteLine(c2 - c1); // Prints (2, -4)

Or, Coords can have constants added to/subtracted from them:

Coord c1 = Coord.Get(2, 5);
c1 = c1 + 2; // Adds 2 to both the x and y values of c1
System.Console.WriteLine(c1); // Prints (4, 7)
c1 = c1 - 2; // Subtracts 2 from both the x and y values of c1
System.Console.WriteLine(c1); // Prints (2, 5)

Coords can also be scaled by constants:

Coord c1 = Coord.Get(2, 5);

c1 = c1 * 2; // Multiplies x and y value of c1 by 2
System.Console.WriteLine(c1); // Prints (4, 10)

// Divides x and y value of c1 by 3.  The resulting values are not integers, so results are rounded
// to the nearest integer
c1 = c1 / 3;
System.Console.WriteLine(c1); // Prints (1, 3)

// Coords can also be scaled by non-integer constants -- like before, results are rounded to the nearest integer.
c1 = c1 * 2.5;
System.Console.WriteLine(c1); // Prints (3, 8)
c1 = c1 / 2.5;
System.Console.WriteLine(c1); // Prints (1, 3)

Coords can also be compared by-value, and are considered equal if and only if the X and Y values are equal:

Coord c1 = Coord.Get(-5, -6);
Coord c2 = Coord.Get(-5, -6);
Coord c3 = Coord.Get(1, 2);

System.Console.WriteLine(c1 == c2); // Prints True
System.Console.WriteLine(c1 == c3); // Prints False

System.Console.WriteLine(c1.Equals(c2)); // Equivalent to c1 == c2; prints True

Hashing Support

Coord also provides an efficient hashing function via the GetHashCode function. The hashing function it uses produces an exceptionally low collision rate when we only consider Coords between (-3, -3) and (255, 255), and still a reasonably low collision rate outside that range. This allows Coords to function very efficiently as keys in dictionaries and other hash-based data structures:

Coord c1 = Coord.Get(1, 2);
// Coords can be used efficiently as keys for Dictionary and similar hashing-based data structures
// out of the box
Dictionary<Coord, int> myDictionaryOfCoords = new Dictionary<Coord, int>();
myDictionaryOfCoords[c1] = 1;
System.Console.WriteLine(myDictionaryOfCoords[c1]); // Prints 1

Translating Coords to 1D-Array Indices

When a 1D array or index representing 2D space is necessary (which is performed because it often results in better performance), Coord provides a convenient set of functions to translate Coords to 1D indices and back. The ToIndex function takes the width of the array, and produces the 1-dimensional array index representing that location. For convenience, a static function is also provided to allow retrieval of such an index without a Coord index:

int width2D = 5;
int height2D = 4;

Coord c1 = Coord.Get(1, 2);
// This array represents a 2D with (width, height) of (width2D, height2D)
bool[] myArray = new bool[width2D * height2D];

// Index in the 1D array above representing the location c1
int indexForCoord = c1.ToIndex(width2D);
// Another way to get the same index, just without using a Coord instance
int indexForCoord2 = Coord.ToIndex(1, 2, width2D);
System.Console.WriteLine(indexForCoord == indexForCoord2); // Prints true

myArray[indexForCoord] = true;
System.Console.WriteLine(myArray[indexForCoord]); // Prints true

Various functions are also provided to extract the Coord, or x and y values individually, from an index:

int WIDTH = 5;
int HEIGHT = 4;

// Get 1D index for (1, 2), assuming 2D width of WIDTH
int indexForPosition = Coord.ToIndex(1, 2, WIDTH);

// Get Coord for index, assuming it was created using width WIDTH
Coord c1 = Coord.ToCoord(indexForPosition, WIDTH);
System.Console.WriteLine(c1); // Prints (1, 2)

// Get only the x-value of Coord represented by the index
int xValue = Coord.ToXValue(indexForPosition, WIDTH);
// Get only the y-value of Coord represented by the index
int yValue = Coord.ToYValue(indexForPosition, WIDTH);
System.Console.WriteLine(yValue); // Prints 2

Utility

The Coord class also offers a number of utility functions to assist with common point-related functions.

Bearing of a Line

The BearingOfLine function can retrieve the heading in degrees of a straight line drawn between the two points specified. 0 degrees is considered to be a line consistent with Direction.UP -- as such, the exact output of this function is dependent on the setting of the Direction.YIncreasesUpwards flag. See Direction documentation for details.

Coord start = Coord.Get(0, 0);
Coord end = Coord.Get(1, 1);

// Bearing is 135 degrees
System.Console.WriteLine("Bearing of line is: " + Coord.BearingOfLine(start, end));

// We can also specify the points using integer x and y values, rather than 
// Coords.  This is another way to specify the same line as above.
System.Console.WriteLine("Bearing of line is: " + Coord.BearingOfLine(0, 0, 1, 1));

// In addition , we can specify a delta-x and delta-y value across the line, rather
// than the points defining the line themselves.  We can do this using either a single
// Coord (a vector containing the x and y values), or a separate dx and dy value.
System.Console.WriteLine("Bearing of line is: " + Coord.BearingOfLine(end - start));
// Specifies a dx of 1 and a dy of 1
System.Console.WriteLine("Bearing of line is: " + Coord.BearingOfLine(1, 1));

// We switch UP to having a positive DeltaY value.  Thus, the bearing of the same
// line this time 45 degrees
Direction.YIncreasesUpward = true;
System.Console.WriteLine("Bearing of line is: " + Coord.BearingOfLine(start, end));

Calculating Midpoint

The Midpoint function implements the midpoint calculation, rounding the x and y values of the resulting point to the nearest integer:

Coord c1 = Coord.Get(1, 2);
Coord c2 = Coord.Get(4, 5);

Coord midpoint = Coord.Midpoint(c1, c2);
System.Console.WriteLine(midpoint); // Prints (3, 4)

// We may also specify the points using integer values, rather than Coords
midpoint = Coord.Midpoint(1, 2, 4, 5); 
System.Console.WriteLine(midpoint); // Prints (3, 4)

Comparing Euclidean Distances Quickly

The EuclideanDistanceMagnitude function is useful when comparing Euclidean distances. Given two positions, instead of producing standard Euclidean distance, i.e. sqrt((x2 - x1)^2 + (y2 - y1)^2), it instead produces simply (x2 - x1)^2 + (y2 - y1)^2. This is exactly the Euclidean distance formula, but without the square root. The square root is relatively time-expensive to compute, and does not change magnitude differential. Thus, when one is simply comparing two distances (i.e. is the distance between points P1 and P2 greater than the distance between P3 and P4?), the square root is unnecessary, and as such using this function will produce the same result but in less time:

Coord c1 = Coord.Get(1, 2);
Coord c2 = Coord.Get(6, 2);

// Distance between c3 and c4 is greater than the distance between c1 and c2
Coord c3 = Coord.Get(5, 7);
Coord c4 = Coord.Get(15, 7);

// See Distance documentation for details on usage -- simply produces the actual
// Euclidean distance between the specified points
double euclideanDist1 = Distance.EUCLIDEAN.Calculate(c1, c2);
double euclideanDist2 = Distance.EUCLIDEAN.Calculate(c3, c4);

// Calculate result from EuclideanDistanceMagnitude
double euclideanDistMag1 = Coord.EuclideanDistanceMagnitude(c1, c2);
double euclideanDistMag2 = Coord.EuclideanDistanceMagnitude(c3, c4);

// The values calculated are different...
System.Console.WriteLine("Distance: " + euclideanDist1 + ", " + euclideanDist2);
System.Console.WriteLine("DistanceMagnitude: " + euclideanDistMag1 + ", " + euclideanDistMag2);

bool distGreater = euclideanDist2 > euclideanDist1;
bool distMagGreater = euclideanDistMag2 > euclideanDistMag1;

// However, the relative magnitude is the same -- euclideanDistMag2 is still greater
// than euclideanDistMag1, since euclideanDist2 > euclideanDist1.
System.Console.WriteLine("Dist c2 > Dist c1: " + distGreater);
System.Console.WriteLine("Dist Mag c2 > Dist Mag c1: " + distMagGreater);

As before with the BearingOfLine function, we can also pass the points as a pair of ints dx and dy, which specify the distance between the two points, a Coord that specifies the same, or four integers representing the x and y values of each point.

Table of Contents

Clone this wiki locally