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

[James Paige]

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.


>
>
>>
>> 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 :)

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)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170529/5ed1b080/attachment.htm>