[Library] Introducing pathfinder.road

[Yexo]

paullb: Did you copy the exact code from the wiki page? Can you show me an example where it geos wrong (savegame + input / output tiles)?

[svetovoi]

I think current pathfinder can make mistakes in following(or similar) situation.

[Yexo]

I think current pathfinder can make mistakes in following(or similar) situation.

As stated in the comment, the current pathfinder will only try to build bridges on starting on a non-flat tile. So this situation can't be handled by the current pathfinder. The problem with trying to build bridges more often is that cpu-time will explode. If you find any other examples you think the pathfinder doesn't handle correctly, please post them here.

[TrueBrain]

I think current pathfinder can make mistakes in following(or similar) situation.

You were absolutely right on IRC, also the road pathfinder needs directional search to avoid mistakes it makes sometimes on slopes. When a foundation is build from one side, the other side might still hold a valid route. So nice job on spotting that problem. pathfinder.road v3 fixes that, and should find a path when ever possible.

[Yexo]

The only things that changes for AI writes is that GetNode() is renamed to GetTile().

[svetovoi]

Find following problem.

[Rubidium]

Find following problem.

Looks like the estimate function needs tweaking. However doing that makes the search area much much larger, which makes the pathfinding much much slower.

[Yexo]

The problem is introduced in r13956, a speedup for the pathfinder. That speedup was realised by exploring flat tiles only once, so not from every direction. The problem you see is that the north corner tile is entered by the pathfinder first from the south-east (as entering from the south-west involves both a turn penalty and a little less penalty for no existing roads). Later on, the tile isn't entered again from the south-west as it is already in the closed list. It's easy to fix this, just remove line 281 from the pathfinder (if (!is_bridge && AITile.GetSlope(to) == AITile.SLOPE_FLAT) return 0xFF;), but that will slow down the pathfinder so much (it'll take +- twice as long) that I'm against doing it in trunk.

Summary: the problem only exists when the added penalty for a turn is higher then the lower penalty because of used roads. So with the default cost, it only happens for up to two connected road tiles. In the image posted above there are two road tiles, so if one roadbit was added on one of the two sided the problem wouldn't occur.

Thx to ac84 for the bug report. If any of you find more problems with the pathfinder, please keep reporting them here.

[paullb]

paullb: Did you copy the exact code from the wiki page? Can you show me an example where it geos wrong (savegame + input / output tiles)?

Yes, I did. But the wiki explicitly says you have to build to loop yourself to make sure it built sucessfully. I was asking if anyone had that code.

As it says on http://wiki.openttd.org/index.php/AI:Pathfinder (please check it out)

This code loops over all the whole route. For every element, it checks whether it's already connected to the previous tile via road or via a bridge. If it's not connected it tries to build a road. Note that in a real AI you'll probably want to check if AIRoad.BuildRoad returns true, and if not restart pathfinding.

So its that check and restart pathfinding loop that i am after. Has anyone made one that works?

[GeekToo]

Convoy retries to build, when there is eg a vehicle in the way, and retries to plan the route when the road can not be build ( both with a limited number of retries )

[Yexo]

This code loops over all the whole route. For every element, it checks whether it's already connected to the previous tile via road or via a bridge. If it's not connected it tries to build a road. Note that in a real AI you'll probably want to check if AIRoad.BuildRoad returns true, and if not restart pathfinding.

So its that check and restart pathfinding loop that i am after. Has anyone made one that works?

That check is not that difficult, so you should be able to create it yourself. Example: at places where the wiki says: "TODO: handle error", you return false from you build-route-functoin. at the end of that function, return true. You check the return value and if false, call the pathfinder again and after that the builder. of course it'd better to check the error you get and only return false when necesary (for example, when you get vehicle in the way you could do a sleep(1) and retry).

[paullb]

This code loops over all the whole route. For every element, it checks whether it's already connected to the previous tile via road or via a bridge. If it's not connected it tries to build a road. Note that in a real AI you'll probably want to check if AIRoad.BuildRoad returns true, and if not restart pathfinding.

So its that check and restart pathfinding loop that i am after. Has anyone made one that works?

That check is not that difficult, so you should be able to create it yourself. Example: at places where the wiki says: "TODO: handle error", you return false from you build-route-functoin. at the end of that function, return true. You check the return value and if false, call the pathfinder again and after that the builder. of course it'd better to check the error you get and only return false when necesary (for example, when you get vehicle in the way you could do a sleep(1) and retry).

As I said, I tried that and it just looped for ever without giving any real error message.

[Yexo]

I don't understand your problem. Of course it doesn't magically print an error message. If you want an error message, you AILog.Error(AIError.GetLastErrorString()); somewhere.

[paullb]

I don't understand your problem. Of course it doesn't magically print an error message. If you want an error message, you AILog.Error(AIError.GetLastErrorString()); somewhere.

Yexo, Its quite simple. I was wondering if anyone had developped code to do the following as the wiki page states (please read the wiki page)

Note that in a real AI you'll probably want to check if AIRoad.BuildRoad returns true, and if not restart pathfinding.

Rather than reinventing the same wheel as everyone else, it would make sense to share that code too.

[Yexo]

I don't understand your problem. Of course it doesn't magically print an error message. If you want an error message, you AILog.Error(AIError.GetLastErrorString()); somewhere.

Yexo, Its quite simple. I was wondering if anyone had developped code to do the following as the wiki page states (please read the wiki page)

I know what is on the wiki page, I wrote that one myself

Note that in a real AI you'll probably want to check if AIRoad.BuildRoad returns true, and if not restart pathfinding.

Rather than reinventing the same wheel as everyone else, it would make sense to share that code too.

Aha, you just want better code. This is the code I use in AdmiralAI, note that the building is a bit optimized (building straight tracks in one go instead of piece by piece).

The function can return 3 different values:
0: everything is ok
-1: The pathfinder didn't find a path.
-2: You didn't have enough money to build the route.

Other errors then not-enough-money are just ignored. However, it's easy to change the comments "Other errors are ignored for now." with return -3, indicating something went wrong.

To use this function, you could for example do:
GetMoney(some value);
local ret = BuildRoad(pf, sources, goals);
while (ret != 0){
if (ret==-1) break;
if (ret==-2) getmoremoney or sleep untill we made some more.
ret = BuildRoad(pf, sources, goals);
}
If you are going to do this, make sure you don't thread ERR_ALREADY_BUILD as an error

Other than taking this code, you can also download several AIs from this forum and take a look at their code. For example the new RobotAI has a nice build function with a lot of error-checking http://www.tt-forums.net/viewtopic.php?f=65&t=38133

Code: Select all

function RouteBuilder::BuildRoadRoute(pf, sources, goals)
{
	pf.InitializePath(sources, goals);
	local path = pf.FindPath(-1);
	if (path == null) {
		AILog.Warning("RouteBuilder::BuildRoadRoute(): No path could be found");
		return -1;
	}

	while (path != null) {
		local par = path.GetParent();
		if (par != null) {
			local last_node = path.GetTile();
			local force_normal_road = false;
			while (par.GetParent() != null && par.GetTile() - last_node == par.GetParent().GetTile() - par.GetTile()) {
				last_node = par.GetTile();
				par = par.GetParent();
				force_normal_road = true;
			}
			if (force_normal_road || AIMap.DistanceManhattan(path.GetTile(), par.GetTile()) == 1 ) {
				if (!AIRoad.BuildRoad(path.GetTile(), par.GetTile())) {
					/* An error occured while building a piece of road, check what error it is. */
					if (AIError.GetLastError() == AIError.ERR_NOT_ENOUGH_CASH) return -2;
					/* Other errors are ignored for now. */
				}
			} else {
				/* Build a bridge or tunnel. */
				if (!AIBridge.IsBridgeTile(path.GetTile()) && !AITunnel.IsTunnelTile(path.GetTile())) {
					/* If it was a road tile, demolish it first. Do this to work around expended roadbits. */
					if (AIRoad.IsRoadTile(path.GetTile())) AITile.DemolishTile(path.GetTile());
					if (AITunnel.GetOtherTunnelEnd(path.GetTile()) == par.GetTile()) {
						if (!AITunnel.BuildTunnel(AIVehicle.VEHICLE_ROAD, path.GetTile())) {
							if (AIError.GetLastError() == AIError.ERR_NOT_ENOUGH_CASH) return -2;
							/* Other errors are ignored for now. */
						}
					} else {
						local bridge_list = AIBridgeList_Length(AIMap.DistanceManhattan(path.GetTile(), par.GetTile()));
						bridge_list.Valuate(AIBridge.GetMaxSpeed);
						bridge_list.Sort(AIAbstractList.SORT_BY_VALUE, false);
						if (!AIBridge.BuildBridge(AIVehicle.VEHICLE_ROAD, bridge_list.Begin(), path.GetTile(), par.GetTile())) {
							if (AIError.GetLastError() == AIError.ERR_NOT_ENOUGH_CASH) return -2;
							/* Other errors are ignored for now. */
						}
					}
				}
			}
		}
		path = par;
	}
	return 0;
}

[svetovoi]

I was wrong on IRC, when said that pf will make mistake not more then <turn.cost> value.
Seems there is a chance it can make such mistake each time when needed to turn.
With turn.cost increased to 200(still very low), pf can make awesome things(see screenshots).
If I calculated right, the mistake value is 960(24 clear tiles instead of 24 road tiles). It is almost 30% of best way cost! And may be more, when provoked by high turn penalty.
With low turn.cost pf is working not bad at all(with zero should be excelent), so instead of removing line

Code: Select all

if (!is_bridge && AITile.GetSlope(to) == AITile.SLOPE_FLAT) return 0xFF;

each AI writer can add simple check for turn.cost: if it too high => not ingore that condition.
Then pathfinder will be accurate(but indeed slower) or fast(but give small mistake) when you want it.

[wilco_moerman]

I think I've found a bug in the pathfinder. It tries to build bridges (perhaps also tunnels, not observed yet) that cannot be connected: The library-pathfinder tries to connect two adjacent bridges that are not in the same direction.



The small bridge is an already existing bridge, the longer bridge is built by the pathfinder. The "+" denotes the path tiles.

[Yexo]

I think I've found a bug in the pathfinder. It tries to build bridges (perhaps also tunnels, not observed yet) that cannot be connected: The library-pathfinder tries to connect two adjacent bridges that are not in the same direction.



The small bridge is an already existing bridge, the longer bridge is built by the pathfinder. The "+" denotes the path tiles.

This was fixed in trunk in r13641, and NoAI was synced in r13684, so since that version the pathfinder won't make this mistake again.

[wilco_moerman]

This was fixed in trunk in r13641, and NoAI was synced in r13684, so since that version the pathfinder won't make this mistake again.

great work!

[Michiel]

The path finder sometimes finds paths that lead into the side of a drivethrough station. Looking through the code, I'd guess this is due to AIRoad.CanBuildConnectedRoadPartsHere(). This function considers slope and direction of roads, but not whether there is a station on the tile. Shouldn't it?