News:

Beta test the new forum at https://simutrans.forum/

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

Factory chains not being built correctly (fishing port, slaughterhouse)

Started by neroden, May 06, 2023, 12:37:38 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

neroden

So I've started several 1750 games and there's a recurring, reliable problem.  It will generate ONE slaughterhouse and ONE fishing port at the beginning of the game, and then... never build another one.  It'll build 100 markets, and link them all to the same slaughterhouse and the same fishing port, which have grossly insufficient production rates to supply those markets.

I'm not sure what's going on here.  I've taken a look at the code, and it looks like it should be working.  All the direct producer-consumer chains are working. Other producer-manufacturer-consumer chains (Ironworks, Spinning Cottage) seem to be working and correctly generating the intermediate manufacturing industries.  It's just these two, the Fishing Port and the Slaughterhouse, where the algorithm is not making new ones.  I'm not sure how to start tracking this down.

The problem may be in the Markets -- although a bunch of Orchards and Vegetable Farms are generated at game start, when more markets are getting generated (which is happening routinely, arguably far too often, but that's a different issue), they are initially linked to nothing, and then the next month, they are linked to preexisting Orchards, Vegetable Farms, and the (one) Fishing Port and Slaughterhouse.  They never generate new manufacturing buildings, unlike other final consumers.  I can't figure out why.

I will say this was happening before I put any of my other patches in, so it's a pre-existing problem.  I'm wondering if it might be something like the following: market demand for meat from any one market is so low that it never triggers "build a new slaughterhouse" even though the *net* demand from *all* the markets is *plenty* high enough to need *five or six* new slaughterhouses. 

Matthew

#1
The history of this as I remember it: there was a problem because pak128.Britain-Ex industry chains are intentionally unbalanced. Producers (e.g. Ironworks or Fishing Ports) grow to make hundreds of tons of goods per month. Consumers (e.g. Hardware Shop or Fish'n'Chip Shop) typically take less than ten tons of goods per month. Even if you interlink chains, with an average of one Producer per Consumer, most Producers are useless due to a lack of customers and you can never make a profit on freight. Therefore the code was changed to override the set Distributionweights and make only Consumers, to temporarily generate enough Consumers until the big town growth rework, after which Towns will generate their own Consumers.

But if the code was still there, I would have thought that you would have seen it. So maybe it was only there for the rest of that B-B game?? Or I have misremembered. I will try to find the discussion.

EDIT: The relevant code comment is here.

EDIT2: And the relevant forum discussion is here.
(Signature being tested) If you enjoy playing Simutrans, then you might also enjoy watching Japan Railway Journal
Available in English and simplified Chinese
如果您喜欢玩Simutrans的话,那么说不定就想看《日本铁路之旅》(英语也有简体中文字幕)。

neroden

No, that's not the problem, I think. Something isn't right about that implementation, but I can't pin down where the problem is.
It's all very well to intentionally create extra consumers, but *the consumers need to generate the rest of the chain when it's needed*.  And the thing is, they DO, for the other consumer buildings -- we get new fields being built, etc.  Even a new ironworks or two.
The key function is build_chain_link.  This measures factory capacity, and adds producers if the new consumers have exceeded the existing factory capacities. This should be called at some point and should start making the new slaughterhouses as needed.  The CHAINS are not being built.  But when I look at the code, it looks like it should be getting called.

After reading the forum discussion -- the implementation is blatantly not doing what James said it was supposed to in the forum discussion.  It simply does not work.  We are getting a dozen consumer industries in a city of population 1200 and nothing in a big city, so it absolutely is *not* maintaining this:
 "Thus, with increase_industry_every set to 2,000, the game will try to maintain one consumer industry in the town per 2,000 in population. "
That would be a good thing to do.  It is not happening.  Was the consumer-industry-calibration branch ever merged with master?

(My current game has a village of 624 population with 6 consumer industries and a large city of 31,000 with 14.  New consumer industries are still appearing in the small towns. industry_increase_every is set to 2000.)

From that thread, Sirius found the following, which may be the core problem which needs to be rewritten:
"Observing a single type of goods, it generally seems that industry chains are fine if the amount of required goods increases from producers towards consumers, because it is always ensured any consumer can be served enough goods, which I guess is the assumption inherited from standard, to paksets city chains."

Apparently it's just not doing the math right.  I'm ending up with one slaughterhouse and umpty-bazillion markets.  The game will never build another slaughterhouse -- ever.  I can't figure out why the code in build_chain_link isn't doing its job -- its job is to figure out that there aren't enough manufaturers of fish in the world, and build another one -- but I haven't looked into it in detail.

If Sirius is right, the problem is likely to be that when it checks whether it needs to build a new manufacturing building (rather than linking an old one), it's doing the math wrong.  It should be checking to see whether the old manufacturing building is overcapacity -- has conusmer buildings demanding more than its max production -- and build a new manufacturing building if it is.  Now, it *looks* like the code in build_chain_link is *supposed* to do that, but maybe the code in build_chain_link is not doing that?  Or maybe build_chain_link is getting bypassed for some reason?

I'm finding this part of the code very confusing because there are too many weird adjustment factors floating around.  Is there a way we can simplify this?  Does anyone actually play a pak with a non-default meters_per_tile?  Do we actually want the capacity numbers multiplied by the production factor?  Getting rid of these two so that the numbers in the .dat files were the in-game numbers would make the code far more readable.  Then there's two additional shift factors, which I remember deciphering at some time, but I can't remember what they are now... getting the gunk out of the code might make it easier to find this sort of error.

Also when I play, the factory production rates are jumping around wildly, and I'm not sure why.  I suppose it should have something to do with the passengers received and mail received, but the math doesn't seem to add up, and I'm wondering if I'm missing some ofher factor, or how this is computed.  This is making it hard to figure out what's going on with the production rates too.  Is there any chance of simplifying this to the point of comprehensibility?


P.S.  To give a sense of the scale of the problem, my current game has one slaughterhouse, producing 4 units of meat per month (built during map creation), one fishing port, producing 20 to 32 units of fish per month (built during map creation), and 130 markets (many built at map creation and many built after map creation), demanding from 16 to 32 units of fish per month each and from 2.6 to 5.2 units of meat per month (but generally operating at very low capacity, probably due to shortage of goods) which are linked ONLY to the one unique fishing port and slaughterhouse.  This is whacked out.  None of the other industries are behaving this perversely.

neroden

I'm doing some manual testing.  If I go in as public service an "build a city chain of industries" for the market, it WILL build the slaughterhouse and the fishing port.  Why isn't this getting triggered by the automatic consumer-industry-construction code ever?  It should get triggered some of the time.  Something is causing this code to be bypassed, and it's a bug.

Meanwhile, if I "build a city chain" for the Cooper, it will correctly realize that there are enough Ironworks and link it to existing Ironworks rather than building new ones.  So it's not going to overbuild.

So my current guess is that something is bypassing or short-circuiting the call to build a chain in increase_industry_density, where it shouldn't.  Grrr.

neroden

So, Matthew, you may have been right about what introduced the problem.

It looks like force_add_consumer didn't do what it said on the label.  It doesn't just force add a consumer, it force bypasses the entire check for finishing industry chains.  This is bad.

So I have an untested patch.  This is on the factory-chain-fix branch, pushed to my github.  What this does is, if force_add_consumer is active, it will *still* try to complete the unfinished industry chain, but will then go ahead and build a consumer industry afterwards (rather than bailing out as in the usual case).  This should keep generating extra consumer industries but without breaking the chains.

It's OK to force new industries, it's not OK to bypass the industry completion code.  However, I still don't fully understand this code so this may have introduced new bugs -- I will test it when I get a chance (others should feel free to test it too).

But this doesn't feel like it should be the problem.  Because even with the previous code, force-building a consumer, it calls build_link, and build_link should have built an entire industry chain from one market, and it *didn't*.

------

OHO, I think I've found the other half of the problem.  The code for building a new industry...


nr += build_link(NULL, consumer, -1 /* random prodbase */, rotation, &pos, welt->get_public_player(), 1, ignore_climates);See that last "1"?  That becomes "number_of_chains" in build_link...
  // now build supply chains for all products
  for(int i=0; i<info->get_supplier_count()  &&  i<number_of_chains; i++) {
    n += build_chain_link( our_fab, info, i, player);
  }
Whoopsy-daisy.  I believe this means that the Market, with *four input products*, will only ever build one chain.  Guess what, it checks the first supply product on the list, occasionally builds a new Orchard, and never builds new for everything else.  :-P 

I think *this* may be at the root of the problem. This is also why other factories which only have one input are doing fine -- the problem only affects factories with 2 or more inputs.

That "1" should be replaced with a functional infinity.

This is now on the factory-chain-fix branch.  The previous change is still there too; that may not be needed, frankly, so I'm going to think about backing it out. In addition, there may be some cleaner way to do this.

James, don't merge this branch right away, but everyone, please do test it to see how it works and what new unexpected issues crop up.

----

OK, so this is exposing another issue.  Now the market / fishing port ratio and market / slaughterhouse ratio look right -- but each fishing port is generating its own fishery, even though each fishery can support many fishing ports.  My first guess here is that there's a distance limit, that the fishing port is requiring a "nearby" fishery in order to declare that connecting to an existing port is good enough -- I'm going to have to dig deeper into the code to figure out why it isn't connecting to preexisting ports -- again, build_chain_link SHOULD link to an existing factory instead of building a new one as far as I can tell from a quick read...

neroden

I am now convinced that the fishing port situation is not a bug but is intentional.  Fisheries are listed in the pak with a max_distance_to_consumer of 40 km, which I presume is based on real-world fishing distances in 1750 in the vicinity of Britain. 

Assuming this is correct, it might actually be desirable to limit the doggers and other fishing boats in their maximum distance the same way.

(If it's not correct and British fishermen went hundreds of km offshore, we should just raise the max_distance_to_consumer.)

James?

I'm trying to find information on fishing distances from 1750-1800 period based on a quick Googling.  My first try didn't go far, but then I found this:
https://en.wikipedia.org/wiki/Cod_Wars

"By the end of the 14th century, fishing boats from the east coast of England, then as now home to most of the English fishing fleet, were sailing to Icelandic waters in search of these catches; their landings grew so abundant as to cause political friction between England and Denmark, who ruled Iceland at the time. "

Iceland is a solid 1500 km away by sea from the east coast of England.  I think we should raise the max_distance_to_consumer to 1500 km for the fishing ports!

----
I will now try backing out my first change given that the second change seems to solve the problem.  I'm also going to try patching the pak for fishing port - fishery distances

neroden


jamespetts

Quote from: neroden on May 08, 2023, 01:05:32 PMFishery patch is here.  https://github.com/jamespetts/simutrans-pak128.britain/pull/152

I'm still working on the main code patch.
Excellent, thank you for that. I have incorporated the "cod wars" patch. That is interesting research.

Thank you very much for your work in relation to the other industry issues. I suspect that this will significantly improve the game balance relating to industry.
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.

neroden

Confirmed that (with the main code patch in and the "cod wars" patch in) the game is no longer generating excessive numbers of fisheries -- it really was just due to the maximum_distance_to_consumer parameter.

I have refactored my main code patch -- the patch to build full factory chains, I'm quite sure is correct.   Here is the clean version ready to pull.

 https://github.com/jamespetts/simutrans-extended/pull/614

I now want to play the game for a while to see whether the other part is needed.  It may not be needed.

jamespetts

Quote from: neroden on May 08, 2023, 01:55:58 PMConfirmed that (with the main code patch in and the "cod wars" patch in) the game is no longer generating excessive numbers of fisheries -- it really was just due to the maximum_distance_to_consumer parameter.

I have refactored my main code patch -- the patch to build full factory chains, I'm quite sure is correct.  Here is the clean version ready to pull.

 https://github.com/jamespetts/simutrans-extended/pull/614

I now want to play the game for a while to see whether the other part is needed.  It may not be needed.
Excellent, thank you: now incorporated.
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.

Matthew

Quote from: neroden on May 08, 2023, 11:57:47 AMI am now convinced that the fishing port situation is not a bug but is intentional.  Fisheries are listed in the pak with a max_distance_to_consumer of 40 km, which I presume is based on real-world fishing distances in 1750 in the vicinity of Britain. 

Assuming this is correct, it might actually be desirable to limit the doggers and other fishing boats in their maximum distance the same way.

(If it's not correct and British fishermen went hundreds of km offshore, we should just raise the max_distance_to_consumer.)

James?

I'm trying to find information on fishing distances from 1750-1800 period based on a quick Googling.  My first try didn't go far, but then I found this:
https://en.wikipedia.org/wiki/Cod_Wars

"By the end of the 14th century, fishing boats from the east coast of England, then as now home to most of the English fishing fleet, were sailing to Icelandic waters in search of these catches; their landings grew so abundant as to cause political friction between England and Denmark, who ruled Iceland at the time. "

Iceland is a solid 1500 km away by sea from the east coast of England.  I think we should raise the max_distance_to_consumer to 1500 km for the fishing ports!

----
I will now try backing out my first change given that the second change seems to solve the problem.  I'm also going to try patching the pak for fishing port - fishery distances

I think we should reconsider this. In real life, Great Britain and Ireland are islands and therefore Iceland can be reached from any part of their coast. In Sim-Ex maps (including at default settings) there are usually substantial bodies of water that are not connected to all coasts. My intuition is that the further the fishery is from the fishing port, the more likely it is to be on a separate and unreachable body of water. I am aware that my intuition may well very well be wrong but as I only have secondary school maths I can't think of any way to check this beyond running a bunch of tests, though it strikes me as the kind of thing where mathematics has already found a general answer. I might ask on Maths Stack Exchange or try to work it out as a C++ learning exercise (though this should not be taken as a prerequisite for what follows).

This problem is compounded by the fact that this pakset only allows live fish to be transported by seagoing vessels, so nothing less than a ship canal can be used to connect bodies of water. The ship canal restriction in itself is accurate: fishing boats were the main commercial users of the Caledonian Canal until the pandemic (I don't know why they have not returned) and the Forth & Clyde Canal before it closed in 1963. But these routes were not economically viable from fishing income alone. Certainly the Caledonian Canal was funded by HMG for strategic reasons and operated by non-profit-making commissioners (because there was no way a commercial owner could have repaid the capital cost). The Forth & Clyde was built commercially and I think profitably but that was because of Scotland's good fortune in having its two largest cities on the estuaries of its two major rivers close together at its narrowest point; there is no guarantee that will happen on a Sim-Ex map.

At the very least, I think that the maximum distance between fisheries and fishing ports should be much lower for the 1750 Fishing Port, since at the start of the game no player will have the capital to construct a transcontinental ship canal. But it should also be viable to start play at later dates so I am not sure than 1500km is ever a good choice.

This whole problem could be sidestepped if there was code to guarantee that fishing ports and fisheries were connected to the same body of water, but AFAIK there is no such check yet.
(Signature being tested) If you enjoy playing Simutrans, then you might also enjoy watching Japan Railway Journal
Available in English and simplified Chinese
如果您喜欢玩Simutrans的话,那么说不定就想看《日本铁路之旅》(英语也有简体中文字幕)。

neroden

Regarding the other possible change: Some things are coming back to me.  IIRC, the factory relinking code exists to deal with factory closures.  (It was not intended to be triggered under other circumstances.)  It is conceptually independent from the code for building new consumer factory chains.

I don't think it should be bypassed when the code is called to force build a new consumer, but I also don't think it should replace the code to force-build a new consumer.  Both should activate in a given month.

So I think the other change is *conceptually correct*, though it has absolutely nothing to do with the bug I was trying to address.

However, I also think it's probably not gameplay-significant (a month or two's delay in relinking factories, OK, whatever) so I'm going to put it off to one side and look at it later.

neroden

Quote from: Matthew on May 08, 2023, 03:45:11 PMI think we should reconsider this. In real life, Great Britain and Ireland are islands and therefore Iceland can be reached from any part of their coast. In Sim-Ex maps (including at default settings) there are usually substantial bodies of water that are not connected to all coasts. My intuition is that the further the fishery is from the fishing port, the more likely it is to be on a separate and unreachable body of water. I am aware that my intuition may well very well be wrong
I've generated a lot of maps.  We've been getting fisheries and fishing ports on separate and unreachable (without canal-building) bodies of water all along. :-(

I don't think distance is the way to address this.  Honestly we should write some code to detect "same lake". 

HOWEVER....

....in practice, with this change, each fishery is linked to quite a lot of fishing ports -- especially since there is some cross-linking going on (15% as set in pak128.britain) Maybe one or two of these links is on an isolated body of water, but most of them are going to work.  If a few of them are unimplementable, that's OK for gameplay, it's not necessary for every possible connection to be viable in 1750, as long as most of them are.

And of course, you CAN build canals if you absolutely have to.

A more pertinent concern is the huge economic cost of a large enough fleet to run a steady fish supply halfway across the map, but again, with more fishing ports, more fisheries, and a fair amount of cross-linking, *enough* of the routes work that I think it's OK if some of them aren't economically exploitable.

Making the distance short enough to guarantee "same lake" requires making it REALLY short and effectively means one fishery per fishing port.  (This is because the fishing port location is always generated *first*, and the fishery *afterwards*, contrary to real life -- but changing this would be a major, major rewrite of a huge amount of code.)  Make the distance just a bit longer, just long enough to have multiple fishing ports per fishery, and you *immediately* start getting a few which are in the "wrong lake".  Make the distance significantly longer, and you start getting more cross-linked fisheries and significantly more possible routes, so it actually works out better IMO.

jamespetts

If anyone can write sufficiently performant code to get "same lake" functionality, that would be excellent - but it would be quite a project, I think,
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.

neroden

We can leverage existing code.  There's already an entire route-finding apparatus (several, actually).

I had insomnia and woke up thinking about how to do this, so I wrote a prototype. It compiles.  Unfortunately, it segfaults.  I may be able to debug it.

https://github.com/neroden/simutrans/tree/water-factory-route-check

----
Followup:  Well, that's frustrating.  I actually got it *working* but the route finder refuses to find long water routes. 

It'll find relatively short water routes and say yay, all good.  But it'll just return "no route" for longer ones, even when they are in the same lake and have a pretty straightfoward route between them.  I don't understand the route finder well enough to understand why it can find a route for a ship from point A to point B halfway across the map during gameplay, but, most of the time, it can't find a route when I call it manually here (during new game creation).  It is not that the route is too complex (it's not hitting max steps) -- it's simply not finding it at all.

Anyway, the work in progress is on that branch.  If anyone wants to look at it and see if they can figure out why the route finder isn't doing its job, it's there.  If you want a clean patch without my other work-in-progress or the masses of false starts, I also pushed the branchpoint water-factory-route-check-branchpoint as a tag, so you can do a diff between the branchpoint and the branch to get a clean patch.

Matthew

Quote from: neroden on May 09, 2023, 06:27:52 AMI had insomnia and woke up thinking about how to do this, so I wrote a prototype.

I'm the same, sometimes I wake up in the middle of the night and a lesson plan is perfectly clear in my mind. Our brains are busy busy busy while we're sleeping.

QuoteBut it'll just return "no route" for longer ones, even when they are in the same lake and have a pretty straightfoward route between them.  I don't understand the route finder well enough to understand why it can find a route for a ship from point A to point B halfway across the map during gameplay

It can't.... It's common on large maps for ships to get stuck if you don't give them lots of waypoints (I aim for every 200 tiles or so; I don't know whether that's optimal but it's somewhere in that ballpark). Also, if you are experimenting with this you should know that there's a separate bug where stuck ships don't move after being rescheduled. The workaround is to reload the game.

QuoteAnyway, the work in progress is on that branch.  If anyone wants to look at it and see if they can figure out why the route finder isn't doing its job, it's there.  If you want a clean patch without my other work-in-progress or the masses of false starts, I also pushed the branchpoint water-factory-route-check-branchpoint as a tag, so you can do a diff between the branchpoint and the branch to get a clean patch.

Thank you for your continued efforts on this and other matters. I have been trying to test some of your patches but new ones come out faster than I can set up the tests. It's a wonderful problem to have!
(Signature being tested) If you enjoy playing Simutrans, then you might also enjoy watching Japan Railway Journal
Available in English and simplified Chinese
如果您喜欢玩Simutrans的话,那么说不定就想看《日本铁路之旅》(英语也有简体中文字幕)。

jamespetts

Quote from: neroden on May 09, 2023, 06:27:52 AMWe can leverage existing code.  There's already an entire route-finding apparatus (several, actually).

I had insomnia and woke up thinking about how to do this, so I wrote a prototype. It compiles.  Unfortunately, it segfaults.  I may be able to debug it.

https://github.com/neroden/simutrans/tree/water-factory-route-check

----
Followup:  Well, that's frustrating.  I actually got it *working* but the route finder refuses to find long water routes. 

It'll find relatively short water routes and say yay, all good.  But it'll just return "no route" for longer ones, even when they are in the same lake and have a pretty straightfoward route between them.  I don't understand the route finder well enough to understand why it can find a route for a ship from point A to point B halfway across the map during gameplay, but, most of the time, it can't find a route when I call it manually here (during new game creation).  It is not that the route is too complex (it's not hitting max steps) -- it's simply not finding it at all.

Anyway, the work in progress is on that branch.  If anyone wants to look at it and see if they can figure out why the route finder isn't doing its job, it's there.  If you want a clean patch without my other work-in-progress or the masses of false starts, I also pushed the branchpoint water-factory-route-check-branchpoint as a tag, so you can do a diff between the branchpoint and the branch to get a clean patch.
Thank you for this. I should note that I am saying this from memory rather than from having checked the code recently, but I believe that there may be a parameter (possibly with a default value, so it is hidden unless you explicitly invoke it) for how long/complex that the water route is allowed to be, which permits the game to cease route-finding for excessively long routes to prevent serious performance problems on very large maps for ships where there are very complex routes between two points. If this is correct, then you may simply need to increase this parameter.
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.

neroden

Quote from: Matthew on May 09, 2023, 07:25:10 PMIt can't.... It's common on large maps for ships to get stuck if you don't give them lots of waypoints (I aim for every 200 tiles or so; I don't know whether that's optimal but it's somewhere in that ballpark). Also, if you are experimenting with this you should know that there's a separate bug where stuck ships don't move after being rescheduled. The workaround is to reload the game.

Yeah, thanks for letting me know. :-( I realized that yesterday. :-(  I've been absolutely obsessively thinking about this (haven't checked anything else, not even other topics in this forum), and, uh, I have a fix for this.

I want to clean it up quite a lot more before merging it (please don't merge it as is, I want to do some refactoring and rewrite the commit history so it isn't full of my dead-end attempts and failed trials) but you can test it on the water-factory-route-check branch.  (And if you want to get some insight into my programming methods, go ahead and look at all those dead-end attempts and failed trials!)

What I did is to implement a new routefinding system for ships on the ocean.  It only applies to oceangoing ships, and it only applies when they're starting on the water and ending on the water.  This is good enough for the search between the fishery and the factory.

It's *also* good enough for actual ships -- I have now tested it in a running game.

This routefinding system attempts to go in a straight line, like the airplane routefinding system.  It tries both the orthogonal-then-diagonal, and the diagonal-then-orthogonal routes.  If it encounters up to 128 tiles of land (I am still thinking about how many this should be -- it's a performance question), it will keep looking in a straight line, and then use the regular routefinder to find a "detour" around a spit of land or a small island, and then continue on the straight line. If it can't find a detour, it gives up.  (The length of land it should attempt to detour around is a performance question, it needs to be kept short to keep the regular, slow routefinder from spending too much time on it.)

This won't find every possible open-ocean route; it won't navigate from one side of an island or peninsula around to the other side if the island or peninsula is large.

But it'll handle the "really, that shouldn't require waypoints" cases where it's basically a straight line through the ocean from point A to point B with a few possible detours around small islands or penisulas. 

The underlying problem is that the regular routefinder is basically a "explore every possible route" approach, which is great for thinly connected networks like roads which only occasionally have intersections, but not so great when every sea tile connects to every other sea tile.  (Which is also why airplanes use a different routefinder.)  The regular routefinder does have a special case for sea routing which works well for short hops around islands, where it runs in a straight line and then turns when it hits something, but this isn't the best for really long routes.  Essentially it's exploring a lot of possible route options which are wandering off in silly directions, which takes a lot of time and doesn't get you closer to the goal.

The solution is to have a "global path" routefinder which is taking the big picture and knows where it's trying to go (along the straight line) and only uses the regular routefinder for shorter, local deviations.  This will get you all the clean, open-ocean or mostly-open-ocean routes *quickly*.

If there is land in the way, it won't actually be the shortest route (it'll follow the main straight line, deviate around the island, then follow the main straight line again) but it'll *work*, and the player can add waypoints if they want to shorten the route, so that's OK.

Now... ha... this still doesn't solve the problem of fisheries showing up in the wrong lake from the fishing port.  That's happening during cross-connection of industries, and I haven't worked out how to suppress that yet (I tried, and... it didn't work).

Also, raising the radius to 1500 exposed some unnecessary performance issues in the code for randomly locating new factories.  That code assumed that the radius was smaller than the map size, and will waste time checking a whole lot of areas outside the map.  So I wrote a fix for that.

But anyway, without actually solving the "fishery in wrong lake" problem (!!!!), I think I have a few useful improvements.

First, I'm going to break out a patch for the issue where, with large radius for "next factory", the game was looking in areas outside the map to place the factory.

Then I'm going to break out a patch for the new ocean ship routefinder.  I think this is a generic improvement to gameplay anyway.

Then I can take a look at the problem of "fishery in wrong lake" again and see what's left.

neroden

OK.  I've got the ocean ship routefinder really genuinely working.  Enjoy.  It's still on the same branch, water-factory-route-check.

I'm getting two odd errors thrown in the log: I'm triggering a floating point divide by zero somewhere (?!?!?... I can't figure out what I am doing which could possibly be related to this in any way) and I'm sometimes getting the same tile listed twice in the route schedule I'm assembling (this may be the cause of the floating point error?) -- it looks like the code shouldn't be adding duplicates, but maybe I missed something.

I'm still going to do a little more refactoring; there's a little duplication of code in the code to try the "straight line" in both directions (since it's different in the two directions, diagonal first or second), and I want to abstract that into route_t.  I also feel like I should be more honest about the data I'm passing to the regular routefinder in the regular ship case (as opposed to the finding-factory-links case), which should come from the test driver rather than all being dummied out.

jamespetts

Excellent, thank you very much for this! This should be a major improvement.

Can I check - you mention the new system giving up if it encounters > 128 tiles of land. Does this mean that the route will fail entirely, or that it will fall back to the existing system? I would suggest the latter behaviour so that we do not have any cases where routes can be found at present but cannot be found with the new system (as we might have, e.g., on maps with lots of large lakes interconnected by small channels or even rivers/canals).

Also - can I check that you have tested whether this affects network synchronisation? Vehicle route-finding is multi-threaded, so changes to this are possibly sync-critical.

Thank you again for this!

Edit: I see that you have already coded for this to fall back on the existing route-finding system if the new system should fail - excellent, thank you.
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.

neroden

I have not been able to test network synchronization yet.  I am not sure *how* to test network synchronization.
I am still refactoring the main code and preparing a coherent patch series -- there's no reason to have my long series of false starts and debugging code in the commit history.

In the meantime, here is the first patch.  This just deals with the issue of factory placement wasting time searching off the edge of the map.  It is tested and should not be problematic in any way.

https://github.com/jamespetts/simutrans-extended/pull/616

-----

It would help if you could explain the theory behind the multithreading of the route finder.  Currently what I do is: from calc_route in water_vehicle.cc, I try the straight-line approach, calling calc_ocean_route, which is not written in a multithreaded fashion at all, but which may call the regular intern_calc_route as a subroutine (which may be multithreaded, I don't know?).  I call it in sequence, one "bypass" at a time.  If that fails, or if it isn't triggered in the first place (it is bypassed if the start or end point is not ->in_water(), or if the vehicle can only travel in canals, or if the distance is short), then it will simply call the regular calc_route once.

I don't think this should lead to any multithreading trouble.  The only issue which I can see coming up is if... the terrain was being changed while the routefinding was running?  Which would already be generating issues for the existing code, so I'm assuming that's been dealt with and it isn't happening?

Otherwise, everything is deterministic (no calls to simrand) and can theoretically be done in any order, but in fact is being doing in a totally deterministic order.  So I see that do_route can be run in parallel in several threads -- this is fine.  When a particular instance of do_route calls calc_route, it calls it in a single thread each time, right?  So we're running linearly in one thread for a particular call to calc_route or calc_ocean_route.  Instead of running intern_calc_route once, I run it several times, but each time it's allowed to set up nodes and tear them down down just the way it normally does (I haven't actually touched it, I'm just calling it within a for loop), and those happen in sequence within the thread (I was worried about different calls stomping on each other so I was careful about that).  Other than what intern_calc_route does, the only storage I'm using is stack-allocated, which should not be an issue (each thread gets its own stack).

So I'm pretty sure this should be fine for the existing thread structure.  It looks like there's only one thread per invocation of do_route.  Where do_route currently calls calc_route, which calls intern_calc_route, now sometimes (deterministically) do_route will call calc_ocean_route, which will call intern_calc_route several times in sequence.  This should be just fine.

-----

The ocean route finder, by itself, is now on the ocean-route-finder branch.  (Putting the part about trying to make sure fisheries are in the same lake as fishing ports off to one side for later!)

I am still trying to figure out whether the mysterious floating-point divide-by-zeros are from my code or whether they were pre-existing. 

I'm also trying to figure out why I'm sometimes getting duplicate tiles in the route.  The existing code looks like it should eliminate these when adding the "detour" routes during .append(route_t detour_route), and the code for adding a straight line shouldn't add one at all (it picks up after the last tile added to the route), so I'm not seeing it.  If someone can spot where this might be coming from it would be helpful.

Other than that I can't figure out any more improvements to make to this.  It is tested and more or less ready to go, though I'd give it a couple of days to see if I can think of anything else or solve those two niggling issues.

----
The checks for connectivity between a fishery and a fishing port are now on the water-factory-route-check-new branch, which is designed to be committed after the ocean-route-finder branch (and please don't commit it at this time, I don't think it's ready).

Matthew

Quote from: neroden on May 11, 2023, 06:24:22 PMI'm getting two odd errors thrown in the log: I'm triggering a floating point divide by zero somewhere (?!?!?... I can't figure out what I am doing which could possibly be related to this in any way) and I'm sometimes getting the same tile listed twice in the route schedule I'm assembling (this may be the cause of the floating point error?) -- it looks like the code shouldn't be adding duplicates, but maybe I missed something.

The divide by zero error occurs on the released build too (on B-B it's an average of 84 errors per real-life minute), so it's probably not your changes. I will start a separate thread to discuss this.
(Signature being tested) If you enjoy playing Simutrans, then you might also enjoy watching Japan Railway Journal
Available in English and simplified Chinese
如果您喜欢玩Simutrans的话,那么说不定就想看《日本铁路之旅》(英语也有简体中文字幕)。

neroden

If anyone spots why I'm getting errors in the log about duplicate tiles in the route occasionally (not always!), let me know.  It seems to work in any case so I'm going to ask for it to be merged.

https://github.com/jamespetts/simutrans-extended/pull/617

jamespetts

Thank you for your reply - I am not sure whether you still need me to reply in relation to vehicle routing. This algorithm is not merely parallel but concurrent: see lines 5436 and onwards and 5155 and onwards of simworld.cc. The convoy threads run concurrently with sync_step, and, indeed, concurrently with everything except those parts of step that sit between the blocks of code starting at 5155 and 5436.

To test network synchronisation, what you need to do is run a build of your version, and then load a well developed game (e.g. the save from the Bridgewater-Brunel server) with the "Start this game as a server" checkbox enabled. Then, you need to start another instance of the same build and connect to the first using the loopback interface, by opening the load dialogue and typing, "net:127.0.0.1" and pressing return/enter. The client will then connect to the server. If you then run this for a while, you will be able to see whether this stays in sync or not.
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.

ceeac

Alternatively you can use the Heavy Mode: Just start both client and server with the -heavy 1 command line option. However, there are some caveats regarding user interaction; for example, creating new convoys in a depot causes an instant desync because a schedule for the new convoy is created on the client but not on the server. Running the game without user interaction should not produce any such desyncs.

neroden

Quote from: jamespetts on May 13, 2023, 12:36:52 PMThank you for your reply - I am not sure whether you still need me to reply in relation to vehicle routing. This algorithm is not merely parallel but concurrent: see lines 5436 and onwards and 5155 and onwards of simworld.cc. The convoy threads run concurrently with sync_step, and, indeed, concurrently with everything except those parts of step that sit between the blocks of code starting at 5155 and 5436.

To test network synchronisation, what you need to do is run a build of your version, and then load a well developed game (e.g. the save from the Bridgewater-Brunel server) with the "Start this game as a server" checkbox enabled. Then, you need to start another instance of the same build and connect to the first using the loopback interface, by opening the load dialogue and typing, "net:127.0.0.1" and pressing return/enter. The client will then connect to the server. If you then run this for a while, you will be able to see whether this stays in sync or not.

Great.  You should do this testing.  Please do so.  I do not have the time to do this.  I have more important things going on, such as dealing with the problem of Covid outbreaks in hospitals (yes, I'm not kidding, that's what I'm currently working on).

Please get back to me after you've done the testing.  I expect it will work.  If it doesn't, I hope you're able to debug it.

jamespetts

Thank you for that - the ocean route finder patch is now incorporated following local server testing.
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.