Can you get there from here?

Discuss the new AI features ("NoAI") introduced into OpenTTD 0.7, allowing you to implement custom AIs, and the new Game Scripts available in OpenTTD 1.2 and higher.

Moderator: OpenTTD Developers

Post Reply
User avatar
Kev!
Engineer
Engineer
Posts: 36
Joined: 21 Jun 2011 16:30
Location: In Da House!
Contact:

Can you get there from here?

Post by Kev! » 08 Feb 2019 01:50

Howdy,

TL;DR Is there a simple method to test if there is a working path between two non adjacent road tiles?

I have been tinkering with an AI off and on(mostly off) for years, and recently returned to it. Looking at my own code is like a foreign language! What was I thinking? I recall getting answers to my foolish questions from this forum, so here I go again...

My AI is designed to operate with little to no meta data. It chooses what to do from it's config settings and looking at the state of the game. I had working Airport, Ship, and Bus modules, but hit the wall trying to do the Trains. Each time I get back to working on it, I end up re-writing(improving?) or starting over. I'll see it do something like build a depot but it doesn't join any road and vehicles built there just drive around inside trying to get to a station they can never reach. Or build a station and cut off the road section from the path to the station. So I am back at the buses at the moment.

It first checks for existing stations.
If there are no stations,
choose some likely town,
choose some likely neighbor town
if easily connected and
if both have likely station sites
build the stations and road connection
along with a depot, then return

next iteration:
this time it finds the stations.
loop through the stations.
if the station has no vehicles,
find a likely station to form a vehicle route with.

And here is my problem... It's possible, and in fact fairly common for it to choose a different station than the one it built when connecting the towns. I really need some method to test whether the stations are actually connected via existing roads. I do make an attempt to connect the two chosen, and no longer build the vehicle in question if that fails, so no more buses driving around town unable to get to the destination.

I tried to use a path finding lib but it ran for 21 months and returned no path.

There must be a simpler or elegant method or algorithm. I can't be the first person to desire such a thing.

Can you set me on the right path?


Thanks in advance,
Kev!
I DO like a nice caboose...

User avatar
PikkaBird
Graphics Moderator
Graphics Moderator
Posts: 5383
Joined: 13 Sep 2004 13:21
Location: The Moon
Contact:

Re: Can you get there from here?

Post by PikkaBird » 08 Feb 2019 03:00

Kev! wrote:Is there a simple method to test if there is a working path between two non adjacent road tiles?
Yes. You run the road pathfinder a sensible number of iterations having set cost.no_existing_road to cost.max_cost. If it returns no path, then there is no path.

FWIW CivilAI saves almost no data, and runs itself entirely on what it can "see" on the map.

User avatar
Kev!
Engineer
Engineer
Posts: 36
Joined: 21 Jun 2011 16:30
Location: In Da House!
Contact:

Re: Pathfinder documentation (was: Can you get there from here?)

Post by Kev! » 08 Feb 2019 13:39

Howdy,

your quick response is much appreciated!
PikkaBird wrote:
... run the road pathfinder a sensible number of iterations having set cost.no_existing_road to cost.max_cost.
I'm certain this is meaningful to someone with an understanding of the term "set" in this context.

Is there documentation somewhere on a level for dummies? I have looked at the wiki and the examples were not helpful to me.

specifically...
how to limit the portion of the map the pathfinder considers.
how to "set" cost.whatever

You see, I am not knowledgeable in this area, but I am teachable.

perhaps there is a library that already has a function for this purpose? find if there is an existing road path from a to z?
I really can't believe this doesn't exist.
PikkaBird wrote:If it returns no path, then there is no path.
Also good to know

PikkaBird wrote:FWIW CivilAI saves almost no data, and runs itself entirely on what it can "see" on the map.
I will take a look at your code.

Thanks for taking the time to help out,
Kev!
I DO like a nice caboose...

User avatar
PikkaBird
Graphics Moderator
Graphics Moderator
Posts: 5383
Joined: 13 Sep 2004 13:21
Location: The Moon
Contact:

Re: Can you get there from here?

Post by PikkaBird » 08 Feb 2019 17:27


User avatar
Zuu
OpenTTD Developer
OpenTTD Developer
Posts: 4553
Joined: 09 Jun 2003 18:21
Location: /home/sweden

Re: Can you get there from here?

Post by Zuu » 14 Feb 2019 21:08

It may be as easy to do it yourself, but if you want medium to high level library with some opinions on how to do certain things, then SuperLib may be helpful. If not else to get you started and then swap out its station building code for your own if you want to dig into details.

SuperLib is a collection of different helper routines which I created back in the time when I maintained two AIs and wanted to put common code in a library. It has since then evolved into a quite large library which can be useful or overwhelming depending on how much control you want over details vs medium/high level functionality. My most maintained AI is CluelessPlus which obviously do make heavily use of SuperLib.

SuperLib.RoadBuilder is for example providing an opinionated road path finder with additions over the basic road pathfinder library and do have a repair parameter which I use to check connections for broken roads but try to avoid building new parallel roads that are only slightly better than the old one.
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)

Post Reply

Return to “OpenTTD AIs and Game Scripts”

Who is online

Users browsing this forum: No registered users and 2 guests