<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Jun 4, 2017 at 10:09 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"><br><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="h5">On 4 June 2017 at 03:07, 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 3 June 2017 at 09:25,  <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-02 14:25:38 -0700 (Fri, 02 Jun 2017)<br>
181<br>
Pathfinding NPCs can now path around other NPCs and zone restrictions by using npc_collision_check_at() instead of just check_wall_edges()<br>
<br>
This causes a noticeable performance hit<br>
---<br>
U   wip/game.bas<br>
U   wip/pathfinding.bas<br>
U   wip/<a href="http://pathfinding.bi" rel="noreferrer" target="_blank">pathfinding.bi</a></blockquote></span><div><br>With gengcc=1 debug=0, the 100 NPC map now (barely) runs at 30fps for me. <br></div><div><br>npc_collision_check_at does a whole bunch of stuff, but the slowest part in generally will be checking for collisions with all other npcs. (I did profile, this is where most of time is spent on the 100 slime map)<br></div><div>We could speed this up by using a map with one integer per tile which says how many obstructing npcs there are at that tile. wrapcollision just calculates the effective tile for both thngs passed into it and checks for equality. (The half-way solution would be to cache that position).<br></div><div>The only practical way to keep that map up-to-date would be member functions/properties.<br><br></div><div>This isn't really critical right now, but even since I played Mutant Warzone (a Megazeux game) by Robot/8bit, I've wanted to be able to have thousands of NPCs on the map at once. Eventually.<br></div></div><br></div></div></blockquote></div></div><div>Actually:<br><br></div><div>-Rather than use a map of integers, it would be simpler to use a hashmap or even a sorted list as a lookup table of "obstructed tiles". And that way you can also find out which NPC is at that location.<br><br></div><div>-Whatever data structure is used, for A* there isn't a need to keep it constantly correct as NPCs move. Instead it could just be rebuilt every time that an A* path is calculated. Doing so would cost about as much as doing collision checking for a single tile the way it's done now! Not having a permanent lookup table just means it can't be used for regular NPC movement but that is so much faster than A* that it's probably not worth optimising until there are several thousand of NPCs.<br></div></div><br></div></div></blockquote><div><br></div><div>Yeah, I think I will cache NPC obstruction data in AStarPathfinder.nodes() and update it once at the beginning of each .calculate()<br><br></div><div>I'll try it out when I get a chance. <br></div></div><br></div></div>