[Ohrrpgce] SVN: james/8832 A* Pathfinding now caches NPC locations in an NPCCollisionCache object

Sat Jun 10 09:31:02 PDT 2017

Currently as an NPC moves to a destination a path is calculated every step
(so, for the default walk speed, every 5 ticks), the first step is used and
the rest is discarded. Keeping the path instead of always recalculating it
would be the biggest time saving we can achieve. But it's quite tricky:

-if you're chasing a moving target then by the time that you move one step
the destination may have moved as well. But if it's far away then the
previous path must still be pretty good. We could compare the distance to
the target with the distance that the target has moved to decide when to
recompute.
-due to zones and one-way walls it's possible that a small movement of the
target makes a big difference, but this doesn't matter much.
-other npcs are constantly moving and changing the available paths. But we
don't want the path to change dramatically every step anyway. It's more
important to path around nearby NPCs than those in the distance.
Potentially we could track when nearby NPCs move and recompute immediately.
-wallmaps or zones or npc data might also be changed by script.

So we could do something modest like make several steps before
recalculating the path, provided we're still far away from the destination,
and the original and current destinations are within a few tiles of each
other. but even this will lead to noticeable artifacts: suppose there's an
rolling rock immediately between the hero and a chasing npc to the north,
three tiles away from the npc. If the npc computes a path and follows it
for three steps it'll go south-south-west  even if the rock is long gone.

A bunch of special logic seems like a lot of extra complexity, and if
pathfinding is fast enough anyway I wouldn't bother. (Keeping the paths and
using dumb logic would be easy, enough.) However, most of these testcases
have small maps; we need more realistic testcases. (James, could you add
more NPCs and walls to the big test map? I don't want to edit the file
while you are.) And the current 1000 tile limit could easily be too little
on a large map, though should be configurable.

On 10 June 2017 at 10:36, Michael Kidder <mkidder at gmail.com> wrote:

> This is a long shot but maybe an optimization that could be done would be
> to interlace NPCs on every pathfinding check?
>
> All odd ID NPCs one go round and even the next.
>
> My thought here is there's some time when NPCs are moving between tiles,
> so it's not like they need to update every single frame. You could skip it
> for ones in between tiles but I'm not sure if that'd make you lose your
> gains from doing the check in the first place.
>
> On Fri, Jun 9, 2017 at 3:52 PM, Ralph Versteegen <teeemcee at gmail.com>
> wrote:
>
>>
>>
>> On 10 June 2017 at 08:50, Ralph Versteegen <teeemcee at gmail.com> wrote:
>>
>>> I used pprof, part of gperftools, to generate that. I couldn't get it to
>>> work on 32 bit builds, so had to run it on 64 bit ones.
>>> Strangely, I also couldn't get gprof to work.
>>> I've only just figured out how to get oprofile to reconstruct the
>>> callgraph. It probably can construct similar graphs out of the box; it
>>> includes a bunch of tools with heaps of options. It can even show you spent
>>> on each line of the kernel source while your program was executing! And one
>>> advantage it has is that its timing resolution is far far better than the
>>> other profilers, because it times context switches and other events instead
>>> of using a statistical sampler with a low 100Hz resolution. So it produces
>>> detailed results in a second instead of needing to leave the program
>>> running a while.
>>>
>>
>> Err, it does still do statistical sampling of what the program is doing,
>> but it uses a high resolution interrupt instead of a SIGALARM signal
>> handler.
>>
>>
>>>
>>> I might do a couple more things, but mostly I would say the optimisation
>>> is done.
>>>
>>>
>>> On 10 June 2017 at 08:20, James Paige <Bob at hamsterrepublic.com> wrote:
>>>
>>>> That chart is cool! Did oprofile generate that?
>>>>
>>>> I am really happy about how the A* performance is going right now.
>>>> Thank you for all the optimizations :)
>>>>
>>>> On Fri, Jun 9, 2017 at 1:00 PM, Ralph Versteegen <teeemcee at gmail.com>
>>>> wrote:
>>>>
>>>>> At this point, I'm having trouble speeding up pathfinding any further.
>>>>> The main obvious remaining step I see is to split up AStarNode into two
>>>>> UDTs.
>>>>> Profiling (see attachment) shows time is spent fairly evenly all over
>>>>> the place, largely in functions where it's hard to see any alternative way
>>>>> to write the function.
>>>>>
>>>>> As for differences between different builds, here's a benchmark: I
>>>>> commented out "npcmove_walk_ahead(npci)" in npcmove_pathfinding_chase after
>>>>> calculating the path so the npcs never move, run with --runfast -z 1, and
>>>>> then go to the 100 npc map and don't move. (Note that this means the NPCs
>>>>> attempt to repath every tick, except those in the interior, which is most
>>>>> of them.)
>>>>>
>>>>> debug=2 gengcc=0: 34fps
>>>>> debug=0 gengcc=0: 122fps
>>>>> debug=0 gengcc=1: 195fps
>>>>> debug=0 gengcc=1 arch=64: 245fps
>>>>> (If I don't comment out that line, and instead run around with F11
>>>>> enabled, I get ~500fps)
>>>>>
>>>>> On 9 June 2017 at 18:02, Ralph Versteegen <teeemcee at gmail.com> wrote:
>>>>>
>>>>>> This makes a big difference!
>>>>>> Amazingly pathfinding seems to be almost 10x faster if you compile
>>>>>> with debug=0; the 100 NPC map only takes about 20% CPU time for me in that
>>>>>> case, even without gengcc. I'm rather shocked that the difference is that
>>>>>> much, since gengcc only adds overhead on each function call and pointer
>>>>>> access, but there aren't that many of those.
>>>>>>
>>>>>> I found another profiling tool I'd installed on my system, oprofile.
>>>>>> This one is very fancy indeed, it can simultaneously profile the whole
>>>>>> system. Anyway, it shows that all the runtime is inside fb_TlsGetCtx and
>>>>>> libpthread. I didn't realise that the -exx overhead when you call a
>>>>>> function (calls to fb_ErrorSetFuncName and fb_ErrorSetFuncName) store the
>>>>>> current function name in thread local storage.
>>>>>>
>>>>>> On 9 June 2017 at 07:34, James Paige <Bob at hamsterrepublic.com> wrote:
>>>>>>
>>>>>>> Now the 100 npc map runs *almost* completely smoothly on my computer.
>>>>>>>
>>>>>>> On Thu, Jun 8, 2017 at 12:33 PM, <subversion at hamsterrepublic.com>
>>>>>>> wrote:
>>>>>>>
>>>>>>>> james
>>>>>>>> 2017-06-08 12:33:51 -0700 (Thu, 08 Jun 2017)
>>>>>>>> 195
>>>>>>>> A* Pathfinding now caches NPC locations in an NPCCollisionCache
>>>>>>>> object
>>>>>>>> which is used for the whole pathfinding operation, rather that
>>>>>>>> looping over every npc on every pathfinding collision check.
>>>>>>>> ---
>>>>>>>> U   wip/game.bas
>>>>>>>> U   wip/game.bi
>>>>>>>> U   wip/game_udts.bi
>>>>>>>> U   wip/pathfinding.bas
>>>>>>>> U   wip/pathfinding.bi
>>>>>>>> U   wip/testgame/a-star.hss
>>>>>>>> U   wip/testgame/a-star.rpg
>>>>>>>> _______________________________________________
>>>>>>>> Ohrrpgce mailing list
>>>>>>>> ohrrpgce at lists.motherhamster.org
>>>>>>>> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherh
>>>>>>>> amster.org
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> Ohrrpgce mailing list
>>>>>>> ohrrpgce at lists.motherhamster.org
>>>>>>> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherh
>>>>>>> amster.org
>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> Ohrrpgce mailing list
>>>>> ohrrpgce at lists.motherhamster.org
>>>>> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>>>>>
>>>>>
>>>>
>>>> _______________________________________________
>>>> Ohrrpgce mailing list
>>>> ohrrpgce at lists.motherhamster.org
>>>> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>>>>
>>>>
>>>
>>
>> _______________________________________________
>> Ohrrpgce mailing list
>> ohrrpgce at lists.motherhamster.org
>> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>>
>>
>
> _______________________________________________
> 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/20170611/c9aaf337/attachment-0001.htm>