Details on Pathfinding

[ev.delen]

Hey All,

So the fact that I can't have my 90 ships from my previous post is really bugging me. I've been thinking about it, and I can't figure out why the pathfinding system for ships takes up so much processor time. My idea of a pathfinding system for Ships would have the path finder find the most direct route (just like with planes), then deviate it slighly for any obstacles or land masses. Then it would store the route some how (maybe devided into a series of line secments from the origin to the destination) and shouldn't need to pathfind anymore. Once the route has been established, there shouldn't be need to pathfind anymore.

So I know people are going to discuss this and stuff, and I would like to help in writing a better, leaner, meaner pathfinding system. I can't code (atleast using anything non-web) but I can write pseudo-code! As well, anyone intimate with the pathfiniding sysems, if you can describe how they really work, would be really appreciated!

[andrewas]

As I understand it, the problem here is that water is treated as a blanket of junction tiles. YAPF creates a node for every junction and routes across the resulting graph. This is not a good approach by any means. Ships cant be treated as aircraft are, because they have to worry about terrain. It might be worth digging about somewhere like http://www.gamedev.net for a pathfinder algorithm more suited to ships. The current approach is only good for networks.

In the meantime, the best approach is to turn off YAPF for ships, and use buoys to compensate for the problems with the basic pathfinder.

[sc79]

There is atleast one thread i can recall discussing this problem. In short, theres no easy way to do it. I'm certain your idea is similar to some that came up, and I expect has the same sticking point; what happens when terrain gets raised/lowered? Also, "finding the most direct route" isn't that easy, as planes ignore terrain, whereas ships may have to circle around whole land masses.

[ev.delen]

HMM... thats right, if the landscape changes then it may make it impossible for a ship to continue its journey as originally planned. to solve that there could be a function to check the square ahead and make sure its water. If not, then it would call in the function to re-calculate a path.

[Expresso]

I recall liquid wars dealt with a similar problem in a rather interesting way.
It divides the map in mesh of blocks, trying to keep the blocks rectangular. When a block can't be made rectangular, it is reduced to a smaller block until it has a rectangular shape again (even down to 1x1 blocks).
This strategy allows it to find a route from block A to block B, which is a lot faster then taking a look at each and every pixel.
OpenTTD could make use of the same solution. Instead of letting yapf evaluate each and every tile, it could instead evaluate each and every block until it has arrived in the block where it wants to be. From there on a simple line could be drawn to the ship's destination.
I think this will improve ship path finding performance a lot when implemented in OpenTTD.

[Bilbo]

There is a bit difference with this approach. Liquid wars have only very few destinations in their pathfinding (basically one destination per player) which allowed them to do some optimizations we can't do so easily (we have much more destinations, relatively few sources and much larger maps).

Some attempt to solve this (using hierarchical pathfinding) is here:
http://tt-forums.net/viewtopic.php?f=33&t=33054

... and last post of the thread is actually patch with that pathfinding (for ships) implemented:
http://tt-forums.net/viewtopic.php?f=33 ... a&start=60

I've not tested that patch, but you can try it .... it may work.

[nlmark]

Maybe you could somehow trace the coastline and divide the water in the map into convex or near-convex regions, with polygons (or lines) as their boundaries. By near-convex I mean that straight-line travel from any point on the coast to the vertices of the bounding polygon or line is possible. Using the vertices from the polygons as nodes for the pathfinder, I think a pretty optimal route can be found without overloading the pathfinder. When you have found a path, you just use straight-line travel from node to node, which is always possible because the regions are convex. When encountering concave areas, the optimal path should be to just follow the coastline.

[ev.delen]

I've been thinking about it some more... why don't we just introduce tracks to ships? Make a simple dotted line like a track, and have the ship follow that....

The tile can just be a standard square water tile, with a white dot in the middle and be fully omni-directional. That way the ship is limited in the paths it can find.

[Youri219]

I've been thinking about it some more... why don't we just introduce tracks to ships? Make a simple dotted line like a track, and have the ship follow that....

The tile can just be a standard square water tile, with a white dot in the middle and be fully omni-directional. That way the ship is limited in the paths it can find.

This effectively means (for pathfinder purposes) that a buoy is located at each intersection of multiple dotted lines. Since a player still has to draw this lines, we're back at the old pathfinder.

[ev.delen]

perhaps I should further explain...

Right now the path finder finds a path from the ships position to point B over a network consisting of every attached water tile...
What I'm saying is, lets make a track, so the rail pathfinder can be used, which is more efficient, although a simpler pathfinder would be needed because of the lack of signals, and the ability for ships to occupy the same tile.

The omnidirectionality aspect of it I was refering too dealt with the fact that it doesn't really need to be a track in the sense of a rail, just a line.


A simple way to implement it might be do drop multiple buoys in a line (like with the omni-directional track laying too), or seperated by a given distance, and have some way of adding them to the orders list as a group.


Right now, a lot of ships slows the game down, no? This might help to eliminate that. Would atleast eliminate the need for YAPF for ships, which I understand is less efficient than the original ship pathfinder.

Thanks,

[Noldo]

This is a topic that has been bugging me for a long long time.

I have tested the regional pf patch mentioned earlier and it did work, but the implementation is basically just a proof of consept.

Other ways to solve the issue I have heard or thought of:

The original one.
+Is fast enough
+Exists and works
-A lot of work required by the user when adding a new ship on a long route making ships making it impossible to use on a large map.
-A bit less work required to build buoys for a new route

Yapf/NPF
+Exists and works
+Easy on the user
-Slow on a large map making it impossible to use.

User adds buoys and pathfinder uses buoys automatically to plot a route through those buoys.
-no implementation exists
+might be fast enough
+ semi-easy on the user (need buoy building but no need to add the buoys to the orderlists)

Using a cached graph to make the previous solution faster.
-no implementation exists
+should be fast enough
+ semi-easy on the user (need buoy building but no need to add the buoys to the orderlists)

User adds buoys and asks the pathfinder(custom one) to add the required buoys to the orderlist and then uses the old system/yapf/npf
+ semi-easy on the user (need buoy building but no need to add the buoys to the orderlists)
-no implementation (just came up with this)
+might be easier to make and can made as a network compatible clientside patch

The regional pathfinder mentioned earlier.
+Fast enough
+Easy on the user
-only proof of consept exists.

Building tracks on the water
+Fast enough as it's functionally the same as trains
+semi-easy on the user (need track building but no need to add the buoys to the orderlists, less than building a railroad network though)
(-feels ugly and clunky, but that just personal preference. I'd really rather plot the route through existing buoys as it's functionally almost the same to the user )

[Moriarty]

I think the idea of the CPU creating a "route" and storing it is probably the best, from both a computational and result perspective.

Should the terrain change, then check to see if the changed square co-ords are along the route. If they are, recalculate.

Anyone see any problems with this? You wouldn't even need to store the route in the save, just re-calculate upon load.

Simple yet effective.

[ev.delen]

I think the idea of the CPU creating a "route" and storing it is probably the best, from both a computational and result perspective.

Should the terrain change, then check to see if the changed square co-ords are along the route. If they are, recalculate.

Anyone see any problems with this? You wouldn't even need to store the route in the save, just re-calculate upon load.

Simple yet effective.

The problem is what may seem to be a very simple task (find route from point A to point B) is actually really hard to do from a step by step perspective. If a pathfinder has to make 100 decisions for each route, per turn, that could lead to an exponential amount of CPU time in a game.

I think storing the route some how would decrease the amount of CPU time used. Right now, with trains, it only stores the portion of the route from its current position to the closest switch, and calculates a new route when it reaches that switch (or the final destination).

This is good in that it eliminates the need for some monitoring algorithm (it would watch, and apply a DIRTY tag to routes affected by a change, necessatating a re-calculation of the route), but its bad in that its constantly running!

Ships are a different matter entirely! The main issue is that a ship can take ANY route to get from point A to point B... straight line, or all the way around the map! This results in the pathfinder having to calculate many routes (randomly) then pick the shortest one. As distances between the two points increases the time it takes to calculate those routes, increases. Multiply that by (as in my original post) 90 ships, thats a lot of CPU time, and why it was so slow!

Still, the only ways I can think of to eliminate this is to
A) turn of YAPF and use A LOT of buoys, which still necessatates the pathfinder figuring out the route between the buoys,
B) Shipping Channels... Tracks that ships can find the route to one end of, follow through, then can find a destination to their destination.


So as an example: X = oil-ref, Y = oil-platform, '=' = shipping channel, '.' = open sea

X...................................========================...............................Y

OR

X============================.............................Y


In terms of implementation, it would be no different that rail road tracks.

[prissi]

Well, the dynamic pathfinder of OpenTTD allows for automatically choosing of an empty plattfrom. In simutrans (which uses static routes, i.e. only calculated at start of the consists) special signals are needed to force a recalculation en route.

Imho, caching will be useful for ships only. Otherwise people may be too much offended by a static system here.

[DaleStan]

Should the terrain change, then check to see if the changed square co-ords are along the route. If they are, recalculate.

No. What if a water tile is created that would allow a shorter route? Obviously, since the water tile is just created, it's not part of any old route, but you still have to check to see if any routes might now want to go through that tile.

IOW, that would only work if the cache was invalidated every time a water tile is created or destroyed.

[CMircea]

Should the terrain change, then check to see if the changed square co-ords are along the route. If they are, recalculate.

No. What if a water tile is created that would allow a shorter route? Obviously, since the water tile is just created, it's not part of any old route, but you still have to check to see if any routes might now want to go through that tile.

IOW, that would only work if the cache was invalidated every time a water tile is created or destroyed.

I agree. It's not only the problem of impassable tiles, it's also the problem of passable tiles that can lead to shorter routes.

But IMO, I think it's better to remove the limitation of route length from the old pathfinder and let it pick a relatively short route. We need to make trade offs between speed and route length, and I think it's better to let the route be a little longer and have a large performance boost. I mean, in reality, ships pick a route and go away from it only if it reduces the length significantly, else they stick to it and avoid any obstacles. The old pathfinder does this pretty well, the only problem is the route length limit.

BTW, telling YAPF to use buoys will also improve it's performance a lot and is better than the old pathfinder this way, but it's still the problem of putting buoys, which are more suitable for redirecting ships through another passage.

[Ben_Robbins_]

If there was a pre-calculated (stored) route and water was destroyed along that route, if the route didn't update instantly the ship would sail over land, but if water is created surely that doesn't have to be instantly sorted. Therefore is the problem really the same between the 2 situations? i.e. Can a new route be checked for only once a minute for example? (ships that are on the original route when a route changes would have to then create a temporary route back to the new 'main route' which is one concern)

In fact, in reference to the almost blasphemous word, with 'reality', a new route would have to be surveyed first surely rather than a ship just sailing straight on through if it witnessed land crash into the sea in front of it. So the lack of an instant change of route wouldn't be 'weird' as such

The other idea of manually creating a route as you do with trains/road vehicles: Personally I like the automatic route generating, but at the same time, if a ship (treading a new route) did leave visual 'breadcrumbs' marking 1 of these routes, and that route was manually editable then that would be interesting to play with.

Another thing I'm wondering, is that, if ships are every programmed so they cannot pass through one another, then upon one ship meeting another ship in front of it along the 'route' it would have to generate a new overtaking route if possible. This might again need a temporary route to be generated. Although if no ship can pass through another ship, and each tile is treated like a bit of track in effect, then each none-junction tile could be 'signalled' accordingly with one-way being default, which then adds the factor that the quickest route would only be possible 1 way, so a new route would have to only cross or join an existing route, but otherwise avoid it (i.e connect to different directional lanes). Also, Crossing a route should be avoided if the orders list of boats creating it are the same.

[DaleStan]

If there was a pre-calculated (stored) route and water was destroyed along that route, if the route didn't update instantly the ship would sail over land, but if water is created surely that doesn't have to be instantly sorted.

Yes it does. What if someone joins the game between the creation of the water and the updating of the paths?

[Ben_Robbins_]

Sorry, I don't understand the issue there. When they download the game in it's current state, the current route would be the same as it is for all, and await being updated. The changes made (i.e. the creation of new water) would be stored in a list, ready for creating a new route).

Is this/would this data have to be local, or could it not be sent in the same fashion as the rest of the data is sent, when they join a game?

[DaleStan]

Is this/would this data have to be local, or could it not be sent in the same fashion as the rest of the data is sent, when they join a game?

It would have to go in the savegame to be sent. And I just don't see that happening.