Author Topic: v2.0.0 Changes Discussion Thread  (Read 122712 times)

0 Members and 1 Guest are viewing this topic.

Offline serger

  • Commodore
  • **********
  • Posts: 634
  • Thanked: 120 times
  • Silver Supporter Silver Supporter : Support the forums with a Silver subscription
    2021 Supporter 2021 Supporter : Donate for 2021
    2022 Supporter 2022 Supporter : Donate for 2022
Re: v1.14.0 Changes Discussion Thread
« Reply #300 on: September 07, 2021, 12:24:21 AM »
Make a graph of JPs (w/o Lagrange ones) with a path lengths between those that are in the same pair of systems. Recalculate those lengths every production cycle.
When you have to find a path - run for minimal number of jumps, continue this cycle with additional 3 iterations (memorizing paths), then calc distances for every path and find the shortest.
To use Lagrange JPs more accurate it's possible to get their positions for estimated time of jump into this system. The same with the last trajectory patch (JP to final target) if it's orbital target.

The task will be much easier without Lagrange JPs, and it's not the only problem with them.
They are inconsistent with overall JP narrative (they are visible and usable before JP theory researched!), they are easy and natural way to abuse AI with massive salvos and so on.
Maybe it worth to consider to replace them with static in-system potential JPs to stabilize, smth like 1/2^n distances between central body and every interstellar JP. Or just exterminate them, because not enough game value for too much problems.
« Last Edit: September 07, 2021, 12:30:08 AM by serger »
 

Offline Steve Walmsley (OP)

  • Aurora Designer
  • Star Marshal
  • S
  • Posts: 11649
  • Thanked: 20350 times
Re: v1.14.0 Changes Discussion Thread
« Reply #301 on: September 07, 2021, 08:31:35 AM »
Make a graph of JPs (w/o Lagrange ones) with a path lengths between those that are in the same pair of systems. Recalculate those lengths every production cycle.
When you have to find a path - run for minimal number of jumps, continue this cycle with additional 3 iterations (memorizing paths), then calc distances for every path and find the shortest.
To use Lagrange JPs more accurate it's possible to get their positions for estimated time of jump into this system. The same with the last trajectory patch (JP to final target) if it's orbital target.

The task will be much easier without Lagrange JPs, and it's not the only problem with them.
They are inconsistent with overall JP narrative (they are visible and usable before JP theory researched!), they are easy and natural way to abuse AI with massive salvos and so on.
Maybe it worth to consider to replace them with static in-system potential JPs to stabilize, smth like 1/2^n distances between central body and every interstellar JP. Or just exterminate them, because not enough game value for too much problems.

As you mentioned above, to make the above work I would need Lagrange point locations at the point of arrival in-system, not at the point the journey begins. I could use fleet speed to work out the arrival point at the system, then use that time to run orbital movement forward to learn the LP locations. However, I can't pre-store that information as it would be different for each fleet in each system. Also, some fleets (tugs) may change their speed mid-journey so I would need to handle that too, plus other fleets may be spending time loading/unloading or using delay orders rather than moving so that needs to be handled too. 'Load until full' is even worse.

Someone else mentioned not checking a JP chain beyond finding a valid path, but unfortunately a) that isn't necessarily true because leaving the system and re-entering could be a shorter route to the destination than simply heading in-system from the first jump point. Secondly, I would still be checking all the other jump chains to their end, so I don't save much processing time.

Ultimately, it is all the edge cases that make this a lot more intensive that it might seem at first glance. I'm happy that the current system is right 95% of the time and I don't want to spend a lot of effort and processing power trying to get the extra few percent, especially when there are manual interventions available to the player.
 
The following users thanked this post: StarshipCactus

Offline Zincat

  • Captain
  • **********
  • Z
  • Posts: 566
  • Thanked: 111 times
Re: v1.14.0 Changes Discussion Thread
« Reply #302 on: September 07, 2021, 10:20:36 AM »
Make a graph of JPs (w/o Lagrange ones) with a path lengths between those that are in the same pair of systems. Recalculate those lengths every production cycle.
When you have to find a path - run for minimal number of jumps, continue this cycle with additional 3 iterations (memorizing paths), then calc distances for every path and find the shortest.
To use Lagrange JPs more accurate it's possible to get their positions for estimated time of jump into this system. The same with the last trajectory patch (JP to final target) if it's orbital target.

The task will be much easier without Lagrange JPs, and it's not the only problem with them.
They are inconsistent with overall JP narrative (they are visible and usable before JP theory researched!), they are easy and natural way to abuse AI with massive salvos and so on.
Maybe it worth to consider to replace them with static in-system potential JPs to stabilize, smth like 1/2^n distances between central body and every interstellar JP. Or just exterminate them, because not enough game value for too much problems.

As you mentioned above, to make the above work I would need Lagrange point locations at the point of arrival in-system, not at the point the journey begins. I could use fleet speed to work out the arrival point at the system, then use that time to run orbital movement forward to learn the LP locations. However, I can't pre-store that information as it would be different for each fleet in each system. Also, some fleets (tugs) may change their speed mid-journey so I would need to handle that too, plus other fleets may be spending time loading/unloading or using delay orders rather than moving so that needs to be handled too. 'Load until full' is even worse.

Someone else mentioned not checking a JP chain beyond finding a valid path, but unfortunately a) that isn't necessarily true because leaving the system and re-entering could be a shorter route to the destination than simply heading in-system from the first jump point. Secondly, I would still be checking all the other jump chains to their end, so I don't save much processing time.

Ultimately, it is all the edge cases that make this a lot more intensive that it might seem at first glance. I'm happy that the current system is right 95% of the time and I don't want to spend a lot of effort and processing power trying to get the extra few percent, especially when there are manual interventions available to the player.

Having had to code pathing more than once during my life, I 100% agree. Pathing can be incredibly complex to code efficiently, and honestly, most of the time a "sufficiently good" approximation is used. At the end of the day, if it works decently enough,  it's often not worth it to double the complexity or more for very marginal gains.

In Aurora, I think what we have is more than good enough, and I don't see why Steve would have to invest a large amount of time and effort, not to mention slowing down the code execution, to have gains in edge cases.
 

Offline Migi

  • Captain
  • **********
  • Posts: 465
  • Thanked: 172 times
Re: v1.14.0 Changes Discussion Thread
« Reply #303 on: September 07, 2021, 12:48:38 PM »
Would "improving the AI" be a sufficiently good reason to take a stab at it?
You mentioned that players can manually intervene to improve the situation, but that doesn't help the AI.
 

Offline Droll

  • Vice Admiral
  • **********
  • D
  • Posts: 1703
  • Thanked: 599 times
Re: v1.14.0 Changes Discussion Thread
« Reply #304 on: September 07, 2021, 01:27:14 PM »
Would "improving the AI" be a sufficiently good reason to take a stab at it?
You mentioned that players can manually intervene to improve the situation, but that doesn't help the AI.

I don't understand what the seemingly massive problem with pathfinding is. It works just fine from my perspective.

If we're going to improve the AI you'll get much more mileage from trying to make them better at empire building or giving multi-system random NPR generation a try. That's the main problem I see wit the AI. Not their pathfinding.
 
The following users thanked this post: Andrew, Black, BAGrimm, StarshipCactus, nuclearslurpee

Offline TMaekler

  • Vice Admiral
  • **********
  • Posts: 1112
  • Thanked: 298 times
Re: v1.14.0 Changes Discussion Thread
« Reply #305 on: September 07, 2021, 02:50:39 PM »
The only way to not lose time on these calculations would be to make them during the player is doing his moves. Don't know how easy it would be to set up a separate thread that does some pre-calculations during the time we work on our moves... though we are slow enough to lose 10% of processing power and not be able to recognize that.
 

Offline db48x

  • Commodore
  • **********
  • d
  • Posts: 641
  • Thanked: 200 times
Re: v1.14.0 Changes Discussion Thread
« Reply #306 on: September 07, 2021, 03:08:04 PM »
As you mentioned above, to make the above work I would need Lagrange point locations at the point of arrival in-system, not at the point the journey begins. I could use fleet speed to work out the arrival point at the system, then use that time to run orbital movement forward to learn the LP locations. However, I can't pre-store that information as it would be different for each fleet in each system. Also, some fleets (tugs) may change their speed mid-journey so I would need to handle that too, plus other fleets may be spending time loading/unloading or using delay orders rather than moving so that needs to be handled too. 'Load until full' is even worse.

It can be done more easily than that. Simply disregard LPs when planning a multi–system route. Then when a fleet starts a route segment, have it consider the LPs to see if they would make a shorter trip than flying direct. This will always be after entering a system, or after loading cargo, or after a delayed order, or releasing a tugged ship, etc. You may still want to allow the player to specify a route going via LPs manually, even though they wouldn’t be included in the plan otherwise.

Of course that still leaves cases where the pathfinder will fail to choose the shortest route. However, it is an improvement because those cases will be rarer and they will involve smaller distances in trip length. And there will be compensating improvements elsewhere.
 
The following users thanked this post: skoormit

Offline db48x

  • Commodore
  • **********
  • d
  • Posts: 641
  • Thanked: 200 times
Re: v1.14.0 Changes Discussion Thread
« Reply #307 on: September 07, 2021, 03:20:26 PM »
Someone else mentioned not checking a JP chain beyond finding a valid path, but unfortunately a) that isn't necessarily true because leaving the system and re-entering could be a shorter route to the destination than simply heading in-system from the first jump point. Secondly, I would still be checking all the other jump chains to their end, so I don't save much processing time.

The A* pathfinding algorithm is a bit smarter than that; it quickly drops paths that are longer than the shortest known path. In this case you would start with the direct in–system path being the shortest known path, and the pathfinder would stop and return it whenever it had eliminated all of the alternatives. It would begin by considering paths that start by flying to the system JPs. These n additional paths are incomplete, but it can calculate (or rather keep track of) their length so far, which in this case is just the distance between the starting location and the JPs. If any of those distances are larger than the known shortest path, then those routes are simply dropped. The most common scenario will be that all alternative routes are immediately dropped, or that they are dropped after hopping to one more system to consider the JPs there.

Plus remember that you can cache these routes. Ships fly from Earth to Mars all of the time, or from Earth to Aldebaran IX or whatever, and they shouldn’t even be using the pathfinder at all to do so. They should be looking in a table of known routes and finding the shortest route there. If you’re not already doing this, then that may be where the next performance boost comes from.
 

Offline db48x

  • Commodore
  • **********
  • d
  • Posts: 641
  • Thanked: 200 times
Re: v1.14.0 Changes Discussion Thread
« Reply #308 on: September 07, 2021, 03:23:02 PM »
The distance between jump points never changes,

This is actually not true as the travel distance between jump points is influenced by Lagrange Points which are subject to orbital mechanics.

That doesn’t change the distance from one JP to another.
 

Offline Droll

  • Vice Admiral
  • **********
  • D
  • Posts: 1703
  • Thanked: 599 times
Re: v1.14.0 Changes Discussion Thread
« Reply #309 on: September 07, 2021, 06:39:46 PM »
The distance between jump points never changes,

This is actually not true as the travel distance between jump points is influenced by Lagrange Points which are subject to orbital mechanics.

That doesn’t change the distance from one JP to another.

The effective travel distance does potentially change thanks to the aforementioned lagrange movement. But if you are simply concerned with the absolute distance between two JPs, that is static. Since we are talking about pathfinding still the former is more important than the latter for our purposes.
 

Offline TheTalkingMeowth

  • Captain
  • **********
  • T
  • Posts: 494
  • Thanked: 203 times
  • Gold Supporter Gold Supporter : Support the forums with a Gold subscription
    2021 Supporter 2021 Supporter : Donate for 2021
    2022 Supporter 2022 Supporter : Donate for 2022
Re: v1.14.0 Changes Discussion Thread
« Reply #310 on: September 07, 2021, 11:01:13 PM »
This pathfinding stuff came up previously:

http://aurora2.pentarch.org/index.php?topic=12211

The last post includes a python script (from me) demonstrating the runtime cost of possible improvements to the pathfinding on notional jump networks. It also shows how to find the shortest path to moving goals (though I didn't implement ships or planets so the demo is only on non-moving goals).
 
The following users thanked this post: skoormit

Offline Migi

  • Captain
  • **********
  • Posts: 465
  • Thanked: 172 times
Re: v1.14.0 Changes Discussion Thread
« Reply #311 on: September 08, 2021, 10:45:59 AM »
Would "improving the AI" be a sufficiently good reason to take a stab at it?
You mentioned that players can manually intervene to improve the situation, but that doesn't help the AI.

I don't understand what the seemingly massive problem with pathfinding is. It works just fine from my perspective.

If we're going to improve the AI you'll get much more mileage from trying to make them better at empire building or giving multi-system random NPR generation a try. That's the main problem I see wit the AI. Not their pathfinding.

The problem is that an AI empire in Steve's current position would be moving ships and resources through a long route of a single jump rather than the shorter multi-system route.

Steve mentioned that a player can intervene to fix the situation with his newly implemented locking of jump points, but I thought there was a small chance that he might look at it from the other perspective.
 

Offline nuclearslurpee

  • Admiral of the Fleet
  • ***********
  • Posts: 2960
  • Thanked: 2222 times
  • Radioactive frozen beverage.
Re: v1.14.0 Changes Discussion Thread
« Reply #312 on: September 08, 2021, 10:59:14 AM »
Would "improving the AI" be a sufficiently good reason to take a stab at it?
You mentioned that players can manually intervene to improve the situation, but that doesn't help the AI.

I don't understand what the seemingly massive problem with pathfinding is. It works just fine from my perspective.

If we're going to improve the AI you'll get much more mileage from trying to make them better at empire building or giving multi-system random NPR generation a try. That's the main problem I see wit the AI. Not their pathfinding.

The problem is that an AI empire in Steve's current position would be moving ships and resources through a long route of a single jump rather than the shorter multi-system route.

Steve mentioned that a player can intervene to fix the situation with his newly implemented locking of jump points, but I thought there was a small chance that he might look at it from the other perspective.

I believe Droll's point was more that while there is a legitimate benefit to the NPRs from adding better pathfinding it is a relatively minor improvement because it does not fix the bigger problems that limit the effectiveness of the AI, which includes the inability to effectively expand to multiple systems and build an empire of decent size while maintaining a functional economy. Making an AI shipping lane faster in ~5% of cases, if that, really does little if anything to address those bigger problems.

Basically, the benefit of fixing pathfinding for NPRs is small enough that it would only matter if the question of whether or not to implement a new pathfinding method was borderline. It sounds like it is not as Steve is satisfied with the current system, and honestly if the major goal is to improve the AI his time would be better spent on a dedicated AI improvement project than on a pathfinding upgrade with tangential benefits.
 
The following users thanked this post: Black, Droll, StarshipCactus

Offline db48x

  • Commodore
  • **********
  • d
  • Posts: 641
  • Thanked: 200 times
Re: v1.14.0 Changes Discussion Thread
« Reply #313 on: September 08, 2021, 03:31:49 PM »
The effective travel distance does potentially change thanks to the aforementioned lagrange movement. But if you are simply concerned with the absolute distance between two JPs, that is static. Since we are talking about pathfinding still the former is more important than the latter for our purposes.

You missed my point, or I didn’t explain it effectively.

Pathfinding is a recursive process, where you repeatedly apply simple steps in order to achieve a complex result. In Auora, the simplest possible step is to fly from one JP to another. Instead of doing a square root to calculate that distance every single time the pathfinder considers a JP, we can save time by looking the number up in a pre–built cache. Once that number is known, the pathfinder can check for multi–step paths to reach the same goal, such as going via a pair of LPs, if there are any. Regardless of whether the pathfinder does it, it must first consider the simpler straight–line path, and that’s where the cache is most useful. The existence of LPs does not make the cache invalid or useless. Those straight–line paths are the bedrock on which all fancier paths are built.
 

Offline Density

  • Warrant Officer, Class 1
  • *****
  • D
  • Posts: 98
  • Thanked: 44 times
Re: v1.14.0 Changes Discussion Thread
« Reply #314 on: September 08, 2021, 09:01:06 PM »
Of course that still leaves cases where the pathfinder will fail to choose the shortest route.

You missed my point, or I didn’t explain it effectively.

You seem to be aware that what you're proposing doesn't address the cases where stabilized lagrange points cause a different set of systems to have a shorter route than when only direct JP to JP travel is considered. But when it is pointed out to you, your tone is dismissive.

You could have just as easily been explicit in saying that the LP cases would still be unaddressed, but that you still consider your proposal an improvement in that you believe (if I am reading it correctly) there would be fewer edge cases and that it would improve overall performance.