strange paths, operator() called with UINT_MAX

[PcChip]

Hi,

I'm sure I'm doing something wrong here, but I'm stumped as to what

In my game, I replaced the normal A* pathfinder with your JPS version, and half the time the paths generated are perfect, but the other half of the time they're crazy. I started adding debugging and checks everywhere I could think of, and I noticed that operator() gets called with x and y being UINT_MAX (or -1 as a signed integer)

Is this expected behavior?

(Note the "< 9" part is because this was originally used in a variable cost pathfinding solution, but I just put in "< 9" for use with yours)

`inline bool teMapModule::operator()(unsigned int x, unsigned int y) const
{
bool canwalk = ((x < 512) && (y < 512) && (x >= 0) && (y >= 0));

if (canwalk)
{
	canwalk = pathingMap[y*512 + x] < 9;
}
return canwalk;

}

bool teMapModule::findJPSPath(int startingX, int startingY, int goalX, int goalY, std::vector<xzCoordsStruct>& resultingPath)
{

JPS_Path_Results.clear();
JPS::Position start{startingX,startingY};
JPS::Position goal{goalX,goalY};  
bool pathFound = JPS_Searcher->findPath(JPS_Path_Results, start,goal, 1); 

if(pathFound)
{
	for (JPS::PathVector::iterator it = JPS_Path_Results.begin(); it != JPS_Path_Results.end(); ++it)
	{
		resultingPath.push_back({ it->x ,it->y });
	}
}
return pathFound;

}`

Can you see any obvious errors or have any idea why I'm getting crazy paths half the time?

Thanks for any suggestions you might have!

[fgenesis]

Yes, -1 can happen as the search underflows when going out-of-bounds. This is expected and you're supposed to handle this in your grid check. (You could implement wrap-around easily this way, if that's your thing)

Note that in your case the part (x >= 0) && (y >= 0) is always true since x, y are unsigned.

Aside from this your code looks correct and I'm not sure why you're getting "crazy paths", whatever that means. If you could give an example that shows your problem that would be great (image, coordinate point list, whatever).

The coordinates are unsigned on purpose, so that you can simplify your grid check by taking advantage of unsigned underflow (which is perfectly fine according to the C/C++ standard).

Something like this:

inline bool teMapModule::operator()(unsigned int x, unsigned int y) const
{
    return x < 512 && y < 512 && pathingMap[y*512 + x] < 9;
}

If your map absolutely wants signed coordinates all you need to do is to use those unsigned x, y as signed and check both minimum and maximum, then do the grid lookup.

If everything fails try this version: https://github.com/fgenesis/tinypile/blob/9893d8fe68ef5360f097f23f3a7e6ff0c772c21d/jps.hh (note the slight API change between this and current HEAD!)
Maybe I've messed up the recent changes; i've run the usual tests and those worked fine, but who knows...

[PcChip]

Thanks for the reply!

Sure, here's an example:

• correct pathing: https://i.imgur.com/vdTcq6T.png
• incorrect pathing: https://i.imgur.com/4f7X5N2.png
• incorrect pathing: https://i.imgur.com/rT6kWXD.png

In the pictures, red highlighted squares are 9 (not walkable)

notice in the incorrect versions the first step is way off from where the actual starting location was. It seems like when the path is going in one direction (maybe negative x and negative y?) it works fine, but any other direction it gets wonky

I'll give the other version a shot and see what happens, thanks!

[PcChip]

Update: the old version you linked seems to be working!

Although from my logs it looks like some of the searches are failing for some reason, but the workers are still getting paths... hmm...

https://i.imgur.com/qpnYHgP.jpg

Update2: seems to be failing because start or end node are obstructed - I'll figure that out on my end

thanks again for the help!

Update3: fixed the start node being obstructed, was a float->int rounding error
the little guys are finding paths all over the place now! https://i.imgur.com/pCq9aHq.jpg

[fgenesis]

Eh, so i DID introduce a bug in the meantime, yes?
Please confirm, then i'll go look when i have time.

The newer rev adds a bunch of flags, JPS_Flag_NoStartCheck and JPS_Flag_NoEndCheck that might also do what you want, but i haven't tested those extensively yet, so beware.

[PcChip]

I can't confirm there's a bug, but I would assume there is since swapping in the old version you linked has been working perfectly

[fgenesis]

Just fixed a bug. Pull + try again now.
EDIT: I've noticed that passing JPS_AStarOnly results in really bad paths, so there must be another bug since i haven't tested that flag much (or the #define in the previous versions)
EDIT2: Wait i accidentally posted under the wrong issue. Ah well, this applies here too. Derp.