Pathfinding issue on portal crossover

[dmwever]

The following pathfinding is a failure, right on the portal line. The algorithm seems to prefer wrapping around black spaces when heading southwest across portal lines.

Here is a last comparison between a movement on the east side of the portal connection (ideal) and secondly the west side (longer).

[jere8184]

I'll take a look.

[jere8184]

@heinezen is there a reason we set the current cost of the start portals to zero instead of making it relative to the start position?

[heinezen]

The following pathfinding is a failure, right on the portal line. The algorithm seems to prefer wrapping around black spaces when heading southwest across portal lines.

For the first two results you got: This is because the A* portal search currently terminates immediately after finding a portal in the exit sector. I think the top portal is discovered first because it is closer to the target (orange). Therefore, the pathfinder terminates the portal search there immediately, instead of checking the other options. We could fix this by not terminating immediately and instead do a few more iterations to be sure that it's really the best result.

Here is a last comparison between a movement on the east side of the portal connection (ideal) and secondly the west side (longer).

The problem here is the calculation the heuristic cost for the portal nodes. The pathfinder uses the center position of the portal for its heuristic cost calculation. The ideal path in the second picture would use the portal on the right of the start node (green), but its center position is further down which makes it seem like the path is further from the target location than the portal going upwards.

[heinezen]

@heinezen is there a reason we set the current cost of the start portals to zero instead of making it relative to the start position?

It was previously done because that info was expensive to calculate, but we can actually get the info from start_integration_field in the get_path() function now if we want.

[heinezen]

Or using the heuristic cost as you did in your PR ^^

[jere8184]

Or using the heuristic cost as you did in your PR ^^

So my PR solves the first three results, but not the last one.

[jere8184]

Or using the heuristic cost as you did in your PR ^^

Would using start_integration_field be the better approach?

[heinezen]

@jere8184 Using the start integration field would only be marginably better I think. It's more accurate but also more complicated to check.

[heinezen]

So my PR solves the first three results, but not the last one.

The last one cannot be solved without changing the weighting of the distance cost. Currently, the distance is from portal center to portal center and this is not always accurate.

[jere8184]

So my PR solves the first three results, but not the last one.

The last one cannot be solved without changing the weighting of the distance cost. Currently, the distance is from portal center to portal center and this is not always accurate.

I'm not following. isn't the path chosen based on a minimum future_cost (heuristic + current), so the left portal is slightly closer to the start which equates to a slightly lower current_cost, but shouldn't it have a much higher heuristic cost?

[heinezen]

The heuristic cost ist the cost from portal center to target cell, so the left portals heuristic cost are lower because its center is closer to the target.

[jere8184]

the left portal being red and right portal being blue, where am I going wrong?

[heinezen]

@jere8184 With left portal, I mean the portal at the top of the start sector (i.e. red in your screenshot). With right portal, I mean the portal on the right of the start sector (i.e. not the blue portal you encircled but the one that the green cell is on)

[jere8184]

ahh, that makes sense. Should we look into addressing this?

[dmwever]

I also thought, looking at the current implementation, that there should probably be some method to implement a corner check so that a unit doesn't have pathfinding issues when the most direct approach would be through the corner.

Just imagine a unit navigating to that specific corner tile in-game.

[jere8184]

Maybe we can implement corner portals?

[heinezen]

@dmwever I'm not sure how corner checks would solve the issue at hand in this case. The problem that we see here is mostly an accuracy issue in the high-level pathfinder, i.e. the portal search, with the goal being that we find the sectors that we need to integrate for the low-level search. Going through the corners would make this process far more complicated for the low-level pathfinding, while only creating a benefit for specific edge cases in the high-level search.

For optimizing direct approaches, we already have LOS integration.

[jere8184]

S

ssue at hand in this case. The problem that we see here is mostly an accuracy issue in the high-level pathfinder, i.e. the portal search, with the goal being that we find the sectors that we need to integrate for the low-level search. Going through the corners would make this process far more complicated for the low-level pathfinding, while only creating a benefit for specific edge cases in the high-level search.

Wouldn't creating portals between sector corners solve the issue?

[heinezen]

@jere8184 Not sure what you mean. In the comment your citing, I was trying to explain why making portals between corners would make the pathfinding much more complicated, while only maybe solving a specific edge case.

[jere8184]

Oh okay no worries, I didn't read any of this thoroughly I guess a better question is what's next when it comes to this issue, are there any tasks?