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

[Ralph Versteegen]

On 30 May 2017 at 06:11, James Paige <Bob at hamsterrepublic.com> wrote:

>
>
> On Sun, May 28, 2017 at 8:40 PM, Ralph Versteegen <teeemcee at gmail.com>
> wrote:
>
>>
>>
>> On 29 May 2017 at 02:52, James Paige <Bob at hamsterrepublic.com> wrote:
>>
>>>
>>>
>>> On Sat, May 27, 2017 at 7:49 AM, Ralph Versteegen <teeemcee at gmail.com>
>>> wrote:
>>>
>>>>
>>>>
>>>> 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.
>>>
>>
>> But there are many reasons why an NPC not set to Standing Still won't
>> move. So I think it is better to use a counter for how long it's been since
>> the NPC moved rather than rely on the move type. You could try to add logic
>> to determine all the reasons an NPC isn't going to move in future, too.
>>
>
> That is true. I don't want to get too complicated, but a
> time-since-last-move timer would be pretty easy.
>
>
>
>> NPCs could also be set to being pushy, meaning they will swap places with
>> another NPC they're trying to get past, provided that both NPCs would be
>> otherwise able to make that move. This is sometimes used in roguelikes so
>> that a boss enemy pushes its way to the front of a crowd instead of
>> becoming stuck.
>>
>
> Hmm... That is a cool idea. I'll save that one for later, but I like it.
>
> We might also want heroes to be able to push-path past certain NPCs too
> eventually.
>

Of course, a far easier thing to do is to add an NPC setting to let the NPC
move through other NPCs. I would like to split up the NPC activation type
into separate activation (never, use only, touch or use, step-on or use)
and obstruction (obstruct all, obstruct npcs, obstruct heroes (well,
technically just the leader), ghost) settings.

Speaking of caterpillar party obstruction quirks, A* would allow much nice
caterpillar party handling!


>
>
>>
>>
>>>
>>> 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
>>> default.
>>>
>>> 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 share.
>>>
>>> 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 think you're looking at the wrong thing. On a large map, when computing
>> very short paths, the array allocation time would dominate, but it's going
>> to be a negligibly small part of the worst case running time, when there is
>> no path.
>> Note that the line "status as AStarNodeStatus = AStarNodeStatus.EMPTY"
>> causes FB to create a constructor for the type, which slows down redimming
>> and deleting the array. With -gen gcc I found that gcc is able to optimise
>> it, so the slowdown is only 50%. With -gen gas, the slow down is enormous,
>> over 200x slower. Taking 1.5ms on a map with 100k tiles (the max allowed
>> map size).
>> Without the constructor, the redim only takes 8us on my machine for a
>> 100k map (regardless of gen gcc/gas). It could even be sped up more, by
>> reducing the size of AStarNode.
>>
>> (I also noticed that without the constructor, compiling for x86_64 made
>> the redimming 10x-80x slower on my machine, even after I made sure the UDT
>> size was the same and if I use gen gcc both ways. It appears to be a libc
>> problem: all the time is spent in calloc, but the codepath used on x86_64
>> seems to be very slow. Probably it's inappropriate for my CPU; it's using
>> some fancy new instructions I've never heard of.)
>>
>> (BTW, I would like to switch all releases and nightly builds to gen gcc,
>> because the binaries are faster, smaller, and bugs that currently only
>> affect -gen gcc will be found faster.
>> (Also, the currently Windows nightly builds are huge. The .exes are
>> aronud twice the size that they used to be before switching to the new
>> build machine. I haven't looked into why yet.))
>>
>> Anyway, looking at the code (haven't profiled), I think the real
>> bottlenecks are check_wall_edges, function call overhead including passing
>> around AStarNodes, searching for the best node, and v_append and v_remove.
>> Of course, the later few will be to blame for all runtime the worst case.
>> getnode is called excessively. I never optimised vectors to avoid calling
>> realloc every time that the vector is resized. I've been meaning to.
>>
>>
> After I get all the behavior correct, then I can start worrying about
> performance. I can't remember if I have ever done real profiling on
> freebasic code before or not-- but if not, I'll have to learn :)
>

It's pretty easy:
scons profile=1
./ohrrpgce-game
gprof ohrrpgce-game gmon.out
or
gprof --line ohrrpgce-game gmon.out
To see a line-by-line annotation.

You might also be interested in https://github.com/jrfonseca/gprof2dot  (I
haven't tried it)

There's another tool, pprof, part of Google performance tools, which is
very similar to gprof but has nice visualisation features built in, and
doesn't add any overhead to the program. You use it by linking to a library
libprofiler. One nice advantage it has over gprof is that it shows time
spent in libc functions.



>
> defaulting to gen gcc builds sounds great.
>
>
>
>>
>> Oh, I notice that guess_cost_after_node doesn't work on wrapping maps.
>>
>
> Yep! Making pathing work correctly on wrapping maps is the next thing on
> my to-do list.
>
>
>
>>
>>>
>>>
>>>> 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.
>>>
>>
>> So how would you break ties?
>>
>>
> Well, right now anything with the same manhattan distance is a tie.
> I could break ties by comparing distance squared.
> That still leaves some true ties, and I would probably break those by
> biasing in favor of the direction the NPC is currently facing at the time
> of the pathing (unless I think of something better)
>

Tie-breaking by Euclidean (ie squared) distance is an interesting idea. I
suppose that will cause the path to go diagonally (in a staircase movement)
when possible, which could seem more natural. You don't want to make
comparison too expensive, though.


>
>
>
>
>
>
> _______________________________________________
> Ohrrpgce mailing list
> ohrrpgce at lists.motherhamster.org
> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170530/9b7038aa/attachment-0001.htm>