News:

The Forum Rules and Guidelines
Our forum has Rules and Guidelines. Please, be kind and read them ;).

Patch to search_route*

Started by Dwachs, January 10, 2020, 08:25:39 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Dwachs

Here is a small patch for the search-route routines. Instead of a binary heap, it uses a combination of a fixed-length array of vectors and a binary heap as open list. In the fixed length array (the buckets) the nodes will be inserted
in the list with index equal to the node weight. If the weight is larger than the array length, the node goes into the heap. Surprisingly, the rather small length of the arrary is sufficient: the patch currently uses 200. The largest game i have available is the op-game, which uses the array up to length ~160.

This reduces the runtime of search_route by 10%. The additional memory consumption is negligible.
Parsley, sage, rosemary, and maggikraut.

jamespetts

This is very interesting. I wonder how well that this would work multi-threadedly* as has been done in Extended since late 2016?

* I.e. multiple vehicles route searching at once concurrently with some other processes in step(), but not doing anything with the route found other than saving the resulting route until the next single threaded step.
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.

Dwachs

This is only used for cargo routing. I did not investigate vehicle routing.

The patch introduces a new data structure that replaces binary heap. It works under the assumption that the maximal weight of an inserted node is somehow small. For cargo routing in standard, max weight does not exceed 200 even for very large games.
Parsley, sage, rosemary, and maggikraut.

jamespetts

Thank you - that is a helpful clarification. This will not be relevant to Extended, in that case, as Extended uses an entirely different routing system for passengers, mail and goods.

However, there may be some benefit to Standard in multi-threading some of the routing code (both for cargo and for vehicles; both are multi-threaded in Extended) as this can make a noticeable difference to performance in a larger game.
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.

prissi

Since Extended uses precalculated tables (or did this change?) for the actual routing (which is then very cheap), the building of the tables is the critical part. It is about if everything is connected to everything or just a much smaller fraction is accessible. In the latter case, (which standard's assumption) the routing allows for much faster reaction to schedule changes, but the cost of routing increases with network size each time a new packet enters. In Extended, the cost is upfront in building the tables, but then routing is cheap.

Back on topic: Since goods routing is one of the remaining biggest effort in Simutrans Standard, improvement is a very good idea. Since most route searches are a few hops, I am surprised there is so much improvement. Please submit.