[Ohrrpgce] SVN: james/8760 Add an A* pathfinding for maps. NPCs can be set to chase the hero around

James Paige Bob at hamsterrepublic.com
Sun May 28 07:52:57 PDT 2017

On Sat, May 27, 2017 at 7:49 AM, Ralph Versteegen <teeemcee at gmail.com>

> On 27 May 2017 at 11:35, <subversion at hamsterrepublic.com> wrote:
>> james
>> 2017-05-26 16:35:19 -0700 (Fri, 26 May 2017)
>> 346
>> Add an A* pathfinding for maps. NPCs can be set to chase the hero around
>> obstacles.
>> Currently only supports wallmap checking, I will be adding zone-checking
>> and NPC-collision checking soon.
>> You can test this already, but the NPC movement type is marked
>> "EXPERIMENTAL" because the behavior will definitely change a bit before I
>> am done with it.
>> ---
>> U   wip/SConscript
>> U   wip/customsubs.rbas
>> U   wip/game.bas
>> A   wip/pathfinding.bas
>> A   wip/pathfinding.bi
>> U   wip/util.bas
>> U   wip/util.bi
>> U   wip/walkabouts.bas
>> U   wip/walkabouts.bi
> Excellent!
> I was going to remind you about one-way walls, but looking quickly at the
> code, it looks like they would just work automatically.
> How will you handle tiles blocked by other NPCs? Just give them a high
> cost? I don't know a good solution for this. If the cost isn't high enough,
> then the NPC won't go a different way while there's an NPC in the way if
> the other way is an extra X files.
> Really, any stationary NPC should be treated more like a wall. But so
> should NPCs that are just stuck in a corridor.
> Maaaaybe this could be handled by giving each NPC a dynamic path cost. For
> every tick that another NPC is trying to get past it (its path goes
> straight through the blocking NPC), its cost increases. Finally the pathing
> NPC gets so sick of waiting that it goes another way. This could happen
> before the pathing NPC ever reaches the blocking NPC, since the cost can be
> updated for each tick that the pathing NPC moves. I don't know what the
> condition would be for decreasing the dynamic cost. Maybe something like
> when the NPC moves off someone's path. If an NPC gains a really high cost,
> then computed paths across the map with fluctuate wildly when the high-cost
> NPC steps in and out of a corridor.

[re-sending this reply too. I think the server hosting the mailing list had
a full-disk last night, but dreamhost has fixed it by today]

I'll definitely treat NPCs with a non-moving movement type as walls, and
I'll probably just go with giving moving NPCs a higher pathing cost but
still treating them as if they are permeable. I don't think there is a
perfect solution for this, so I am going to err on the side of a simple
solution, and give it a bunch of testing. I was also thinking of giving
them a higher cost when they are close (thus having less time to get out of
the way) and a lower cost if they are far away.

Testing will show whether I need to add a bunch of configuration options
for this or not.

> Have you tried running this on larger maps? In particular when you place
> some NPC that can't reach the hero? I image that in that case the NPC would
> try to repath every tick. We're going to have to stop that from happening.
> Maybe delay for half a second before trying again. It's also possible to
> cancel further pathing attempts until either the map changes or the hero
> crosses a one-way wall (approximation: when the hero/target changes).

I haven't done any profiling or stress-testing of this yet, but I plan to.

A cooldown time before an failed-path NPC tries to path again is a great
idea. Not sure if I will make it configurable or just pick a reasonable

Right now I expect that most of my pathing time is wasted in re-allocating
a new pathfinder object each time an NPC wants to use it.

I hope to have just one pathfinder object that all the NPCs on the map can

I read about some optimizations that are possible by using OPENED/CLOSED
values that increment +2 on each new call rather than being constants, so I
can just allocate the open/closed status array once per map, and only have
to flush it clean once every billion calls.

I don't plan on actually trying that one until after I have some profiling
tests of some kind set up so I can know how much it helps.

> I notice that how you determine the 'best' node of the openlist is very
> inefficient. Instead, you should keep openlist sorted so you can pop off
> the end (popping off the front is slow). You can use v_sort to sort the
> list, but first you need to define a compare function. See vector.bas for
> examples.
> Using v_sort on an almost-sorted array is still less efficient than it
> could be (linear instead of logarithm time). I have some C code for a
> priority queue, so I could add a couple functions for using a vector as a
> priority queue, and we can switch to that later.
I saw your other reply about v_sort

There is another reason I like open-list sorting that is unrelated to
performance. I could have my sort-order resolve ties in a well-documented
and minimally biased way. Right now I just favor the first closest step
found, which has some directional biases based on the fact that I loop
north/south/east/west around each next node.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170528/cb31e0e2/attachment-0001.htm>

More information about the Ohrrpgce mailing list