[Ohrrpgce] SVN: james/8801 Implement AStarPathfinder.maxdist which limits how far the A* flood-fill

[Ralph Versteegen]

On 3 June 2017 at 08:52, <subversion at hamsterrepublic.com> wrote:

> james
> 2017-06-02 13:52:32 -0700 (Fri, 02 Jun 2017)
> 231
> Implement AStarPathfinder.maxdist which limits how far the A* flood-fill
> is allowed to go before giving up.
> Currently set to 30 tiles (manhattan distance)
>
> I'll definitely want this to be customizable on an NPC-by-NPC basis later.
> ---
> U   wip/game.bas
> U   wip/pathfinding.bas
> U   wip/util.bas
> U   wip/util.bi
>

I think it would be better to place a limit on the number of open+closed
nodes instead (aka number of tiles explored). That way, if there is a cheap
path, it can be found, and the limit is directly proportional to the amount
of time spent. Although it might be less intuitive how far "1000 tiles"
gets you, it is intuitive that 2000 tried twice as hard as 1000, and
setting the limit to 100000 may be a bad thing although maxdist 100 may not
sound bad.

In fact, I found that this maxdist limit actually hugely slows down
pathfinding when there is a path. If you are 32 tiles from the NPC, then
the pathfinding can't reach you, but explores all other possible tiles in
range (which is up to about 1800, which is really slow now, but should be
OK once pathing is optimised)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170603/8d59ff0e/attachment.htm>