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

[James Paige]

On Sun, Jun 4, 2017 at 10:09 AM, Ralph Versteegen <teeemcee at gmail.com>
wrote:

>
>
> 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.
>
>
Yeah, I think I will cache NPC obstruction data in AStarPathfinder.nodes()
and update it once at the beginning of each .calculate()

I'll try it out when I get a chance.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170604/de4e0233/attachment.htm>