[Ohrrpgce] SVN: james/8760 Add an A* pathfinding for maps. NPCs can be set to chase the hero around

[Ralph Versteegen]

On 28 May 2017 at 02:49, Ralph Versteegen <teeemcee at gmail.com> wrote:

>
>
> On 27 May 2017 at 11:35, <subversion at hamsterrepublic.com> wrote:
>
>> james
>> 2017-05-26 16:35:19 -0700 (Fri, 26 May 2017)
>> 346
>> Add an A* pathfinding for maps. NPCs can be set to chase the hero around
>> obstacles.
>>
>> Currently only supports wallmap checking, I will be adding zone-checking
>> and NPC-collision checking soon.
>>
>> You can test this already, but the NPC movement type is marked
>> "EXPERIMENTAL" because the behavior will definitely change a bit before I
>> am done with it.
>> ---
>> U   wip/SConscript
>> U   wip/customsubs.rbas
>> U   wip/game.bas
>> A   wip/pathfinding.bas
>> A   wip/pathfinding.bi
>> U   wip/util.bas
>> U   wip/util.bi
>> U   wip/walkabouts.bas
>> U   wip/walkabouts.bi
>>
>
> Excellent!
> I was going to remind you about one-way walls, but looking quickly at the
> code, it looks like they would just work automatically.
>
> How will you handle tiles blocked by other NPCs? Just give them a high
> cost? I don't know a good solution for this. If the cost isn't high enough,
> then the NPC won't go a different way while there's an NPC in the way if
> the other way is an extra X files.
> Really, any stationary NPC should be treated more like a wall. But so
> should NPCs that are just stuck in a corridor.
> Maaaaybe this could be handled by giving each NPC a dynamic path cost. For
> every tick that another NPC is trying to get past it (its path goes
> straight through the blocking NPC), its cost increases. Finally the pathing
> NPC gets so sick of waiting that it goes another way. This could happen
> before the pathing NPC ever reaches the blocking NPC, since the cost can be
> updated for each tick that the pathing NPC moves. I don't know what the
> condition would be for decreasing the dynamic cost. Maybe something like
> when the NPC moves off someone's path. If an NPC gains a really high cost,
> then computed paths across the map with fluctuate wildly when the high-cost
> NPC steps in and out of a corridor.
>
> Have you tried running this on larger maps? In particular when you place
> some NPC that can't reach the hero? I image that in that case the NPC would
> try to repath every tick. We're going to have to stop that from happening.
> Maybe delay for half a second before trying again. It's also possible to
> cancel further pathing attempts until either the map changes or the hero
> crosses a one-way wall (approximation: when the hero/target changes).
>
> I notice that how you determine the 'best' node of the openlist is very
> inefficient. Instead, you should keep openlist sorted so you can pop off
> the end (popping off the front is slow). You can use v_sort to sort the
> list, but first you need to define a compare function. See vector.bas for
> examples.
> Using v_sort on an almost-sorted array is still less efficient than it
> could be (linear instead of logarithm time). I have some C code for a
> priority queue, so I could add a couple functions for using a vector as a
> priority queue, and we can switch to that later.
>

Errr... I was imagining that searching for the 'best' node was quadratic
time, but it's only linear. That's still not good, but it's similar to
re-sorting. The advantage of sorting however is that it allows popping from
the end... however you need to shuffle items around to sort anyway, so you
gain nothing!
So, my bad. Don't bother with v_sort. I'll implement a priority queue at
some point.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170528/20c7407a/attachment-0001.htm>