Obstructed start-point

[perara]

I've been using your library for pathfinding in a 2D simulation for quite some time. I'm working on implementing the v2 version but encountered a silly issue where no path is found due to obstructed start position.

This makes sense because consider that a unit starts off at position 5,5. When the algorithm tries to find a path, the position 5,5 would be occupied and instantly return NO_PATH found

This could potentially be remedied by a skip paramter? By commenting out the following lines, the code works as expected (or atleast the start position part of the if statement)

Line 1303-1305

            //if(!grid(start.x, start.y) || !grid(end.x, end.y))
            //    return JPS_NO_PATH;

[fgenesis]

The old version had exactly this check as well. If it worked there this must have been by pure chance. I mean sure you can comment that out to make that work but to me this looks like a problem in your code that needs to be fixed. Starting pathfinding from inside a wall and expecting it to work doesn't make sense to me. Maybe i'm misunderstanding what you're doing there? A unit(?) blocking itself? Why is a unit part of your map data?

[perara]

I'll try to make my case a bit more clear. Sorry!

Below is a graphical representation of the game I'm implementing your JPS Implementation.

As you stated, the units are part of the map-data (grid). The reason for this is that a tile/cell is not "walkable" if occupied by another unit. When the algorithm starts, it checks if the start-tile is obstructed, and this is always true because the unit already stands on the start position.

Also in order for the algorithm to have any practical use in such 2-dimensional games, it has to evaluate if the path is obstructed by other units.

Say I would evaluate the blue unit to move towards the upper right corner of the map. Here, the blue unit would simply move through the enemy if "other units" were not part of the map data.

Other units are simply treated as walls, and is, therefore, a non-issue, But because there is no way identify which unit the "findPath" request came from I cannot make exceptions for the first step of tile path calculation.

I'm not sure why this worked without issue in the first version. I did, however, not encounter this issue before doing an in-place replacement of the header file.

It is a non-issue for me to remove the first part of the if-statement mentioned earlier, but I feel it natural to have an option to skip obstruction of the start position.

[perara]

Hi, I've tested the new version. Without the flags, it does not move at all (I suppose this is expected for my case)

There is some weird behavior when calculating the path is calculated: s denotes start g denotes goal p denotes JPS path

Standing at 1,1 clicking at 13,1

sx=1, sy=1, gx=13, gy=1
px=1, py=24
px=1, py=23
px=1, py=22
px=1, py=21
px=1, py=20
px=1, py=19
px=1, py=18
px=1, py=17
px=1, py=16
px=1, py=15
px=1, py=14
px=1, py=13

Standing at 1,1 clicking at 1,13 (lower left)

sx=1, sy=1, gx=1, gy=13
px=24, py=1
px=23, py=1
px=22, py=1
px=21, py=1
px=20, py=1
px=19, py=1
px=18, py=1
px=17, py=1
px=16, py=1
px=15, py=1
px=14, py=1
px=13, py=1

I've double checked that the grid collision is represented correctly (Worked before with JPS2)

[perara]

        JPS::findPath(path, unit.getPlayer().getGame().tilemap, unit.tile->x, unit.tile->y, goal->y, goal->x, 1, (JPS_Flag_NoStartCheck | JPS_Flag_NoEndCheck));
        std::cout << "sx=" << unit.tile->x << ", sy=" << unit.tile->y << ", gx=" << goal->x << ", gy=" << goal->y << std::endl;
        for(auto pathItem : path) {
            std::cout << "px=" << pathItem.x << ", py=" << pathItem.y << std::endl;
        }

        // Insert found path to the walking path vector
        std::reverse(path.begin(), path.end());
        for(auto pathItem : path) {
            Tile& tile = unit.getPlayer().getGame().tilemap.getTile(pathItem.x, pathItem.y);
            unit.walking_path.push_back(&tile);
        }

[perara]

And thanks for the support by the way! Much appreciated!

[fgenesis]

        JPS::findPath(path, unit.getPlayer().getGame().tilemap, unit.tile->x, unit.tile->y, goal->y, goal->x, 1, (JPS_Flag_NoStartCheck | JPS_Flag_NoEndCheck));

(..., goal->y, goal->x, ...)

Did you by chance switch x and y? And why do you reverse the path? It should deliver the path points in the right order already.

I just did a quick check by replicating your level as ascii-art and it appears to work fine here. But you're not the only one with problems with the new version, so there must be something wrong that i'm just too dumb to see. It should definitely not go out-of-bounds like this (assuming your grid check function is correct). I assume your map is non-wraparound, and the border rock tiles are non-walkable?

[perara]

Hi,

The x and y should be correct and i cannot recollect how i defined the grid check (ill check later today).

Nontheless, the exact same codebase runs fine on the older version.

Ill come back to you later today with additional details and see if i can identify any reason behind the behavior.

Edit: yes, non wrappable and tiles such as tree, rock, and border are not walkable

Edit2: The behavior was quite similar to swapped x,y so i did test to swap them,. This dis however not work

Edit3: i assume the reverse is there because of how i pop the path later. I think this is from earlier attempts at making it more efficient. Anyways, as you point out, it is no longer needeed 😅

[fgenesis]

There was a bug, fix is up! Pull + test again.

[perara]

@fgenesis works perfectly!

[perara]

I'll close this help ticket and query you if I find any funnies. You have done an incredible job with this library and I thank you for your continued maintaining!