Can L1 Distance Give Underestimates In a 2-D Rectangular Lattice?

Question

I am working on this program that plays PacMan and involves calculating the Manhattan distance between the player and some enemies.

Here's my problem, if we have an enemy straight ahead of the player $\theta$ units away, and another enemy that is also $\theta$ units away, however, this enemy is at a tangential position then the enemy at the tangential position always is closer in terms of moves taken than the one that lies straight ahead of the enemy. This is causing disruptions in how my bot reacts to the enemies (since they're both technically the same distance away but in reality one catches the player quicker than the other).

e.g., player is at point (0,0); $enemy_1$ is at point (0,5) and $enemy_2$ is at point (3,2) the L1 distance between the player and both the enemies is 5 yet one enemy reaches faster than the other.

My question is this: are there any cases where the Manhattan distance estimate |$x_1$ - $x_2$| + |$y_1$ - $y_2$| underestimates the true distance or is this more to do with the implementation of the game?

Answer 1

I think I understand the question. You're considering two points $(x_1,y_1)$ and $(x_2,y_2)$, where all coordinates are integers, as vertices on the graph of integer locations.

• This graph has horizontal and vertical unit-length edges, and one can ask what is the distance $d((x_1,y_1);(x_2,y_2))$ between the two vertices. This "true" distance is the minimal length of a path between the vertices.
• At the same time, one defines the function $L^1((x_1,y_1);(x_2,y_2))=|x_1-x_2|+|y_1-y_2|$.

Then your question is whether we have the identity $d=L^1$. (Or, on the other hand, whether $L^1$ might be an underestimate for $d$.)

The answer is simply, yes: $d=L^1$ exactly. Nothing funny going on there. It suffices to prove that there exists a path of length $L^1$, and that there does not exist any shorter path. For the first part, consider a path that follows $|x_1-x_2|$ horizontal edges and then $|y_1-y_2|$ vertical edges. For the second part, consider that each path segment can reduce $L^1$ by only $1$.

Knowing this, and given your evidence that the enemy times don't equal $L^1$, we conclude that the enemy times don't equal $d$ either. They're doing something more complicated than crossing graph edges at a constant speed.