💾 Archived View for thrig.me › blog › 2024 › 03 › 16 › grid-based-distance.gmi captured on 2024-07-09 at 01:19:06. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2024-03-21)
-=-=-=-=-=-=-
There are several ways to measure distance on a grid, often with several different names for the same algorithm:
The romanisation of Chebyshev may vary, as also happens with e.g. Rachmaninov.
Rachmaninoff - Prelude in C Sharp Minor Op.3 No.2
Anyways, which algorithm to use will depend on the context. Roguelikes may use round field-of-view (FOV) as it "looks best", see e.g. Brogue, though Dungeon Crawl Stone Soup switched at some point to a square FOV. Concerns here revolve around minor but maybe tactically significant points like whether diagonal moves "cost more" to make; that is, whether the game is more realistic or more like chess where a Bishop move does not involve the square root of two.
Some code to play around with:
Horizontal or vertical distances are not very interesting; the distance should be identical regardless the algorithm.
@...M
Diagonals vary, with Chebyshev two, taxicab four and Pythagorean (using lround(3)) a distance of three in the following illustration. Figuring this out can be important if monsters behave differently at different distances to some target. This may also depend on whether the game allows diagonal (eight way) motion or not, and may tie into the field-of-view system, if any.
@##
#.#
##M
For field-of-view (FOV) you will probably need to fiddle around with different algorithms. There are many, and the discussion gets into the weeds over things like whether diagonal moves can move you adjacent to a previously unseen monster, whether the algorithm is symmetric, etc. FOV may also involve drawing lines, so another distance measurement could be "how many steps it took Bresenham's line algorithm to get from point A to point B". And there are different algorithms for drawing lines…