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

Knowledge is power — and I WEB a lot

What does the digital industry look like?

4 prerequisite conditions to start with Scrum

What I’ve learned from joining a hackathon with only 1.5 months of coding experience

Run Espresso in pCloudy using Gradle

A Complete Spring Boot Microservice Build Pipeline using GitLab, AWS and Docker — Part 1.

Dealing with Scrum Team members spread over multiple locations

What is set in python

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

Code Optimization- Game Dev Series 145

Game Programming Pattern: Singleton

Did you just hit me! — Hitbox attack system in Unity2D

Gamedev Log: “Slash’n’crack” #5 (Unity/C#)