News:

Want to praise Simutrans?
Your feedback is important for us ;D.

Portals

Started by jamespetts, May 14, 2017, 09:25:19 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

zook2

I assumed the tree would be randomized; note that I pulled the distances out of my made up the distances. But I guess there's no reason why one couldn't load an XML file with a pre-made city list instead of random generation at startup.

zook2

Quote from: jamespetts on June 04, 2017, 10:09:08 AM
On a large map, a destination would have to be extremely far away for the optimum departure tile to be identical from all origin points. Given that it should be possible for foreign destinations to be as close as 100km away (the distance between Dover and Calais is only 33km), this does not seem feasible.

Store the compass direction for each distant city (only required for the first city in each branch, like New York in my above example map). Then divide each map edge (e.g. west) into four quarters to get three equidistant portals to New York. Assume that the distance to NY is 3000km for all of them, but note that it now makes a difference which portal you send the plane to. Also, the number of portals could depend on map size.

You could have more than one city branch for each map edge. For example, NY could be North-West at a distance of 3000km, Havana could be South-West, and Baltimore could be West. Then you could simply rule that the northernmost portal is only 2800km from NY, the middle one 3000km, and the southern portal 3200km (see the attached image).

If you're a stickler for correctness then calculate the distances. You know the length of the map edge, the compass direction to NY and the distance to New York. Just apply some fancy trigonometry functions.

Now if you look at the image, you'll see that we have three western portals, two of which are land-locked, and we only allow ships and planes to leave the map. That gives us two air-travel-only portals. What if our game map has no water on the western map edge? Do we allow ships to travel via a portal on the southern map edge to go to NY (with an arbitrary distance penalty)?

jamespetts

Thank you for your interesting thoughts. I have not yet resolved finally how to implement this, but my current leaning is towards a system that does not really involve portals, as such, at all, but rather a range of points on a hypothetical super-map of which the real game map is in the centre delineated by co-ordinates. I had not considered having the map wrapped, as I am not sure whether there is an algorithm that can do this efficiently with lots of pathfinding using only co-ordinates as nodes and simulated edges between those nodes. If wrapping can be done without too much difficulty, this would be preferable to simulating Flatland.

With this system, it should be possible for vehicles to calculate distances and directions to distant, off-map locations using the existing pathfinding system and system for calculating distances without having to use complex branching logic inside the pathfinding code to have different logic for pathfinding inside the map compared to pahtfinding outside the map. I have not, however, considered fully how this might work with the current 16-bit limitation on co-ordinates, which might make this rather more complex.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

DrSuperGood

QuoteThank you for your interesting thoughts. I have not yet resolved finally how to implement this, but my current leaning is towards a system that does not really involve portals, as such, at all, but rather a range of points on a hypothetical super-map of which the real game map is in the centre delineated by co-ordinates. I had not considered having the map wrapped, as I am not sure whether there is an algorithm that can do this efficiently with lots of pathfinding using only co-ordinates as nodes and simulated edges between those nodes. If wrapping can be done without too much difficulty, this would be preferable to simulating Flatland.
Wrapping would be achieved for such algorithms by translating all wrapped points and connections into non wrapped form. For example you test which direction a point is closest from the city and then place it at that point for any algorithms. The results of this translation can be cached in the save file, and at most may need update every time the map is expanded, or every time the points change (possibly with time?).

As far as the local pathfinder is concerned, it just needs to get the convoy to the appropriate portal. Once at the portal, the convoy can be removed off the playable field and added to another system which deals with "off world" convoys. Such system would be nothing more than a timer queue where once the convoy reaches the portal it is added to the queue to arrive back at a certain time and with certain results. The advantage of such system is you could have potentially thousands of off world convoys and they would have practically no computational overhead.

jamespetts

Quote from: DrSuperGood on August 19, 2017, 02:56:52 PM
Wrapping would be achieved for such algorithms by translating all wrapped points and connections into non wrapped form. For example you test which direction a point is closest from the city and then place it at that point for any algorithms. The results of this translation can be cached in the save file, and at most may need update every time the map is expanded, or every time the points change (possibly with time?).

Are you aware of any known algorithms that do this?

QuoteAs far as the local pathfinder is concerned, it just needs to get the convoy to the appropriate portal. Once at the portal, the convoy can be removed off the playable field and added to another system which deals with "off world" convoys. Such system would be nothing more than a timer queue where once the convoy reaches the portal it is added to the queue to arrive back at a certain time and with certain results. The advantage of such system is you could have potentially thousands of off world convoys and they would have practically no computational overhead.

This is still assuming that we have actual portals, rather than convoys just leaving the map and carrying on. The difficulty with actual portals, as discussed above, is that choosing the appropriate portal is not easy. Do you think that having actual portals (rather than seamlessly integrated foreign destinations) would have a major advantage?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

DrSuperGood

QuoteAre you aware of any known algorithms that do this?
I recall polar projection from primary school. Basically the map becomes the centre of view and all destinations are then translated to be around it. The nature of the projection is such that the real life distance is conserved during translation. This sort of projection is often used for aircraft routes since they need to be distance optimized for maximum economy, with deviations only for air hazards or weather effects such as using jet streams or avoiding storm fronts.

The projection wraps from the surface of a sphere into 2D with only lines of radius being distance correct and lines of circumference not being correct. As such it can be used for routes leaving the city, but the same projection result cannot be used for routes from 1 out of world place to another. For inter out of world routes one would have to create a separate projection for each and obtain the distances for valid routes as appropriate. Of course the projection only needs to be created involving potential destinations with regard to a single place and exist to generate the routing graph, after which the routing graph itself can be used and saved. Routing graphs would only be invalidated and need regeneration if changes occur to available out of world routes or their locations, so at most will be regenerated very seldom.

QuoteThis is still assuming that we have actual portals, rather than convoys just leaving the map and carrying on. The difficulty with actual portals, as discussed above, is that choosing the appropriate portal is not easy. Do you think that having actual portals (rather than seamlessly integrated foreign destinations) would have a major advantage?
One could define an entire map edge to be a portal. For actual routes then one would use a separate algorithm with more than 16bit precision to compute the actual portal point, the point where the convoy will leave the world. Once the convoy reaches this portal point it is subject to portal mechanics and will eventually return at the portal point. Things like running cost and time of profit could be interpolated based on the out of world graph. The advantage of not having a convoy physically travel to the place is that one does not have to simulate movement and even running cost granularity can be lowered greatly reducing the computational overhead of the convoy. This would be very advantageous because one can potentially expect thousands of convoys being off world at a time as some trips might take in game years (think of the massive multiplayer server, the ships took 1-2 years to travel from one side of the map to the other and that represented ~800 km, hence thousands of ships were used).

jamespetts

Quote from: DrSuperGood on August 19, 2017, 06:02:11 PM
I recall polar projection from primary school. Basically the map becomes the centre of view and all destinations are then translated to be around it. The nature of the projection is such that the real life distance is conserved during translation. This sort of projection is often used for aircraft routes since they need to be distance optimized for maximum economy, with deviations only for air hazards or weather effects such as using jet streams or avoiding storm fronts.

The projection wraps from the surface of a sphere into 2D with only lines of radius being distance correct and lines of circumference not being correct. As such it can be used for routes leaving the city, but the same projection result cannot be used for routes from 1 out of world place to another. For inter out of world routes one would have to create a separate projection for each and obtain the distances for valid routes as appropriate. Of course the projection only needs to be created involving potential destinations with regard to a single place and exist to generate the routing graph, after which the routing graph itself can be used and saved. Routing graphs would only be invalidated and need regeneration if changes occur to available out of world routes or their locations, so at most will be regenerated very seldom.

Does polar projection work when the starting point is a sizeable area rather than a point?

QuoteOne could define an entire map edge to be a portal. For actual routes then one would use a separate algorithm with more than 16bit precision to compute the actual portal point, the point where the convoy will leave the world. Once the convoy reaches this portal point it is subject to portal mechanics and will eventually return at the portal point. Things like running cost and time of profit could be interpolated based on the out of world graph. The advantage of not having a convoy physically travel to the place is that one does not have to simulate movement and even running cost granularity can be lowered greatly reducing the computational overhead of the convoy. This would be very advantageous because one can potentially expect thousands of convoys being off world at a time as some trips might take in game years (think of the massive multiplayer server, the ships took 1-2 years to travel from one side of the map to the other and that represented ~800 km, hence thousands of ships were used).

That is one way of doing it - but would that not involve some branching logic in the vehicle pathfinding algorithm? Perhaps I am not fully understanding: say one has a vehicle on tile 100,52 (in world), and it its destination is (imaginary) tile 200952,127359 (off-world). What steps would it go through to calculate to which map edge tile to fly/sail in your suggested model?

Thank you for your useful thoughts on this.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

zook2

Quote from: jamespetts on August 19, 2017, 07:47:17 PM
That is one way of doing it - but would that not involve some branching logic in the vehicle pathfinding algorithm? Perhaps I am not fully understanding: say one has a vehicle on tile 100,52 (in world), and it its destination is (imaginary) tile 200952,127359 (off-world). What steps would it go through to calculate to which map edge tile to fly/sail in your suggested model?

That sounds trivial for straight lines, i.e. aircraft. But what if it's a ship and the calculated edge tile is not water? Maybe the entire map edge is land, or water tiles not reachable from the ship's position. I guess the existing pathfinder could still route the ship through a different map edge, but I remember that very long paths are a problem.

I agree that portal-less travel is more elegant and (slightly) more correct in terms of distance, fuel use, range etc., but portals would avoid the above problem. They could also serve as GUI elements, e.g. clicking a portal could open a list of cities lying in that direction and the vehicles traveling there. Finally, I suppose moving through a binary city tree structure should use much less CPU/RAM.

DrSuperGood

QuoteDoes polar projection work when the starting point is a sizeable area rather than a point?
Maybe from the centre of the map? If not then it can be done as part of the scheduler when caching a route to an off world city. The projection logic itself should be trivial cost as long as the results are cached.
QuoteWhat steps would it go through to calculate to which map edge tile to fly/sail in your suggested model?
Use polar projection at stop to find portal tile for route, and subtract that Euclidian distance from the total distance to stop, placing that into the portal logic and get convoy to move to portal tile. Once convoy reaches portal tile (similar to a normal stop point) then remove it from standard convoy update logic and place it into convoy portal logic system. Portal logic does off world stuff (flexible). Once it is time for convoy to come back into the world then it is removed from portal logic and placed back into convoy update logic with its pathfinding related stuff set to move from the portal point to its next stop.

As far as schedule goes, there would be automatically added portal points (which are like normal waypoints). When in the portal logic it advances the schedule appropriately until the re-entry portal point where the convoy is placed back into standard convoy update logic. If the automatically generated portal entry or exit waypoints are deleted all off world destinations they were involved with are also deleted. If an off world destination is deleted, then all portal way points are removed and recomputed resulting in new ones as appropriate. This schedule logic would allow one to have a convoy visit multiple off world locations and manipulate the schedule reliably. Off world logic for a convoy will not change if its assigned schedule changes, it will still arrive at its originally scheduled time however once it does then it will re compute its route and start the new schedule.

These are really rough ideas of how one could try to do it. There might be implementation problems and oversights.

As far as off world accuracy goes. As long as computed times are roughly correct it would be good enough and no one will notice the difference. This means that delays such as airport turn around times can be factored in as constant times, and that there are no deviations on flight paths and shipping routers. One could add a cost factor for routes that increases the effective off world distance travelled but does not increase the profit earned, this could apply to certain transport types such as ships to factor in having to go around obstacles. Off world mechanics do not need to be exact, they just need to feel good enough for an illusion of the convoy traveling to a far away place.

jamespetts

Quote from: zook2 on August 19, 2017, 09:10:21 PM
That sounds trivial for straight lines, i.e. aircraft. But what if it's a ship and the calculated edge tile is not water? Maybe the entire map edge is land, or water tiles not reachable from the ship's position. I guess the existing pathfinder could still route the ship through a different map edge, but I remember that very long paths are a problem.

The pathfinder would only need to do anything complicated within the game world for the ships - it could assume straight lines outside the game world (on the assumption that we cannot sensibly simulate things like the Cape of Good Hope and Cape Horn).

Quote
I agree that portal-less travel is more elegant and (slightly) more correct in terms of distance, fuel use, range etc., but portals would avoid the above problem. They could also serve as GUI elements, e.g. clicking a portal could open a list of cities lying in that direction and the vehicles traveling there. Finally, I suppose moving through a binary city tree structure should use much less CPU/RAM.

The trouble is that the original idea of portals also has intractable problems, as discussed above.


Quote from: Dr. Supergood
Maybe from the centre of the map? If not then it can be done as part of the scheduler when caching a route to an off world city. The projection logic itself should be trivial cost as long as the results are cached.

Vehicle routing is not cached - only passenger/mail/goods routing. Vehicle routes are calculated just before each convoy begins its journey.

Quote
Use polar projection at stop to find portal tile for route, and subtract that Euclidian distance from the total distance to stop, placing that into the portal logic and get convoy to move to portal tile. Once convoy reaches portal tile (similar to a normal stop point) then remove it from standard convoy update logic and place it into convoy portal logic system. Portal logic does off world stuff (flexible). Once it is time for convoy to come back into the world then it is removed from portal logic and placed back into convoy update logic with its pathfinding related stuff set to move from the portal point to its next stop.

Hmm - is the idea that it would first check to see whether the destination is in map or out of map and use a different pathfinding algorithm depending on the result of that check, one that, in the case of off-map destinations, used polar projection to find the appropriate portal point? That conceivably might work as the checks for on/off map would be infrequent enough not to affect CPU usage, although I am not quite sure how the actual pathfinding might work for off-map destinations.

Perhaps the schedule entries would have to be different for off-map destinations, and contain special 32-bit co-ordinates which could then be fed to an exit point finding algorithm?

QuoteAs far as schedule goes, there would be automatically added portal points (which are like normal waypoints). When in the portal logic it advances the schedule appropriately until the re-entry portal point where the convoy is placed back into standard convoy update logic.

Ahh, is this how you imagining the caching working? I suppose that, in the case of a ship where the exit point had been turned into land, this could be discarded and recalculated? I wonder how one might deal with the case of unreachable portal exit points, e.g. a portal exit point for ships in a small inland lake?

QuoteIf the automatically generated portal entry or exit waypoints are deleted all off world destinations they were involved with are also deleted. If an off world destination is deleted, then all portal way points are removed and recomputed resulting in new ones as appropriate. This schedule logic would allow one to have a convoy visit multiple off world locations and manipulate the schedule reliably. Off world logic for a convoy will not change if its assigned schedule changes, it will still arrive at its originally scheduled time however once it does then it will re compute its route and start the new schedule.

These are really rough ideas of how one could try to do it. There might be implementation problems and oversights.

Thank you for your thoughts on this: they are much appreciated. The ability for player vehicles to travel between different off-map destinations would be very worthwhile, as it would simulate the practice of having early aircraft calling at multiple points between origin and destination to refuel.

QuoteAs far as off world accuracy goes. As long as computed times are roughly correct it would be good enough and no one will notice the difference. This means that delays such as airport turn around times can be factored in as constant times, and that there are no deviations on flight paths and shipping routers. One could add a cost factor for routes that increases the effective off world distance travelled but does not increase the profit earned, this could apply to certain transport types such as ships to factor in having to go around obstacles. Off world mechanics do not need to be exact, they just need to feel good enough for an illusion of the convoy traveling to a far away place.

The mechanics do need to be fairly exact, as all of the balancing data will be based on real life data, so things will not balance if things are too far out of line: but deviation from reality by a few percent will not matter greatly. How far off reality do you think that polar projection would be for an Earth sized world (max. straight line journey without getting closer to the starting point again ~ 20,000 km) with a map of 1,000 - 2,000 km square?

Thank you again for your thoughts in respect of this: this will be most useful when I eventually come to implement this.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.