Partial Paths

General
#1

Hi Aron,

I’m having troubles with calculations of partial paths using ABPath.calculatePartial.
Currently using 3.4.0.5 in the project, but have checked out 3.5.1 as well - same applies.

So the problem Nr.1 is: partial paths doesn’t seem to get calculated at at.
When calculatePartial is enabled I always get Error or Compete state, newer the Partial. So I have reviewed places where Partial state is assigned in code - and there are only two. The first is in ABPath.CalculateStep(…), in the final code block of tracing the path. But from looking at the WHILE loop of calculations it seems like the tracing block at the end of the method is never reached in case of partial path. If the end node hasn’t been reached yet and there are no more nodes to open, the CalculateStep method is exited with error regardless of calculatePartial setting. Here is the exit code:

`//any nodes left to search?
if (pathHandler.HeapEmpty()) {
    Error ();
    LogError ("No open points, whole area searched");
    return;
}`

Now if I add a BREAK instead of RETURN in case of calculatePartial being enabled, like this:

`//any nodes left to search?
if (pathHandler.HeapEmpty()) {
    if (calculatePartial) break; // FIX?
    Error ();
    LogError ("No open points, whole area searched");
    return;
}`

then we jump to tracing part and get the partial path done and eventually returned.

The second place where Partial state gets assigned is ABPath.Initialize(). If the starting node is completely walled, this method is supposed to complete the calculations immediately. But if calculatePartial is enabled, there is no RETURN statement after marking as Partial and tracing (like in case of Error), therefore code continues to last line of the method where node is poped, which throws an exception because the heap is empty. Here is the code with one-liner possible fix:

`//any nodes left to search?
if (pathHandler.HeapEmpty ()) {
    if (calculatePartial) {
        CompleteState = PathCompleteState.Partial;
        Trace (partialBestTarget);
        return; // FIX?
    } else {
        Error ();
        LogError ("No open points, the start node didn't open any nodes");
        return;
    }
}

currentR = pathHandler.PopNode ();`

So that’s the two fixes I’m using right now to make the Partial state to be possible to reach. Let me know if my understanding of those places in code is correct or not.

The problem Nr.2 is: the partial paths don’t seem to be optimal, i.e. don’t always have the closest node as the end point. I’m using Diagonal Manhattan and here is what I get:

Red dot is searching for the possibly partial path to the green dot. The start and end nodes are marked with the big circles. Orange squares are unwalkable. Small blue dots mark the nodes of the returned partial path. Doesn’t look optimal at all.
I have not investigated the library’s code regarding this problem.

So, I need your help in solving those two problems.

Thanks,
Mindaugas

P.S. When registering into the forums there is a “Humanity Check” question like “How much is eight and five?” which doesn’t accept the answer as a word “thirteen” - only “13” makes the robot happy.

#2

I encountered the exact same problem with my test case. Trying to calculate a path to an enclosed object with calculatePartial set to truealways results in the error: “No open points, whole area searched”. I even traced it to the same spot in the code mrudokas pointed out.

#3

Sorry, the partial paths feature is not really implemented yet, it’s mostly unused alpha code in the current version.
I shouldn’t have released it into an official version.

“P.S. When registering into the forums there is a “Humanity Check” question like “How much is eight and five?” which doesn’t accept the answer as a word “thirteen” - only “13” makes the robot happy.”
:stuck_out_tongue: well, I am moving to a new forum software (discourse) hopefully in a few days which I don’t think will have that problem. Also, that will make the search on the forum actually useful.