Public Roads

Forum for technical discussions regarding development. If you have a general suggestion, problem or comment, please use one of the other forums.

Moderator: OpenTTD Developers

Post Reply
KeldorKatarn
Transport Coordinator
Transport Coordinator
Posts: 274
Joined: 13 Apr 2010 21:31

Public Roads

Post by KeldorKatarn »

Just something I'm working on atm. You can see the current results in the screenshot.
I wanted the game to (optionally) connect all the towns with roads so there's already a public road network in place.
The player can start sending busses on that and expand upon it. It was always a bit silly to me that I pay maintenance on
stuff that usually the state builds, i.e. city connections.

Of course this will be optional (since it also takes a bit of time, though I got it already running at decent speed).

I'll post a patchfile once I've got it finished, in case other people want to add it to their patch-packs.

The patch will be based on my own development code base but since it changes files that shouldn't be any different from trunk, it should apply fine.
Even if not the changes are only in 2 files I think and nothing major, so even applying them by hand would be a matter of minutes.
Unnamed, 1st Jan 2040#1.png
(277.77 KiB) Not downloaded yet
Unnamed, 1st Jan 2040#2.png
(421.64 KiB) Not downloaded yet
0001-Public-Roads.patch
(41.02 KiB) Downloaded 312 times
Last edited by KeldorKatarn on 18 Sep 2017 03:56, edited 1 time in total.
User avatar
kamnet
Moderator
Moderator
Posts: 7483
Joined: 28 Sep 2009 17:15
Location: Eastern KY
Contact:

Re: Public Roads

Post by kamnet »

That seems like a better option to me than using an AI to build roads.
KeldorKatarn
Transport Coordinator
Transport Coordinator
Posts: 274
Joined: 13 Apr 2010 21:31

Re: Public Roads

Post by KeldorKatarn »

I think so too, especially since AIs take ages to do it.
User avatar
einsteinyh
Engineer
Engineer
Posts: 36
Joined: 15 Feb 2016 01:22
Location: Bogotá

Re: Public Roads

Post by einsteinyh »

I like the idea :D , this is better than using an AI, which spends CPU Resources constantly, in order to get roads.
User avatar
Redirect Left
Tycoon
Tycoon
Posts: 6754
Joined: 22 Jan 2005 19:31
Location: Wakefield, West Yorkshire

Re: Public Roads

Post by Redirect Left »

Brilliant idea, I love it.

It also seems to be very good at routing through the shortest route through all towns too from the image!
Image
Worst Behaved IRC Member of 2008, 2009 & 2010 - Go Me!
KeldorKatarn
Transport Coordinator
Transport Coordinator
Posts: 274
Joined: 13 Apr 2010 21:31

Re: Public Roads

Post by KeldorKatarn »

Ok, should be done. I tested the crap out of it and it's full of assertions which don't trigger in a ton of test runs. So it should work fine.

the patch file is attached. Obviously the saveload code and the settings.ini "From" version needs to be adjusted to whatever savegame system you're using, trunk or JGR or whatever.

The rest should be fine against trunk though. I had to change AyStar. The used Hash in there was... well.. crap. It's about 4-10 times slower than std::unordered_map so I have no clue why anybody thought rewriting that container from scratch was a good idea.
I had no idea why my code was so slow until I profiled it and saw that it spent 50% of the CPU time in that Hash's loopup function, which should be the FAST function in a hashmap, not the slow one. Anyway, the AyStar with changed containers should still work fine.

There's two settings to activate it, allowing curves and avoiding curves. The first one makes more organic paths with lots of curves, which are a bit slower for vehicles though. If anybody doesn't like that for visual or speed reasons, there's the other setting which will make it almost like a grid, avoiding curves where possible (and it's a tiny bit faster too I think).

Edit: Files moved to first post
Last edited by KeldorKatarn on 18 Sep 2017 03:56, edited 1 time in total.
KeldorKatarn
Transport Coordinator
Transport Coordinator
Posts: 274
Joined: 13 Apr 2010 21:31

Re: Public Roads

Post by KeldorKatarn »

Performance wise some values are: ~1600 towns on a 4k x 4k map in about 2min 50secs. ~400 on a 1k x 1k map in under 5 seconds.

That's roughly only though. it depends a bit on how many islands there are which are disconnected from eachother. But there's code in place to detect that and it doesn't make a HUGE difference. but don't kill me if the 4k map takes 4 minutes :P

It doesn't connect everything with everything, it just makes sure everything is connected to SOMETHING if possible. There should still be work left for the player after all ;) The nice thing about every town having a connection is that they grow along those roads, which makes for a much more natural, less circular, town growth. Very nice to look at.
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4760
Joined: 09 Sep 2007 05:03
Location: home

Re: Public Roads

Post by Alberth »

KeldorKatarn wrote:I have no clue why anybody thought rewriting that container from scratch was a good idea.
That code pre-dates std:: anything.
Being a retired OpenTTD developer does not mean I know what I am doing.
KeldorKatarn
Transport Coordinator
Transport Coordinator
Posts: 274
Joined: 13 Apr 2010 21:31

Re: Public Roads

Post by KeldorKatarn »

I doubt it predated boost.
KeldorKatarn
Transport Coordinator
Transport Coordinator
Posts: 274
Joined: 13 Apr 2010 21:31

Re: Public Roads

Post by KeldorKatarn »

PS: there seems to be one problem still.

Remove the assertion "assert(road_built.Succeeded());" in the "static void PublicRoad_FoundEndNode(AyStar *aystar, OpenListNode *current)"
function for now. It's not a necessary assertion to prevent breaking anything. It just indicated a found path couldn't be actually built as a road, so worst case a town doesn't get connected, even though there's a good chance the game will try again later. I don't know yet why this happens and it seems to be incredibly rare. I'll check if I can find it out, for now just remove that to prevent it from triggering. It won't break anything if you do.

I'll report back once I found why it fails to build the road.
KeldorKatarn
Transport Coordinator
Transport Coordinator
Posts: 274
Joined: 13 Apr 2010 21:31

Re: Public Roads

Post by KeldorKatarn »

I think I got it fixed. I removed the assertion anyway just to be safe. Even if this still fails in rare occastion (I spent hours generating 4k maps with 900 roads without triggering it, so it has to be very rare) the game will try later to connect a city again. So it's very unlikely anything stays unconnected even if it fails once.

Should be fine now. To make sure rare strange maps don't cause too much of a slowdown (happens maybe 1:100 times, but can take a few minutes for a single town then), I added a max limit for the A* search of a million nodes. That's still more than good enough for 4k by 4k maps and still fast enough in the worst case that the game won't seem frozen.

If anybody adds this to a patch that supports maps larger than 4k x 4k you probably don't want to increase this either. Most of the time less than 30k nodes are explored to find a path. So unless you create a 16k x 16k town with two unconnected continents and like 4 cities on each, this shouldn't be a problem. If it is, just get rid of the limit, but then it can take quite a while sometimes, if the map is weirdly set up.

1024x1024 maps usually get their roads set up in seconds, even with towns set to "many". In fact, many is probably faster, since the cities are closer together. But even custom low numbers work. I've tries 4k x 4k with a 100 town limit, and it was still fast enough. Should be fine now :)

If anything else fails, which I don't think it will, report a bug on my GitHub pls. I don't check here too often.

@JGR and others who might look at this: If you find any improvements, any fixes or ways to improve performance even more, let me know and maybe do a pull request. I'll put the branch online as well. Thanks.

Newest patch file and screenshots in the first post.
User avatar
wallyweb
Tycoon
Tycoon
Posts: 5833
Joined: 27 Nov 2004 15:05
Location: Canada

Re: Public Roads

Post by wallyweb »

:shock: Amazing :shock:
:bow:
I nominate this for the 2017 Patch-Of-The-Year Award. 8)

A little creative NewGRF Action A fiddling to change the default paved roads to dirt roads for the early years with a revert to paved roads in, for example, 1930, or whatever, ... ... ... Whoa! :mrgreen:

Hopefully it will patch into NRT (either the current version or the anticipated code rewrite or both). 8)
McZapkie
Tycoon
Tycoon
Posts: 1252
Joined: 18 Jan 2014 18:10

Re: Public Roads

Post by McZapkie »

I tried to incorporate this patch into JGR, fixed minor rejections, but finally got error:

Code: Select all

aystar.h:69:50: error: invalid use of incomplete type ‘struct std::hash<Trackdir>’
   return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
                                                  ^
Any idea how to fix it?

BTW, settings for limiting tunnel length would be appreciated (to exclude or limit tunnels constructed by this patch).
Projects: Reproducible Map Generation patch, NewGRFs: Manpower industries, PolTrams, Polroad, 600mm narrow gauge, preindustrial houses, wired, ECS industry extension, V4 CEE train set.
Addicted to freeciv longturn.
User avatar
Quast65
Tycoon
Tycoon
Posts: 1848
Joined: 09 Oct 2011 13:51
Location: The Netherlands

Re: Public Roads

Post by Quast65 »

A bit offtopic...

How does this work? Does it check for the coordinates of the towns and then makes connecting roads?
If so, is it possible to somehow extract that information?

Reason I ask is because I want to enlarge an existing scenario (already made a hightmap from it and doubled it in size) and want to import the towns from the old scenario (by also doubling the coordinates information).
AFAIK there is not (yet) an "easy" way to extract town coordinate information, right now I can only do it "manually", so going to each town and writing down the coordinates, but that is a lot of work ;-)

Have you found an easier way to get the town coordinates?
Projects: http://www.tt-forums.net/viewtopic.php?f=26&t=57266
Screenshots: http://www.tt-forums.net/viewtopic.php?f=47&t=56959
Scenario of The Netherlands: viewtopic.php?f=60&t=87604

Winner of the following screenshot competitions:
sep 2012, jan 2013, apr 2013, aug 2013, mar 2014, mar 2016, oct 2020
All my work is released under GPL-license (either V2 or V3), if not clearly stated otherwise.
KeldorKatarn
Transport Coordinator
Transport Coordinator
Posts: 274
Joined: 13 Apr 2010 21:31

Re: Public Roads

Post by KeldorKatarn »

Well town coordinates are easy to get in code. every town has a center tile that can be looked up if you have a pointer to the town. So getting the location is easy.
As for tunnels.. the public roads use the value for maximum tunnel length from the settings.
User avatar
Quast65
Tycoon
Tycoon
Posts: 1848
Joined: 09 Oct 2011 13:51
Location: The Netherlands

Re: Public Roads

Post by Quast65 »

Well town coordinates are easy to get in code. every town has a center tile that can be looked up if you have a pointer to the town. So getting the location is easy.
But how would one extract that information from the code, without doing it manually? So without having to go to each center tile ingame and using the ?-tool to get the coordinates and then type that information into a spreadsheet.
Do you think that is possible at all?
Projects: http://www.tt-forums.net/viewtopic.php?f=26&t=57266
Screenshots: http://www.tt-forums.net/viewtopic.php?f=47&t=56959
Scenario of The Netherlands: viewtopic.php?f=60&t=87604

Winner of the following screenshot competitions:
sep 2012, jan 2013, apr 2013, aug 2013, mar 2014, mar 2016, oct 2020
All my work is released under GPL-license (either V2 or V3), if not clearly stated otherwise.
Eddi
Tycoon
Tycoon
Posts: 7580
Joined: 17 Jan 2007 00:14

Re: Public Roads

Post by Eddi »

the most portable way to get the locations of all towns would be a game script that outputs that to the debug console (or the admin port)
You might not exactly be interested in Ferion, but if you are, have fun :)
Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: No registered users and 8 guests