In reply to a comment on my recent blog entry, Archduke Piccolo made mention of the Euclidean, Chebyshev, and Manhattan methods of measuring distances on a squared grid.
I knew a little (not much at all, in fact!) about the three different methods, but spurred on by his comment, I found out more ... and decided that what I found out might be of interest to other wargamers who use square gridded tabletops.
Euclidean Distance
Euclidean distance (or Euclidean metric) is the 'ordinary' straight-line distance between the centres of two grid squares as one would measure using a simple ruler.
It is named after Euclid of Alexandria, the Greek mathematician who is regarded as being the father of geometry.
Chebyshev Distance
Chebyshev distance (or maximum value distance) is a metric defined on a vector space where the distance between two vectors is the greatest of their differences along any coordinate dimension. For example, in Chebyshev distance all eight adjacent grid squares from a given grid square can be reached by one unit.
It is named after Pafnuty Lvovich Chebyshev, a Russian mathematician.
Manhattan Distance
Manhattan (or Taxicab) distance is the distance between two grid squares in a square grid using a strictly horizontal and/or vertical path as opposed to the diagonal or 'as the crow flies' one. The Manhattan distance is the simple sum of the number of horizontal and vertical grid squares used.
It takes its names from the shortest distance a taxicab can take to go from one place to another in a city built on a squared gridded pattern, such as Manhattan.
Note: According to Wikipedia:
I knew a little (not much at all, in fact!) about the three different methods, but spurred on by his comment, I found out more ... and decided that what I found out might be of interest to other wargamers who use square gridded tabletops.
Euclidean Distance
Euclidean distance (or Euclidean metric) is the 'ordinary' straight-line distance between the centres of two grid squares as one would measure using a simple ruler.
It is named after Euclid of Alexandria, the Greek mathematician who is regarded as being the father of geometry.
Chebyshev Distance
Chebyshev distance (or maximum value distance) is a metric defined on a vector space where the distance between two vectors is the greatest of their differences along any coordinate dimension. For example, in Chebyshev distance all eight adjacent grid squares from a given grid square can be reached by one unit.
It is named after Pafnuty Lvovich Chebyshev, a Russian mathematician.
Manhattan Distance
Manhattan (or Taxicab) distance is the distance between two grid squares in a square grid using a strictly horizontal and/or vertical path as opposed to the diagonal or 'as the crow flies' one. The Manhattan distance is the simple sum of the number of horizontal and vertical grid squares used.
It takes its names from the shortest distance a taxicab can take to go from one place to another in a city built on a squared gridded pattern, such as Manhattan.
Note: According to Wikipedia:
In mathematics, a metric or distance function is a function that defines a distance between each pair of elements of a set. A set with a metric is called a metric space.Well I hope that cleared that up for you!
Bob,
ReplyDeleteIn the definition of Chebyshev distance should it not read 'the distance between two POINTS is the greatest of their differences along any coordinate dimension.'
Fortunately, the diagram is much easier to understand!
Some new terminology to make playing with toy soldiers on a grid with sound more profound: 'I propose to simulate military operations using Chebyshev distance on a vector space and cubic random number generators.'
I might have been given a better mark for my educational game - merely a rehash of my then Napoleonic rules (which I now know would have been totally unsuitable for the 'classroom situation'; luckily my tutor didn't realise this!) to save me the trouble of actually creating something - for my PGCE course had I known this!
Regards,
Arthur
Arthur Harman (Arthur),
DeleteI think it depends on the definition you look at. I checked several, and used what I thought was the easiest to understand. Using the work 'point' seems to clarify the definition that I chose to use,
Adding a bit of profound-sounding, mathematic terminology can certainly give the illusion of gravitas to wargame design! I am put in mind of a menu that described a particular dessert as being sun-dried plumbs served with a creme anglais. Translated into non-pseud English it was - of course - prunes and custard.
All the best,
Bob
In general, there are many mathemtical functions that would qualify as a "distance metric". If you really want to go into the mathematics, here's the defintion of a distance:
ReplyDelete- distance from point a to itself equals 0
- distance from a to b equals the distance from b to a (symmetry)
- distance from a to b, added to distance from b to c, must be greater or equal than the distance from a to c directly. In other words, you cannot suddenly have a shorter distance by first going to an intermediate destination before going to your final destination.
W.r.t. grids, here are some more ways to count distances: http://wargaming-mechanics.blogspot.be/2017/06/square-grids.html
Although what I wrote above is of course for continuous space. A grid used for gaming is actually a graph (imagine all cells being nodes, and adjacent cells being connected by edges in the graph). Graph metrics compute distances by travelling from node to node across edges. See e.g. https://en.wikipedia.org/wiki/Distance_(graph_theory) But it would go too far to discuss graph theory on a wargaming forum ;-)
DeleteBut anyway, bear in mind that that are subtle differences between defining a distance (e.g. the distance between two cells in a grid), and how to compute or count that distance (going form cell to cell and accumulate a number that will result in the distance). In a wargame, one is foremost interested in the latter, e.g. a simple method that allows a gamer to quickly compute a distance between two cells, by moving a unit from cell to cell, and accumulating a number by doing so, which results in the total movement point cost.
Phil Dutré,
DeleteThanks for the definition of distance and the link. Very interesting and something that I intend to read more about.
All the best,
Bob
To illustrate what I said in my previosu reply: you could imagine positioning units on a grid, but using Euclidean distance cost (the straight-line distance from centre-cell to centre-cell). However, there's no simple way to measure that distance except by using a ruler. It's hard to come up with a (simple) method that accumulates a number going from cell to cell, and that will result in the Euclidean distance between starting cell and target cell. In the ideal wargaming rules, that's perhaps what we want, but it would result in complex movement mechanic.
DeleteE.g. we might say that moving orthogonally costs 1 point, and moving diagonally costs 1.5 point. That's an approximation for a Euclidean distance. But you could also say that when a unit wants to make a Knigh't's move (2 squares forward, one square left), it counts as 2.25 movement points (approx for square root of 5). That would give you a procedure even closer to measuring Euclidean distances on a grid, but it also means you have to group movements over different cells together. And why stop there? You could as well define that moving 2 squares forward and 3 squares left will cost you 3.5 movement points (approx for square root of 13). Etc. At some point you might as well revert to using a ruler :-)
Phil Dutré,
DeleteAnother thank you for your comments and contribution. I have yet to master all the mathematics involved, but it does no harm for me to exercise my brain trying to get to grips with it.
All the best,
Bob
Bob.
DeleteSorry if I got carried away here, but as a computer science professor, thinking about this sort of stuff is 2nd nature to me ;-)
Phil Dutré,
DeletePlease feel free to get carried away! It is always interesting to have knowledgeable and expert input into a discussion. I may be retired and closer to 70 years of age than I am to 60, but the day I stop learning something new is the day when I will begin to despair!
All the best,
Bob
I'll 'fess up and state that I ran across the Chebyshev/Manhattan/Euclidean nomenclature only recently, from a comment on one of my postings by Phil Dutre. Turns out he had been looking into the topic of square grids himself. Although I was familiar with the notions, I never knew that anyone had labelled them.
ReplyDeleteThe Chebyshev distance is well known to chess players, who find that a king standing at the a1-square on a chessboard can reach a8, h1 or h8 in precisely the same time: 7 moves. This applies to the king only. The bishop, rook and queen moves restricted only by the edge of the board, the notion of 'distance' doesn't really apply to them. It is most curious, though, that for a knight, chessboard distances are Euclidean. A knight standing at a1 takes 5 moves to reach a8, but 6 to reach h8.
Archduke Piccolo,
DeleteIt would appear from Phil Dutré's comments that he is a much greater expert in this area than we appear to be ... and I am finding this topic quiite intellectually stimulating. It's making me do some serious thinking, which is no bad thing!
All the best,
Bob
AP, If you are going to fess up,at least get the attribution correct. I believe it was from moi!
DeleteBob,
DeleteThank you for the nice words, but I only wanted to point out there 's a ton of mathematical theory you could throw at this problem.
In a gaming context, I think it's most important to have an elegant "counting mechanic" as I mentioned above. Going from cell to cell, count a numberadd up to a running total (perhaps some connections count as 1.5, or as 2, or perhaps something else), that results in a tallied number which we call the movement cost.
That's also why the Manhattan distance is actually very elegant: the definition of the distance function, and simply adding 1 to the total when moving from cell to cell (no diagonals!) are unified. The definition implies the mechanic, and vice versa.
Jonathan is right - I don't think I mentioned the Chebyshev measure in any of our discussions before.
DeleteQuite right: my apologies to Jonathan and Phil both. I think I should choose a time other than past midnight to comment on stuff... Fact is, though, both have given me food for thought, and induced me to research the topic. I have used, by the way the 'approximate Euclidean' approach to square grids and have always imagined such an approach should work.
DeleteMost of my thoughts on that topic have appeared here and there in my blogspot, so I won't dilate upon them here. I guess the next thing is to playtest the ideas.
What better than a slight tweak on a Portable Wargame?
Archduke Piccolo,
DeleteDon't worry about what time you make your comments; its always past midnight somewhere in the world!
As to tweaking the PORTABLE WARGAME with the 'approximate Euclidean' approach ... well that sounds like an excellent idea! I look forward to reading your results.
All the best,
Bob
Jonathan Freitag,
DeleteIn the flurry of comments I missed yours!
It is interesting to see that this has been a topic that has got so many of us thinking.
All the best,
Bob
Ok, one more thought (and then I'll stop :-))
ReplyDeleteYou could also look at counting distances on a grid in a top-down manner rather than bottom-up.
Let's say you have a unit on a grid cell with a movement allowance of 7. What grid cells do you want that unit being able to reach with it's movement allowance? You could colour these cells in a diagram (e.g. all cells whose midpoint are within a circle with radius 7).
The hard part: now come up with a counting procedure that would allow that unit to reach exactly those cells, and no further cell.
And the hardest part: the counting routine should not only be valid for 7, but also for 5, 6, 8, 9 etc ... depending on the movement points defined in your game.
(just a different way of thinking about it)
Phil Dutré,
DeleteI've been playing around with your method and a piece of graph paper this evening, and I have realised that somehow (probably by sheer luck) that the movement distances I have used in my PW rules achieve what I wanted.
All the best,
Bob
Here's something I did along these lines earlier this year.
Deletehttps://archdukepiccolo.blogspot.co.nz/2017/02/measuring-shooting-ranges-on-gridded.html
If a wargame is to be playable, then I think you must either go with measurement by ruler - preferably marked off and colour-coded for the different arms so one doesn't have to squint at fractions of an inch or centimetres - or go with Manhatten or Chebyshev movement on a grid. Anything else seems likely to be too difficult/slow, and liable to cause mistakes in the heat of the moment.
ReplyDeleteArthur Harman,
DeleteI totally agree. If you want players to get on with taking part in a wargame it is vital to keep the mechanisms as simple and user-friendly as possible.
All the best,
Bob
i'm coming to the same conclusion, though I think the Euclidean ought to be given a fair suck of the sav. In principle the added complication isn't huge, but only a practical test will tell us for sure.
DeleteArchduke Piccolo,
DeleteThere is no reason not to give this idea a try. Even if if doesn't work as well as you hope, you will have learned something.
All the best,
Bob
I wrote a little post about including "Zebra" and "Camel" moves on a grid: https://wargaming-mechanics.blogspot.be/2018/01/square-grids-2.html
ReplyDeletePhil Dutré,
DeleteAt interesting article that I was able to understand in spite of the heavy cold/'flu I am currently suffering from.
I think that having a counting procedure make more sense than a movement procedure.
All the best,
Bob