<div dir="ltr">Yeah, part of my thought was if you check for too many things, you'll wash out any optimization from all the conditional checking.<div><br></div><div>A configurable parameter would probably be best, then people making a game can "choose your own framerate".</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jun 10, 2017 at 11:31 AM, Ralph Versteegen <span dir="ltr"><<a href="mailto:teeemcee@gmail.com" target="_blank">teeemcee@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div>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:<br><br></div><div>-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.<br></div><div>-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.<br></div><div>-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.<br></div>-wallmaps or zones or npc data might also be changed by script.<br><br></div>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.<br><br>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.<br></div><div><div class="h5"><div><br></div><div><div><div><div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On 10 June 2017 at 10:36, Michael Kidder <span dir="ltr"><<a href="mailto:mkidder@gmail.com" target="_blank">mkidder@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">This is a long shot but maybe an optimization that could be done would be to interlace NPCs on every pathfinding check?<div><br></div><div>All odd ID NPCs one go round and even the next.</div><div><br></div><div>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.</div></div><div class="m_8025476488826168932m_-7105482104447381522HOEnZb"><div class="m_8025476488826168932m_-7105482104447381522h5"><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jun 9, 2017 at 3:52 PM, Ralph Versteegen <span dir="ltr"><<a href="mailto:teeemcee@gmail.com" target="_blank">teeemcee@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span>On 10 June 2017 at 08:50, Ralph Versteegen <span dir="ltr"><<a href="mailto:teeemcee@gmail.com" target="_blank">teeemcee@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div>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.<br>Strangely, I also couldn't get gprof to work.</div>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.<br></div></div></div></blockquote><div><br></div></span><div>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.<br></div><div><div class="m_8025476488826168932m_-7105482104447381522m_-478158318459661341h5"><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div></div><br></div>I might do a couple more things, but mostly I would say the optimisation is done.<div><div class="m_8025476488826168932m_-7105482104447381522m_-478158318459661341m_-947512351684091563h5"><br><div><div><div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On 10 June 2017 at 08:20, James Paige <span dir="ltr"><<a href="mailto:Bob@hamsterrepublic.com" target="_blank">Bob@hamsterrepublic.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div>That chart is cool! Did oprofile generate that?<br><br></div>I am really happy about how the A* performance is going right now. Thank you for all the optimizations :)<br></div></div><div class="m_8025476488826168932m_-7105482104447381522m_-478158318459661341m_-947512351684091563m_46814267973235938gmail-HOEnZb"><div class="m_8025476488826168932m_-7105482104447381522m_-478158318459661341m_-947512351684091563m_46814267973235938gmail-h5"><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jun 9, 2017 at 1:00 PM, Ralph Versteegen <span dir="ltr"><<a href="mailto:teeemcee@gmail.com" target="_blank">teeemcee@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><div><div>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.<br></div><div>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.<br></div><div><br>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.)<br><br></div>debug=2 gengcc=0: 34fps<br></div>debug=0 gengcc=0: 122fps<br></div>debug=0 gengcc=1: 195fps<br>debug=0 gengcc=1 arch=64: 245fps<br></div>(If I don't comment out that line, and instead run around with F11 enabled, I get ~500fps)<br></div><div class="m_8025476488826168932m_-7105482104447381522m_-478158318459661341m_-947512351684091563m_46814267973235938gmail-m_-2642271893063367002HOEnZb"><div class="m_8025476488826168932m_-7105482104447381522m_-478158318459661341m_-947512351684091563m_46814267973235938gmail-m_-2642271893063367002h5"><div class="gmail_extra"><br><div class="gmail_quote">On 9 June 2017 at 18:02, Ralph Versteegen <span dir="ltr"><<a href="mailto:teeemcee@gmail.com" target="_blank">teeemcee@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>This makes a big difference!<br>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.<br><br></div>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.<br></div><div class="m_8025476488826168932m_-7105482104447381522m_-478158318459661341m_-947512351684091563m_46814267973235938gmail-m_-2642271893063367002m_2265559051657535388HOEnZb"><div class="m_8025476488826168932m_-7105482104447381522m_-478158318459661341m_-947512351684091563m_46814267973235938gmail-m_-2642271893063367002m_2265559051657535388h5"><div class="gmail_extra"><br><div class="gmail_quote">On 9 June 2017 at 07:34, James Paige <span dir="ltr"><<a href="mailto:Bob@hamsterrepublic.com" target="_blank">Bob@hamsterrepublic.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Now the 100 npc map runs *almost* completely smoothly on my computer.<br></div><div class="m_8025476488826168932m_-7105482104447381522m_-478158318459661341m_-947512351684091563m_46814267973235938gmail-m_-2642271893063367002m_2265559051657535388m_182013937881666103HOEnZb"><div class="m_8025476488826168932m_-7105482104447381522m_-478158318459661341m_-947512351684091563m_46814267973235938gmail-m_-2642271893063367002m_2265559051657535388m_182013937881666103h5"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jun 8, 2017 at 12:33 PM, <span dir="ltr"><<a href="mailto:subversion@hamsterrepublic.com" target="_blank">subversion@hamsterrepublic.co<wbr>m</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">james<br>
2017-06-08 12:33:51 -0700 (Thu, 08 Jun 2017)<br>
195<br>
A* Pathfinding now caches NPC locations in an NPCCollisionCache object<br>
which is used for the whole pathfinding operation, rather that looping over every npc on every pathfinding collision check.<br>
---<br>
U wip/game.bas<br>
U wip/<a href="http://game.bi" rel="noreferrer" target="_blank">game.bi</a><br>
U wip/<a href="http://game_udts.bi" rel="noreferrer" target="_blank">game_udts.bi</a><br>
U wip/pathfinding.bas<br>
U wip/<a href="http://pathfinding.bi" rel="noreferrer" target="_blank">pathfinding.bi</a><br>
U wip/testgame/a-star.hss<br>
U wip/testgame/a-star.rpg<br>
______________________________<wbr>_________________<br>
Ohrrpgce mailing list<br>
<a href="mailto:ohrrpgce@lists.motherhamster.org" target="_blank">ohrrpgce@lists.motherhamster.o<wbr>rg</a><br>
<a href="http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org" rel="noreferrer" target="_blank">http://lists.motherhamster.org<wbr>/listinfo.cgi/ohrrpgce-motherh<wbr>amster.org</a><br>
</blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
Ohrrpgce mailing list<br>
<a href="mailto:ohrrpgce@lists.motherhamster.org" target="_blank">ohrrpgce@lists.motherhamster.o<wbr>rg</a><br>
<a href="http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org" rel="noreferrer" target="_blank">http://lists.motherhamster.org<wbr>/listinfo.cgi/ohrrpgce-motherh<wbr>amster.org</a><br>
<br></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
Ohrrpgce mailing list<br>
<a href="mailto:ohrrpgce@lists.motherhamster.org" target="_blank">ohrrpgce@lists.motherhamster.o<wbr>rg</a><br>
<a href="http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org" rel="noreferrer" target="_blank">http://lists.motherhamster.org<wbr>/listinfo.cgi/ohrrpgce-motherh<wbr>amster.org</a><br>
<br></blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
Ohrrpgce mailing list<br>
<a href="mailto:ohrrpgce@lists.motherhamster.org" target="_blank">ohrrpgce@lists.motherhamster.o<wbr>rg</a><br>
<a href="http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org" rel="noreferrer" target="_blank">http://lists.motherhamster.org<wbr>/listinfo.cgi/ohrrpgce-motherh<wbr>amster.org</a><br>
<br></blockquote></div><br></div></div></div></div></div></div></div></div></div>
</blockquote></div></div></div><br></div></div>
<br>______________________________<wbr>_________________<br>
Ohrrpgce mailing list<br>
<a href="mailto:ohrrpgce@lists.motherhamster.org" target="_blank">ohrrpgce@lists.motherhamster.o<wbr>rg</a><br>
<a href="http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org" rel="noreferrer" target="_blank">http://lists.motherhamster.org<wbr>/listinfo.cgi/ohrrpgce-motherh<wbr>amster.org</a><br>
<br></blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
Ohrrpgce mailing list<br>
<a href="mailto:ohrrpgce@lists.motherhamster.org" target="_blank">ohrrpgce@lists.motherhamster.o<wbr>rg</a><br>
<a href="http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org" rel="noreferrer" target="_blank">http://lists.motherhamster.org<wbr>/listinfo.cgi/ohrrpgce-motherh<wbr>amster.org</a><br>
<br></blockquote></div><br></div></div></div></div></div></div></div></div></div></div>
<br>______________________________<wbr>_________________<br>
Ohrrpgce mailing list<br>
<a href="mailto:ohrrpgce@lists.motherhamster.org">ohrrpgce@lists.motherhamster.<wbr>org</a><br>
<a href="http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org" rel="noreferrer" target="_blank">http://lists.motherhamster.<wbr>org/listinfo.cgi/ohrrpgce-<wbr>motherhamster.org</a><br>
<br></blockquote></div><br></div>