Road Pathfinder Modifications

[Yexo]

Building bridges can be cheaper than actually building road there. 'newai' got some code to prevent building unnecessary bridges even though it's more expensive.

Only the road pathfinder doesn't check the actual cost, so that can't be the problem here.

*sob* Sometimes bug fixing drives me to the very brink of insanity.

Yexo can you tell me what max_length_multiplier means?...

Code: Select all

function Road::InitializePath(sources, goals, max_length_multiplier = 0, max_length_offset = 10000)

Is it something to do with making the pathfinder sub-admissable? i.e. that a value > 1 means the RPF prefers faster completion to cheaper cost.

No, _estimate_multiplier is for making it non-perfect. max_length_multiplier is for setting the maximum route length (in tiles) the pathfinder will find. The maximum route the pathfinder will find

Code: Select all

max_route_length (in tiles) = DistanceManhattan(source, goal) * max_length_multiplier + max_length_offset;

Any path longer than max_route_length will not be considered by the pathfinder. This is to prevent searching the complete map if a route is blocked (either the source or the destination is on an unreachable island for example). You can use the defaults (0 and 10000) to not use this feature at all, it'll then behave the same as in the previous version.

[Zutty]

Thanks for the replies.

Hmmmm.... what on earth am I doing wrong.

As you know I added a feature that forces roads to "snap" to town road layouts by adding cost to any tile not on the grid. The RPF can get around this though by simply bridging over the more expensive tiles.

I have tried to fix this by calculating how many tiles under a bridge would be in violation of the grid but it just wasn't working. So I then gave a penalty for EVERY tile under a bridge, meaning the bridge was more expensive than the equivalent road and it still didn't work. This suggested to me that something else was wrong, but I've no idea what.

Damn.

On the bright side, I really like v4. I'll post my updated modifications soon.

[Zutty]

Ok here are my changes to the new RPF v4.

Edit: See my later post...
I re-added the cost callbacks, which you seemed to forget AGAIN! I also seems like you forgot to change self to this, which I also fixed.

In order to allow cost callbacks to modify bridge costs I had to re-work the _Cost() method so that there is only one return statement.

For now I'm sticking with your method of getting neighbors 'cos its faster, but I might fall back into my nasty old ways after Ive done some more thorough testing.

Hope this all makes sense, and that someone can perhaps benefit from this. Enjoy

Also, I'll be releasing this in v6 of PathZilla, so can aystar v5 go onto BaNaNas if/when you are finished with it Yexo?

[Yexo]

Ok here are my changes to the new RPF v4.

Road_v4.diff

I re-added the cost callbacks, which you seemed to forget AGAIN! I also seems like you forgot to change self to this, which I also fixed.

In order to allow cost callbacks to modify bridge costs I had to re-work the _Cost() method so that there is only one return statement.

For now I'm sticking with your method of getting neighbors 'cos its faster, but I might fall back into my nasty old ways after Ive done some more thorough testing.

Hope this all makes sense, and that someone can perhaps benefit from this. Enjoy

Also, I'll be releasing this in v6 of PathZilla, so can aystar v5 go onto BaNaNas if/when you are finished with it Yexo?

You seem to have an older version of pathfinder.road.4. The latest version (which I uploaded in this post: http://www.tt-forums.net/viewtopic.php?p=767157#p767157) already contains the self->this cahnges and also the cost callbacks (though the code is slightly different from yours). I didn't forget them. I'll try to finish it up later this week,if you have no further comments to AyStar.5 I will already upload that one.

[Zutty]

Awww damn. How did I miss that. Sorry Yexo I thought I had the latest version. Hang on...

I have no changes to aystar v5.

[Yexo]

I have no changes to aystar v5.

Graph.AyStar.5 is now available from bananas.

[Zutty]

I have no changes to aystar v5.

Graph.AyStar.5 is now available from bananas.

Brilliant thanks

Here are my changes to your latest v4 pathfinder.

Road_v4.diff

(4.52 KiB) Downloaded 182 times

Now its just a change to the _Cost() method as I described before, and a slight code style change (which I thought was more inline with the rest of it).

Sorry about the mixup Yexo. I hope I got it right this time!

Comments?

[Yexo]

Comments?

Only that I agree 100% with that diff . If there are no other comments (and I assume not, since it's been quite some time ago since I uploaded v4 then I'll apply your diff tomorrow and upload the new version then.

[Zutty]

Hooray! Thanks Yexo.

[fanioz]

Finally...
You've all done a good job. its now give much flexibility how the rpf would find it path. And uploading to bananas is good news too.

[fanioz]

Building bridges can be cheaper than actually building road there. 'newai' got some code to prevent building unnecessary bridges even though it's more expensive.

Could not understand with the meaning of 'newai'.
And ever found that highest bridge price is 6 x road tile. CMIIW

[Zuu]

Could not understand with the meaning of 'newai'.

Before NoAI, there was a previous new AI attempt in C++ that aimed at creating one new improved AI.

[fanioz]

I see.. that mean there are :
- Old AI (native)
- New AI (attempt to rewrite in C++) <-- this what I've missed one
- NoAI ( current AI framework )
---------------
Yexo, would you update http://devs.openttd.org/~yexo/ai_libraries/ too ?

[Zutty]

There was also Trolly, which was an attempt to create a tram AI before NoAI.

http://hg.openttd.org/openttd/branches/ ... ai/trolly/

In fact there was even another AI framework written by TrueBrain before NoAI that used some other langauge (not Squirrel), but it never took off! I can't remember what it was called though.

They really want better AI for OpenTTD!

[Yexo]

In fact there was even another AI framework written by TrueBrain

See http://libgpmi.org/

[Zutty]

Hi again Yexo,

I have a couple of bugs that I wanted to address by modifying the pathfinder again. These aren't so much new features as hacks to get my AI working!

The first problem I had was that the AI cannot find a path through traffic. My old pathfindaer was able to do this, as was my version of the library RPF I released in PathZilla v5, however the curret RPF uses AIRoad.BuildRoad() and so fails with a VEHICLE_IN_THE_WAY error. I get around this with the following hack...

traffic_hack.diff

Apply to the RPF v4 cumulatively with my previous patch

(1.06 KiB) Downloaded 161 times

If a vehicle is in the way it just falls back to CanBuildConnectedRoadPartsHere(), which works since a vehicle in the way implies that a road already exists on at least ONE of the two tiles. This useful mainly for building tram lines over road.

The second issue I am having is that the pathfinder sometimes builds bridges over the goal tile. My AI assumes that the goal tile is buildable (i.e. to put a station on it), so this behaviour messes up that assumption.

I haven't written a fix for this yet, but I'm planning on adding a test to _GetTunnelsBridges() in the for loop to skip an iteration if the goal tile is between cur_node and target. I haven't thought up an efficient way of doing this yet.

I didn't post these to have them considered for the new RPF and to make your life difficult, but just to ask your opinion on these hacks and if you have any ideas. Do you think there are better ways of fixing these issues?

Thanks.

[Yexo]

Hi again Yexo,

I have a couple of bugs that I wanted to address by modifying the pathfinder again. These aren't so much new features as hacks to get my AI working!

I'm happy you post it now, before I uploaded it to bananas, otherwise we would need another version again

The first problem I had was that the AI cannot find a path through traffic. My old pathfindaer was able to do this, as was my version of the library RPF I released in PathZilla v5, however the curret RPF uses AIRoad.BuildRoad() and so fails with a VEHICLE_IN_THE_WAY error. I get around this with the following hack...

traffic_hack.diff

If a vehicle is in the way it just falls back to CanBuildConnectedRoadPartsHere(), which works since a vehicle in the way implies that a road already exists on at least ONE of the two tiles. This useful mainly for building tram lines over road.

Are you sure it's ok to remove can_demolish from there?

The second issue I am having is that the pathfinder sometimes builds bridges over the goal tile. My AI assumes that the goal tile is buildable (i.e. to put a station on it), so this behaviour messes up that assumption.

I haven't written a fix for this yet, but I'm planning on adding a test to _GetTunnelsBridges() in the for loop to skip an iteration if the goal tile is between cur_node and target. I haven't thought up an efficient way of doing this yet.

This is pretty easy to check as the end tile of the bridge is extended starting from the begin tile, so just break out of the loop as soon as you hit a goal tile. We might want to add a seperate array 'no_brigde_above' next to ignored tiles, just so it can also work if a not-yet-build station consists of multiple tiles.

[Zutty]

Are you sure it's ok to remove can_demolish from there?

I haven't removed anything (have I?). The line is very long ATM, so maybe you didn't see it. I'll break it up to make it more readable.

This is pretty easy to check as the end tile of the bridge is extended starting from the begin tile, so just break out of the loop as soon as you hit a goal tile. We might want to add a seperate array 'no_brigde_above' next to ignored tiles, just so it can also work if a not-yet-build station consists of multiple tiles.

Thats a brilliant idea! I'll have a go at that later on.

[fanioz]

I was thinking, that this line is necessary. I'm sorry I can't make a diff file right now. But this line is inside Road::_Cost function.

Reason :: After changed the code style by zutty for cost callback, this function should not add un-necessary cost.

Code: Select all

    if (!AITile.IsBuildable(new_tile) && !AIRoad.IsRoadTile(new_tile) {
        cost += this._cost_demolition;
    }

Proposed revision is :

Code: Select all

    /* Check if need to demolish
     *  1: not demolish road tile
     *  2: not demolish own property
     *  3: the pathfinder is set to allow demolition
     *  4: the tile is demolish-able
     */
    if (!AITile.IsBuildable(new_tile) && !AIRoad.IsRoadTile(new_tile) && this._allow_demolition &&
        !AICompany.IsMine(AITile.GetOwner(new_tile)) && AITile.DemolishTile(new_tile)) {
        cost += this._cost_demolition;
    }

OR, the Road::_Neighbours function handled this well ?

[Bilbo]

As you know I added a feature that forces roads to "snap" to town road layouts by adding cost to any tile not on the grid. The RPF can get around this though by simply bridging over the more expensive tiles.

Well, there can be problem - if there are two towns close to each other, their road grid can be not aligned. Especially as the towns grow, their grids will clash, causing a little biut of extra road around the line where the growth of the town touches.

How do you solve this situatiuon?