Developer's request for comment: direct railway path

[Ignatus]

Request for comment in development of OSDN#46051: if we implement CivII "connected by road/railway in a direct way" rules, what would count as "direct way"? CivII has a very twisted idea of it that hardly will be reproduced. My own ideas:

1. Move diagonally always when the destination tile is not straightly in cardinal direction. Pluses: very easy to program, easy to understand, any transit city is also connected to the destination. Minuses: maximally asymmetric path among the family of shortest paths, bordering tiles not belonging to any shortest path; not so clear on hexagonal map.
2. Trace a line "by a ruler", selecting closest tile centers. Moderately difficult to program, may be made symmetric, mostly intuitive (though in some places one may miss a tile or two), transit cities may require different path (but again, only one tile astray).
3. Lines of power: all verticals, horizontals and diagonals have power assigned to them, among the parallelogram of the shortest paths the strongest ones are selected for connection. Symmetric, many paths are reusable, probably not intuitively understandible, I have very vague idea how it may be programmed.

[Corbeau]

I don't know what are technical specifications, but I'd go with "1.2*landtiles > railtiles", where one is the number of tiles a unit would have to cross on the shortest land route between cities and the other is the number of railroad tiles that a unit will cross when going by rail. The number is arbitrary and could be anywhere between 1 and 2, but more than 2 wouldn't make much sense.

Basically, for the two cities to be "directly connected" by rail, the rail shouldn't go too far away from the shortest possible route. I wouldn't impose a direct 1-1 precondition, but keep it reasonably tight.

[nef]

I have a pathfinder written in Lua. I only run it in mapgen callback so peformance issues are not easily assessed but what I can say is that its use is intensive in that callback and I have NOT noticed any performance issues starting up a new game. I would think that for interactive use performance would NOT be an issue (e.g. assessing the effect of one caravan entering a city).

For the connection issues being described above I think the current tolua facilities would be (almost) sufficient. Compared to what I currently use it for I would regard the current proposals as trivia. The only issues I see is to get the tolua done. One callback to ask for the assessment, and acceptance and use of the parametric return value. If someone can do that, I can do all the Lua.

In order to 'program' the pathfinder one only has to define 'edge lengths' i.e. the 'cost' for going from one tile to an adjacent one (if allowed) taking into consideration the tile types, and what is on them. I will knock up a demo of Corbeau`s suggestion (or #3 by Ignatus). It will a a 'utility' where you specify start and ending cities using ,<ctrl><alt><rmc>. You can mess with the numbers to see what you like.

For general use (e.g. goTo or Goto) one would need to have tolua features scheduled for fc3.2. But also one would need to take control of the actual movement of the unit. Needed would be some way to take over the goTo/Goto (so that it is done by Lua, not hardcode).

[Ignatus]

I don't know what are technical specifications, but I'd go with "1.2*landtiles > railtiles", where one is the number of tiles a unit would have to cross on the shortest land route between cities and the other is the number of railroad tiles that a unit will cross when going by rail. The number is arbitrary and could be anywhere between 1 and 2, but more than 2 wouldn't make much sense.

Basically, for the two cities to be "directly connected" by rail, the rail shouldn't go too far away from the shortest possible route. I wouldn't impose a direct 1-1 precondition, but keep it reasonably tight.

I would like to keep this condition computatively simple and not always performable (unless the cities are on the same convex continent all covered in rails) as it is in CivII, basically because I don't intend to spend much time on it. For the same reason, in this ticket I am not going to put in play something worth calling "pathfinder". But probably you are right in that the algorithm should be less rigid. What about this: iterations follow in parallel from source and destination, with each one step from one route end performed towards where currently is the position counted from the other route end. If the closest (by #1 conception) tile is blocked, the route selects a tile mutually adjacent to it and the current tile that is passable. That still may lead into a dead end when the route of minimal length actually exists but at least you don't need so much practice in recognizing weird patterns. Well, maybe even a little recursion is possible if we select between two equally distant tiles that form a forking path... or would it be too kind?

[Ignatus]

Yes, probably that should be done: a unit class would have a parameter approach_measure = "ManhattanOrReal"|"Manhattan"|"Real"|"ManhattanAndReal"|"SinglePath"; the latter is proposal 1, all the rest is which distances are compared to see if next step is an approach - no matter on hexagonal map, and on rectangular that changes the area where the paths may run from

Code: Select all

   *---
  /    \
  \    /
   ---*

to

Code: Select all

*
|\
\|
 *

I just don't now know how to write the iterator (to avoid retracing paths; likely, we should just go one side to another).

[Corbeau]

I would like to keep this condition computatively simple

Technically, you already have a working GoTo function. This is all you need.

[Ignatus]

I would like to keep this condition computatively simple

Technically, you already have a working GoTo function. This is all you need.

Technically yes, we have unit pathfinder, but it's rather bulky (lot of malloc's and stuff) and I want everything that is tested in requirements to be maximally optimized (ideally, cached in three pointer jumps access). Also, if we reproduce CivII ballance to some extent, +50% caravan bonuses should not lay on roads (or should they?).

[nef]

Below is the demo for the pathfinder.

I used this opportunity to 'refresh' both the pathfinder and the project that uses it.

The principal changes I made to the pathfinder were:

1. A minor improvement in performance for applications like the demo (but not my project).
2. The use of a coroutine to make it easier to implement the 'exhaustive' search mode (such as when the demo is called with just the first city.)

To run the demo you will need to treat it as a type 3 SP utility, that is, you will need FEATURED_TEXT, PARSER, and SUPPORT_extended (or the soon to be released SUPPORT_continuity).

And, of course, the pathfinder.

djikstra.txt

(8.65 KiB) Downloaded 180 times

Here is the demo:

demo.txt

(2.94 KiB) Downloaded 166 times

Treat all these files as you would for a type 3 SP utility.

Some notes on the demo:

When called with cities for the first TWO arguments, the demo will calculate the shortest path between them AND provide a traceback.

When called with just one city (the second argument being nil - or defaulting), the utility will do an 'exhaustive' search for all cities accessible from the specified city (but no tracebck).

One can supply a third argment for benchmarking purpose. This is the number of times to repeat the basic search (with only one traceback and printout). When using this, one should be aware that there is a WatchDogTimer of about 3 seconds operating. In my tests on the older laptop I found typical 'exhaustive' search times to be 5 - 10 mS (obviously dependent on the number of accessible tiles).

If in a particlar application one was doing an exhautive search FROM EVERY city on a large continent, one could start to experience an unacceptable delay, but there are many steps that could be taken to mitigate this. Such as:

1. Limit the distance.
2. Identify sub paths already taken (tricky?)
3. Have the AI cities not perform the search from every city every turn.

One final note: for 'edge' lengths I have used the values suggested by Corbeau, but I do so only for the purposes of this demonstration. For testing purposes read 'land tiles' as tiles connected by road.