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

Sat Jun 10 11:33:03 PDT 2017

Yeah, part of my thought was if you check for too many things, you'll wash
out any optimization from all the conditional checking.

A configurable parameter would probably be best, then people making a game
can "choose your own framerate".

On Sat, Jun 10, 2017 at 11:31 AM, Ralph Versteegen <teeemcee at gmail.com>
wrote:

> 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-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/20170610/3e85df10/attachment.htm>