Manhattan distance formula is (of course) flawed !

Hey again,

So my latest game creation will be using the A* pathfinding algorithm. In brief, A* works from it's starting point, evaluating each of the neighbouring squares and seeing how far away it is from the target. It picks the nearest one to the target. I've bolded "nearest" here because in gaming, calculating the distance to the target is a somewhat hot bed of potatoes (if that's a metaphor?). Let's look at an example:

Here we have a grid and we need to get from point A to point B. The A* algorithm sums up the cost of moving to an adjacent square (g-cost) and adds in the distance from that square to the target (h-cost). It does this for every square and moves to the square with the lowest value. There's a bit more to it than that (a great article can be read on it here), but the key problem we have is with how to calculate the h-cost.

We could use the Euclidean Distance, which is a pretty straightforward formula once you get your head round it, and obviously very accurate. But this involves using something that game programmers try and avoid like the plague. The dreaded Square Root !! Of course, using square roots in the example above would be fine. We're talking about 6 diagonal gaps to fill before we reach the target. But what about a bigger grid? Or even multiple start points with multiple targets? I hope you can see that it might not always be the first choice.

And here's where I bring in the Manhattan Method (or Manhattan Heuristic as it might be more appropriately called). All the Manhattan Method does is work out how many units horizontally and vertically it would need to move to get to the target.

Clearly it's not the quickest route, but because the same algorithm is being applied to all the adjacent squares to A, you can (hopefully) see that the one to the bottom right of A is going to return the best score. Why am I using units of 10? Don't worry about it for now, but read the A* article above and it should become clear why.

It's lovely and fast because no division or square root calculations need to be done. Everybody's happy... Right?

Well I thought I was until a rather strange thing happened when I put a wall in the way:

Now the squares to the right of A are not available and are hence their distance is not considered. I have diplayed above the two points with the lowest Manhattan distances. But which point do you think has a lower "Manhattan" distance above, Point 1 or Point 2? I hope you are thinking that it is point 2, and you'd be right. But I'm afraid you'd also be right if you picked point 1! Don't believe me? Well, let's take the number of steps inbetween point 1 and B:

As you can see it's 6 places (or 60 as I'm using units of 10 here). Let's look look at point 2:

Oh dear, also 60 units away. So depending on which order you work through the adjacent squares, you may end up with a rather skewed route towards your goal. I should point out that the A* algorithm still finds it's way to the target in this example, but it might take a rather skewed route!

So how do you get round this? Well, I am pretty sure this anomaly will only occour in situations where the source and the target are either vertically or horizontally equal. Therefore, the Manhattan Heuristic could penalise the straight route by a small number (eg 1).

Interested to hear others !

A Catmull Rom Spline (curve) Implementation in Java

Hey,

Another little challenge for my gaming world was to create a smooth route for a given node (eg a soldier). Using an A* algorithm gives very awkward turns (ofter 90 degrees) between two cells. What would be nice is to make the soldier turn in increments between the two cells. The more increments you have, the smoother the turn.

Let's say you have two points p1 and p2. You would like to find the smooth curve point halfway (0.5) between them. In order to do this with a Catmull Rom Spline curve, you're also going to have to provide the point before(p0) and after (p3).

Here's the method:


    public float q(float t) {
        return 0.5f * ((2 * p1) +
                      (p2 - p0) * t +
                      (2*p0 - 5*p1 + 4*p2 - p3) * t * t +
                      (3*p1 -p0 - 3 * p2 + p3) * t * t * t);    
    }

So let's start with a one-dimensional curve. The four values:

p0 = 1
p1 = 2
p2 = 2
p3 = 1

We want a point a point halfway (t=0.5). Plugging this into our method call q(0.5f), it returns a value of 2.125. Smoothing further:

q(0.25) = 2.171875
q(0.5) = 2.125
q(0.75) = 2.171875

Lovely, so we could potentially break this up an infinite number of times, but that would clearly take an infinite of time to run. You'll want to play with your implementation


You're probably already wondering how this can be configured for a 2D (or maybe 3D) A* algorithm. It's very simple actually, you just need to perform the algorithm for the x values and y values (or indeed, z values) on their own. I'm including all of the source code below, and I'll leave you to figure out how you might implement a CatmullRomSpline3D (I hope you can see it's really easy!). There are three Java classes below. I had some issues pasting them in, so please separate them by each "package".


By the way, if this is the first point in your A* route, then you're not going to have a previous point, so specify p0 = p1 (ie double-up on the value). If it's the last point on your route, then set p3 = p2.

Using the CatmullRomSplineUtils class (below) I as able to create a much smoother path (above diagram) around a particularly tricky route. I also noticed that it is blindingly fast. I haven't given it a thorough soaking yet, but this 13 point route with 5 subdivisions (which amounts to 121 new points) did not register a single milisecond in duration.

I can see that this could be workable for a racing game. The computer car ai calculations can be quickly recalculated if it got knocked off course.

---

package catmullrom;

public class CatmullRomSpline {

    private float p0, p1, p2, p3;

    public CatmullRomSpline(float p0, float p1, float p2, float p3) {

        this.p0 = p0;

        this.p1 = p1;

        this.p2 = p2;

        this.p3 = p3;

    }

    public float q(float t) {
        return 0.5f * ((2 * p1) +
                      (p2 - p0) * t +
                      (2*p0 - 5*p1 + 4*p2 - p3) * t * t +
                      (3*p1 -p0 - 3 * p2 + p3) * t * t * t);    
    }

    /**

     * Example implementation

     */

    public static void main(String[] args) {

        CatmullRomSpline crs = new CatmullRomSpline(1f, 2f, 2f, 1f);

        System.out.println(crs.q(0f));

        System.out.println(crs.q(0.25f));

        System.out.println(crs.q(0.5f));

        System.out.println(crs.q(0.75f));

        System.out.println(crs.q(1f));

    }

    /**

     * @return the p0

     */

    public float getP0() {

        return p0;

    }

    /**

     * @param p0 the p0 to set

     */

    public void setP0(float p0) {

        this.p0 = p0;

    }

    /**

     * @return the p1

     */

    public float getP1() {

        return p1;

    }

    /**

     * @param p1 the p1 to set

     */

    public void setP1(float p1) {

        this.p1 = p1;

    }

    /**

     * @return the p2

     */

    public float getP2() {

        return p2;

    }

    /**

     * @param p2 the p2 to set

     */

    public void setP2(float p2) {

        this.p2 = p2;

    }

    /**

     * @return the p3

     */

    public float getP3() {

        return p3;

    }

    /**

     * @param p3 the p3 to set

     */

    public void setP3(float p3) {

        this.p3 = p3;

    }

}

---

package catmullrom;

public class CatmullRomSpline2D {

    private CatmullRomSpline splineXVals, splineYVals;

    public CatmullRomSpline2D(Point2D p0, Point2D p1, Point2D p2, Point2D p3) {

        assert p0 != null : "p0 cannot be null";

        assert p1 != null : "p1 cannot be null";

        assert p2 != null : "p2 cannot be null";

        assert p3 != null : "p3 cannot be null";

        splineXVals = new CatmullRomSpline(p0.getX(), p1.getX(), p2.getX(), p3.getX());

        splineYVals = new CatmullRomSpline(p0.getY(), p1.getY(), p2.getY(), p3.getY());

    }

    public Point2D q(float t) {

        return new Point2D(splineXVals.q(t), splineYVals.q(t));

    }

}

---

package catmullrom;

public class Point2D {
    private float x, y;

    public Point2D() {
        this(0f, 0f);
    }

    public Point2D(float x, float y) {
        this.x = x;
        this.y = y;
    }

    /**
     * @return the x
     */
    public float getX() {
        return x;
    }

    /**
     * @param x the x to set
     */
    public void setX(float x) {
        this.x = x;
    }

    /**
     * @return the y
     */
    public float getY() {
        return y;
    }

    /**
     * @param y the y to set
     */
    public void setY(float y) {
        this.y = y;
    }
}

package catmullrom;

public class CatmullRomSplineUtils {
    /**
     * Creates catmull spline curves between the points array.
     *
     * @param points The current 2D points array
     * @param subdivisions The number of subdivisions to add between each of the points.
     *
     * @return A larger array with the points subdivided.
     */
    public static Point2D[] subdividePoints(Point2D[] points, int subdivisions) {
        assert points != null;
        assert points.length >= 3;

        Point2D[] subdividedPoints = new Point2D[((points.length-1) * subdivisions) + 1];

        float increments = 1f / (float)subdivisions;

        for (int i = 0; i < points.length-1; i++) {
            Point2D p0 = i == 0 ? points[i] : points[i-1];
            Point2D p1 = points[i];
            Point2D p2 = points[i+1];
            Point2D p3 = (i+2 == points.length) ? points[i+1] : points[i+2];

            CatmullRomSpline2D crs = new CatmullRomSpline2D(p0, p1, p2, p3);

            for (int j = 0; j <= subdivisions; j++) {
                subdividedPoints[(i*subdivisions)+j] = crs.q(j * increments);
            }
        }

        return subdividedPoints;
    }


    public static void main(String[] args) {
        Point2D[] pointArray = new Point2D[4];

        pointArray[0] = new Point2D(1f, 1f);
        pointArray[1] = new Point2D(2f, 2f);
        pointArray[2] = new Point2D(3f, 2f);
        pointArray[3] = new Point2D(4f, 1f);

        Point2D[] subdividedPoints = CatmullRomSplineUtils.subdividePoints(pointArray, 4);

        for (Point2D point : subdividedPoints) {
            System.out.println("" + point);
        }
    }
}

PSP Downloads... What was I thinking?

I've just downloaded GTA: Chinatown Wars on my shiny new PSP 3000. I love the fact that you can make an impulse decision and get yourself a game in about 30 minutes (assuming a reasonable broadband connection). It's much quicker running from a memory stick too.

But then you realise something very quickly. You actually end up with nothing but data. No box, no disk, no instructions. Oh crap!

It's not a bad game, but I'm not really enjoying it. I'm finding it just a fraction too fiddly. The police are too easy to aggro, and the control is just too frantic. Many disagree, so I think I may have to bow to their gaming sage-ness. Age is inversely proportional to thumb dexterity it would seem.

And therefore, I now have nothing. I very much doubt I can get a refund based on a "I don't like it" argument. I can't e-bay it either. That's always been a staple excuse of mine that I would be able to get a bit back (sometimes 80% of the RRP) if things didn't work out. Now I'm just empty.


Blockbuster have stopped stocking PSP's and games because Sony's latest PSP-Go only does downloads (ie no UMD slot anymore!). They see this as a smack in the face for their sales and have taken the hard line. I'm tempted to adopt a similar stance. Maybe I'm old-fashioned, but my next purchase (over a tenner) is going to be on e-bay. I'll just have to curb my enthusiasm for a day or two and wait under the letterbox!

That will get Sony quaking in its boots ;-)

A Maze Algorithm in Java

I had a good hunt around for a maze creator written in Java, but couldn't find one quite to my liking. So I wrote my own, using the Depth First - Recursive Backtracker method.

Download source my files here

First of all, I created a class that contains the details for each "cell" of the maze (GridCell.java). This contains the details required for each maze cell (which walls are up/down, and whether that cell has been visited yet).

Now on to the main code, my (MazeGrid.java). Hopefully, there's enough commenting on here to make it clear what it's doing, but just in case, here is the pseudo-code for the generateMaze() method:

• Reset all cells in the grid ( resetGridCells() ).
• Work out how many cells there are (width*height) and also create a last-in-first-out stack of visited cells.
• Start at the top-left (y=0,x=0)
• While there are still cells left unvisited (cellsVisited < width*height):
• See if there are any cells that can be visited from the current cell that we have not yet visited ( unvisitedCellCanBeReached(...) ).
• If there are cells we can visit, pick one at random ( getRandomUnvisitedCell(...) ), set the wall on the current side as down and move to the next cell. Add this next cell to the top of the stack, set it to "visited" and increase the visited count.
• If there are no cells we can visit from our current location, then "pop" the previous location off the stack and move back there.
• Once we've visited all the cells, I need to do a "cleanup". A slight flaw in my design means that if (say) a cells east wall is flagged as down (intact = false), then the cell next to it (on the east side) should have its west wall down (basically I've created double-strength walls). So the cleanup method knocks down any of these walls as well.

That's it. You can now call getGridCells() to get the array. If you want to try it out, download the MazeGenerator.jar file. It should auto-execute. It's got some other Java classes in there that I created quickly in Netbeans to allow a visual representation.

Have fun!