I’ve just published the first version of GridMath nuget package. It is a lightweight library for creating and manipulating geometrical shapes on two-dimensional grids. The code is available under MIT license on my github repo.
Motivation for GridMath project
I have recently started working on a project exploring procedural content generation. So far, the tile-based maps were one of the main content types I focused on.
The project makes heavy use of geometry. There are a lot of complex operations in this domain that standard libraries don’t cover. Fortunately, there is NetTopologySuite – a C# port of fantastic JTS library, which I used when working for Jeppesen.
NetTopologySuite gives me a comprehensive support for real-space, 2d geometry. Tile-based maps and objects, however, are best represented on grids.
Grids are essentially 2-dimensional, finite and discrete spaces of integer values. We see them often as orthogonal meshes of square tiles, but they can also be represented as hexagons and other shapes.
A naive (and my first) approach to grid math was to use real-space geometry. I just rounded the floating points to integers. This tends to work just fine when dealing with large integer values, where the results of rounding are insignificant. Grids, however, tend to be no larger than a hundred units or so. See, it’s like pixel graphics vs regular raster graphics. They have the same underlying mechanism, but require different approach in content creation.
Since I found no dedicated-library for integer-space geometry and math, I decided to roll my own.
Mapping of real-space to grid-space
GridMath supports mapping values from real-space to grid-space. I chose to map them such that discrete value N on grid corresponds to half-open set: R[N,N+1). I implement this mapping by getting Floor of the real value. Note that a simple cast of double to int only truncates floating part. This gives correct results for positive numbers but is wrong for negatives.
For example, values 0, 0.1, 0.9 etc. map to grid ordinate 0. But values -0.1, -0.9 map to grid ordinate of -1.
GridCoordinate and GridInterval
The two main building blocks of GridMath are GridCoordinates and GridIntervals. GridCoordinate is a simple pair of integers, but GridInterval provides a host of methods. It’s properties can represent it as:
- Min and Max values – most intuitive representation
- Exclusive Max alternative – less intuitive but more useful in computations
- Min and Lenght – quite intuitive and often useful.
- Center point finding
- Setting position accoriding to anchor point
- Spatial tests
- Alignment against other GridIntervals
This functionality is basically the engine for operations on more complex shapes.
Grid boudning boxes are essentially axis-aligned bounding boxes. They are modelled with two grid intervals and provide similar functionality.
Roadmap for GridMath
- Measuring Manhattan and Chebyshev distances
- Subdivisions into binary trees and quad trees
- Path finding
I’ll try to cook up some example project using the library.