Developer's request for comment: direct railway path

Can you help improve your favourite game? Hardcore C mages, talented artists, and players with any level of experience are welcome!
Post Reply
Ignatus
Elite
Posts: 595
Joined: Mon Nov 06, 2017 12:05 pm
Location: St.Petersburg, Russia
Contact:

Developer's request for comment: direct railway path

Post by 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.
User avatar
Corbeau
Elite
Posts: 1248
Joined: Mon Jan 13, 2014 11:13 pm

Re: Developer's request for comment: direct railway path

Post by 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.
--
* Freeciv LongTurn, a community of one-turn-per-day players and developers
* LongTurn Blog - information nexus with stuff and stuff and stuff
* Longturn Discord server; real-time chatting, discussing, quarrelling, trolling, gaslighting...
nef
Elite
Posts: 314
Joined: Mon Jun 25, 2018 5:01 pm

Re: Developer's request for comment: direct railway path

Post by 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
Elite
Posts: 595
Joined: Mon Nov 06, 2017 12:05 pm
Location: St.Petersburg, Russia
Contact:

Re: Developer's request for comment: direct railway path

Post by Ignatus »

Corbeau wrote: Mon Nov 14, 2022 5:44 pm 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
Elite
Posts: 595
Joined: Mon Nov 06, 2017 12:05 pm
Location: St.Petersburg, Russia
Contact:

Re: Developer's request for comment: direct railway path

Post by 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).
User avatar
Corbeau
Elite
Posts: 1248
Joined: Mon Jan 13, 2014 11:13 pm

Re: Developer's request for comment: direct railway path

Post by Corbeau »

Ignatus wrote: Tue Nov 15, 2022 1:06 pmI would like to keep this condition computatively simple
Technically, you already have a working GoTo function. This is all you need.
--
* Freeciv LongTurn, a community of one-turn-per-day players and developers
* LongTurn Blog - information nexus with stuff and stuff and stuff
* Longturn Discord server; real-time chatting, discussing, quarrelling, trolling, gaslighting...
Ignatus
Elite
Posts: 595
Joined: Mon Nov 06, 2017 12:05 pm
Location: St.Petersburg, Russia
Contact:

Re: Developer's request for comment: direct railway path

Post by Ignatus »

Corbeau wrote: Wed Nov 16, 2022 12:36 am
Ignatus wrote: Tue Nov 15, 2022 1:06 pmI 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?).
Post Reply