Nerd For Tech
Published in

Nerd For Tech

Figuring out Steps on a Grid

GIF illustrating the Manhattan Distance probelm

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

Given an String Matrix in the form of {“0000”,”0001",”2000",”0020"} Where “1” represents a Player and “2” represents an Enemy Return the shortest steps to get from Player to Enemy. The Matrix wraps allowing a Player to leave the Left and Step onto the Right. Same for Top and Bottom. Result for above Matrix should be 2 because of the wrap.

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?

Horizontal distance equals the absolute value of the Target’s X minus the Player’s X. Same again for Vertical but using the Y. Step Distance equals the Horizontal Distance plus the Vertical Distance.

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.

Code for converting the Matrix into a 2D array grid.

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.)

Code for Finding a storing the location of each enemy in the grid

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.

Code for finding the Player in the grid array

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

Full code for Calculating the Manhattan Distance for this class.

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.

--

--

--

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

Recommended from Medium

Midas Gold Layered Farming Model

Force-sync iCloud Music Library

Port Scanning with Python3 for absolute dummies

Why Java is still famous

Gotcha: pyenv-win shims messing with global packages

Minimal APIs in .NET 6: how to use it to enrich data for analytics — Part2

How to prioritize your work ? – Management for Engineers Series

Introduction to Sass

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Thomas Kesler

Thomas Kesler

A Unity Developer with a fondness for Fantasy games and the challenge of pushing boundaries.

More from Medium

Day 19 of my Developer Journey: Creating the Shield Powerup logic

Optimizing the Animator and Callouts

How to Play Sound Effects in Unity

Journal 135 — Unity App Development, Interactive Map Info Cards with Scriptable Objects