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

[Ralph Versteegen]

On 5 June 2017 at 05:07, James Paige <Bob at hamsterrepublic.com> wrote:

>
>
> On Sat, Jun 3, 2017 at 2:17 AM, Ralph Versteegen <teeemcee at gmail.com>
> wrote:
>
>>
>>
>> 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.
>>
>
> COMMON! That was the one! I remember moving big chunks of code into subs
> in other modules and globalling everything with COMMON to bypass compiler
> out-of memory errors, and then later having to move most of those COMMON
> globals into ridiculously long argument lists to get past linker out of
> memory errors.
>

Oh, so that's why everything had so many arguments! I thought you just
didn't like globals - but silly me, stubbornly avoiding globals would have
been some kind of industry best practice, so that can't have been the
reason!


>
> And I have no dang excuse for forgetting DIM SHARED, I shoulda remembered
> that one. ;)
>
> Oh, well, glad it is all moot now anywa :)
>
>
>>
>>
>>>
>>> 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
>>>
>>>
>>
>> _______________________________________________
>> Ohrrpgce mailing list
>> ohrrpgce at lists.motherhamster.org
>> http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
>>
>>
>
> _______________________________________________
> 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/20170605/d3d40ec1/attachment.htm>