RE: Pathfinding

[Peter Dobrovka]

What will the pathfinding be like for trains?
yes ... rein was speaking with this with hajo ... hajo is experienced with Simutrans so we counting at his help

I'm glad to help, but I'm not sure if I can be a big help. The vehicle pathfinding in Simutrans, although having some advantages, is often considered to be too inflexible in comparison to TTDs pathfinding routines.

So you'll have to improve my pathfinding idea, or you'll get the same complaints that I get for Simutrans' pathfinding.

Briefly: Simutrans vehicles use Dijkstras shortest path algorithm (see a book about algoritms). This algorithm guarantees to find a connection if one exists, and to find the shortest connection (for a given distance measure). Due to a problem in Simutrans' implementation of the distance measure, the 'shortest' path that the algorithm finds is sometimes not what a player would consider the shortest path. So be careful how to measure diagonal movement. But of course you don't need to repreat this mistake in TT2

Another problem: In Simutrans vehicles search their path before departing. Changes while the vahicle is driving (i.e. like changing signals on the way) and platforms on the next becoming occupied or free cannot be easily considered. This is becuase the algorithm isn't fast enough to be done while the vehicle is going - a recalculation i.e. to find another free platform, might stall the game for a few seconds in worse cases. Most often the algorithm executes in a few milliseconds, but for large numbers of vehicles or complex networks this is too slow to be done often.

So you'll have to find a way to improve this.

If your implementation is fast enough, you can do it regularly while the vehicle is going, and thus avoid the problems that Simutrtans has. Dijkstras shortest path algorithm can be expanded to find all path, in ascending order of length, so it can be sued to find alternatives if one path is (temporarily) blocked.

There is A*, a variant of Dijkstras algorithm, that executes faster in the average case (but worse in the worst case). You might want to take a look at A* when evaluating pathfinding algorithms. Simutrans uses A* for AI trackbuilding, becuase it allows to determine good locations for tunnels and bridges with only little additional effort. (A* is also used for player trackbuilding, but without the feature to auto-place tunnels and bridges).

Another pitfall: Simutrans uses map coordinates to set start and end of the path to find. But stations are multi-square entities, and to find empty platforms you need some other system to determine start and end - using coordinates, you get the option to send trains to distinct platforms (like in Simutrans) but it seems most players prefer trains that choose platforms by themselves.

I think if you want to please former TTD players it'd better to research and implement TTDs pathfinding instead of Simutrans' - but then the Simutrans mailing list members are divided on this, it seems that both pathfinding algorithms are suitable for a game, but require different style of play. Players who are used to TTD style have a hard time with Simutrans scheduling/pathfinding, while others think it works well.

c.u.
Hajo
http://www.simutrans.de

Point 1:

The algorithm in 3DTT is extremely quick and maybe useable, so I post it here as pseudo. There are some similarities to A* and Dijkstra´s:
a)
Every node (for you: every tile) has additional information in its data structure:
- where did the PF come from
- waycost until here
- current PF ID
b)
Step 1: get new PF ID first and define maxcost = (the maximum waycosts that the PF is allowed to consume (by default a very high number, f.e. 999999999999999999); set currentcost = 0; goalhasbeenfound = false
Step 2: start at the starting node (its own PF ID, waycost 0 and the "where" is irrelevant here.) by calling find(startingnode, 0);

Some implementation:

bool isgoalreached(node)
{
if (node==goalnode)
..{
..maxcost=node.waycost
..goalhasbeenfound = true;
..return true;
..};
..else return false;
}

void find(currentnode, currentcost)
{
look for the neighbour node(s). Sort them to start with the most promising one (sounds costy but it reduced calculation time in 3DTT by factor 50!!)
One important optimization: as long there is only one neighbour there is no brain needed:
while (currentnode has only one neighbour)
..{
cost = (calculate costs for moving to neighbournode)
..totalcost = currentcost + cost;
..if (totalcost < maxcost)
....{
....neighbour.ID = ID;
....neighbour.waycost = currentcost + cost;
....neighbour.from = currentnode;
....currentnode = neighbour;
....currentcost = totalcost;
....if (isgoalreached(currentnode)) return;
....}
....else return;
..}
for (all neighbour nodes)
..{
..cost = (calculate costs for moving to neighbour node)
..if (currentcost + cost < maxcost)
....{
....if (neighbour´s PF ID != current ID) || (neighbour´s waycost>totalcost)
......{
......// this node is not tested yet or cheaper
......neighbour.ID = ID;
......neighbour.waycost = cost;
......neighbour.from = currentnode;
......if (isgoalreached(neighbour)) return;
......call find(neighbour, totalcost);
......}; // end of if (neigh...
....} // end of if (curr...
..} // end of for
}

Step 3:
if you have found a goal (see variable) then start at the goal and (re)construct the path by the node´s "from"s.


I don´t know what bugs I may have left in here since I have written this down from memory.

Peter

[Peter Dobrovka]

Now there is another thingy, too:
In case of a switch I do always look for signals behind, and if there is a red signal at the route I do a run of the PF with maxcost = remaining way and if there is an alternative route without red signals then the train goes THERE!

Peter

[Hellfire]

Thanks for the tips, Peter!

Rein, if it's ok with you, I'll look into this.

Topic locked, please continu the discussion here (13112006).