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

[James Paige]

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.

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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.motherhamster.org/pipermail/ohrrpgce-motherhamster.org/attachments/20170604/201d3479/attachment-0001.htm>