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

[James Paige]

On Friday, June 2, 2017, Ralph Versteegen <teeemcee at gmail.com> wrote:

>
>
> On 3 June 2017 at 08:52, <subversion at hamsterrepublic.com
> <javascript:_e(%7B%7D,'cvml','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)
>
>
I think you are right. I had picked max manhattan distance from start
because being able to get around a 30 block obstacle made sense to me, but
your point about an tiles-explored limit being directly proportional is
even more important. I'll change it, when I get a chance.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170602/6fc6753e/attachment.htm>