New AI builder - Pathfinder questions

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
4Droogs
Engineer
Engineer
Posts: 4
Joined: 15 May 2016 02:04

New AI builder - Pathfinder questions

Post by 4Droogs »

Hi AI aficionados,

I am developing a new AI which so far is going pretty well. One of the main goals of the AI is to expand existing networks and keep building in the same area of the map, rather than build a route on one side of the map, then build a new route in a random location on the other side of the map. Currently I have the code working quite well for bus transport. However my goal of expanding networks is being hindered by the PathFinder library (or perhaps by my lack of understanding of the PathFinder library).

My AI currently attempts to build Road networks with a single node(station) in each town. When the time to build something comes, it will try and expand the network by finding nearby towns and building a road connection between it and one of the towns already in the network. The problem is I can rarely expand the network beyond about 4 or 5 nodes as the PathFinder library fails to find a path - even when the towns are quite close together.

An example of this is shown in the attached screenshot. The PathFinder fails to find a path between Great Gruwood and Dontbridge, despite the terrain being flat, and the distance short. I am setting the PathFinder to run for 300 iterations which is more than recommended but it still doesn't find the path. Is this expected behaviour? Or is there some setting I need to tweak? I have tried playing around with the cost of a turn but that didn't help. All other settings are left as default.

Thanks in Advance.
Attachments
ssPathFail1.png
(843 KiB) Not downloaded yet
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: New AI builder - Pathfinder questions

Post by Alberth »

I never coded an AI with pathfinding, but your screenshot looks quite trivial in terms of a pathfinder run.
However, with only a .png no way to draw more conclusions than this.

Maybe one of the start/end tiles is not reachable??


I think the best would be if you make a new AI (stripping your AI to the bare bones of pathfinding would work too, but may be more work) that only performs pathfinding between an example like above, so people can have a look in detail, and possibly play with the code to understand what's going on.
It may even help you in establishing whether pathfinding is not doing its job, or whether there are problems elsewhere.

Your full AI code may work too, but usually pathfinding is deeply buried in other code, making it more difficult to understand what happens.


Edit: and perhaps make a savegame with it too. Since you're debugging, it's fine if you hard-code city-names for example or start/end tiles.
Being a retired OpenTTD developer does not mean I know what I am doing.
4Droogs
Engineer
Engineer
Posts: 4
Joined: 15 May 2016 02:04

Re: New AI builder - Pathfinder questions

Post by 4Droogs »

Hi Alberth

Thanks for the advice. So I stripped down the AI just to the path finding and hardcoded the two cities showing in the attached screenshot. Pathfinder is still failing to find a path. I am using the code below. My AI just starts up and calls the TestPathFinder() method. The output from the script is shown in the screenshot.

If I can't fix this I will have to build my own Pathfinder class which seems like a lot of unnecessary work given that a library already exists. If anyone has any suggestions as to what could be going wrong here they would be most appreciated.

Code: Select all

function ParryAI::TestPathFinder()
{
	AILog.Info("Searching for path betweeen " + AITown.GetName(483) + " and " + AITown.GetName(171));
	if (FindPathBetweenTwoGivenTowns(483, 171))
	{
		AILog.Info("Success");
	}
	else
	{
		AILog.Info("Failed");
	}
}

function ParryAI::FindPathBetweenTwoGivenTowns(t1, t2)
{
	local success = false;
	local path = false;
	if (!success)
	{
		if (t1 != t2)
		{
			local tile1 = AITown.GetLocation(t1); //The centre square of the town
			local tile2 = AITown.GetLocation(t2);
			if (AITile.GetDistanceManhattanToTile(tile1, tile2) < 100)
			{
				local pathfinder = RoadPathFinder();
				pathfinder.cost.turn = 2;
				AIRoad.SetCurrentRoadType(AIRoad.ROADTYPE_ROAD);
				pathfinder.InitializePath([tile1], [tile2]);
					path = pathfinder.FindPath(300);
					AIController.Sleep(1);
				if (path != false)
				{
					success = true;
				}
			}		  
		}
	}
	return success;
}
Attachments
ssPathFail2.png
(366.88 KiB) Not downloaded yet
Wormnest
Engineer
Engineer
Posts: 117
Joined: 14 Jul 2013 12:33
Location: Netherlands

Re: New AI builder - Pathfinder questions

Post by Wormnest »

I haven't done any work on pathfinding in my own AI yet but if I look at the documentation in the road pathfinder I see this:
You can call this function over and over as long as it returns false, which is an indication it is not yet done looking for a route.
I don't see you using a loop in your code so I would try adding a loop checking whether FindPath returns false. And maybe add a check besides that to catch the pathfinding taking longer than you want.
User avatar
Zuu
OpenTTD Developer
OpenTTD Developer
Posts: 4553
Joined: 09 Jun 2003 18:21
Location: /home/sweden

Re: New AI builder - Pathfinder questions

Post by Zuu »

Yes, without a loop, 300 is quite low.

Put it in a loop and print/sign the number of used iterations so you get a feeling for what is a good upper limit in terms of iterations or a date based limit.
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
4Droogs
Engineer
Engineer
Posts: 4
Joined: 15 May 2016 02:04

Re: New AI builder - Pathfinder questions

Post by 4Droogs »

OK, a big thankyou to all who contributed to this thread. I tried it with a loop and it works.

For those interested, when I first wrote my pathfinding code I had used a loop, but that didn't work so I removed it. However I'd created my while loop as follows:

Code: Select all

while (!path)
whereas the while loop on the wiki (and the one I just corrected my code with) is created as:

Code: Select all

while (path == false)
Since the latter worked but the former didn't, I am concluding that in Squirrel, the expression !path returns true when path == null

Is that correct?
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: New AI builder - Pathfinder questions

Post by Alberth »

http://squirrel-lang.org/doc/squirrel2.html#d0e993 wrote:The '!' operator will return null if the given value to negate was different than null, or a value different than null if the given value was null.
Mostly indeed.
Being a retired OpenTTD developer does not mean I know what I am doing.
Post Reply

Return to “OpenTTD AIs and Game Scripts”

Who is online

Users browsing this forum: Google Adsense [Bot] and 3 guests