Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Wed Aug 15, 2018 9:13 pm

All times are UTC




Post new topic  Reply to topic  [ 17 posts ] 
Author Message
 Post subject: Public Roads
PostPosted: Fri Sep 15, 2017 10:10 pm 
Offline
Transport Coordinator
Transport Coordinator

Joined: Tue Apr 13, 2010 9:31 pm
Posts: 274
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.

Attachment:
Unnamed, 1st Jan 2040#1.png [277.77 KiB]
Not downloaded yet

Attachment:
Unnamed, 1st Jan 2040#2.png [421.64 KiB]
Not downloaded yet

Attachment:
0001-Public-Roads.patch [41.02 KiB]
Downloaded 238 times


Last edited by KeldorKatarn on Mon Sep 18, 2017 3:56 am, edited 1 time in total.

Top
   
 Post subject: Re: Public Roads
PostPosted: Sat Sep 16, 2017 12:46 am 
Offline
Tycoon
Tycoon
User avatar

Joined: Mon Sep 28, 2009 5:15 pm
Posts: 6134
Location: Eastern KY
That seems like a better option to me than using an AI to build roads.

_________________
Do you like drones, quadcopters & flying toys? Check out Drone Strike Force!
Image

Base Music Sets: OpenMSX | Scott Joplin Anthology | Traditional Winter Holiday Music | Modern Motion Music
Other Projects: 2CC Trams | Modern Waypoints | Sprite Sandbox & NewGRF Releases | Ideabox | Town Names | Isle of Sodor Scenario | Random Sprite Repository
Misc Topics: My Screenshots | Forgotten NewGRFs | Unfinished Graphics Sets | Stats Shack | RoadTypes?


Top
   
 Post subject: Re: Public Roads
PostPosted: Sat Sep 16, 2017 5:55 pm 
Offline
Transport Coordinator
Transport Coordinator

Joined: Tue Apr 13, 2010 9:31 pm
Posts: 274
I think so too, especially since AIs take ages to do it.


Top
   
 Post subject: Re: Public Roads
PostPosted: Sun Sep 17, 2017 12:20 am 
Offline
Engineer
Engineer
User avatar

Joined: Mon Feb 15, 2016 1:22 am
Posts: 33
Location: Bogotá
I like the idea :D , this is better than using an AI, which spends CPU Resources constantly, in order to get roads.


Top
   
 Post subject: Re: Public Roads
PostPosted: Sun Sep 17, 2017 12:35 am 
Offline
Tycoon
Tycoon
User avatar

Joined: Sat Jan 22, 2005 7:31 pm
Posts: 6334
Location: Wakefield, West Yorkshire
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!


Top
   
 Post subject: Re: Public Roads
PostPosted: Sun Sep 17, 2017 3:09 pm 
Offline
Transport Coordinator
Transport Coordinator

Joined: Tue Apr 13, 2010 9:31 pm
Posts: 274
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 Mon Sep 18, 2017 3:56 am, edited 1 time in total.

Top
   
 Post subject: Re: Public Roads
PostPosted: Sun Sep 17, 2017 3:23 pm 
Offline
Transport Coordinator
Transport Coordinator

Joined: Tue Apr 13, 2010 9:31 pm
Posts: 274
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.


Top
   
 Post subject: Re: Public Roads
PostPosted: Sun Sep 17, 2017 3:52 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Sun Sep 09, 2007 5:03 am
Posts: 4655
Location: home
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 OpenTTD developer does not mean I know what I am doing.
Also, other OpenTTD developers may have different opinions.


Top
   
 Post subject: Re: Public Roads
PostPosted: Sun Sep 17, 2017 5:28 pm 
Offline
Transport Coordinator
Transport Coordinator

Joined: Tue Apr 13, 2010 9:31 pm
Posts: 274
I doubt it predated boost.


Top
   
 Post subject: Re: Public Roads
PostPosted: Sun Sep 17, 2017 5:40 pm 
Offline
Transport Coordinator
Transport Coordinator

Joined: Tue Apr 13, 2010 9:31 pm
Posts: 274
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.


Top
   
 Post subject: Re: Public Roads
PostPosted: Mon Sep 18, 2017 4:04 am 
Offline
Transport Coordinator
Transport Coordinator

Joined: Tue Apr 13, 2010 9:31 pm
Posts: 274
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.


Top
   
 Post subject: Re: Public Roads
PostPosted: Wed Sep 20, 2017 9:52 am 
Offline
Tycoon
Tycoon
User avatar

Joined: Sat Nov 27, 2004 3:05 pm
Posts: 5282
Location: Canada
: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)

_________________
wallyweb on tt-forums: Screenshots - Projects - Releases
wallyweb on Simuscape: Projects - Releases
Other Stuff: TTDPatch 2.6 "Nightly" download - cirdan's OpenTTD branch (New Map Features)
Screenshot Of The Month Contest Winner: August 2015 - Tied May 2016 - January 2018


Top
   
 Post subject: Re: Public Roads
PostPosted: Fri Nov 03, 2017 12:32 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Sat Jan 18, 2014 6:10 pm
Posts: 1074
I tried to incorporate this patch into JGR, fixed minor rejections, but finally got error:
Code:
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).

_________________
My experimental openTTD server: 149.156.194.203:3979 non-standard client, now testing: JGRPP http://tiny.pl/ggnch
Projects: Reproducible Map Generation patch, NewGRFs: Manpower industries, PolTrams, Polroad, 600mm narrow gauge, preindustrial houses, wired, ECS industry extension.
Addicted to freeciv longturn.


Top
   
 Post subject: Re: Public Roads
PostPosted: Wed Nov 08, 2017 12:30 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Sun Oct 09, 2011 1:51 pm
Posts: 1581
Location: The Netherlands
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: viewtopic.php?f=26&t=57266
Screenshots: viewtopic.php?f=47&t=56959

Winner of the following screenshot competitions:
sep 2012, jan 2013, apr 2013, aug 2013, mar 2014, mar 2016
All my work is released under GPL-license (either V2 or V3), if not clearly stated otherwise.


Top
   
 Post subject: Re: Public Roads
PostPosted: Sun Nov 12, 2017 3:37 pm 
Offline
Transport Coordinator
Transport Coordinator

Joined: Tue Apr 13, 2010 9:31 pm
Posts: 274
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.


Top
   
 Post subject: Re: Public Roads
PostPosted: Mon Nov 13, 2017 5:40 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Sun Oct 09, 2011 1:51 pm
Posts: 1581
Location: The Netherlands
Quote:
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: viewtopic.php?f=26&t=57266
Screenshots: viewtopic.php?f=47&t=56959

Winner of the following screenshot competitions:
sep 2012, jan 2013, apr 2013, aug 2013, mar 2014, mar 2016
All my work is released under GPL-license (either V2 or V3), if not clearly stated otherwise.


Top
   
 Post subject: Re: Public Roads
PostPosted: Sun Dec 03, 2017 3:20 pm 
Offline
Tycoon
Tycoon

Joined: Wed Jan 17, 2007 12:14 am
Posts: 7086
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 :)


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 17 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000-2018 phpBB Limited

Copyright © Owen Rudge/The Transport Tycoon Forums 2001-2018.
Hosted by Zernebok Hosting.