<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sat, May 27, 2017 at 7:49 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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span class="gmail-">On 27 May 2017 at 11:35,  <span dir="ltr"><<a href="mailto:subversion@hamsterrepublic.com" target="_blank">subversion@hamsterrepublic.<wbr>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">james<br>
2017-05-26 16:35:19 -0700 (Fri, 26 May 2017)<br>
346<br>
Add an A* pathfinding for maps. NPCs can be set to chase the hero around obstacles.<br>
<br>
Currently only supports wallmap checking, I will be adding zone-checking and NPC-collision checking soon.<br>
<br>
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.<br>
---<br>
U   wip/SConscript<br>
U   wip/customsubs.rbas<br>
U   wip/game.bas<br>
A   wip/pathfinding.bas<br>
A   wip/<a href="http://pathfinding.bi" rel="noreferrer" target="_blank">pathfinding.bi</a><br>
U   wip/util.bas<br>
U   wip/<a href="http://util.bi" rel="noreferrer" target="_blank">util.bi</a><br>
U   wip/walkabouts.bas<br>
U   wip/<a href="http://walkabouts.bi" rel="noreferrer" target="_blank">walkabouts.bi</a><br></blockquote><div><br></div></span><div>Excellent!<br></div><div>I was going to remind you about one-way walls, but looking quickly at the code, it looks like they would just work automatically.<br><br></div><div>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.</div><div>Really, any stationary NPC should be treated more like a wall. But so should NPCs that are just stuck in a corridor.<br></div><div>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.<br></div></div></div></div></blockquote><div><br></div><div>[re-sending this reply too. I think the server hosting the mailing list had a full-disk last night, but dreamhost has fixed it by today]<br></div><div><br>I'll definitely treat NPCs with a non-moving movement type as walls, and I'll probably just go with giving moving NPCs a higher pathing cost but still treating them as if they are permeable. I don't think there is a perfect solution for this, so I am going to err on the side of a simple solution, and give it a bunch of testing. I was also thinking of giving them a higher cost when they are close (thus having less time to get out of the way) and a lower cost if they are far away.<br><br>Testing will show whether I need to add a bunch of configuration options for this or not.<br><br> </div><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 class="gmail_extra"><div class="gmail_quote"><div></div><div>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).</div></div></div></div></blockquote><div><br>I haven't done any profiling or stress-testing of this yet, but I plan to.<br><br>A cooldown time before an failed-path NPC tries to path again is a great idea. Not sure if I will make it configurable or just pick a reasonable default.<br><br>Right now I expect that most of my pathing time is wasted in re-allocating a new pathfinder object each time an NPC wants to use it.<br><br>I hope to have just one pathfinder object that all the NPCs on the map can share.<br><br>I read about some optimizations that are possible by using OPENED/CLOSED values that increment +2 on each new call rather than being constants, so I can just allocate the open/closed status array once per map, and only have to flush it clean once every billion calls.<br><br>I don't plan on actually trying that one until after I have some profiling tests of some kind set up so I can know how much it helps.<br><br> </div><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 class="gmail_extra"><div class="gmail_quote"><div>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.<br></div><div>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.<br></div><br></div></div></div></blockquote></div><br>I saw your other reply about v_sort<br><br>There is another reason I like open-list sorting that is unrelated to performance. I could have my sort-order resolve ties in a well-documented and minimally biased way. Right now I just favor the first closest step found, which has some directional biases based on the fact that I loop north/south/east/west around each next node.<br><br></div></div>