Ship Pathfinding Idea.

[Xaroth]

Ok, small convo on IRC about the ship pathfinding, currently it lacks a bit of speed when trying to find a path from A to B, simply because it's not that optimised (yet).

The idea.

I've fiddled around with some data CCP provides of their game Eve Online (for the unaware, MMORPG, space-based, http://www.eve-online.com will tell you all), part of this data is the information of all solar systems in the game, what constellations and regions they lie in etc etc.. but also to which they are connected.

So after a good night of coding I came up with a simple test on how their optimalisation seemed to work.

Normal A* works like this:



Having a grid like that, through normal A* without any optimisation, it would explore every cell there is trying to find the path untill it reached B, you could add optimisation where it would look at the direction and try that first, saves a few cells, but in OpenTTD with wierd landscapes that wouldn't allways work, so is pretty much useless.

What -does- work, is using regions for the water, making another grid, only this time 8x8 instead of 1x1, and making one even bigger (for big maps mostly) doing 64x64, you increase the time spent calculating a path in small areas by only a tiny bit, probably an increase of 10% in cycles needed, but the huge difference would come with big (200-squares+ routes).. going from 'unable to find path', to actually finding a path.


The main idea:

when calculating a path, calculate a path using the 64x64 regions from start to end , this should give a 'general path' of the direction the ship would take, then calculating the same path using a 8x8 regions, but this time the regions can only be within the 64x64 path found, or adjacent to it (Because, obviously, sometimes the map can be an ass and throws in a de-tour), after that is done, the similar thing with a normal 1x1 grid, using the 8x8 path..

every region is connectable to it's adjacent when there's water on it's side, might want to have some optimalisation where it rules out small lakes (so it only inlcudes open water)

I'll attach some sample C# code i am fiddling with, it might not really compile that good since there's 1 function that i was working on.. the data you'll have to imagine yourself since i'm not going to upload 10 megs worth of xml data (There's not much to completely no comments in the code, but that keeps the code clean to read, if you have questions drop me a line on irc)

[DaleStan]

What if there's a long, skinny island that runs through the middle of five adjacent 64x64 "tiles"?

Sounds to me like the the 64x64 pathfinder will find a path across that island, and maybe the 8x8 pathfinder too, but the 1x1 pathfinder will be utterly unable to find a path.

[misnomer]

Having a grid like that, through normal A* without any optimisation, it would explore every cell there is trying to find the path untill it reached B, you could add optimisation where it would look at the direction and try that first, saves a few cells, but in OpenTTD with wierd landscapes that wouldn't allways work, so is pretty much useless.

What? I thought the whole point of A* was that it was a heuristic best-first search. So I don't know what you mean exactly by "without any optimisation" as that would be a pretty weird implementation of A* - and as for saves a few cells, depending on the situation it can save a few orders of magnitudes of cells. I don't think there are many situations in which an A* algorithm would explore 'every cell there is'.

I don't really know much about this suggestion, but I have dealt with A* a few times and this paragraph just struck me as a bit odd. *shrug*
Maybe I'm misunderstanding what you mean.

[Xaroth]

Probably you are, but the 'best-first' search can go terribly wrong with certain maps.

@DaleStan: Hence why you allow nodes 'next' to it as well as misnomer pointed out, A* is often used with best-first searching, using the region searches gives you results which are best-search, the regions next to it are still good, but less good.. you can 'limit' the search in some cases, where you want only the good or less-good areas, but you can also implement that they modify the cost of the tile, that a good tile has a modifier of *1 , a less good of *2, adjacent to a less-good tile *4 and the rest *16 .. that way pathfinding will find the tile eventually, but will at least try the straight or as-straight-as-possible approach before trying huge detours

[KUDr]

Xaroth (or Shaman?): Finding the way through grapf of adjacent regions is pretty easy, I agree. What I still can't see, is how to make such graph.
As DaleStan mentioned, ottd map can't be simply divided into such square regions, as there can be no path from one edge of region to another edge, or from one region to adjacent. So if we want to use such approach, we must be able to generate complex grapf of complex regions. Each region (even if they all will be 64x64 squares) must have defined where its borders are connected (passable) to the neighbors by water and where not. Also it can happen that the region will be divided into two or three by land. Such region must be there multiple times in the graph - once for each passable subregion as you cannot pass it through.
I can't imagine any effective algorithm, how to generate such a graph nor any understandable data structure describing such complex region. This is what I expected to see in your samples after our discussion on IRC.

[Xaroth]

the regions don't have to be a set size per definition, using a list of bodies of water as each region, and cut them in pieces if they get too big would work as well, probably even better since you then don't have to deal that much with land areas..

I'll see if i can get something worked out after the missus gets out of the hospital, something that might explain better.. (maybe even code some C if I understand it well enough )

[LKRaider]

Since I'm new to A* and stuff, I've been looking around some links and info of it.
Here are some good resources:

Newsgroup discusson on A* optimization - http://theory.stanford.edu/~amitp/Archi ... ding2.html
Discusses the A* algorithm very well - http://theory.stanford.edu/~amitp/GameProgramming/
A good A* tutorial - http://www.policyalmanac.org/games/aStarTutorial.htm

At first look, seems that optimizing the open/closed lists make a huge difference, also with using an applicable heuristic.

How are the open/closed lists implemented in OTTD? Apparently, binary heaps make the A* function much better on large paths.
Binary heaps in A* - http://www.policyalmanac.org/games/binaryHeaps.htm

[KUDr]

LKRaider: all three PFs (NTP, NPF, YAPF) use binary heaps. But for ships it is still slow. PF must visit up to several milions of nodes to find the route. If you calculate ~1us for one round (very fast PC, optimized code) then it is still very slow - seconds for each ship entering new tile.

[LKRaider]

I see. So the problem is the number of nodes.
I simulated a shipline pathfinding -using a standard A* algorithm- around a complex terrain, much like we see on OTTD (see attached image), and noticed how it quickly looses speed on these conditions (it had to scan almost the whole map).

Now, I could imagine some ways to optimize it, but figured we may be thinking this the wrong way around.
What we are asking it to do is to build a route at every move, like if we, for instance, placed train stations and expected the trains to build their own tracks linking these stations.

What I propose is to introduce a new concept on the game, that is, the design of ship routes by the player, and not by the game itself.

So, instead of just placing shipyards and expecting the ships to find their way, the player would have to actually design the paths for the ships. This could be done by using the current buoys as nodes of the shiproutes, and designing the connections between these buoys.

I think this would make the ship part of the game more interesting, since now they would have the same elements the land vehicles have, that is, route designing.

What do you think?

[Master X]

What I propose is to introduce a new concept on the game, that is, the design of ship routes by the player, and not by the game itself.

So, instead of just placing shipyards and expecting the ships to find their way, the player would have to actually design the paths for the ships. This could be done by using the current buoys as nodes of the shiproutes, and designing the connections between these buoys.

The implementation of ship pathfinding in Anno 1503 is similar: When making a route, the computer generates buyons once for easier navigation(when ship is not activated, these waypoints are not visible). When the ship is selected, these buyons can be pushed to another location, so the ship takes anohter way.

The auto-generation of buyons makes it easier for people, who does not care about making routes on their own.

[LKRaider]

Yes, but I think the network should still be created by the player. This is a transportation game afterall

[gigajum]

i had that idea too. The game calculates the route for you when you setup the orders. So far so good. But what if someone raises the land somewhere, where a ship route takes course. You could recalculate the route. But what if that isn't successful? Alert with "Ship lost"?

That's what think about the ship wayfinding.

[LKRaider]

gigajum: I imagine the ship network would be represented in-game, so you could manually modify it. Something like the screeny attached.

The ship part of the game is quite boring as it is now. Adding a new toolset to design ship routes would improve gameplay much more than auto-routing, IMO.

When you build land, it wouldn't allow destroying a ship route, the same way it doesn't for tracks or roads. You would first have to clear the route, then landscape, then re-route, much like with the other transports.

When you place a buoy, it could auto-link to the last placed (or maybe to the nearest one) and show the plotted path to the player. The player could edit the path by placing other buoys then. This should be better thought out tho.

[Hazelrah]

Does this mean we can start crashing ships into each other like we crash trains into each other?

Seriously though, I think that shiping lanes is a great idea! It would need some serious thought of how it would fit into the map array and all. Of course you can probably cram the bits into the same place as where the rail is for land.

-Hazelrah

[gigajum]

gigajum: I imagine the ship network would be represented in-game, so you could manually modify it. Something like the screeny attached.

The ship part of the game is quite boring as it is now. Adding a new toolset to design ship routes would improve gameplay much more than auto-routing, IMO.

When you build land, it wouldn't allow destroying a ship route, the same way it doesn't for tracks or roads. You would first have to clear the route, then landscape, then re-route, much like with the other transports.

When you place a buoy, it could auto-link to the last placed (or maybe to the nearest one) and show the plotted path to the player. The player could edit the path by placing other buoys then. This should be better thought out tho.

Ok, good idea how to solve it

[bobingabout]

you still need something for people like me though, who don't use, nor want to have to use buoys

[Archonix]

How about something that auto-generates sea lanes that the ships follow automatically for the majority of their journey, and that only gets updated if and when terraforming directly inpinges on the lanes themselves? I assume this will reduce the amount of path-finding a ship will have to do on a journey and there could be cacheing of some sort involved as well... soemwhere.

[prissi]

I fiddled around with Priorityqueues also in Simutrans for Pathfinding for ships. THe result was not so overwhelming. Comparing a relatively simple and straight forward array implementation to the priorityques, the latter was sometimes faster and sometimes slower, really depending on the geometry. THe array is also very assymetrical, if one have to discard a lot of tiles, the array get slow. Otherwise the arrays is faster or equal, same goes also for shorter paths.

With very long path exceeding the cache size both algorithms suck, especially on 1024*1024 maps. Checking a pathes of more than 2500 tiles that required 400000 tiles to be checked took in both cases half a minute.

The fazit: Priorityqueues may help a little, but do not expect miracles. A path exceeding 200 tiles took always more than a secod to calculate. Thus a useful chaching of pathes (only recalculate after five trips or so) seems the better choice.

EDIT:
When not doing an A* like in the book (i.e. allowing the same open node to be in the list with different cost values) the array is much faster, since the position to insert is found using binary search, and insert into a linear array is much faster. In the end using arrays versus priority queue on a 1024*1024 map with a very inderect path the array won by far. The times with the arrays were 4-5 times faster than the priority queues on a Athlon.

Using the A* with double node, it had to search 700000 nodes and used about 3500ms compared to an array with checking which only needed 440000 nodes but 8000 seconds. Priority queues were then 14500ms. Route length was 2650 tile by the way.

My guess is that the better performance of the array is due to the fact that is handles data as bulk, i.e. inserting is o(n/2), but the operations are very fast compared to the o(n) for searching a node in a list where every node may be in a different cache line and very much against pipeline architecture. Maybe in a 2000*2000 map the priority queues will get better, but the time needed will be too high for any practical use for todays average computer.