Calculating distance with Euclidean, Manhattan, and Chebyshev in C#

Question

I am by no means proficient at being able to take mathematical concepts and converting them to code. I was wondering if you guys could look at it and make suggestions on how I could fix it or if my thinking is correct on these. I used a combination of the wikipedia pages for each of these as well as http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html to come up with my solutions.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithms
{
    public static class Heuristics
    {
        // implementation for integer based Manhattan Distance
        public static int ManhattanDistance(int x1, int x2, int y1, int y2)
        {
            return Math.Abs(x1 - x2) + Math.Abs(y1 - y2);
        }

        // implementation for floating-point  Manhattan Distance
        public static float ManhattanDistance(float x1, float x2, float y1, float y2)
        {
            return Math.Abs(x1 - x2) + Math.Abs(y1 - y2);
        }

        // implementation for integer based Euclidean Distance
        public static int EuclideanDistance(int x1, int x2, int y1, int y2)
        {
            int square = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
            return square;
        }

        // implementation for floating-point EuclideanDistance
        public static float EuclideanDistance(float x1, float x2, float y1, float y2)
        {
            float square = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
            return square;
        }

        // implementation for integer based Chebyshev Distance
        public static int ChebyshevDistance(int dx, int dy)
        {
            // not quite sure if the math is correct here
            return 1 * (dx + dy) + (1 - 2 * 1) * (dx - dy);
        }

        // implementation for floating-point Chebyshev Distance
        public static float ChebyshevDistance(float dx, float dy)
        {
            // not quite sure if the math is correct here
            return 1 * (dx + dy) + (1 - 2 * 1) * (dx - dy);
        }
    }
}

Answer 1

Let's start with some housekeeping. You're not using these using so they should be removed:

using System.Collections.Generic;
using System.Linq;
using System.Text;

---

Your namespace is far too generic - it's much better than ConsoleApplication1 but you should use something like <Company>.<Product>.<Feature> in your real app.

---

Your method names should be verb phrases ManhattanDistance should be CalculateManhattanDistance (and likewise for the others).

---

Why does your ChebyshevDistance take different parameters to the others? That seems unfriendly in the API design.

---

You should add documentation comments rather than simple comments to explain what a method does.

e.g.

/// <summary>
/// Calculates the Manhattan distance between the two points.
/// </summary>
/// <param name="x1">The first x coordinate.</param>
/// <param name="x2">The second x coordinate.</param>
/// <param name="y1">The first y coordinate.</param>
/// <param name="y2">The second y coordinate.</param>
/// <returns>The Manhattan distance between (x1, y1) and (x2, y2)</returns>
public static int CalculateManhattanDistance(int x1, int x2, int y1, int y2)
{
    return Math.Abs(x1 - x2) + Math.Abs(y1 - y2);
}

I'd also consider swapping the order of the parameters so you specify x1, y1, x2, y2 or using Point and PointF instead.

---

Now that's out of the way... ManhattanDistance looks correct.

---

EuclideanDistance is missing the final square root. The article you've linked to explains why that's bad:

I’ve seen several A* web pages recommend that you avoid the expensive square root in the Euclidean distance by just using distance-squared [snipped pseudocode] Do not do this! This definitely runs into the scale problem. The scale of g and h need to match, because you’re adding them together to form f. When A* computes f(n) = g(n) + h(n), the square of distance will be much higher than the cost g and you will end up with an overestimating heuristic. For longer distances, this will approach the extreme of g(n) not contributing to f(n), and A* will degrade into Greedy Best-First-Search.

---

According to the Chebyshev distance Wikipedia article, in the Cartesian plane it's simply:

max(|x2 - x1|, |y2 - y1|)

Making it:

public static int CalculateChebyshevDistance(int x1, int x2, int y1, int y2)
{
    return Math.Max(Math.Abs(x2 - x1), Math.Abs(y2 - y1));
}

Although, following the article you linked your result should be:

public static int CalculateChebyshevDistance(int x1, int x2, int y1, int y2)
{
    var dx = Math.Abs(x2 - x1);
    var dy = Math.Abs(y2 - y1);
    return (dx + dy) - Math.Min(dx, dy);
}

I can't see how to prove that they're equivalent... If anyone can, I'd be interested to see it!

They are obviously equivalent... If you add the dx and dy together and then subtract the smaller of the two you are obviously left with just the bigger value i.e. the max of dx and dy.