Wow! Convoy is so FAST!

[Zutty]

My AI is far from finished but I couldn't help but try it out against Convoy, and now I'm feeling rather depressed as it got completely beaten to death!

I can fix most things (e.g. the biggest reason is that my AI still only builds one route!) with some ease, but the biggest difference that I noticed was the absolutely BLINDING speed with which Convoy builds its roads. With AI construction speed set to "Very Fast" Convoy can kick out a long route in 4 days. FOUR FREAKING DAYS! THATS MENTAL.

It took my AI 16 days to build a short route, and around a month for a route of a similar length. This WAS on a hard map (rough, mountenous terrain - I'm testing tunnel contruction ATM), but that only makes Convoy even more impressive! Worse yet on a particularly difficult map and for a very long route it takes up to 4 months (though an earlier version of my code took 18 months!). DAMMIT!

Plus Convoy has better support for building on slopes! *sob*

How do you do it GeekToo???

This was for Convoy 1.2 BTW, before the new version that uses Aystar.

Edit: To give some some indication of why this might be, the code that I use to find neighbouring tiles for the A* search is over 200 lines long, compared to 8 in Convoy!!

[Edit Moderator] Please mind your language ... there are also young people reading these forums ... topics should be a less .. well .. they shouldn't be a line you shout to your neighbour or something. We understand your enthusiasm, but try to keep it in line. [/edit]

[Finaldeath]

Um...you need to know...

For instance, the following code snippet will create a list of tiles directly adjacent to tile...

Code: Select all

local adjacent = AITileList();
adjacent.AddTile(tile - AIMap.GetTileIndex(1,0));
adjacent.AddTile(tile - AIMap.GetTileIndex(0,1));
adjacent.AddTile(tile - AIMap.GetTileIndex(-1,0));
adjacent.AddTile(tile - AIMap.GetTileIndex(0,-1));

I hope you are incorrect in saying how to get the immediately adjacent tiles and meant something else

[GeekToo]

Um...you need to know...

For instance, the following code snippet will create a list of tiles directly adjacent to tile...

Code: Select all

local adjacent = AITileList();
adjacent.AddTile(tile - AIMap.GetTileIndex(1,0));
adjacent.AddTile(tile - AIMap.GetTileIndex(0,1));
adjacent.AddTile(tile - AIMap.GetTileIndex(-1,0));
adjacent.AddTile(tile - AIMap.GetTileIndex(0,-1));

I hope you are incorrect in saying how to get the immediately adjacent tiles and meant something else

Well, that does look like the code I created for Convoy. Zutty, if you really need 200 lines of code, I suggest to use my Tile code. It's GPL so reuse what you find useful, and if you can improve it, republish it (a link or mention would be nice).

About the speed: I indeed did spend a lot of time on improving the build time of roads for Convoy. My first attemps were very slow too, so don't be depressed Zutty. I did find out that improving the speed of builiding is very important to create a well performing AI.

Some hints:
-Use a binary heap for the pathfinding. I did create a binheap class, and it is reused ( and improved ) in the code for the library pathfinder.
-Don't use BuildSigns in the final pathfinder. They're very useful in debugging, but when your pathfinder algorithm is debugged, remove them, as they will a a Sleep(1) to every sign you build.
-In the pathfinder algorith, at first I did use a Sleep(1) for every tile that was evaluated in the openlist. That really slows things down a lot. After some experimenting, doing a Sleep only every 100 tile you evaluate does speed up things a lot, without completely blocking OpenTTd. If you use the library pathfinder, it does use also this value for the number of iterations.

In short, I suggest you to use the library pathfinder. It's pretty good, and if you find ways to improve it, please do post them here, all AI developers will benefit from it.

[Zutty]

Don't worry... I know how to get adjacent tiles! Its the next neightboring NODES in the chain thats over-complicated. I have four passes... One for following existing roads, one for new roads, once for bridges, and one for tunnels. The code is still mostly unoptimised and is laid out for readability and ease of maintenancea this stage rather than speed. Having said that though, I'm not really sure what steps I can actually make to optimise!

-In the pathfinder algorith, at first I did use a Sleep(1) for every tile that was evaluated in the openlist. That really slows things down a lot. After some experimenting, doing a Sleep only every 100 tile you evaluate does speed up things a lot, without completely blocking OpenTTd. If you use the library pathfinder, it does use also this value for the number of iterations.

Now THATS clever! I wouldn't have thought of that!!!

In short, I suggest you to use the library pathfinder. It's pretty good, and if you find ways to improve it, please do post them here, all AI developers will benefit from it.

I think I'm too far in to my pathfinder switch to the library one now. I've only just finished tunnel and bridge construction which too ages, and I'd rather not chuck that away. Plus my pathfinder is bloated with many other features. Stuff like estimating expenditure (so we can borrow JUST enough cash to cover a new route) and the length of the path. Plus I do all my slope checks in there. My node cost heuristic is rather long too. f(x) equals the following....

Code: Select all

function PathNodeFactory::ComputeCost(tile, parentNode, type) {
	// Estimated the distance from this node to the goal
	local h = sqrt(AITile.GetDistanceSquareToTile(tile, this.goalTile));
	//local h = AITile.GetDistanceManhattanToTile(tile, this.goalTile);
	
	// Distance were travelling in this step 
	local len = 1;
	if(parentNode != null && type == PathNode.TYPE_TUNNEL) {
		len = AIMap.DistanceMax(parentNode.GetTile(), tile);
		AILog.Info("    Tunnel length is " + len);
	}

	// Construction cost
	local constructionCost = 0;
	if(parentNode != null) {
		constructionCost = this.EstimateConstructionCosts(parentNode.GetTile(), tile, type);
	}

	// Normalised construction cost for pathfinding heuristic
	local relaxedCost = constructionCost;
	if(type == PathNode.TYPE_BRIDGE) {
		relaxedCost /= 2; // Be lenient to encourage use of bridges.
	} else if(type == PathNode.TYPE_TUNNEL) {
		relaxedCost /= 5; // Be VERY lenient for tunnels, or they'll never get built!
	}
	local normConstCost = max(((relaxedCost - 7) / 100), 0);

	// Cost for corners - prefer straight paths
	local cornerCost = 0;
	if(parentNode != null && parentNode.GetParent() != null) {
		local alignX = (AIMap.GetTileX(tile) == AIMap.GetTileX(parentNode.GetTile()))
				 && (AIMap.GetTileX(tile) == AIMap.GetTileX(parentNode.GetParent().GetTile()));
		local alignY = (AIMap.GetTileY(tile) == AIMap.GetTileY(parentNode.GetTile()))
				 && (AIMap.GetTileY(tile) == AIMap.GetTileY(parentNode.GetParent().GetTile()));
		if(!(alignX || alignY)) cornerCost = 1;
	}

	// The cost of climbing or descending a hill	
	local hillCost = (LandManager.IsLevel(tile) && type == PathNode.TYPE_ROAD) ? 0 : 1;

	// j term is sum of all the non-distance based metrics - more to come here!!
	local j = cornerCost + normConstCost + hillCost;
	
	// Return a cost object
	return PathCost((parentNode != null) ? parentNode.GetCost() : null, h, len, constructionCost, j);
}

Then I have a SEPARATE PathCost class to keep the compound cost for each node, so that I can retreive the final length and expenditure from the head of the path.

I keep trying to slim the code down, but its hard without dropping features!

Edit: Sorry about the initial thread title by the way! Swearing is a bad habit of mine, and I often don't realise I'm doing it!

[Zutty]

-In the pathfinder algorith, at first I did use a Sleep(1) for every tile that was evaluated in the openlist. That really slows things down a lot. After some experimenting, doing a Sleep only every 100 tile you evaluate does speed up things a lot, without completely blocking OpenTTd. If you use the library pathfinder, it does use also this value for the number of iterations.

GeekToo can I say a massive thank you for this suggestion! This is the magic bullet that instantly made my AI much faster! Its still not quite as fast as Convoy, but its at least within the same order of magnitude now. A route that used to take months to find now takes days.

Cheers