Road Pathfinder Modifications

[Zutty]

Hi all,

After a quick discussion with Yexo and a sharp blow to the head I have decided to abandon my custom pathfinder in favour of making modifications to the library road pathfinder, so that any modifications I might make can be shared with others. So here they are...

Road.diff

(7.47 KiB) Downloaded 349 times

EDIT: Diff 18/01/09 updated with a small bug fix.

I must admit I've never done a diff before so I hope this is the right format!

I have added the following functionality...

• 1) Allow tiles to be ignored
• 2) Optionally enable demolition to allow removal of town houses
• 3) Allow additional cost to be applied to nodes via registerable cost callback functions

Note that none of these modifications change the API. I've also tried to stick to the standard coding style.

1) Is very simple, as I have simply exposed the ignore_tiles parameter from the aystar library.

Code: Select all

function InitializePath(sources, goals, ignored_tiles = []) {
	...
	this._pathfinder.InitializePath(nsources, goals, ignored_tiles);
}

This allows the pathfinder to build simple road loops by blocking the trivial path to the goal and forcing it to go around.

2) was much more difficult as I had the change the way the pathfinder checks if a road can be built. The pathfinder allows demolition on any tile that isn't buildable but that can be demolished in test mode. Unfortunately this means that construction of those tiles in entirely speculative until the tile has actually been demolished in exec mode. This means that the pathfinder cant use AIRoad.BuildRoad() in test mode to check if the road can be built. To get around this I used three calls of AIRoad.CanBuildConnectedRoadPartsHere(). One for the current tile, and one each for the next a previous tiles, for which we have to search for neighbours (the nn_tile and pp_tile). The other two checks are necessary for some cases where a path meets an existing road on a slope.

Code: Select all

function Road::_IsConnectable(cur_node, par_node, next_tile)
{
	local offsets = [AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1),
	                 AIMap.GetTileIndex(1, 0), AIMap.GetTileIndex(-1, 0)];
	local connectable = true;
	
	if (par_node != null) {
		connectable = AIRoad.CanBuildConnectedRoadPartsHere(cur_node, par_node.GetTile(), next_tile);
		foreach(offset in offsets) {
			local pp_tile = par_node.GetTile() + offset;
			local nn_tile = next_tile + offset;
			
			if (AIRoad.AreRoadTilesConnected(par_node.GetTile(), pp_tile)) {
				connectable = connectable && AIRoad.CanBuildConnectedRoadPartsHere(par_node.GetTile(), pp_tile, cur_node);
			}
			if (AIRoad.AreRoadTilesConnected(next_tile, nn_tile)) {
				connectable = connectable && AIRoad.CanBuildConnectedRoadPartsHere(next_tile, nn_tile, cur_node);
			}
		}
	}
	
	if (AIRoad.IsDriveThroughRoadStationTile(cur_node)) {
		connectable = connectable && (AIRoad.GetRoadStationFrontTile(cur_node) == next_tile
					 || AIRoad.GetDriveThroughBackTile(cur_node) == next_tile);
	}
	if (AIRoad.IsDriveThroughRoadStationTile(next_tile)) {
		connectable = connectable && (AIRoad.GetRoadStationFrontTile(next_tile) == cur_node
					 || AIRoad.GetDriveThroughBackTile(next_tile) == cur_node);
	}
	return connectable;
}

It looks ugly but I promise you it works, and it doesn't seem to impact performance dramatically. If you can find a better way though, without using test mode I'd love to know.

This is turned off by default. You activate it setting the allow_demolition parameter...

Code: Select all

pathfinder.cost.allow_demolition = true;
pathfinder.cost.cost_demolition = 1250;

3) uses a simple array to store a list of [callback, args] tuples and then executes each one in the cost function and accumulates the result. This allows additional costs to be added to alter the pathfinders behaviour at runtime, and does so in a loosely-coupled manner.

Code: Select all

function RegisterCostCallback(callback, ...) {
	local args = [];
	for(local c = 0; c < vargc; c++) {
		args.append(vargv[c]);
	}
	this._cost_callbacks.push([callback, args]);
}

Code: Select all

foreach(item in self._cost_callbacks) {
	local args = [{}, new_tile, prev_tile];
	args.extend(item[1]);
	local value = item[0].acall(args);
	
	if (typeof(value) != "integer") {
		throw("Invalid return type from cost callback");
	}
	
	cost += value;
}

Hope you find these useful In particular I hope Yexo finds 2) useful.

I must confess that I haven't tested this extremely thoroughly, so if you find bugs please let me know. Plus if anyone has any other suggestions please post them.

[Yexo]

Hi all,

After a quick discussion with Yexo and a sharp blow to the head I have decided to abandon my custom pathfinder in favour of making modifications to the library road pathfinder, so that any modifications I might make can be shared with others. So here they are...

Road.diff

I must admit I've never done a diff before so I hope this is the right format!

Nearly right, next time reverse the files as arguments to diff, so the lines you add will show up with a + in front of them in the patch, and the lines you remove will be prefixed with a -.

Nice and clean changes Zuu, I'll certainly incorporate the town house demolition part in AdmiralAI (if that's ok with you of course ). Tomorrow I'll clean up my changes to AyStar / the road pathfinder and post them. Most important change I've made is an addition so I can quite pathfinding if the total path will be too long anyway (this prevents searching the whole map for a route if the destination can't be reached.)

[Zutty]

Nearly right, next time reverse the files as arguments to diff, so the lines you add will show up with a + in front of them in the patch, and the lines you remove will be prefixed with a -.

Oops! Thanks for the tip. I've changed the diff.

Nice and clean changes Zuu, I'll certainly incorporate the town house demolition part in AdmiralAI (if that's ok with you of course ). Tomorrow I'll clean up my changes to AyStar / the road pathfinder and post them. Most important change I've made is an addition so I can quite pathfinding if the total path will be too long anyway (this prevents searching the whole map for a route if the destination can't be reached.)

Thanks very much. Of course I'm happy for you or anyone else to use it. I'm glad you like it!

I'll look forward to seeing your modifications.

[Yexo]

The following patch adds a maximum length to the road pathfinder, this prevents the pathfinder searching the whole map if the destination is unreachable. Only api change is InitializePath.

Code: Select all

function InitializePath(sources, goals, max_length_multiplier, max_length_offset, ignored_tiles = []);

The maximum length for a route is max_length_offset + max_length_multiplier * AIMap.DistanceManhattan(sources[0], goals[0]);

Edit: for normal routes, I use offset = 20 and multiplier = 1.2

[Yexo]

I'd like to combine these changes, and maybe more, into a new library version so multiple AIs will use the library again. Before I do this however, I'd like to know from other AI writers if there are any changes they'd like to see in the road pathfinder library. Please keep in mind that those changes should be useful for multiple AIs. This is also the time to discuss the default values for several pathfinding parameters, if you think you've found better defaults and you'd like to share them, please do.

@Zutty: "3) Allow additional cost to be applied to nodes via registerable cost callback functions"
What is the purpose of this?

To start I propose to change the maximum bridge length from 10 tiles to 20 tiles. On maps with a lot of water 10 tiles just isn't enough.

[Zutty]

@Zutty: "3) Allow additional cost to be applied to nodes via registerable cost callback functions"
What is the purpose of this?

This is to allow additional costs to be added to tiles without having to change the code of the pathfinder. Think of it as an implementation of the decorator design pattern.

I use this ATM to give my road loops depth by adding a high cost to the tiles either side of a DTRS. This is to avoid ugly stuff like this...

A 'flat' loop - ugly!

dtrsflatloop.png (12.41 KiB) Viewed 10090 times

I plan to use it for all sorts of things in future like 2-lane highways, separation of tram tracks and roads, snapping roads in towns to a preset layout (e.g. to match with 2x2/3x3 town road layouts), and so on...

If you really don't like it then take it out, but I will keep it either way.

To start I propose to change the maximum bridge length from 10 tiles to 20 tiles. On maps with a lot of water 10 tiles just isn't enough.

Sounds good. I use currently use a much higher number to avoid broken networks on maps with A LOT of water (in lieu of a real solution!).

[Yexo]

@Zutty: "3) Allow additional cost to be applied to nodes via registerable cost callback functions"
What is the purpose of this?

This is to allow additional costs to be added to tiles without having to change the code of the pathfinder. Think of it as an implementation of the decorator design pattern.

I use this ATM to give my road loops depth by adding a high cost to the tiles either side of a DTRS. This is to avoid ugly stuff like this...

Leaving it in is ok with me, I just didn't understand of what use it was, but now I do.

[Zutty]

Apologies but there was a bit of a bug in my diff.

Line 236 should have a this instance instead of an empty table {}, i.e.

Code: Select all

local args = [this, new_tile, prev_tile];

I've updated the diff with this change.

I suppose this technically means that pathfinder instance can be accessed from within a cost callback, but I dont think that has huge implecations for code security TBH!

BTW just to prove the value of the cost callback system, here is the result of a callback that penalises roads that are built on top of other roads of a different type, but that promotes roads built directly adjacent to existing roads of a different type. In simple terms it forces tram tracks to be next to roads...

The tram track is built NEXT to the road, not over it. Its like this all over the map.

parrl.png (289.02 KiB) Viewed 2164 times

The code that gave rise to this is simply...

Code: Select all

pathfinder.RegisterCostCallback(function (tile, prevTile, roadType) {
	local diff = AIMap.GetMapSizeY() / (tile - prevTile);
	local parrl = (AIRoad.IsRoadTile(tile + diff) && !AIRoad.HasRoadType(tile + diff, roadType))
				|| (AIRoad.IsRoadTile(tile - diff) && !AIRoad.HasRoadType(tile - diff, roadType));
	return ((AIRoad.IsRoadTile(tile) && !AIRoad.HasRoadType(tile, roadType)) ? PathWrapper.COST_SEPARATE_ROAD_TYPES : 0)
				+ ((parrl) ? 0 : PathWrapper.COST_PARALLEL_BONUS);
}, roadType);

[zothar]

Code: Select all

function Road::_IsConnectable(cur_node, par_node, next_tile)
{
	local offsets = [AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1),
	                 AIMap.GetTileIndex(1, 0), AIMap.GetTileIndex(-1, 0)];
	local connectable = true;
	
	if (par_node != null) {
		connectable = AIRoad.CanBuildConnectedRoadPartsHere(cur_node, par_node.GetTile(), next_tile);
		foreach(offset in offsets) {
[...]
	return connectable;
}

It would seem to me that the Road::IsConnectable() method could be optimized, though it's very likely I just don't know what I'm talking about, not having done any NoAI coding before. If once the "connectable" local variable is false, it will never be true for this call, then why not short-circuit the logic (apologies for any coding-style badness):

Code: Select all

function Road::_IsConnectable(cur_node, par_node, next_tile)
{
	local offsets = [AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1),
	                 AIMap.GetTileIndex(1, 0), AIMap.GetTileIndex(-1, 0)];
	local connectable = true;
	
	if (par_node != null) {
		connectable = AIRoad.CanBuildConnectedRoadPartsHere(cur_node, par_node.GetTile(), next_tile);
		if(!connectable) {
			return false;
		}
		foreach(offset in offsets) {
			local pp_tile = par_node.GetTile() + offset;
			local nn_tile = next_tile + offset;
			
			if (AIRoad.AreRoadTilesConnected(par_node.GetTile(), pp_tile)) {
				connectable = connectable && AIRoad.CanBuildConnectedRoadPartsHere(par_node.GetTile(), pp_tile, cur_node);
			}
			if(!connectable) {
				return false;
			}
			if (AIRoad.AreRoadTilesConnected(next_tile, nn_tile)) {
				connectable = connectable && AIRoad.CanBuildConnectedRoadPartsHere(next_tile, nn_tile, cur_node);
			}
			if(!connectable) {
				return false;
			}
		}
	}
	
	if (AIRoad.IsDriveThroughRoadStationTile(cur_node)) {
		connectable = connectable && (AIRoad.GetRoadStationFrontTile(cur_node) == next_tile
					 || AIRoad.GetDriveThroughBackTile(cur_node) == next_tile);
	}
	if(!connectable) {
		return false;
	}
	if (AIRoad.IsDriveThroughRoadStationTile(next_tile)) {
		connectable = connectable && (AIRoad.GetRoadStationFrontTile(next_tile) == cur_node
					 || AIRoad.GetDriveThroughBackTile(next_tile) == cur_node);
	}
	return connectable;
}

[zothar]

Of course, now having posted, I re-read my suggested changes and realize that the existing code partially short-circuited already, so here's my revised version:

Code: Select all

function Road::_IsConnectable(cur_node, par_node, next_tile)
{
	local offsets = [AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1),
	                 AIMap.GetTileIndex(1, 0), AIMap.GetTileIndex(-1, 0)];
	local connectable = true;
	
	if (par_node != null) {
		connectable = AIRoad.CanBuildConnectedRoadPartsHere(cur_node, par_node.GetTile(), next_tile);
		if(!connectable) {
			return false;
		}
		foreach(offset in offsets) {
			local pp_tile = par_node.GetTile() + offset;
			local nn_tile = next_tile + offset;
			
			if (AIRoad.AreRoadTilesConnected(par_node.GetTile(), pp_tile)) {
				connectable = connectable && AIRoad.CanBuildConnectedRoadPartsHere(par_node.GetTile(), pp_tile, cur_node);
			}
			if (connectable && AIRoad.AreRoadTilesConnected(next_tile, nn_tile)) {
				connectable = connectable && AIRoad.CanBuildConnectedRoadPartsHere(next_tile, nn_tile, cur_node);
			}
			if(!connectable) {
				return false;
			}
		}
	}
	
	if (connectable && AIRoad.IsDriveThroughRoadStationTile(cur_node)) {
		connectable = connectable && (AIRoad.GetRoadStationFrontTile(cur_node) == next_tile
					 || AIRoad.GetDriveThroughBackTile(cur_node) == next_tile);
	}
	if (connectable && AIRoad.IsDriveThroughRoadStationTile(next_tile)) {
		connectable = connectable && (AIRoad.GetRoadStationFrontTile(next_tile) == cur_node
					 || AIRoad.GetDriveThroughBackTile(next_tile) == cur_node);
	}
	return connectable;
}

[Yexo]

You are still overdoing it:

Code: Select all

         if (connectable && AIRoad.AreRoadTilesConnected(next_tile, nn_tile)) {
            connectable = connectable && AIRoad.CanBuildConnectedRoadPartsHere(next_tile, nn_tile, cur_node);
         }

can be simplified to:

Code: Select all

         if (connectable && AIRoad.AreRoadTilesConnected(next_tile, nn_tile)) {
            connectable = AIRoad.CanBuildConnectedRoadPartsHere(next_tile, nn_tile, cur_node);
         }

But I'll make sure to take this function into account before posting a new version.

@Zutty: If I wasn't convinced by your explanation here, I'm now by your examples. To me it's clear this should be in the next road pathfinder version.

I'll wait for new suggestions / patches to the road pathfinder until Thursday 22th January. On friday I'll start integrating all changes and post a beta version for you to test. When no bugs are found / enough AI writers are happy with that version, I'll upload it (or rather ask TrueBrain to upload it) to BaNaNas as the next version of the road pathfinder library.

[Rubidium]

I'll wait for new suggestions / patches to the road pathfinder until Thursday 15th.

That'd be the Thursday 15th May 2009 or do you mean another day?

[Yexo]

Oops, fixed the previous message

[GeekToo]

Zutty,

I did not think too long about it but some remarks:
-Do you have to loop the pp_tiles? Weren't they checked in the previous iteration?
-AIRoad.AreRoadTilesConnected, does that make sense in test mode as the road won't be build yet
-You only have to check 3 out of 4 of the nn_tiles (leave the cur tile out)
-CanBuildConnectedRoadPartsHere is no boolean, so failing the preconditions will return -1, and probably evaluate as true. May lead to problems on invalid tiles.
Using values as boolean is, let's say ... creative

[Zutty]

Thanks for the suggestions guys...

It would seem to me that the Road::IsConnectable() method could be optimized, though it's very likely I just don't know what I'm talking about, not having done any NoAI coding before. If once the "connectable" local variable is false, it will never be true for this call, then why not short-circuit the logic

Good point, thanks for the tip. Every little bit of performance helps

You are still overdoing it...

Ah yes, ofcourse.

Zutty,

I did not think too long about it but some remarks:
-Do you have to loop the pp_tiles? Weren't they checked in the previous iteration?
-AIRoad.AreRoadTilesConnected, does that make sense in test mode as the road won't be build yet
-You only have to check 3 out of 4 of the nn_tiles (leave the cur tile out)
-CanBuildConnectedRoadPartsHere is no boolean, so failing the preconditions will return -1, and probably evaluate as true. May lead to problems on invalid tiles.
Using values as boolean is, let's say ... creative

1 & 2) The whole point of this is to check those very rare cases where a path meets an existing road on a slope. pp_tile isn't necessarily on the path we've found so far, nor is nn_tile.
3) Good point. I'll roll that into zothar's suggestions.
4) ARGH! Damn you're right. In my haste to make clean looking code I neglected the "== 0" test. I did know this already, honest!!

It took me ages to come up with a solution that is guaranteed to work, not least of all because its exeedingly difficult to debug an issue that crops in in such a small proportion of cases. Because of this I've been too scared to touch it now it works! Theres probably a more efficient way to do this, but I haven't looked for one yet!

A really good solution might be to create a new API function that checks for road bits on all three tiles in a single call. If some clever person wants to have a go at this I'd be very interested to see how it turns out.

@Zutty: If I wasn't convinced by your explanation here, I'm now by your examples. To me it's clear this should be in the next road pathfinder version.

Yay! I've finally contributed something useful!

[GeekToo]

-Do you have to loop the pp_tiles? Weren't they checked in the previous iteration?
-AIRoad.AreRoadTilesConnected, does that make sense in test mode as the road won't be build yet

1 & 2) The whole point of this is to check those very rare cases where a path meets an existing road on a slope. pp_tile isn't necessarily on the path we've found so far, nor is nn_tile.

I still fail to see why you have to loop over the pp_tiles. Maybe I misunderstand what your algorithm tries to achieve, or I am missing a situation where things go wrong, or the algorithm does too much work. Until proven otherwise, I'll assume the first two reasons are true, so I can learn something, or else the algorithm gets improved (that's a situation I like: in every case I have a benefit...).

To start with the first:
My assumption about what the algorithm should do:
Given a previous (parent) tile, and the current tile, on every iteration of the pathfinder you try to find a connectable next tile, more precise, whether a connection can be made from the centre of the current tile to the centre of the next.

That's why I asked why you loop over the neighbours of the parent tile, because in the previous iteration of the pathfinder you already checked that the current tile was a valid connection coming from the parent tile (which was current in that iteration). Imo you wouldn't even have to check whether the road is already connected, only thing that matters would be whether the current tile can connect to the next, and the CanBuild function should cover that.

4) ARGH! Damn you're right. In my haste to make clean looking code I neglected the "== 0" test. I did know this already, honest!!

I've got no reason not to believe you already knew, I guess I've made a billion of mistakes like that in my life, and still trying to make better ones...

[GeekToo]

I know, I'm far too late to meet the deadline, but anyway..
The thing that annoys me most in the current pathfinder: it fails to build bridges, when it really should.

See screenshot.

I reduced the bridge_per_tile cost to 0, or even negative values, still it fails to build a bridge.

[Zutty]

I know, I'm far too late to meet the deadline, but anyway..
The thing that annoys me most in the current pathfinder: it fails to build bridges, when it really should.

See screenshot.

I reduced the bridge_per_tile cost to 0, or even negative values, still it fails to build a bridge.

I've been trying to tell people this! I hoped someone else would notice this problem too.

The thing is that building a bridge in test mode always returns false, regardless of whether the bridge can actually be built. Maybe its just for road, or maybe its just the code used in the road pathfinder but its not right either way.

[Yexo]

I know, I'm far too late to meet the deadline, but anyway..
The thing that annoys me most in the current pathfinder: it fails to build bridges, when it really should.

See screenshot.

I reduced the bridge_per_tile cost to 0, or even negative values, still it fails to build a bridge.

That deadline was only there to set a date when I could start implementing all features, since I'm still not finished, I'd accept new features even now. Someone reported the bridge building problem earlier in some other thread, but I forgot to look into it. I'll make sure I do now.

[Yexo]

The problem with building bridges in AITestMode was fixed in r15277.

And here I have a proposal for the new road library (version 4). I've attached a diff to the current version and a tar to this post. One of the patches needs a small addition to the A* library, so I've added a tar of too.

Changes (in no particular order):
- Updated version to 4.
- Use only a single tile in the _Estimate function (instead of looping over all tiles)
- Add the option to specify a maximum length for the pathfinder, this prevents looping over the complete map if the destination can't be reached.
- Add a cost for crossing rail tiles, this should prevent always building crossings.
- Add the option to build bridges starting on flat tiles when the next tile is a rail or water tile.
- Option to demolish houses (based on patch by Zutty)
- Use the cheapest bridge instead of the first one to try if a bridge can be build, this way you need less money while pathfinding.
- Default for maximum bridges length changed from 10 to 25.

Changes to A*:
- Add GetLength() next to GetCost()

I've tested it only a little bit. I hope some of you can do some more testing and report problems / more suggested changes.

Edit: I forgot to add the callback functions, I'll post an update later.

Edit2: Judging from the downloads, nobody seems interested. I'll leave those here, if you want updated versions I suggest you have a look at the road pathfinders integrated in several AIs.