[Patch] Faster Route Calculation for Centralised Search

[knightly]

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 r2682		2503		327
Colin v5.1		252		105
Colin v4.3		625		127
Yoshi		7177		1928
1982		205		37
Wipi		53		22

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

[jamespetts]

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.

[jamespetts]

Knightly,

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

Code Select Expand


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


[sanna]

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

Code Select Expand


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 Expand

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

[knightly]

Hi Sanna

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

[sanna]

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!

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