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

[James Paige]

On Sun, Jun 4, 2017 at 10:20 AM, Ralph Versteegen <teeemcee at gmail.com>
wrote:

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

Haha! Yep. The limit of my exposure to the "avoid globals" best practice
back in those days was maybe a line or two in a GWBASIC textbook that I
definitely ignored if it was even there.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170604/18d1042a/attachment-0001.htm>