Add "shortest path to closest point"

[LispEngineer]

Hi there,

Thanks for your very nice library! It is very easy to use, although I modified Grid to use my underlying data structure directly.

I was wondering if you could add a version (e.g., GetPathToClosest() or an option to GetPath) that would return a path to the closest point to the destination, if the destination itself could not be reached, please. This would be useful, for example, when using it for pathfinding for monsters who are extremely numerous and are "mobbing" the player, assuming of course that only one monster can be in a cell and hence would BlockCell their locations.

The shortest path, if multiple end up equidistant, would be preferred, of course.

(Yes, I know a non-infinite cell cost could be used as well.)

Thanks,

Doug

[roy-t]

Hey Doug,

Great to hear that you're using the library. I think this is a good feature to add. I think the logic will be quite different than from the normal A* path finding so I will have to think about the implementation. But we can probably do something with keeping track of the path that got the closest 'as the crow flies' distance to the desired location. But there is a problem:

At the moment there is no distinction between a path blocked by an immovable object, or by an object that might move out of the way. So we could end up with a path that leads to a wall, meaning the agent will get near the object it desires to be, but even after fighting cannot reach it.

It would be great to hear from you if this limitation would still make the feature useful to you, or not.

[cclogg]

Posting this here instead of on #14
The general idea of 'best' path, from what I can tell, is taking the node that had the lowest H score in the case of no full path found. I just made some changes on my end to test this out and I think it works.

1. In Grid.cs, "GetPath" becomes:

public Position[] GetPath(Position start, Position end, Offset[] movementPattern, int iterationLimit, out bool fullPathNotFound)
{
        var current = PathFinder.FindPath(this, start, end, movementPattern, iterationLimit, out fullPathNotFound);
        [...]
}

2. In Pathfinder.cs "FindPath" method becomes:

public static List<Position> FindPath(Grid grid, Position start, Position end, Offset[] movementPattern, int iterationLimit, out bool fullPathNotFound)
{
            ClearStepList();

            fullPathNotFound = false;

            if (start == end)
            {
                return new List<Position> { start };
            }

            var head = new MinHeapNode(start, ManhattanDistance(start, end));
            MinHeapNode lowestHNode = head;
            var open = new MinHeap();
            open.Push(head);

            var costSoFar = new float[grid.DimX * grid.DimY];
            var cameFrom = new Position[grid.DimX * grid.DimY];
            
            while (open.HasNext() && iterationLimit > 0)
            {
                // Get the best candidate
                var currentNode = open.Pop();
                var current = currentNode.Position;
                MessageCurrent(current, PartiallyReconstructPath(grid, start, current, cameFrom));
                if (currentNode.ExpectedCost < lowestHNode.ExpectedCost)
                    lowestHNode = currentNode;
                if (current == end)
                {
                    return ReconstructPath(grid, start, end, cameFrom);
                }

                Step(grid, open, cameFrom, costSoFar, movementPattern, current, end);

                MessageClose(current);

                --iterationLimit;
            }

            fullPathNotFound = true;
            return ReconstructPath(grid, start, lowestHNode.Position, cameFrom);

            //return null;
        }

Also in my project, if the path kept coming back with "fullPathNotFound==true" (ie 2 in a row), then I would tell the unit to do something else, since obviously it can't make it to whatever it is trying to.

[roy-t]

Hey cclog, Thanks for this. I think its a great idea to implement it like something like this. Its gonna take me a few weeks to get back to this issue (very busy weeks here, I'm helping with the organisation of a conference). So I wanted to add this comment here to show its not forgotten :).

[roy-t]

I've thought about this more and more and I think every game has a different idea of "shortest to closest point", like what the closest point is (a closed door 10 meters away or an impenetrable wall 1 meter from the objective). For open areas that are congested with enemies its more clear. So I'm still not entirely sure what to do with this.

Maybe I can come up with an idea on how to give developers the tools to measure different types of closest points, and then let them plot a path there?

[LispEngineer]

Hi Roy,

This is an interesting idea. However, perhaps it would be best to hear from other users of your library to discern whether and how they might prefer this, rather than just taking one person's opinion.

I "solved" the problem "for now" by making nothing "impassible" (infinite value) but making game-impassible things very high path cost (like closed doors, other mobile objects) and letting the pathing algo do its thing and then not allowing the path to be followed at the appropriate point.

Cheers!