[Patch] A New, Centralized, Steppable Path Searching System

Topic: [Patch] A New, Centralized, Steppable Path Searching System (Read 10323 times) previous topic - next topic

[Patch] A New, Centralized, Steppable Path Searching System

July 05, 2009, 04:13:18 pm

Hi James,

Currently, the path searching system is using a distributed approach (searches are done at each [origin] halt) with resumable Dijkstra search. As you have stated yourself, most searches are clustered immediately after the paths become stale (e.g. bi-monthly refresh). That's why you try to spread the load by defaulting the periodic refresh to bi-monthly, rebuilding connexions and recalculating paths in different months, and limiting updates to affected halts only, so as to reduce the problem of UI unresponsiveness. The downside, however, is that the game is not very responsive to transport network changes -- it takes quite some time before a change is fully reflected.

That's why I tried to change refresh to update all paths and reroute all goods (limited to certain goods category though) when players make changes to their transportation network. The result is not very good in large games, causing UI unresponsiveness during the refresh. I then tried to create a system whereby the signal to refresh is slowly propagated from the source of change (the affected halts). I have however abandoned it when it was almost finished and start with a new path searching system.

This path searching system centralizes path search and is steppable -- that is, processing is spread across the steps. It uses Floyd-Warshall Algorithm. The principle is like this : for each halt H, check it against all origin-destination pairs; if going from origin to destination via H is faster, update path info. This involves a 3 levels of loop :

for each halt H
   for each origin O
   for each destination D
   if from O to D via H is faster, update path info of O => D

So, the number of iterations involved is the *cube* of the number of halts. Actually, the complexity (H ^ 3) is worse than performing exhaustive Dijkstra search on each (origin) halt. However, since the work done within the innermost loop is usually trivial and fast, and that this algorithm doesn't involve complex data structures, the actual search time is not bad.

Still, I want to reduce the number of iterations. I first tried to limit search to halts having connexions of certain ware category. E.g. If we are refreshing bulk goods paths, only halts with bulk goods connexions are considered. This largely reduced the iterations involved, especially for ware categories other than pax and mail. Later, I realised that the outermost loop corresponds to transfer halts, so I isolate the transfer halts and use them for the outermost loop. Although this depends on how players develop their transport network, the save games I tested so far has search time reduced by over 50%.

Here are the test results of 4 save games which you also have tried before :

Save Game	Distributed	Approach	Centralized	Approach
	Time (ms)	Memory (MB)	Time (ms)	Memory (MB)
1982.sve	810	155	226	103
ferndale.sve	82	97	6	81
wipi.sve	233	126	61	96
colin.sve	5088	272	686	120

The tests compare the processing time for rebuilding all connexions and recalculating all paths, for all categories. To be fair, when testing the distributed approach, all path hashtables and open lists are cleared before timing, and calculate_paths() are directly invoked with a dummy halt to simulate exhaustive search in one call, and the single INT_CHECK() call is also removed from calculate_paths(). As for centralized approach, the 4 phases are combined into 1.

Of course, these results do not necessarily show that centralized approach must always be faster than distributed approach in all cases. So, I leave the distributed system unchanged and both systems can co-exist peacefully together. If you want the centralized approach, set "Refresh routes instantly" option in Display Menu to true; if you want back the distributed approach, set that option to false.

Unlike Dijkstra search, Floyd-Warshall search is not directed -- that is, you have to perform complete search before you can find a single path. That's why, you will notice that, when loading large games with "Refresh routes instantly" option on, there will be a progress bar showing the progress of path calculation. This is a downside, but luckily the search is rather fast for most games.

As for memory consumption, you can see that it uses a lot less memory. The reason is simply that it only creates one sorted_heap (tailored-made to work directly with halthandle) and one H x H matrix for each ware category, where H is the number of halts with connexions of that particular category. There are also some auxilliary arrays, but they are small and are deleted right after use. Please note, however, that when new search is initiated, a new heap and a new matrix will be created during the search, and remains in memory until it replaces the old heap and old matrix, which are then deallocated.

Apart from being centralized, it is also steppable as mentioned above. This will spread the load of refreshing across as many steps as necessary so as not to slow down the game or reduce its responsiveness. I do not preset the number of iterations per step, as the optimal figure varies from PC to PC. Instead, it will dynamically adjust the number of iterations to be performed per step in each phase. (Note: the figure for path exploration phase is iterations per ms, not yet multiplied by the preset limit mentioned below) However, the average milliseconds per step is preset currently at 32ms, as the usual screen refresh rate is 22-25 fps, meaning that there are roughly 40ms (= 1000ms / 25) for us to work between each screen refresh [ or call to INT_CHECK() ]. Since processing speed fluctuate from step to step, 32ms should allow for cases where speed is occasionally slowed down and the step takes longer to run.

A special note. The success of this system depends on the granularity of dr_time() which returns the current time in ms since system boot up. There is no problem for SDL versions or X11 versions, as granularity is down to 1ms. But for Allegro versions, the callback to update the relevant figure is currently set at 5ms, so the centralized system may not function very well, albeit workable. I don't know if it will seriously drag down system performance, so I haven't changed that 5ms to a smaller figure. For Windows/GDI, the default implementation of dr_time() invokes timeGetTime(), which on my PC has a granularity of 15-16ms. This will definitely undermine the centralized system. I can increase granularity by calling timeBeginPeriod(1), but that has the side effect of causing the thread scheduler to switch tasks more frequently, which will in turn reduce overall system performance. To work around, I use performance counter instead. But not all CPUs support performance counter. So, I have made it such that if performance counter is available, use it; otherwise, use timeGetTime(). In case you want to use GDI version and performance counter is not available, please don't use the centralized system.

Incidentally, I have fixed a bug in get_connexions(c), removed superfluous checks in get_connexions(), get_path_to() and calculate_paths(), removed many unused commented code blocks for clarity, moved the speed determination code out of the loop in add_connexion(), and changed simline_t::recalc_catg_index() to refresh only removed/added ware categories. All these changes and the centralized, steppable path searching system have already been pushed to my forked branch at Github. Please take a look when you have time. Thank you

!

Edit :

Forgot to mention that, in the centralized system, global refresh for all categories will be done at the start of each month, after the lines and convoys have rolled their monthly statistics.

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #1 – July 05, 2009, 04:19:40 pm

This is most intriguing - I must confess, I don't know what a Floyd-Warshall Algorithm is, but it certainly sounds as if you've been working hard! Does this have any impact on the gameplay (i.e., the outcomes of the routing) itself, or does it just improve performance?

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #2 – July 05, 2009, 04:57:48 pm

Quote from: jamespetts – on July 05, 2009, 04:19:40 pm

This is most intriguing - I must confess, I don't know what a Floyd-Warshall Algorithm is, but it certainly sounds as if you've been working hard! Does this have any impact on the gameplay (i.e., the outcomes of the routing) itself, or does it just improve performance?

Hi James,

The EXE by Knightly is a must for you to incorporate in the game. I have tested it and continue to do so. The game lag has almost disappeared. In the SDL version there is (sometimes) a slight jerkiness when scrolling the map, in the GDI version there is, or does not appear, to be any lag at all.
I have tried these two versions with my large SVE (of which you have a copy) and with a new game that I have started and been building for about 5 hours. The only problem I found (which incidentally was Knightly's fault) was the Electrification bug which Knightly kindly brought to your attention.

I will keep building on this current game and will let Knightly know via this forum, and by email, of any problems I may, or may not, find.

Colin

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #3 – July 05, 2009, 10:58:13 pm

Colin,

thank you for your feedback on that, and for testing Knightly's patch! If it really makes routing so much faster, it is very interesting indeed. Do you find that the routing gives the same outcomes, or do you find that p****engers/goods take different routes with this new system?

Incidentally, the electrification bug wasn't Knightly's fault :-) I think that it was one of my changes after integrating a commit from the Simutrans-Standard trunk.

Knightly: I shall await with great interest your profiling results!

Edit: Oops - didn't see that they had already been posted... shall read them with interest now!

Edit 2: Right, I have read all that now. Very interesting! The statistics are impressive. It is also very useful that you have left both systems side by side with the GUI toggle (although we may have to change the label for that button to reflect the new significance of selecting it). A few questions if I may:

As asked before, does this change in any way what routes are found, or does it get to exactly the same results in a different way?
What exactly is the significance of the granularity of the system timer? How will inaccuracies affect performance? It was not clear from what you wrote above why exactly it is important to have accurate real-time calculations and timings (perhaps I am missing something, in which case, apologies).
How common are CPUs without the performance counter? Would there be some benefit of an indication in the UI of the GDI version if a PC does not have it?
Does the fine grained counting system work for the Windows SDL version even for CPUs without the performance counter?
Does the standard Macintosh version use SDL or Allegro?
How does the Floyd-Warshall Algorithm differ from Dijkstra's Algorithm?
Could this method allow comfort to be taken into account in either: (1) routing choices; or (2) time tolerance calculations?

Thank you very much again for your excellent work - this is extremely interesting. A big improvement to performance of the routing system would be extremely welcome, especially for those who like to play with larger maps or have older hardware. Thank you very much for your efforts!

Edit 3: One further question:

Does this patch change the way in which I need to implement other routing related features that have been discussed recently (particularly, the maximum time tolerance and the more sophisticated approach to the best line/convoy that you suggested elsewhere)?

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #4 – July 06, 2009, 07:30:47 am

Quote from: jamespetts – on July 05, 2009, 10:58:13 pm

Colin,

thank you for your feedback on that, and for testing Knightly's patch! If it really makes routing so much faster, it is very interesting indeed. Do you find that the routing gives the same outcomes, or do you find that p****engers/goods take different routes with this new system?

Well on my original SVE I haven't noticed p****engers or goods taking different routes. I think that most of my goods, especially trains, are guided by signals so can not deviate from the designated route. Where, and I think this is what you mean, there are two different modes of transport, say Trucks and Trains carrying the same goods to the one consumer, does one or the other take preference? I can't answer that because to be honest, I haven't looked for it. I don't have too many of those situations. I normally only use trucks, or ships, when I have a situation where a can not get rail access.

I've started a new game and when I get to the industrial stage I'll try and incorporate different means of transport.

The main thing I have noticed is that, any lag is so minor as to not be a nuisance. It mainly occurs when scrolling the map.I will have to wait until Knightly incorporates his EXE into v4.6. Incidentally I have noticed another bug in 4.5 regarding the removal of land that has been built up by the AI to accommodate
a building

I was aware that it was not Knightly problem with the electrification. My current amount of money is $106,150,313,870.60 I

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #5 – July 06, 2009, 07:46:12 am

Colin,

thank you for your reply. Can you tell me any more about the bug relating to land (perhaps in a new thread)? Can you reproduce it in Simutrans-Standard?

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #6 – July 06, 2009, 08:29:11 am

Sorry this is a double post because I'm having trouble adding another line to the post below. This preview page keeps blotting out the next line when I try to type it.

Anyway what I was going to say was,

I have noticed that when the AI builds a structure on what was a lower level, the slope removal tool removes the block but leaves a / slope which is hard to remove. I've found that I have to remove everything around the site then use the land build tool to make a normal slope, then the land destroy tool to remove that piece of land.

Hope this makes sense, because it sounds double dutch to me and I wrote it.

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #7 – July 06, 2009, 08:31:11 am

Quote from: jamespetts – on July 06, 2009, 07:46:12 am

Colin,

thank you for your reply. Can you tell me any more about the bug relating to land (perhaps in a new thread)? Can you reproduce it in Simutrans-Standard?

James your post came in as I was typing the below. I haven't tried it in Standard so I'm not sure. It's also difficult to describe. Also I don't currently have a game going in Standard.

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #8 – July 06, 2009, 08:44:30 am

Why not using the check_for _interrupt system for updates, as it is meant to be. Also this implementation of the routing system is very close to the original one, where pathes were also gradually updated after a change. Also the monthly update was tried before simutrans 87 something (and was then discarded to allow larger games).

I am still wondering that 120MB for routing is just quite a lot memory compared to the size of actual map wiht all objects ...

Here my test map (yoshi87-2-101.sve) http://simutrans-germany.com/files/upload/yoshi87-2-101.sve

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #9 – July 06, 2009, 09:15:42 am

James,

You are most welcome, James.

Here are the answers to your questions :

( 1 )
The same routes should be found as if distributed approach recalculates using the most up-to-date info. There is only one difference : if you look into add_connexion(), average speed for the first month using the centralized approach always uses your estimate formula. The reason for this is that, centralized approach rebuild connexions in steps, thus if average speed for the first month changes over the step, the journey times may not be consistent among halts of the same line. Since average speed may be different, the calculated paths may be a little bit different too.

( 2 )
The new system will time the duration of execution of each phase using dr_time(). For instance, if current phase performs 800 iterations in 100ms across some steps, iterations per ms = 800 / 100 = 8. This is then multiplied by the preset limit of 32ms to arrive at 256 iterations for the future execution of a step in this phase. The more inaccurate dr_time() is, the more the projected iteration count will be overestimated or underestimated. Seriously overestimated count will cause the next step to run too long and affects UI responsiveness; seriously underestimated count will cause the next step to do too little work.

( 3 )
I also want to know.

But I suppose this has existed for many years. As for UI indication, I can add a conditional compilation block in colors.cc to change the colour of "Refresh routes instantly" to red if performance counter is unavailable. But I don't know about other platforms and have no access to them.

( 4 )
Thanks for asking this question. I have taken a look at the code of SDL v1.2.13, and its underlying implementation originally supports both (A) timeGetTime() with timeBeginPeriod(1) and (B) performance counter. But for some reason, the SDL developers have completely abandoned option (B), stating in a comment that "Apparently there are problems with QPC on Win2K". So, I think I will change my strategy : add an option to use performance counter if available, but default to using timeGetTime() with timeBeginPeriod(1). I will change change both GDI and SDL versions of simsys source files. As I have said above, timeBeginPeriod(1) will cause the task schedule to switch task more frequently and reduce overall system performance, so if performance counter is available and functions well on the system, we should use it.

( 5 )
I am sorry that I don't know anything about Mactintosh. Maybe you can ask Wernieman who has successfully compiled Mac versions of Simutrans?

( 6 )
Dijkstra algorithm is a single-sourced shortest paths (SSSP) algorithm, which starts search from a single origin node (pops a node from min heap, explores adjacent nodes of the currently examined node, pushes suitable adjacent nodes into min heap, loop again), until the target is found. Floyd-Warshall algorithm, on the other hand, is an all-pairs shortest paths (APSP) algorithm, which does only one thing : determine if going from origin to target via a certain potential transfer is faster; if yes, update path info to reflect that the transfer is used. It performs operations on an origin x destination matrix.

( 7 )
If you also agree that in the near future (after feature freeze is released) we should try to add journey cost/fare in addition to journey time in path search, I think comfort do not need to be separately considered, because a more comfortable, luxurious convoy will charge higher, right

? As for travelling time tolerance, I think it is not checked during path search; rather, it should be checked in find_route() and/or step_p****agiere() to see if a calculated path is within tolerable time limit.

( 8 )
As I have said, I have left your distributed system intact, so any new feature should not be affected. Of course, if there is a new feature that affects path searching code, we have to revise both the distributed system and the centralized system. I will continue to maintain the centralized system, so please feel free to tell me what path-search-related feature you want to add, and I will incorporate it also in the centralized system

Edit :

Prissi,

Thank you very much for your comments.

(1)
For check_for_interrupt system, do you mean INT_CHECK()/interrupt_check()? My understanding is that, INT_CHECK() calls only improves screen refresh (fps) as sync_step() is triggered, but it doesn't improve UI interaction (like response to clicks/drags). Or have I missed or mistaken something?

(2)
It is not possible to have a fair comparison between Simutrans Standard and Simutrans Experimental in terms of memory consumption. At least, ST STD only stores a list of reachable halts, but ST EXP uses a hashtable to store reachable halts together with journey time, waiting time, and the best line/convoy. Waiting times also need a separate minivec too. I can't state all, for there are many new features, each of which may need extra memory.

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #10 – July 06, 2009, 09:24:46 am

Quote from: prissi – on July 06, 2009, 08:44:30 am

Here my test map (yoshi87-2-101.sve) http://simutrans-germany.com/files/upload/yoshi87-2-101.sve

Hi Prissi,
I've just been looking at your sve I like the layout it's all extremely industrious. One thing I don't understand though. All the trains arriving at Emmerich Zweig Bf fully loaded are stuck, because, it seems that they are not unloading, so they are all piling up one behind the other. Is this a result of having the "Just in time" switch on?
Regards
Colin

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #11 – July 06, 2009, 03:28:35 pm

This save is from 87.xx version. I removed some stuff to have it workable on simutrans standard, but depending on just in time and overcrowding switches train may easily stuck somewhere. Also the game was saved without overcrowding of factories, since that was only introduced in 88.xx THus some factories are very overcrowded. Also some new engines are a little bit longre than their original. All this can lead to aparent or actual stucking.

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #12 – July 06, 2009, 09:34:24 pm

Hi James,

I have fixed a couple of problems with the centralized path search, changed the names for the instant path refresh option (instant_path_refresh is changed into path_searching_approach) and added a read-only option for performance counter (changeable only via simuconf.tab, and not saved in save game).

I have also revised the relevant portion of simuconf.tab :

Code: [Select]


# This setting determines whether Simutrans calculates and refreshes paths 
# using a distributed or centralized approach. The distributed approach 
# refreshes only the paths directly (but not indirectly) affected by any 
# changes instantly, and waits until the end of the next path refresh period
# (usually two months: see max_rerouting_interval) before refreshing.
# The centralized approach starts to refresh all paths of any affected ware 
# category immediately upon change, but does so only gradually to avoid making 
# the game unresponsive; it also refreshes all paths at the start of each month.
#
# 0 = distributed approach (default); 
# 1 = centralized approach
#
path_searching_approach = 0

# This setting is Windows specific. It determines whether multimedia timer
# functions or performance counter functions are used for returning system
# time in dr_time(). Using multimedia timer functions causes the thread
# scheduler to switch tasks more frequently, reducing overall system
# performance. Using performance counter functions will not cause this
# problem, but performance counter is not supported by all CPUs and it
# may not work normally on all windows platforms. If performance counter is 
# not supported, setting this option to 1 will have no effect.
# Note : Never include this option in pakset simuconf.tab
#
# 0 = multimedia timer functions (default)
# 1 = performance counter functions
#
system_time_functions = 0;

Edit 1 :

For those who want to try out the new path searching system but don't want to compile source code, you may download the executable here. Only Windows versions are provided.

Edit 2 :

James, another minor fix is pushed to my forked branch in Github. Please check it out when you have time.

Knightly

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #13 – July 07, 2009, 08:39:15 pm

Knightly,

thank you very much for all your help :-) I have been testing your new system - my initial tests seem to confirm your and Colin's findings that your new system is much faster - well done!

Would it be possible for you to write the part of the help text for the display menu relating to your new features? I have changed all reference to "ware" to "goods" ("ware" in this sense is not an English word: its use in the code comes from German) for clarity. I have also changed the word "centralized" from the American to the English spelling, "centralised". Here is the existing help text for the "display" menu (already modified by me previously):

Code: [Select]

<title>Display Settings Help</title>

<h1><strong>Display Settings</strong></h1>

<p>
<strong>Display Settings</strong>lets you control how the game appears, and provides information on computer performance.
</p>
<p>
Click on the display button in the <a href="options.txt">Game Options</a> menu to open the <strong>Display Settings</strong> window.
</p>
<p>
Click on the square buttons to select options (the button is indented when the option is selected), or use the <a href="mouse.txt">arrow buttons</a> to adjust settings:
</p>
<p>
- <em>Show grid:</em> shows the lines between the individual tiles. This can be useful when terraforming.
</p>
<p>
- <em>Underground view:</em> reveals beneath the ground to show tunnels and underground transport networks.
</p>
<p>
- <em>Day and night change:</em> if this is enabled, the game window will slowly cycle through dawn, day, dusk and night, giving graphical variety. If unselected, the game will be permantently set to a particular time of day, depending on the <strong>brightness</strong> setting.
</p>
<p>
- <em>Brightness:</em> affects the ambient light used in the main game window. The higher the number, the darker.
</p>
<p>
- <em>Brightness:</em>sets how light/dark view of game appears; lower number to darken; too low or high values produce problems; use <a href="keys.txt">[+]</a> to increase value over 0.
</p>
<p>
- <em>Scroll Inverse:</em> reverses direction of scroll in the main game window in <a href="window.txt">Game Window</a>.
</p>
<p>
- <em>Scroll Speed:</em> sets speed of scrolling in the main game window.
</p>
<p>
- <em>Transparent instead of hidden:</em> objects that are selected as hidden will instead appear see-through.
</p>
<p>
- <em>Hide trees:</em> all trees will either be made very small, or made transparent, depending on how the last option is set. 
</p>
<p>
- <em>Building settings:</em> determines which, if any, buildings are hidden from view. If <strong>no buildings hidden</strong> is selected, then all buildings are visible. If <strong>hide city buildings</strong> is selected, then only player-built buildings, town halls, industries and tourist attractions will be visible. If <strong>hide all buildings</strong> is selected, then all buildings apart from station/stop buildings will be hidden, but town halls will be highlighted in green, monuments will be highlighted in pink, tourist attractions in yellow, and industries in red.
</p>
<p>
- <em>Transparent station coverage:</em> shows the catchment area of stops/stations as transparent, rather than as a grid.
</p>
<p>
- <em>Show station coverage:</em> displays the catchment area for each station in the main game window. Use the <a href="keys.txt">[V]</a> key to toggle this display.
</p>
<p>
- <em>Show station names:</em> toggle whether the name of each station is displayed in the main game window.
</p>
<p>
- <em>Show waiting bars:</em> toggle whether the miniature bar graphs showing the proportion of waiting goods/p****engers as against the station's total capacity is displayed in the main map window.
</p>
<p>
- <em>Pedestrians in towns:</em> toggles whether pedestrians that appear in <a href="citywindow.txt">urban areas</a> are displayed.
</p>
<p>
- <em>Pedestrians at stops:</em> toggles whether pedestrians that appear when a vehicle arrives at a <a href="station.txt">stop</a> are displayed.
</p>
<p>
- <em>Traffic density:</em> sets volume of private car traffic displayed in the main game window in <a href="citywindow.txt">urban areas</a>. Note that this setting only alters the number of cars actually visible in the main game window: it does not alter the number of <a href="privatecar.txt">private car</a> trips generated, nor the level of congestion in urban areas, or any other aspect of the simulation itself. 
</p>
<p>
- <em>Convoy tool tips:</em> customises the amount of information displayed about convoys in the main game window.
</p>
<p>
<em>Tip</em>: More options and default values for when Simutrans starts can be changed in the simuconf.tab file, located in /simutrans/config/.
</p>
<br>
<p>
<strong>Display Information:</strong>
</p>
<p>
Below these settings, information is shown on computer performance when running Simutrans.<br>
If numbers (usually white) are red or yellow you may need to change your settings.<br>
Changes in rate that time p****es in game, <a href="window.txt">T</a>, (using Fast Forward  >> icon at top of the main game window, or [,]/ [.]) may change number colour.
</p>
<p>
<em>Frame Time:</em> The first number is intended time between frames; second number is actual time between frames.
</p>
<p>
<em>Idle:</em> When above 0, the computer has capacity to run other software without adversely impacting the performance of Simutrans.
</p>
<p>
<em>
FPS:</em> Higher values mean vehicles appear to move more smoothly. If number remains red, the computer is too slow for current settings (try reducing the size of the main game window).
</p>
<p>
<em>Simloops:</em> If this number remains red, the computer is too slow for current settings - try a smaller map with fewer urban areas.
</p>

Thank you again for all your hard work on this :-)

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #14 – July 08, 2009, 06:32:09 am

Hi James,

Thank you for testing.

Regarding "ware" vs "goods", I have no objection at all. As for "centralized" vs "centralised", I thought you (who is from UK) would prefer "centralized" more

So did you change the variable names in the code too? If yes, please kindly pushed your changes to Github, because I may want to make other changes to the code and thus need to keep my local code up-to-date. If not, I can do it myself.

Incidentally, it would be most helpful if you always pushes your latest changes to Github. In that way, Bernd and I will know what you have done and avoid duplicated efforts or incompatible commits.

Quote

Would it be possible for you to write the part of the help text for the display menu relating to your new features?

Sure, no problem. Currently I have 2 optmizations to the new system and after I have finished with them, I will write the help text.

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #15 – July 08, 2009, 01:53:36 pm

Not tested-- yet i want to say that this seems a great patch. keep on going!

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #16 – July 08, 2009, 08:02:53 pm

Knightly,

actually, the UK spellings use "ise", and the US spellings "ize". I have not changed the variable names at this stage - do you think that it would be worthwhile to do so?

As to GitHub pushing other than at releases, the reason that I do not do that at present is that the automatic Linux nightlies will then build a new version, and that version will be linked as the version to download from the "How to get Simutrans-Experimental" post: I do not really want people using half-baked versions, as that is likely to cause confusion with bug reporting. I have currently not had the time to think of the most effective solution to this issue - it might be that, long-term, it is worth moving to a joint system of nightly and release builds, but that relies on somebody (possibly Wernieman) producing nightly builds for all platforms for Simutrans-Experimental, which is not done at present. Any thoughts on how to organise this effectively would be appreciated.

One other thing regarding the path searching system: have a look at Prissi's comments on this thread about the network mode in development. I very much want Simutrans-Experimental to be compatible with the multi-player network mode in due course. One thing that Prissi said is that one ought not call "time functions" in the code. I am not sure precisely what he means, but I am wondering whether this would impact on this code.

Thank you very much for agreeing to write the relevant part of the help texts. I shall look forward also to your further optimisations :-) Thank you again for all your hard work.

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #17 – July 08, 2009, 10:58:56 pm

@ Fabio : Thanks a lot for your encouragement!

@ James :

Quote

the UK spellings use "ise", and the US spellings "ize"

Strangely, in my Oxford Advanced Learner's Dictionary (by Oxford University Press), -ize is consistently used instead of -ise.

Quote

I have not changed the variable names at this stage

Then I will take care of them myself

Quote

As to GitHub pushing other than at releases, the reason that I do not do that at present is that the automatic Linux nightlies

I see, forget my request then.

Quote

One thing that Prissi said is that one ought not call "time functions" in the code. I am not sure precisely what he means, but I am wondering whether this would impact on this code.

When I designed the centralised system, I did not have network mode in mind. I am not sure whether the centralised system will break under network mode or not -- although dr_time() is used to determine iteration limit, each dr_time() pair (start time and stop time) is called within the same step (not sync_step()) and within the same function, so maybe it still works. But even if it works, when various changes are being made by multiple players across the network, the current design may no longer be efficient. I don't know how Prissi's network mode works, so I can't give further comments on this issue.

Prissi suggested above and in your recommended thread to use INT_CHECK(), but I don't think I will try that approach. The reasons are,
(1) I don't know how many INT_CHECK() calls are being made in one world step, and any developer can add or remove INT_CHECK() calls later, so I don't have any control over it
(2) It is difficult to decide how much work to perform when INT_CHECK() calls the search step function. If it is too much, UI interactivity will be compromised; too little, and search on large maps will take unreasonably long time. And don't forget, processing speed is system dependent. What is just right on my PC, may be way too much/little on yours.
(3) If I spread the workload over many INT_CHECK() calls, performance will definitely be much worse than when I centralise search in one place and do more work together in one step within a single function call. Overhead of repeated function call of search step will surely eat away the efficiency.

IMHO, even if centralised search does not work in network mode, you can always switch back to distributed search. If minor changes can be made to make centralised search compatible with network mode, I will be glad to incorporate them; but if significant changes are required (say, use of dr_time() is completely banned), I am afraid there is nothing I can do to make it work.

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #18 – July 08, 2009, 11:12:08 pm

Knightly,

thank you for your response :-) I have no idea why the Oxford Advanced Learners' Dictionary uses "ize" - that is definitely not the normal British English variant. As to the network mode - could you perhaps liaise with Prissi to see what, if anything, needs to be done to make your system compatible with network mode? It would be very good if it was possible for the two to work together, since your system seems to be very efficient and superior to the code that I wrote for that function, and the difference in performance is quite noticeable for some people, so it would be very good if they could work together.

Thank you as ever for all your help :-)

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #19 – July 09, 2009, 03:28:34 pm

AFAIK, -ize is also accepted in the UK, although it may look a bit American... I'd prefer to use -ize though, there's an interesting link to read here Wiki. Good patch by the way! Must've taken a long time to get it done!

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #20 – July 09, 2009, 07:14:58 pm

Quote from: jamespetts – on July 08, 2009, 08:02:53 pm

As to GitHub pushing other than at releases, the reason that I do not do that at present is that the automatic Linux nightlies will then build a new version, and that version will be linked as the version to download from the "How to get Simutrans-Experimental" post: I do not really want people using half-baked versions, as that is likely to cause confusion with bug reporting. I have currently not had the time to think of the most effective solution to this issue - it might be that, long-term, it is worth moving to a joint system of nightly and release builds, but that relies on somebody (possibly Wernieman) producing nightly builds for all platforms for Simutrans-Experimental, which is not done at present. Any thoughts on how to organise this effectively would be appreciated.

What about using branches?
Say: you use master for your daily work (and often pushes) and release is used used for releases (which you push only on release time). In first instance werniermann could use the releases branch for his nighlty builds (and you to keep the current link in "how to )
download...")
At a later stage (hopefully not to far in the future) the nightly build site could be changed so it uses master for -real- nightly builds and release for release builds... (and you change your link to the latest of this)

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #21 – July 12, 2009, 06:17:36 pm

James,

Seems that you are not patient enough to wait for me before releasing v5.0.

I have finished my 2 optimisations and pushed them up to Github.

As for online help text, here it is :

Code: [Select]

<title>Display Settings Help</title>

<h1><strong>Display Settings</strong></h1>

<p>
<strong>Display Settings</strong>lets you control how the game appears, and provides information on computer performance.
</p>
<p>
Click on the display button in the <a href="options.txt">Game Options</a> menu to open the <strong>Display Settings</strong> window.
</p>
<p>
Click on the square buttons to select options (the button is indented when the option is selected), or use the <a href="mouse.txt">arrow buttons</a> to adjust settings:
</p>
<p>
- <em>Show grid:</em> shows the lines between the individual tiles. This can be useful when terraforming.
</p>
<p>
- <em>Underground view:</em> reveals beneath the ground to show tunnels and underground transport networks.
</p>
<p>
- <em>Day and night change:</em> if this is enabled, the game window will slowly cycle through dawn, day, dusk and night, giving graphical variety. If unselected, the game will be permantently set to a particular time of day, depending on the <strong>brightness</strong> setting.
</p>
<p>
- <em>Brightness:</em> affects the ambient light used in the main game window. The higher the number, the darker.
</p>
<p>
- <em>Brightness:</em>sets how light/dark view of game appears; lower number to darken; too low or high values produce problems; use <a href="keys.txt">[+]</a> to increase value over 0.
</p>
<p>
- <em>Scroll Inverse:</em> reverses direction of scroll in the main game window in <a href="window.txt">Game Window</a>.
</p>
<p>
- <em>Scroll Speed:</em> sets speed of scrolling in the main game window.
</p>
<p>
- <em>Transparent instead of hidden:</em> objects that are selected as hidden will instead appear see-through.
</p>
<p>
- <em>Hide trees:</em> all trees will either be made very small, or made transparent, depending on how the last option is set. 
</p>
<p>
- <em>Building settings:</em> determines which, if any, buildings are hidden from view. If <strong>no buildings hidden</strong> is selected, then all buildings are visible. If <strong>hide city buildings</strong> is selected, then only player-built buildings, town halls, industries and tourist attractions will be visible. If <strong>hide all buildings</strong> is selected, then all buildings apart from station/stop buildings will be hidden, but town halls will be highlighted in green, monuments will be highlighted in pink, tourist attractions in yellow, and industries in red.
</p>
<p>
- <em>Transparent station coverage:</em> shows the catchment area of stops/stations as transparent, rather than as a grid.
</p>
<p>
- <em>Show station coverage:</em> displays the catchment area for each station in the main game window. Use the <a href="keys.txt">[V]</a> key to toggle this display.
</p>
<p>
- <em>Show station names:</em> toggle whether the name of each station is displayed in the main game window.
</p>
<p>
- <em>Show waiting bars:</em> toggle whether the miniature bar graphs showing the proportion of waiting goods/p****engers as against the station's total capacity is displayed in the main map window.
</p>
<p>
- <em>Pedestrians in towns:</em> toggles whether pedestrians that appear in <a href="citywindow.txt">urban areas</a> are displayed.
</p>
<p>
- <em>Pedestrians at stops:</em> toggles whether pedestrians that appear when a vehicle arrives at a <a href="station.txt">stop</a> are displayed.
</p>
<p>
- <em>Traffic density:</em> sets volume of private car traffic displayed in the main game window in <a href="citywindow.txt">urban areas</a>. Note that this setting only alters the number of cars actually visible in the main game window: it does not alter the number of <a href="privatecar.txt">private car</a> trips generated, nor the level of congestion in urban areas, or any other aspect of the simulation itself. 
</p>
<p>
- <em>Convoy tool tips:</em> customises the amount of information displayed about convoys in the main game window.
</p>
<p>
<em>Tip</em>: More options and default values for when Simutrans starts can be changed in the simuconf.tab file, located in /simutrans/config/.
</p>
<br>
<p>
<strong>Display Information:</strong>
</p>
<p>
Below these settings, information is shown on computer performance when running Simutrans.<br>
If numbers (usually white) are red or yellow you may need to change your settings.<br>
Changes in rate that time p****es in game, <a href="window.txt">T</a>, (using Fast Forward  >> icon at top of the main game window, or [,]/ [.]) may change number colour.
</p>
<p>
<em>Frame Time:</em> The first number is intended time between frames; second number is actual time between frames.
</p>
<p>
<em>Idle:</em> When above 0, the computer has capacity to run other software without adversely impacting the performance of Simutrans.
</p>
<p>
<em>
FPS:</em> Higher values mean vehicles appear to move more smoothly. If number remains red, the computer is too slow for current settings (try reducing the size of the main game window).
</p>
<p>
<em>Simloops:</em> If this number remains red, the computer is too slow for current settings - try a smaller map with fewer urban areas.
</p>
<p>
<em>Centralized path searching:</em> toggles between distributed path searching system and centralized path searching system
</p>
<p>
<em>Use performance counter:</em> indicates whether performance counter is used, which is only customisable in simuconf.tab
</p>
<p>
<em>Rebuild connexions:</em> centralised path searching -> number of lines/lineless convoys which can be processed per step in this phase
</p>
<p>
<em>Find eligible halts:</em> centralised path searching -> number of halts which can be processed per step in this phase
</p>
<p>
<em>Fill path matrix:</em> centralised path searching -> number of halts which can be processed per step in this phase
</p>
<p>
<em>Explore paths:</em> centralised path searching -> number of search iterations which can be processed per millisecond in this phase
</p>
<p>
<em>Re-route goods:</em> centralised path searching -> number of halts which can have their goods re-routed per step in this phase
</p>
<p>
<em>Status:</em> centralised path searching -> indicates whether search is in process or not
</p>

Regarding the performance counter issue, I haven't received further reply from Prissi. And there seems to be no new code updates for Simutrans Standard on this. Probably Prissi is too busy working on network mode. So, all we can do is to wait.

Knightly

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #22 – July 12, 2009, 07:17:52 pm

Knightly,

thank you very much for the latest optimisations: I have included them in my local version, and they will be integrated into 5.1. Thank you also very much for your help file. One query with the help file: "Path fill matrix" and "Find eligible halts" seem to have the identical description - is this intended?

Re: [Patch] A New, Centralized, Steppable Path Searching System

Reply #23 – July 13, 2009, 03:55:20 am

James,

You are most welcome

Find eligible halts is the phase whereby each halt is checked to see if there are connexions which support a certain goods category. This phase originally rebuilds connexions too, but I have factored it out as the new rebuild connexions phase. I will see if the find eligible halts phase needs its separate iteration counter later.

Fill path matrix is the phase whereby connexion info are filled into the path matrix as basic info in preparation for the floyd-warshall search.

Hope this is clear

Knightly