A Star Pathfinding Diagonals Issues - LibGDX

Newbie & Debugging Questions
#1

I’m trying to create my first 2D RPG game and am running into an issue with pathfinding. I’m using LibGDX framework and imported this pathfinding into my project

It works well when dealing with non diagonals (although it wall hugs), but when adding diagonal’s it makes really questionable and noticeable movements which can kill immersion.

I’ve posted a picture of the pathfinding, this is the code that I changed to add diagonal’s.

The old code

for (int x = 0; x < sizeX; x++) {
        for (int y = 0; y < sizeY; y++) {
            nodes.add(new FlatTiledNode(x, y, map[x][y], weight[x][y], 7));
        }
    }

    // Each node has up to 4 neighbors, therefore no diagonal movement is possible
    for (int x = 0; x < sizeX; x++) {
        int idx = x * sizeY;
        for (int y = 0; y < sizeY; y++) {
            FlatTiledNode n = nodes.get(idx + y);
            if (x > 0)
                addConnection(n, -1, 0);
            if (y > 0)
                addConnection(n, 0, -1);
            if (x < sizeX - 1)
                addConnection(n, 1, 0);
            if (y < sizeY - 1)
                addConnection(n, 0, 1);
        }

The new code

   // Each node has up to 4 neighbors, therefore no diagonal movement is possible
    for (int x = 0; x < sizeX; x++) {
        int idx = x * sizeY;
        for (int y = 0; y < sizeY; y++) {
            FlatTiledNode n = nodes.get(idx + y);
            if (x > 0)
                addConnection(n, -1, 0);
            if (y > 0)
                addConnection(n, 0, -1);
            if (x < sizeX - 1)
                addConnection(n, 1, 0);
            if (y < sizeY - 1)
                addConnection(n, 0, 1);
            if (x > 0 && y < sizeY - 1) {
                addConnection(n, -1, 1);
            }
            if (x < sizeX - 1 && y > 0) {
                addConnection(n, 1, -1);
            }
            if (x < sizeX - 1 && y < sizeY - 1) {
                addConnection(n, 1, 1);
            }
        }
    }

Changing the heuristics to octile didn’t make any difference either

public float estimate (N node, N endNode) {
    float F = (float) (Math.sqrt(2) - 1);
    int dx = Math.abs(endNode.x - node.x);
    int dy = Math.abs(endNode.y - node.y);
    return ((dx < dy) ? F * dx + dy : F * dy + dx);
}

Any help would really be appreciated.

1109×575 3.74 KB

#2

4 notes that may be helpful
1, u say [quote]Each node has up to 4 neighbors, therefore no diagonal movement is possible
[/quote]
, but right below the comment, u define the diagonal connections. and obviously, diagonals are possible per your screenshots. maybe this is just a leftover comment u forgot to deltee
2, u define 3 diagonals (-1, 1), (1, -1), and (1, 1), but u forget the (-1, -1).
3, i’m not sure how ur using ur estimate so there may be error there as well; but this is a common problem that occurs when you don’t add proper cost to moving diagonal (e.g., should cost sqrt(2) more than moving vertical/horizontal does). If diagonal movements don’t cost as much as they should, then the character may prefer to move in zig-zags even when straight connecting paths exist. Maybe your estimate should be something like


    float sqrt2 = (float) Math.sqrt(2);
    int dx = Math.abs(endNode.x - node.x);
    int dy = Math.abs(endNode.y - node.y);
    int maxD = Math.max(dx, dy);
    int minD = Math.min(dx, dy);
    return sqrt2 * minD + (maxD - minD);
#3

Sorry those comments were from the original library I forgot to remove them, also I’ve added the fourth diagonal (-1, -1) about a day or two ago the pathfinding issue still exists.

I’ve changed the estimates to the code you provided and this is how pathfinding looks

881×544 3.3 KB

When I change the estimate to this, the pathfinding is still the same as the image.

return Math.abs(endNode.x - node.x) + Math.abs(endNode.y - node.y);

This is the full class for the pathfinder

http://pastebin.java-gaming.org/79c1876515011

#4

What you have there looks like a perfectly fine astar result, you just need to postprocess the generated path.

Most important: Erase unnecessary nodes by checking line of sight.
You can start at the beginning and erase all nodes that are between the last visible node and the node you begin to check from.

881×544 36.2 KB

When you’ve done this once you just need to start again at the last green node. When you reached the end you finished the optimization!

Play this out in your head, you’ll see that it also removes the little bump at the top right around the sharp corner!
You need to think about the edge cases though where there are no inbetween nodes, etc.

Also search for jump point search!

#5

Basically the way I was doing it previously was using their LibGDX SmoothPathfinding, where it’ll narrow it down to a few nodes, like the image below.

961×631 4.37 KB

The problem with narrowing the node down, is that I want to turn this into an MMORPG so I’m not sure if that would cause any problems there.

Also Jump Point seems poorly optimized

http://qiao.github.io/PathFinding.js/visual/

A* manhattan took 1.4 seconds, compared to Jump Point which took 10.4 seconds.

#6

[quote]Also Jump Point seems poorly optimized
[/quote]

Jump point search IS an optimization, it most certainly is faster than vanilla A* in most cases.
You need to turn off the visualization checkbox for JPS in that javascript example, it somehow inflates the operations counter.

[quote]The problem with narrowing the node down, is that I want to turn this into an MMORPG so I’m not sure if that would cause any problems there.
[/quote]
Can you actually specify any problems? Why are less nodes worse in your case? Why do you need these intermittent nodes?

Also on second thought i realize I’m a bit retarded too, there must be something wrong with your A*, it should by default reject the unnecessary diagonal paths as long as the path cost calculation works correctly. It kinda looks like a diagonal jump costs just as much as a grid aligned jump in your case, resulting in it hugging walls.

[quote]previously was using their LibGDX SmoothPathfinding
[/quote]
Just go back to using that if it’s performance is good enough :smiley:

#7

To calculate the number of steps it takes to get from point A to point B

#8

Just generate the missing nodes between two nodes by rasterizing the line between them with bresenham’s algorithm.

I bet there is a simpler algorithm that just needs the x and y distance and the tile size, but i haven’t done anything in that direction yet