[Ohrrpgce] SVN: james/8803 Pathfinding NPCs can now path around other NPCs and zone restrictions by

[Ralph Versteegen]

On 4 June 2017 at 03:07, Ralph Versteegen <teeemcee at gmail.com> wrote:

>
>
> On 3 June 2017 at 09:25, <subversion at hamsterrepublic.com> wrote:
>
>> james
>> 2017-06-02 14:25:38 -0700 (Fri, 02 Jun 2017)
>> 181
>> Pathfinding NPCs can now path around other NPCs and zone restrictions by
>> using npc_collision_check_at() instead of just check_wall_edges()
>>
>> This causes a noticeable performance hit
>> ---
>> U   wip/game.bas
>> U   wip/pathfinding.bas
>> U   wip/pathfinding.bi
>
>
> With gengcc=1 debug=0, the 100 NPC map now (barely) runs at 30fps for me.
>
> 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)
> 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).
> The only practical way to keep that map up-to-date would be member
> functions/properties.
>
> 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.
>
> Actually:

-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.

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