Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Tue Mar 19, 2019 5:07 am

All times are UTC




Post new topic  Reply to topic  [ 70 posts ]  Go to page 1 2 3 4 Next
Author Message
PostPosted: Fri Jan 16, 2009 12:39 am 
Offline
Director
Director
User avatar

Joined: Tue Jan 22, 2008 4:33 pm
Posts: 565
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...

Attachment:
Road.diff [7.47 KiB]
Downloaded 122 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:
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:
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:
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:
function RegisterCostCallback(callback, ...) {
   local args = [];
   for(local c = 0; c < vargc; c++) {
      args.append(vargv[c]);
   }
   this._cost_callbacks.push([callback, args]);
}

Code:
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.

_________________
PathZilla - A networking AI - Now with tram support.


Last edited by Zutty on Sun Jan 18, 2009 12:08 am, edited 3 times in total.

Top
   
PostPosted: Fri Jan 16, 2009 12:55 am 
Offline
Tycoon
Tycoon

Joined: Thu Dec 20, 2007 12:49 pm
Posts: 3653
Zutty wrote:
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...

Attachment:
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.)


Top
   
PostPosted: Fri Jan 16, 2009 1:15 am 
Offline
Director
Director
User avatar

Joined: Tue Jan 22, 2008 4:33 pm
Posts: 565
Yexo wrote:
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.

Yexo wrote:
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.

_________________
PathZilla - A networking AI - Now with tram support.


Top
   
PostPosted: Fri Jan 16, 2009 4:11 pm 
Offline
Tycoon
Tycoon

Joined: Thu Dec 20, 2007 12:49 pm
Posts: 3653
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:
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


Attachments:
rpf_max_length.diff [6.75 KiB]
Downloaded 114 times
Top
   
PostPosted: Fri Jan 16, 2009 10:29 pm 
Offline
Tycoon
Tycoon

Joined: Thu Dec 20, 2007 12:49 pm
Posts: 3653
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.


Top
   
PostPosted: Fri Jan 16, 2009 10:46 pm 
Offline
Director
Director
User avatar

Joined: Tue Jan 22, 2008 4:33 pm
Posts: 565
Yexo wrote:
@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...

Attachment:
File comment: A 'flat' loop - ugly!
dtrsflatloop.png
dtrsflatloop.png [ 12.41 KiB | Viewed 5466 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.

Quote:
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!).

_________________
PathZilla - A networking AI - Now with tram support.


Top
   
PostPosted: Fri Jan 16, 2009 11:08 pm 
Offline
Tycoon
Tycoon

Joined: Thu Dec 20, 2007 12:49 pm
Posts: 3653
Zutty wrote:
Yexo wrote:
@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.


Top
   
PostPosted: Sun Jan 18, 2009 12:14 am 
Offline
Director
Director
User avatar

Joined: Tue Jan 22, 2008 4:33 pm
Posts: 565
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:
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...

Attachment:
File comment: The tram track is built NEXT to the road, not over it. Its like this all over the map.
parrl.png [289.02 KiB]
Downloaded 117 times


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

Code:
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);

_________________
PathZilla - A networking AI - Now with tram support.


Top
   
PostPosted: Sun Jan 18, 2009 4:08 pm 
Offline
Engineer
Engineer

Joined: Sun Aug 03, 2008 1:38 pm
Posts: 4
Zutty wrote:
Code:
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:
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;
}


Top
   
PostPosted: Sun Jan 18, 2009 4:19 pm 
Offline
Engineer
Engineer

Joined: Sun Aug 03, 2008 1:38 pm
Posts: 4
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:
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;
}


Top
   
PostPosted: Sun Jan 18, 2009 4:38 pm 
Offline
Tycoon
Tycoon

Joined: Thu Dec 20, 2007 12:49 pm
Posts: 3653
You are still overdoing it:
Code:
         if (connectable && AIRoad.AreRoadTilesConnected(next_tile, nn_tile)) {
            connectable = connectable && AIRoad.CanBuildConnectedRoadPartsHere(next_tile, nn_tile, cur_node);
         }

can be simplified to:
Code:
         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.


Last edited by Yexo on Sun Jan 18, 2009 6:01 pm, edited 2 times in total.

Top
   
PostPosted: Sun Jan 18, 2009 5:14 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Thu Feb 09, 2006 7:15 pm
Posts: 3815
Yexo wrote:
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?


Top
   
PostPosted: Sun Jan 18, 2009 5:28 pm 
Offline
Tycoon
Tycoon

Joined: Thu Dec 20, 2007 12:49 pm
Posts: 3653
Oops, fixed the previous message :)


Top
   
PostPosted: Sun Jan 18, 2009 8:47 pm 
Offline
President
President
User avatar

Joined: Sun Jun 03, 2007 10:22 pm
Posts: 950
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 :-)


Top
   
PostPosted: Sun Jan 18, 2009 9:46 pm 
Offline
Director
Director
User avatar

Joined: Tue Jan 22, 2008 4:33 pm
Posts: 565
Thanks for the suggestions guys...

zothar wrote:
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 :)

Yexo wrote:
You are still overdoing it...
Ah yes, ofcourse.

GeekToo wrote:
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!! :oops:

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! :D 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.

Yexo wrote:
@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! :D

_________________
PathZilla - A networking AI - Now with tram support.


Top
   
PostPosted: Mon Jan 19, 2009 9:24 pm 
Offline
President
President
User avatar

Joined: Sun Jun 03, 2007 10:22 pm
Posts: 950
Zutty wrote:

GeekToo wrote:
-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.


Zutty wrote:
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!! :oops:

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... :D


Top
   
PostPosted: Sun Jan 25, 2009 10:09 pm 
Offline
President
President
User avatar

Joined: Sun Jun 03, 2007 10:22 pm
Posts: 950
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.


Attachments:
Campbell & Co., 1 Mrt 1992.png
Campbell & Co., 1 Mrt 1992.png [ 94.13 KiB | Viewed 4725 times ]
Top
   
PostPosted: Mon Jan 26, 2009 12:01 am 
Offline
Director
Director
User avatar

Joined: Tue Jan 22, 2008 4:33 pm
Posts: 565
GeekToo wrote:
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.

_________________
PathZilla - A networking AI - Now with tram support.


Top
   
PostPosted: Mon Jan 26, 2009 2:29 am 
Offline
Tycoon
Tycoon

Joined: Thu Dec 20, 2007 12:49 pm
Posts: 3653
GeekToo wrote:
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.


Top
   
PostPosted: Mon Jan 26, 2009 9:56 pm 
Offline
Tycoon
Tycoon

Joined: Thu Dec 20, 2007 12:49 pm
Posts: 3653
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.


Attachments:
pathfinder.road.4.tar [40 KiB]
Downloaded 142 times
combined.diff [10.6 KiB]
Downloaded 108 times
graph.aystar.5.tar [40 KiB]
Downloaded 182 times
Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 70 posts ]  Go to page 1 2 3 4 Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000-2019 phpBB Limited

Copyright © Owen Rudge/The Transport Tycoon Forums 2001-2019.
Hosted by Zernebok Hosting.