Skip to main content ↑ ↓
Topic: [Patch] Faster Route Calculation for Centralised Search (Read 3860 times) previous topic - next topic

[Patch] Faster Route Calculation for Centralised Search

James,


I have made some changes to the centralised search code, and search speed is much faster. The commits have been uploaded to Github already, please check them out when you have time.

Here are the results on my PC :

Save Game    Before (ms)    After (ms)
Colin r26822503327
Colin v5.1252105
Colin v4.3625127
Yoshi71771928
198220537
Wipi5322

Note : Colin's 3 games are different games, not just saved/played in different versions of Simutrans.

Edit :
Forgot to mention that, as usual, the time recorded includes the time incurred in rebuilding all connexions (similar to destinations in Standard) and recalculating all paths.


Knightly

Re: [Patch] Faster Route Calculation for Centralised Search

Reply #1 –
Knightly,

thank you very much for your efforts - very much appreciated! As you will see, I have uploaded a proto-version of 7.0 onto Github. I am hoping to release this week-end, but may be delayed, because I am moving. Do you think that you could have a look into fixing the mess that I made trying to merge the latest trunk changes with the distributed pathing system?

Also, I notice that the network code (albeit not yet complete, I understand) is now merged with the trunk (although not yet with 7.0). When we last spoke, you were unsure of whether the centralised system would work with the network mode - could you look into that when you have time? For the release of 7.0, I will not synchronise with any trunk version later than the latest stable release version, but for versions > 7.0, I should like to be able to synchronise with the latest nightlies again, so it would be most helpful for this to be looked into. Thank you very much. I shall have a look at integrating your impressive looking changes now.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Re: [Patch] Faster Route Calculation for Centralised Search

Reply #2 –
Knightly,

I have just found that your patch causes a Linux compile error with GCC:

Code: [Select]
In file included from gui/colors.cc:13:
gui/../path_explorer.h:290: error: integer constant is too large for 'long' type

Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Re: [Patch] Faster Route Calculation for Centralised Search

Reply #3 –
Quote from: jamespetts – on
Knightly,
I have just found that your patch causes a Linux compile error with GCC:
Code: [Select]
In file included from gui/colors.cc:13:
gui/../path_explorer.h:290: error: integer constant is too large for 'long' type

As jamesspetts pointed out make fails on path_explorer.h:290
Code: [Select]
static const uint64 maximum_limit_64bit = 0xFFFFFFFFFFFFFFFF;
with error message path_explorer.h:290: error: integer constant is too large for ‘long’ type

I tested the "obvious" thing and added ULL (0xFFFFFFFFFFFFFFFFULL) to the hexadecimal and it seems to work (for a clean make at least); though I am pretty sure that needs to be conditional on os, right? Not all compilers support LL iirc. Furthermore I am not sure if that should really be ULL and not just LL (0xFFFFFFFFFFFFFFFFLL). With "work" I mean I can compile, start game, build a minimal busline and have p****angers transported; further than that I have not tested - so I do not know if the path explorer works as intended..

System: Debian/squeeze, gcc (Debian 4.3.4-5) 4.3.4, i386

Re: [Patch] Faster Route Calculation for Centralised Search

Reply #4 –
Hi Sanna :)

Quote from: sanna – on
I tested the "obvious" thing and added ULL (0xFFFFFFFFFFFFFFFFULL) to the hexadecimal and it seems to work (for a clean make at least); though I am pretty sure that needs to be conditional on os, right? Not all compilers support LL iirc. Furthermore I am not sure if that should really be ULL and not just LL (0xFFFFFFFFFFFFFFFFLL).

Actually I have uploaded a fix at my Github branch, which uses defined constants from limits.h. Using limits.h will hopefully avoid compiler-specific suffixes for "unsigned long long" variables. It has to be ULL because it is intended to be Unsigned.

P.S. I have tested the centralised search again after the release of v7.0, but found that search speed is for some unknown reason (unknown here means that it's not related to centralised search's code) slower than what I got when I improved the centralised search code based on v6.8 in the first place.

Knightly
 

Re: [Patch] Faster Route Calculation for Centralised Search

Reply #5 –
Quote from: Knightly – on
Actually I have uploaded a fix at my Github branch, which uses defined constants from limits.h. Using limits.h will hopefully avoid compiler-specific suffixes for "unsigned long long" variables.
Good to hear!
Quote from: Knightly – on
It has to be ULL because it is intended to be Unsigned.
That was my "guess" which is why I used ULL, but then I am no expert on such suffixes...