(New to this) Pathfinder question

[honnes]

Hello,

For the last few days I've been putting myself into making an AI for OpenTTD but it's quite difficult for me, as I'm not used to the squirel programming language (yet), and run into the first trouble with the pathfinder.

I don't know if there are any tutorials or anything that gives an overview of how to get things done, like a tutorial checking for closest buildable position, or on a road, if it can be a drive-through station. If anyone knows a good site, i'd love to hear that.

But as for now, I've got a question regarding the Pathfinder. I'm using road pathfinder version 4 with aystar 6, which works ok, especially after I found out how to tweak some settings so it won't search years for the 'perfect' route. My trouble is, as a test, I'm trying to build a road between the 2 biggest populated towns there are, and it finds the path ok, and it also starts building, but for some reason, it often stops building in the middle of nowhere. It only happens when the (Manhatten)distance is very long.

I've also tried to check the code of other AI's, but as those are hard for me to understand as a beginner, I couldn't make much out of most of them, except that I managed to get another way of building a route (per segment), and ended up on the same result.

At first I thought the AI ran out of money, but it also happens when I make sure it doesn't build bridges. Does anyone have an idea what I can do or try ? Or should I just quit on testing to build a road over an very, very, long distance ?

Thanks for any help ! And if anyone got some information on to how to get started with things like building a deposit close to a certain tile within the influence area or so, whether it's a tutorial or an existing AI which is easy to understand, I'd love to hear that.

[Roujin]

Hi there,

what ever there is on tutorials/example code, will most likely be found in the noAI section of the OpenTTD wiki.
On your specific problem, did you make sure it didn't run out of money? i.e. by opening the AI company's finance window and check its balance, when the problem happened?

[honnes]

Thanks Roujin, and before I posted, I had read and been through all those wiki-pages of the NoAI, but thanks for referring me to them, just in case

Oh my goodness, I'm afraid you're right, shame on me, I never knew I could check the finance of the other company just like that ingame. (Haven't played for quite a while, but the game caught my interest again)

I'm afraid there's something going wrong with my inputs for the max_cost or so then. As for the pathfinder.cost.tile and such, are there any values which are recommended ? I put the bridge/tunnel tile to like 200-300, as it otherwise starts building bridges even when there's no water or such, which is a shame. I put the max_cost on 15 times the manhatten distance between the start and endtile, of which I read isn't a too bad value, is it ? And since I prefer to build roads without bridges, I put the slope to 10, and the tile costs to 1, but that might be just where I end up going wrong.

I really hope that I'm not being a bugger or anything while asking around things which might sound, or hopefully for me, easy, but I'm here to learn and get to know how to make an AI, and hopefully it will be worthy releasing it here once it's finished, even if it would be one that can be used by other starters, like me, to get to know things better and to understand them.

I read on the forum that OtviAI is one that a lot can be learned from, so I'll check that one surely out to lessen my stupidity , and the AI I'll (try) to build won't be a very advanced one, I guess, but I'll do my best to get lots of documentation in it, about what a function does, can, and maybe parts of the code documented too, so others can learn from it.

[honnes]

I'm once back about this subject, and done some little tests and got some things to work and read most of the time other code to get to know things better. So as a small start from myself, without building any vehicle deposits, I decided to make something that actually makes a road.

I've been watching over a few AI's ingame, and saw that AdmiralAI for instance was building routes quite fast, not just in calculating, but also in speed of getting it done.

What I've been trying is to make a list of all towns and I sorted them on population. After that, I made a small loop, which does nothing more than try to find a route between the biggest town and the next biggest town. I've put some variables in it, like itherations on 15 (but not exactly what kind of performance difference it makes), put the costs on max 40.000 and adjusted some parameters of the pathfinder. (so it won't build bridges or tunnels). It then tries to find a path between the biggest town and the next biggest one, and when it fails, it tries to connect to the next biggest after that one. I know it's a silly test, but I just wanted to try it out. THe thing that surprises me, and works rather on my nerves, is that it takes months and months before it realizes that the path is either too long, or too expensive. (I've put the max ticks it should try on 400)

It really makes me feel down actually, as it's kinda sad to see it is taking so long. I've played around with the _estimation thing, and I've also tried to use the RPF of AdmiralAI (and imported the few Util functions needed, and the aystar), but it made my results not differ anything.

What could I be doing wrong that it takes over, on 512*512 maps, even over 2 years. Is it just my test, and should I look for cargo places and try to connect those, or is it something I possibly could do wrong ?

[Yexo]

What is the distance between the towns you're trying to connect? That is pretty essential information. Also are you sure the exists a path between the two towns? If there is no route and you dno't set max_cost appropriately, the whole map will be searched.

[honnes]

Hello Yexo,

First, I have to say thanks for taking time to read, respond, and for helping me to get things right. I do appreciate that.

As for the pathfinder, I've tried different max_costs, but some of the times, the max_cost was for instance 40k, yet it still built a route which cost the AI all the money it had. As for now, I implemented the AdmiralAI RPF, as I was stunned how fast it could built, so I tried my luck with that one. The max_cost of that one is by default 1 mil, but I guess that AdmiralAI adjusts this value before starting to initiliaze a pathfind action.

I will code a little more, and make my AI do a useful action, like checking for a subsidy offer, and get a route between that and see how that goes. After that, I'll try my test of the biggest to next biggest town route available with decent costs again, and I'll debug some manhatten distance it finds, and put them over here, so maybe someone can give a comment or leave some feedback about if that's a distance that takes long too find or so, anything is appreciated that could help me .

I have to admit I find it hard to understand and get to know how the pathfinder can be optimized and put to really good use, but little by little I hope to get there.

I'll be back here later again, once I got something to work, and post my results.

[Yexo]

As for the pathfinder, I've tried different max_costs, but some of the times, the max_cost was for instance 40k, yet it still built a route which cost the AI all the money it had.

AH, now I see the problem. The max_cost variable is the not for building cost, but for pathfinding cost. So if you set cost_tile to 100 and max_cost to 2000, the maximum length of a route is 20 tiles.

As for now, I implemented the AdmiralAI RPF, as I was stunned how fast it could built, so I tried my luck with that one. The max_cost of that one is by default 1 mil, but I guess that AdmiralAI adjusts this value before starting to initiliaze a pathfind action.

The roadpathfinder in AdmiralAI is just a modification of the default road pathfinder library.

I will code a little more, and make my AI do a useful action, like checking for a subsidy offer, and get a route between that and see how that goes.

THere is a limit on the distance between towns for subsidies, so that'll probably work ok.

[Dustin]

What is the distance between the towns you're trying to connect? That is pretty essential information. Also are you sure the exists a path between the two towns? If there is no route and you dno't set max_cost appropriately, the whole map will be searched.

It's pretty trivial to check the distance before you start the pathfinder and only try to find paths that are not too long. You are probably wasting a lot of time in the pathfinder on routes that are too long for you in the first place.

[honnes]

Thanks for the info

So far, I got my subsidy check done, making the proper stations (with a subsidy cargo check or so, and check if the ID returns 0), end going to try and make a route between those 2 towns.

I start to find out that my first test was kind of a killer looking at how essential the distance information is. Could I do any x.Valuate on the list that would for instance check all Manhatten distances and keep those with a normal distance ? (whatever a normal distance might be ), or is there also a certain thing that can be checked like, look for X tiles in the current range, and keep all those towns in the list, and after that, I could do a valuate on the list and keep those with a decent population, and try to connect routes between them, so my AI won't always look for the most and most benefiting route on the whole map.

[edit]As I don't want to be a topic-bumper, I just edit my current topic, as there hasn't been any reply since, but just found out something myself. I have now got it to work that it builds a road between subsidy roads, and also the stations. But for some strange reason, I must have used the AdmiralAI RPF on the wrong way, because using that RPF, I could not find a route, but with the default RPF, I could. here's the 2 parameters I use to find the route:

Code: Select all

pathfinder.InitializePath(startTiles, endTiles, 1.2, 20)
pathfinder.FindPath(4);

I have to admit, I don't exactly know what the last 2 parameters exactly do. The 1.2 is a max_lenght_offset, and the other is ignored tiles, and filled something in as it gave an error if I just did initializepath with just the first 2 parameters. Also, I'm not quite sure what is meant with '4' parameter of the findpath thing, I know it's the amount of itherations it does, but when I adjust the number to something higher, I think it would search for more routes, until it has done 15 itherations. Please correct me if I am wrong.

I read that the pathfinder returns false when there are more routes to search, and null if there is none at all. Does this mean that I could just 'choose' a route on one or the other way if it returns false ?

If it is, and I should make an own piece of code, could I use this then to search for a route within a certain time limit ?

Assume that this code is part of a function, and that I return 'path' just below the while loop.

Code: Select all

while (path == null) 
{
	path = pathfinder.FindPath(4);
	if ((GetTick() - tick) > 500) 
	{
		AILog.Warning("ROADS: Searching took longer than 500 ticks, stopping with searching");
        	path = null;
		break;
	}
}

Hmm...I just tried this out after writing this, and it gives an error about there's no GetParent when building the route. This makes me think that, as long as the route is 'false', there is not yet a complete route to be returned, as when I change the 'path == null' to false, it makes a route.

I only can tell that I can't find a route between the 2 towns with AdmiralAI RPF usage, but with the normal one, I managed to. (without adjusting the 4). I hope someone can inform me about this, as I am really curious what I have done wrong and what I could adjust, try out, or look at, to increase the performance or to get a better result

I just included 2 screenshots of my RPF errors. On one of them, my debug window of the AI is visible, the distance is really small in my opinion, yet it failed to get it done in 400 game ticks, which is, as visible on the screen, 22 ingame-days. This should not happen, right ? I hope someone can help me in getting this matter fixed. On the other screenshot is a zoomed in shot, of two more towns which it failed to find a route, yet, it can be built with just 1 turn in it.

RPF Fail #1

Thomson & Co., 16th Jan 1953.png (119.03 KiB) Viewed 3733 times

RPF Fail #2

Unnamed, 2nd Sep 1950.png (90.27 KiB) Viewed 1183 times

[/edit]

Anyway, I'll try to figure and work some things out and get back here once I got something working, you guys are a great help to me, that's one thing that has to be said !

Have a nice day and weekend, and keep your weekend to yourself instead of replying and helping me out, I have no rush

[Yexo]

Can you please post the complete code of your AI so far? I'd much rather look through some of your code and try it myself then guessing from your descriptions what went wrong.

[honnes]

Thanks for your offer in helping me, Yexo, as it's going wrong with some routes (99% gets build, when it comes to subsidy routes), I'll post my routefinding code below.

Code: Select all

pathfinder.cost.tile = 1;
pathfinder.cost.max_cost = 40000;		// TODO: Misschien dynamisch maken
pathfinder.cost.no_existing_road = 5;	// The cost that is added to _cost_tile if no road exists yet.
pathfinder.cost.turn = 10;				// The cost that is added to _cost_tile if the direction changes.
pathfinder.cost.slope =	15;				// The extra cost if a road tile is sloped.
pathfinder.cost.bridge_per_tile = 20;	// The cost per tile of a new bridge, this is added to _cost_tile.
pathfinder.cost.tunnel_per_tile = 20;	// The cost per tile of a new tunnel, this is added to _cost_tile.
pathfinder.cost.coast =	20;				// The extra cost for a coast tile.
pathfinder.cost.max_bridge_length = 10;	// The maximum length of a bridge that will be build.
pathfinder.cost.max_tunnel_length = 10;	// The maximum length of a tunnel that will be build.
pathfinder.InitializePath(startTiles, endTiles);
Debug("ROADS: Searching for a cheap route...");
local path = false;
local tick = GetTick();
while (path == false) 
{
	path = pathfinder.FindPath(15);
	if ((GetTick() - tick) > 500) 
	{
		Warning("ROADS: Searching took longer than 500 ticks, stopping with searching");
		path = null;
		break;
	}
}

If it can find a path, I simply go to the buildfunction and that goes just like it is expected to. If I have to do a rough guess on what is going wrong, I'd say there's something wrong with my parameters. I will try to let it search longer, or upon failure of the route, try to find a more expensive route. I think it's because there's many differences in height in the route, which take much in account of the costs.

I hope you can tell me what I'm doing wrong, but until that time, I'll play around with variables, as I never give up, and don't like sitting around and just wait until someone helps me Thank you for the time you put into helping me.

[Yexo]

With those variables it'll be very slow because most tiles are much more expansive that the basic cost (=cost.tile). Have you tried just using the default values?

Otherwise, you could try something like this and see what the results are

Code: Select all

pathfinder.cost.tile = 10;
pathfinder.cost.max_cost = 4000;	    	// = equivalent of 400 tiles
pathfinder.cost.no_existing_road = 0;	  // don't care about reusing existing roads
pathfinder.cost.turn = 1;			     	// minor penalty for turns
pathfinder.cost.slope =	0;		  		//  don't care about slopes
pathfinder.cost.bridge_per_tile = 5;	   // bridges / tunnels are 50% more expensive per tile than normal tiles
pathfinder.cost.tunnel_per_tile = 5;
pathfinder.cost.coast =	0;			  	// don't care about coast tiles
pathfinder.cost.max_bridge_length = 10;	// The maximum length of a bridge that will be build.
pathfinder.cost.max_tunnel_length = 10;	// The maximum length of a tunnel that will be build.

[honnes]

Thanks for your help, I'll try to work with values like those, but as I tried your values, it took longer than it did with those I have. It sometimes also returned true for a path, but yet it could not build it, or when I did path.GetCost(), it gave an error as well.

Mine goes a bit faster when I put the cost based on a multiplier of the distance. (like 20 times the manhattan distance). I don't know what it could be that it takes longer with the values you gave, but I'll look into them and figure it out .

Anyway, when I know what it (possibly) could be, I'll post it down here. Thanks again for your help

[edit] I had a small bug in my code which made the error happen, my bad ! I didn't check properly if there was a path, and I got my values now a bit customized which works like a charm for my purpose !

A little bit 'off-topic', as when I search for '!=null', it searches for the word 'null' and I get numerous results. When programming in other programming languages, the code below works, but in squirrel, it still goes in the if statement.

Code: Select all

station1 = buildStation(x);
station2 = buildStation(x2);

if (station1 != null && station2 != null)
{
 // Some code where I make a depot and vehicles
}

//Somewhere else in the code
function buildStation(stationtile)
{
  if (AIRoad.BuildDriveThroughStation(parameters...))
     return stationtile;

  return null
}

This code of mine has worked when I let my AI run for like 20 years, and then I get an error that I am not allowed to build due to local authority things, so my station1 = null, and my station2 works. Yet, it passes through that IF-statement of mine, which should not happen as it checks if both are not equal to null.

Is there something wrong with my checks, which I think there isn't, or should I check differently, to make sure it won't run the code in that statement ?

[/edit]

[Yexo]

A little bit of debugging can give you that info. Just add the following code as the first lines inside your if-block:

Code: Select all

AILog.Info("station1: " + station1);
AILog.Info("station2: " + station2);

[honnes]

A little bit of debugging can give you that info. Just add the following code as the first lines inside your if-block:

Code: Select all

AILog.Info("station1: " + station1);
AILog.Info("station2: " + station2);

Hmm, I should use more of those debug things indeed, but when the AI crashed, I looked at the variable list in red, which I think is the current list of actual values bound to the variables, and it said [station1] null , [station2] 31456, and that it crashed on line X, where line X is a line between the if statement in my previous off-topic bit of post, but I guess there's something wrong in my code, and I'll use more debug things like you recommend, thanks

[fanioz]

Have you tried with an other expression, eg.

Code: Select all

if (station1 && station2) {
// your next code
}

Edited:
Value of 'null', 'false', '0' would threat as 'false'. Otherwise 'true.

[honnes]

Have you tried with an other expression, eg.

Code: Select all

if (station1 && station2) {
// your next code
}

Edited:
Value of 'null', 'false', '0' would threat as 'false'. Otherwise 'true.

Fanioz, that's some valuable information, in other programming languages, a 'null', number, and boolean are threated differently. Thanks again for all the help .

I'll take a look into the documentation of Squirrel as well, and check if there's anything else that might come in handy

For those whom might be interested in it, or want to check the reference manual as well, it can be found here: http://squirrel-lang.org/doc/squirrel2.html

[edit] And so I found out that the 0.0 float is also considered as false [/edit]

[Kogut]

With those variables it'll be very slow because most tiles are much more expansive that the basic cost (=cost.tile). Have you tried just using the default values?

Otherwise, you could try something like this and see what the results are

Code: Select all

pathfinder.cost.tile = 10;
pathfinder.cost.max_cost = 4000;	    	// = equivalent of 400 tiles
pathfinder.cost.no_existing_road = 0;	  // don't care about reusing existing roads
pathfinder.cost.turn = 1;			     	// minor penalty for turns
pathfinder.cost.slope =	0;		  		//  don't care about slopes
pathfinder.cost.bridge_per_tile = 5;	   // bridges / tunnels are 50% more expensive per tile than normal tiles
pathfinder.cost.tunnel_per_tile = 5;
pathfinder.cost.coast =	0;			  	// don't care about coast tiles
pathfinder.cost.max_bridge_length = 10;	// The maximum length of a bridge that will be build.
pathfinder.cost.max_tunnel_length = 10;	// The maximum length of a tunnel that will be build.

Thanks! It reduced time of work from 8 months to 2. But why?

[Zutty]

I imagine mainly because the max_cost is less, so it will have a shorter OPEN list.

Do you understand how the A* algorithm works? It might help you to study the theory a little if you want to learn how to tune the pathfinder.