[Ohrrpgce] SVN: james/8798 Pathfinding now breaks ties with distance squared

[James Paige]

On Fri, Jun 2, 2017 at 8:45 PM, Ralph Versteegen <teeemcee at gmail.com> wrote:

>
>
> On 3 June 2017 at 15:28, Ralph Versteegen <teeemcee at gmail.com> wrote:
>
>>
>>
>> On 3 June 2017 at 07:02, <subversion at hamsterrepublic.com> wrote:
>>
>>> james
>>> 2017-06-02 12:02:15 -0700 (Fri, 02 Jun 2017)
>>> 50
>>> Pathfinding now breaks ties with distance squared
>>> ---
>>> U   wip/pathfinding.bas
>>> U   wip/pathfinding.bi
>>
>>
>> You didn't notice that I added v_heappush and v_heappop?
>>
>> Also, I didn't notice before that your cost_before_node function is
>> insane. You need to store the cost of the node in the node, not recompute
>> it constantly. That is why pathfinding is so incredibly slow.
>>
>
> (That, and the use of v_sort, which amplifies the problem)
>
> Also, the result of guess_cost_after_node should also be stored in the
> node.
>
> Also, why did you make _pathfinder_obj a global instead of a file-local
> (shared) variable?
>
> Also, you could get rid of _pathfinder_obj altogether, by storing
> cost_a/cost_b from close_node_compare/open_node_compare in the node as
> well, to avoid recomputing that too. This has its own costs, but FB does
> squaring using floating point and pow(), so avoiding doing that repeatedly
> should also be a good improvement.
>
>
Oh, that is interesting!

So does that mean I would get better performance from A * A + B * B than I
would with A ^ 2 + B ^ 2 ?

As for _pathfinder_obj, I had forgotten the correct syntax for a file local
global... I actually not even sure now... is it DIM SHARED?

I've been using EXTERN so long, the only other global stuff I could
remember is my feverish fighting with global scope back in the days when
the code exceeded QB's internal linker limits, and i had not discovered
freelink.exe yet (or whatever it was called)

Anyway, I feel waaay better removing _pathfinder_obj entirely. I'll
implement your suggestion of caching distance squared in the nodes

---
James
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170602/439577a1/attachment.htm>