Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Change: Prevent town growth from blocking ships #6931

Conversation

SamuXarick
Copy link
Contributor

Prevent towns from building roads, houses or bridges on tiles where ships could walk.

https://www.tt-forums.net/viewtopic.php?p=1176101

@nielsmh
Copy link
Contributor

nielsmh commented Nov 1, 2018

This will prevent towns from ever building on one-corner-raised half water tiles, won't it? I don't like that. If a player gets a ship's route blocked by a growing town this way it's their own fault.

@SamuXarick
Copy link
Contributor Author

SamuXarick commented Nov 1, 2018

This will prevent towns from ever building on one-corner-raised half water tiles, won't it? I don't like that. If a player gets a ship's route blocked by a growing town this way it's their own fault.

It would help prevent lost ships from occurring, and it's a common occurence in AI games.

@odisseus
Copy link

It would be nice if the towns avoided only those tiles that are actually used by ships. Preventing them from building on any half-water tiles is IMO unnecessarily restrictive.

@TrueBrain
Copy link
Member

We recently switched from Jenkins as CI to Azure Pipelines as CI. This means you need to rebase before this Pull Request will pass its checks. Sorry for the troubles!

@SamuXarick
Copy link
Contributor Author

SamuXarick commented Jan 6, 2019

@odisseus
[15:21] Samu> how would I detect wether a ship would be using such tiles? impossible
[15:22] Samu> unless i run the pathfinder for every ship and see if they run into them? that's madness
[15:23] nielsm> yeah that's not reasonable
[15:24] nielsm> otherwise you'd need to store per water tile when it was last visited by a ship
[15:24] nielsm> and e.g. prevent clearing it if it was sailed on recently

@andythenorth
Copy link
Contributor

I am -1 to fixing this, even though it happens in my games. I think it's TMWFTLB.

@nielsmh
Copy link
Contributor

nielsmh commented Jan 6, 2019

image

Which of these half water tiles would be appropriate to prevent cities from building on, and why?

@SamuXarick SamuXarick force-pushed the prevent-town-growth-from-blocking-ships branch from 6d44581 to 59a7edf Compare January 6, 2019 19:08
@odisseus
Copy link

odisseus commented Jan 7, 2019

Tiles 1, 2, 3 and 6 are certainly okay to build on, as this doesn't create any disconnected bodies of water.

Tiles 4 and 5 are not okay, because building on them would cut off parts of the larger water body. In particular, building on tile 5 would cut off a single water tile, which may have contained a buoy.

Regarding my suggestion of preserving only the water tiles that are used, it seems reasonable to store the date of last visit per water tile. You don't have to store this information for all water tiles — just for those in the vicinity of towns. However, I am totally unfamiliar with the code, so I have no idea whether this can be implemented in a clean and straightforward way.

@Eddi-z
Copy link
Contributor

Eddi-z commented Jan 7, 2019

i think your approach to that is overly complicated.

all this needs is to look at max. 3 other tiles:

  • each water halftile has two adjacent tiles on water level
  • if one of those tiles is not a traversable water tile, allow overbuilding
  • if both are traversable water tiles, look at the other tile that is adjacent to both (diagonal corner of the original tile)
  • if that is also a traversable tile, allow overbuildng
  • if not, deny overbuilding

@andythenorth
Copy link
Contributor

Eddi's comment explains how to do the shaped tile search I suggested. Anything else is boiling the ocean IMO :)

@SamuXarick
Copy link
Contributor Author

I am working on it
grunton transport 1951-10-23

@nielsmh
Copy link
Contributor

nielsmh commented Jan 7, 2019

I still dislike the entire premise of this change. You can't protect players from their own stupidity. If someone (human or AI) built a ship route that can get ruined by a single house getting built, that was a badly designed route from the outset, not a problem with the game.

@odisseus
Copy link

odisseus commented Jan 7, 2019

Large cities that have little room to expand tend to raise land along the coastlines to build more houses, and this inevitably shrinks any adjacent bodies of water. I have seen sizeable lakes being filled in almost completely over time. Therefore, I don't think you can currently design a sea route that is completely safe from being filled in.

Of course, you can build canals over water, but on many servers removing water is prohibitively expensive (to prevent abuse) and/or canals penalize boat speed. You can just expand existing narrow gaps — unless you can't. Somehow terraforming restrictions affect only players and not towns...

I totally agree that the game shouldn't protect players, whether humans or AIs, from their own bad decisions. However, towns are another kettle of fish. They do make bad decisions as well, but they never get punished for these (have you seen a bankrupted town?), and the ill effects mostly harm the players.

@SamuXarick
Copy link
Contributor Author

SamuXarick commented Jan 8, 2019

TODO: Have yet to verify if it's working correctly when dealing with ship depots and locks.
screenshot

@GabdaZM
Copy link
Contributor

GabdaZM commented Jan 8, 2019

I have an idea about a lazy approach:

  • check if the two neighboring tiles are water
  • mark the tile in question as cleared ground
  • run the selected path finding from one of the neighboring tile to the other
  • if there is a path, and the path length is smaller then let's say 20 tiles, it is OK to build there
  • change back the tile in question from cleared ground to the original tile
    This way you can enable the city to "attach" itself to a small island:
    island

@PeterN
Copy link
Member

PeterN commented Jan 8, 2019

@Gabda87 Running pathfinding any time a town wants to expand on water is anything but lazy. I'm pretty sure that's a no go performance-wise.

@GabdaZM
Copy link
Contributor

GabdaZM commented Jan 8, 2019

I haven't looked into the pathfinding algorithms yes, but most of the times the shortest path would be 2 tiles long, and that is not much computation to find.
I think it is quite rare that a new house would cut the water surface into two areas, and the path finding fails to find a path, but if there is an option to give up after going N tiles away from the source, and we are still not at the destination, and not looking for longer a path, I think it should not be that performance heavy either.

@Eddi-z
Copy link
Contributor

Eddi-z commented Jan 8, 2019

the case where the pathfinder doesn't find a path is always the most problematic. and you are missing the fact that even though that case might be rare, if it occurs, the town will repeatedly try to build a house in that place over and over again, because there is no way to store this information.

i'm still of the opinion that calling the pathfinder here is too complex.

@GabdaZM
Copy link
Contributor

GabdaZM commented Jan 8, 2019

I've looked into the YAPF and found a m_max_search_nodes variable that can limit the search time to fail earlier, but after looking into the pathfinding, it is not at all easier to check the path than to check the neighboring 3 tiles. So enabling the town to attach itself to a small island (like the picture above), does not seem to worth the work.

@SamuXarick SamuXarick force-pushed the prevent-town-growth-from-blocking-ships branch 5 times, most recently from fca8e80 to 367c9e4 Compare January 9, 2019 17:14
@SamuXarick
Copy link
Contributor Author

SamuXarick commented Jan 9, 2019

Code is ready for review. What it does:
1 - check if main tile is coastal tile with one corner raised
2 - check the validity of the connection that passes through main tile
3 - if 2 is valid, look whether an alternative connection on the opposite tile is valid

if 1, 2 and 3 are valid, town can build. If 1 and 2 are valid and 3 is invalid, town can't build. For every other case, town can build.

@SamuXarick SamuXarick force-pushed the prevent-town-growth-from-blocking-ships branch from 4f91a03 to 212a84d Compare January 9, 2019 19:37
src/town_cmd.cpp Outdated Show resolved Hide resolved
src/town_cmd.cpp Outdated Show resolved Hide resolved
@SamuXarick SamuXarick force-pushed the prevent-town-growth-from-blocking-ships branch from 212a84d to 5a81dfa Compare January 11, 2019 04:33
@LordAro
Copy link
Member

LordAro commented Jan 20, 2019

TODO: Have yet to verify if it's working correctly when dealing with ship depots and locks.
screenshot

I'm unsure about this as well, but it would be very nice to be able to stop towns from overbuilding their own rivers, like in the image above

@LordAro LordAro added the needs triage This issue needs further investigation before it becomes actionable label Jan 20, 2019
@SamuXarick
Copy link
Contributor Author

TODO: Have yet to verify if it's working correctly when dealing with ship depots and locks.

I'm unsure about this as well, but it would be very nice to be able to stop towns from overbuilding their own rivers, like in the image above

This TODO already works, just in case you're waiting for that.

* @param tile The target tile
* @return true if building here blocks a water connection
*/
static bool GrowingBlocksWaterConnection(TileIndex tile)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is this function really the simplest for the test needed?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

yes

@SamuXarick SamuXarick force-pushed the prevent-town-growth-from-blocking-ships branch 3 times, most recently from df4f01e to 20d5352 Compare February 25, 2019 19:37
Prevent towns from building roads, houses or bridges on tiles where ships could walk.

https://www.tt-forums.net/viewtopic.php?p=1176101
@SamuXarick SamuXarick force-pushed the prevent-town-growth-from-blocking-ships branch from 20d5352 to 01d4f13 Compare February 25, 2019 22:33
@TrueBrain
Copy link
Member

For weeks we have been moving back and forth if we should do this. The general consensus is that this is a real (but minor) problem, but the solution is totally overboard.

The expectation is, that this can also be resolved in a few lines of readable code, instead of a huge function which does tons of things. It might to exactly what it should do, but it is very hard to verify, and it is like bringing a gun to a pillow-fight.

So I am going to make a choice here, and close up this PR. Feel free to come up with new solutions that involve less code to fix this issue. To be clear: trying this exact PR again is not one of the options.

Tnx for the contribution, and sorry it took so long for us to get a consensus on what to do with it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
needs triage This issue needs further investigation before it becomes actionable
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

9 participants