In earlier articles, we learned how to write code like:
This time we are going to learn how to write code like Christian Bale!
For this, we have to take off the GOG shelf an old yet captivating game called: Sid Meier's Civilization III Complete.
Civilization III is a turn-based strategy game for PC:
- where you build cities,
- those cities produce inudstrial output (shields), and money (gold coin), but...
- Everybody's up to something, hiding something.
- Everbody's got an angle
- and everybody is guilty.
Yeah yeah, the fictional character Perry Mason is played by Matthew Rhys.
Matthew Rhys is NOT Christian Bale, but I pinky promise you that at the end of this post:
You'll learn how to do Christian Bale Oriented Programming.
But before that, we have to make a bit of a detour.
So back to Civilization III: What is happening with all that money?
Distance
Civilization III's developers decided that corruption is going to be a resource sink.
Corruption is a mechanism, so that building more cities offers diminishing returns.
The design goal is to stop the players from snowballing.
There are two kinds of corruption:
- Distance corruption: Cities on the outskirts of your empire are less productive.
- Rank corruption: The more cities you have the worse it gets. For example, your 10th city will be more corrupt than your 4th city.
Corruption is detailed in-depth on this beautiful page.
We are going to deal with Distance Corruption.
The beating heart of all that nonsense is "how to measure distance between two cities"?
The guide states that it is a simple oneliner:
d = max(x,y) + min(x,y)/2
Someone might say it isn't Engineering Magic like for example a React App, or SpringBoot backend, or a Rust CLI tool, and it is not worth a code review.
But... just to be safe...
Let's take a closer look how this corruption thing works.
Deposition
In this section I will lay out statements (Exhibitions).
The goal of doing this is that we won't get any suprises during trial.
This will be really long and boring, sorry, but it serves a higher purpose:
In the later Trial section of this article (which comes after this Deposition), we don't want to misrepresent this case!
We want to arrive at the true, just and honest truth.
Exhibit 1 - Simple 2D Manhattan Distance
There's a thing called Von Neumann Neighborhood or 4-Neighborhood.
It simply means that in a square grid like graph, the following 4 purple nodes are the neighbors of the hollow one:
We can ask a question based on this:
There are a lot of routes, but each of them is a bit different. Quantifiably different:
But there are multiple 8 steps routes too:
You probably know this, but maybe not by the name "manhattan distance":
Exhibit 2 - Simple 2D Chebyshev Distance
There's a thing called Moore Neighborhood or 8-Neighborhood.
We can ask a question based on this:
There are a lot of routes, but each of them is a bit different. Quantifiably different:
This time, and for this pair of points, there's a unique route:
You probably know this, but maybe not with the name "Chebyshev distance":
Exhibit 3 - Minkowski Distance
The Manhattan and Chebyshev distances are well-known from funny 2D problems.
But, let's play a bit with Manhattan distance:
What's the purpose of that p in the Minkowski distance? It is a slider:
What is in the middle? Can you guess?
Yes it is Euclidean distance:
Euclidean distance:
- fits our normal every day assumptions about distance,
- but it does not align with our grid,
- aka it results in non-integer distances.
Doing Euclidean would be illegal.
Exhibit 4 - The absolute lowest minimum bar to remain technically law abiding
The distance used for corruption technically should not abide measure theory or any other mathematical notions.
This "distance" should abide notions of the players' expectations, like:
1. Any city should be 0 distance from itself.
2. Should work "bird's eye distance" / "air flight distance" like.
3. It must "just work" like you know... how the world works, omg :D
And that's the Jira ticket essentially.
Exhibit 5 - Cardinal and Intercardinal Steps
First, let's think of a compass:
The key insight is the Cardinal vs. Intercardinal partitioning.
What is the shortest path between two points using 8-neighborhood?
Of course, there is no THE shortest path. There are MANY equally short paths.
But, if you look at it carefully, each route is just a permutation of the same number of Cardinal / Intercardinal steps.
Can we somehow... compute Cardinal steps and Intercardinal steps? Maybe we could do something with them later.
Let's look at two entirely different cases, side-by-side, and try coming up with something:
The Cardinal and Intercardinal steps are computable separately.
Exhibit 5 - Halfway Happy Distance
With these new Cardinal and Intercardinal steps, I want to ask two questions from you.
I'd like to ask you, to please dumb yourself down to my level. These questions will be... quite... well, dumb.
First question:
Second question:
The answer is of course pretty dumb too:
These two distances just assign different costs to Cardinal / Intercardinal steps.
These are special types of Chamfer AIRQUOTE Distances AIRQUOTE.
Airquotes are necessary because you cannot assign arbitrary weights, because our assumption about shortest paths would completely break down.
Aka: This is a DIRTY LOOPHOLE WHICH JUST BUGS OUT TO WORK IN CERTAIN CASES.
Now comes the One Billion Dollar Question. What is between them?
Before answering the question:
- Remember that you are NOT doing math!
- You are just doing lawyering.
- If you are still stuck on primitive notions like "Good vs. Evil", please listen to the Curious Tale of Slippin' Jimmy.
The answer is 1.5!
What's wrong? What's the matter?
Ahhh, right! You are worried, dear Reader, because it is not going to be an int?! Somebody didn't sleep through ethics did they...
We'll just floor it, baby. Legally speaking it will be an int.
And morally speaking... is there even a big difference between, say, 3 and 4 anyways?
Let me present you the Halfway Happy Distance:
It isn't Manhattan.
It isn't Chebyshev.
It is something that's kind of inbetween, it's like halfway happy.
Exhibit 6 - d
The code which started all of this was:
d = max(x,y) + min(x,y)/2
But what is d? Let's see:
That d is Halfway Happy Distance.
Exhibit 7 - The rabbit hole finally opens up
Below is d in all of its glory, so let's do a little playful code review!
Just look at it for 5-6 seconds:
1 | d = max(x,y) + min(x,y)/2
2 | where
3 | max(x,y) denotes the maximum between x and y,
4 | min(x,y) denotes the minimum between x and y,
5 | x is the distance in the NW/SE direction,
6 | y is the distance in the NE/SW direction,
7 | and the integer division is rounded down.
Yes indeed, Line 5 and 6 seem... odd.
Perhaps a bit... too weirdly odd:
Why would we do it that way? It does not make any sense!
Oh wait...
All this time, we've been looking at the world the wrong way:
But... we can adjust of course:
But... wait... it does not... it does not work!!!!
THAT RIGHT SIDE ISN'T HOW A GRID SHOULD BE NUMBERED!!!
Omg:
- if distance is calculated based on NW-SE / NE-SW axes,
- then why not number the grid cell along those axes?
Why would someone mess up a simple planar problem?!?!?!?!
Because technically... it isn't a planar problem.
Exhibit 8 - Mainlining the secret truth to the Universe
As Inception's city bending scene demonstrates, a Civ III game can be thought of as a cylinder.
But... the game is more general than that:
Much more general:
Earth? How about Earth Torus?
The coordinates are not messed up. If we take a closer look, there's order and pattern in the coordinates:
Yes! They are just regular x, y coordinates following the typical "x grows rightwards, y grows downwards" fashion from good old computer graphics CS 101:
But... there's a slight issue with wrapping.
Wrapping messes with our notion of ordering, so shortest path is a bit more complicated:
Based on this our notion of "deltas" changes too, as we have to always pick the shorter from the two possible routes:
Exhibit 9 - Modified Halfway Happy Distance
With our fancy new deltas, let's think about how we could juggle somehow the Halfway Happy Distance into this weird world:
What actually happened up there is that Cardinals and Intercardinals were switched, so we can just adjust the formula easily by thinking about base vectors (Cardinals) and their simpleton dumb sum (Intercardinals):
So without doing math, we came up with a modified Halfway Happy Distance which kind of bugs out to work in CS 101 screen coordinates.
Exhibit 10 - The Lawyer Tech Stack
I am a Lawyer, so of course I can make heavy computations!
That's what Excel spreadsheets, formulas and conditional formatting are for!
Of course I am a cheapoo so I use Libre Office.
Let's see all 3 distances in both Flat Earther and Inception Torus style:
Chebyshev:
Halfway Happy:
Manhattan:
Basically all 3 distances "work" if we cheese the basis change good enough.
Exhibit 11 - High Level Lawyering
Now comes the most important part of Lawyer Oriented Programming: Diving into the Jira Dumpster.
After a lot of dumpster diving... Bingo! We hit the Jackpot:
Q: We have city A with coordinates (x1,y1) and city B with coordinates (x2,y2) with coordinates as found in the editor N/S and E/W coordinate system. What is distance between A and B in the corruption equation?
A: It's the same distance calculation in a different coordinate system. In the editor coordinate system the distance would be given by:
d = (X + Y) / 2 + |X - Y|/4
where Y = |y1-y2| and X = |x1-x2|
see ainwood's post in the original corruption thread.
Unfortunately the link for ainwood's post does not work.
But at least, we fished out the "actual" d from the dumpster which must be used in the game!
This is the last exhibit.
Now it is time for Trial!
Are you ready?
I want to reiterate why we did this long journey:
- We don't want to misrepresent this case!
- We want to arrive at the true, just and honest truth.
We now have everything at our disposal to reveal the actual truth!
Let the Trial begin!
Trial
Your Honor, I believe that - until proven guilty - every man, woman and child in this country is innocent.
My client's rightful and legal business was wrongfully accused of mishandling funds, and it was grossly misrepresented in the eyes of the public by fabrications like this:
Your Honor, my client lives on the far reaches of our beautiful Country, far from the Capitol!
A third of my client's revenue is spent on traveling expenses alone!
Your Honor, from Exhibit 5 we already know certain facts:
When calculating his travel expenses my client abided by the zoning rules as required by law, please see Exhibit 11:
Your Honor, based on just these Exhibits, we can clearly show that my client was adhering to state approved measures when computing allowable travel expenses:
My client abided the zoning rules in the strictest sense, Your Honor!
Your Honor, please see the below picture:
- my client's residence is located entirely in the red zone as you can see on the right,
- far away from the Capital as you can see on the left,
- the looong black line represents the route my poor client has to endure each and every day to get to the Capital,
- strictly legally speaking of course based on the State-approved zoning rules as per Exhibit 11.
It is so far away from the Capital, that one third of the financial revenue of my poor client is spent on simply travelling expenses alone!
Do I see corruption, jakuzzis, mansions or partys?
No, Your Honor! I see a frail man, who works diligently, travels long hours, pays taxes, bookkeeps revenues, expenses and suddenly gets blamed for committing something he did not even do!
Your Honor, please understand that - strictly legally speaking - my client is living thousands of miles away from the Capital:
Of course, strictly legally speaking, your Honor.
Yes you are right Your Honor, my client is technically living 10 yards away from the Capitolium, and his front porch is basically touching the foot of the Capitolium Hill, but...
But Your Honor, what matters in this Courthouse... in these sacred marble hallways of Justice... is the word and Code of Law.
Christian Bale Oriented Programming
Yeah, we have to address the elephant in the room:
There wasn't an inch of Christian Bale thus far :(
But, remember that we did a floor div-ed Chamfer Distance?
Below is a LibreOffice sheet which goes from Manhattan via Halfway-Happy to Chebyshev using a slider.
We are doing Chamfer Distance and are cycling Cardinal cost (⊕) over:
[0.5, 0.55, 0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95, 1]
with a fixed Intercardinal cost (⨂) of 1:
The above function returns ints which are then used in complex calculations to yield a Corrupted Gold Coins number for the user.
If you are just a random user who bought Civ III from GOG for a couple of bucks, you will enjoy the game and its Corruption Mechanics.
But, remember Minkowski distance?
Remember that it is parameterized by p?
Below is a LibreOffice sheet which goes from Manhattan via Euclidean to Chebyshev using a slider controller in our derpy little spreadsheet.
We are doing Minkowski and are cycling p over [1, 1.1, 1.3, 1.5, 1.8, 2, 3, 5, 6, 8, 10, 100]:
Minkowski actually truly hits Euclidean. Euclidean is the "real distance" in a down to Earth sense.
Yeah-yeah if you compare Chamfer side-by-side with Minkowski the difference screams out but...
Yeah yeah yeah, Chamfer is just a replica of Minkowski even in the special "Halfway Happy" case, but simple users won't be able to tell.
Chamfer is just a slop replica, but Chamfer distance works and that makes users happy, and that's what matters.
Now, who is the Master?
The Minkowski or the Chamfer distance?
The Painter, or the Forger?
Okay now, hear me out on Christian Bale...
Mel Weinberg was a real con artist, charlatan involved in art forgery.
Hollywood actor Chrisitan Bale is not the real Mel Weinberg, as Mr. Bale just played a character based on Mel Weinberg.
Now, who is the Master? The Forger, or its Method Actor?
Summary
The guide stated that distance is a simple oneliner:
d = max(x,y) + min(x,y)/2
To which, someone might say that oneliner isn't Engineering Magic.
But now, after everything, dear Reader...
I hope that I convinced you that, indeed, it is.
Don't let the "oneliner" simplicity fool you!
That oneliner does not even handle the screen-xy-style coordinates, wrapping, overflows and certain nastier edge cases yet!
Remember CS 101? Remember what it taught us?
No, this isn't just a scary story that Professors tell us before going to sleep!
Now, who is the Master? n1 or n3?
Top comments (0)