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

[Ralph Versteegen]

On 3 June 2017 at 16:43, James Paige <Bob at hamsterrepublic.com> wrote:

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

Yes.
I didn't know that in FB the result of ^ is always a float, but I checked
the generated assembly, as I often do.
GCC might have been able to optimise it away... but it's very difficult to
optimise floating pointer operations because even reordering additions can
change the result. (There's a gcc flag, -ffast-math to perform
optimisations anyway, but we don't use it... yet)


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

Yes. We use DIM SHARED everywhere! I think you're thinking of COMMON, which
was the QB way of defining globals. We switched from COMMON to EXTERN about
10 years ago because of a bug in an early version of FB.


>
> Anyway, I feel waaay better removing _pathfinder_obj entirely. I'll
> implement your suggestion of caching distance squared in the nodes
>
> ---
> James
>
> _______________________________________________
> Ohrrpgce mailing list
> ohrrpgce at lists.motherhamster.org
> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170603/0fba60a2/attachment.htm>