Figuring out Steps on a Grid

While reviewing with a student, we came across a challenge problem that had them stumped.

It took a few minutes for us to unpack the problem, but I soon saw that it was the “Taxi Cab” Problem (aka Manhattan Distance).

The Taxi Cab problem boils down to ‘How many blocks does a Taxi have to travel to get from point A to point B?’ and is a somewhat classic distance problem. Normally, in coding, we figure the straight distance between two points, ‘as the crow flies’. But that doesn’t work for a Taxi unable to drive through buildings and having to stick to the grid like streets. Then the ‘Shortest’ route becomes several equal distances that sum as the Right triangle that joins the two points. As you can see in the GIF above, all those different routes equal to the same distance traveled.

So, How do we break this down to code?

The meat of the calculation is Horizontal plus Vertical distances equal the Manhattan distance. And because we deal with computers that don’t know better, we make sure get the absolute value of the difference between Player’s X and Target’s X. Same for the Y coordinates.

As for setting up grid, that takes a little more work. Let’s work on the simpler non-wrapping version.

Strings can be accessed in a similar fashion to Arrays to pull out a single Char. So, we use the first item in the matrix Array’s length to find out how many columns our new two Dimension Array will have. And the Length of the matrix array to figure out how many rows we will need. We use them on Line 5 to initialize the 2D array to the right size.

Then, in a nested For loop, we will use one Item for row X and cycle through it’s Characters with Y to fill in the columns.

Since we are already cycling through each Char to insert it into our grid Array, we can use this chance to count how many Enemy ‘2’s are in the grid. And because we are using Unity Library, we can initialize an Array of Vector2s. If you don’t have this luxury, you will want to create a struct or class to hold the position of the enemies in the grid. (I will post my full code with that revision below.)

As for those targets, now is the time to grab their locations and store them for later checks. We couldn’t do this before because we needed the total number of enemies to initialize the Array. An option for optimization could be to use a list instead.

One thing to note, when using a multidimensional array such as a 2D one, you need to use GetLength(x) to find the length of a particular axis.

We use a similar but slimmed down version of the same method that found the enemies to track down the Player’s location.

Now to fully implement the math for figuring out the Manhattan Distance for this Class.

First, we need to set a too large to be reasonable number as our ‘Best Solution’. And since we only have one Player, we can also now assign their X/Y for clean code.

Then we can loop through what Enemies we found and calculate their distance from the player. Next, we compare the combined distances to the current Best. If it is better, we assign it to the BestSteps.

Once we have gone through all the Enemies, we check if the Best is better than are ‘Too large’ number from before. This allows us to handle cases with no Enemies.

And how I found to quickly and simply check for wrapping, is to create a Super Grid instead of the default grid. A Super Grid is a grid that is made of nine of the smaller grids tiled together. Then when we find the Player, we only search the center grid. As promised, the full code for the checking a wrapping grid without using Unity Libraries.