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

Fri Jun 9 15:36:06 PDT 2017

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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170609/822a25bc/attachment.htm>