Page 1 of 1

PathFinding

Posted: Tue Jul 19, 2016 2:40 pm
by bjgrt
The pathfinding in the PS is rudimentary at best. It doesn't understand to step aside even one "tunnel" to refuel, also doesn't support "long travel" using autorefueling, no wayponts neither. You've also mentioned that even the rudimentary pathfinding is quite expensive.
Would you consider adapting an advanced and optimized pathfinding algorithm (ideas) from another (open source) game? There is a transport simulation game called OpenTTD. They manage to operate hundreds (and even thousands) of vehicles within a complex transport network realtime on a quite "weak" computer. Written in C. The community is quite affable, there is also a semi-separate Russian sub-community.

Re: PathFinding

Posted: Wed Jul 20, 2016 7:56 pm
by Ufnv
bjgrt wrote:The pathfinding in the PS is rudimentary at best. It doesn't understand to step aside even one "tunnel" to refuel, also doesn't support "long travel" using autorefueling, no wayponts neither. You've also mentioned that even the rudimentary pathfinding is quite expensive.
Would you consider adapting an advanced and optimized pathfinding algorithm (ideas) from another (open source) game? There is a transport simulation game called OpenTTD. They manage to operate hundreds (and even thousands) of vehicles within a complex transport network realtime on a quite "weak" computer. Written in C. The community is quite affable, there is also a semi-separate Russian sub-community.
Please do not start this thing about pathfinding. You may not believe me, but I am quite good in graph theory. There is even a special type of graph officially called after my family name.
Please just believe I know what is going on there and things are extremely well optimized algorithmically, in code and in data structures. And also written in C.

I will not even start arguing about pathfinding. Excuse me if I am rough here, but this is my weak spot. For some reason anybody around me pretend to know something about graph theory and pathfinding and try "teaching" me, not knowing I've spent more than 20 years scientifically studying the topic :)

If you have any knowledge in the field you may also try to figure out why exactly "autorefuelling", for example, efficiently kills pathfinding optimizations :)

I certainly know what can be done to make the pathfinding for the player ships in the game more sophisticated, I just see no clear reason for this. To be more precise, the value/price ratio for such steps are so extremely poor I will not be spending my time on it. The current one is good enough for me, period.

Re: PathFinding

Posted: Wed Jul 20, 2016 10:08 pm
by bjgrt
I didn't know that you are a specialist in the graph theory, just asked if you would consider adapting some external knowledge/algorithms. You wouldn't or have reasons to believe yours is better anyway - there is nothing to be hostile about.
The waypoints (I've meant) is just a list of destinations (set by player), all decisions about the next destination/path (as well as autorefuelling) could be done at the previous one, so no optimization would be hurt. Just saying.

Re: PathFinding

Posted: Thu Jul 21, 2016 6:43 am
by Ufnv
bjgrt wrote: The waypoints (I've meant) is just a list of destinations (set by player), all decisions about the next destination/path (as well as autorefuelling) could be done at the previous one, so no optimization would be hurt. Just saying.
Yes, this feature is scheduled but with the low priority, as there are no much use cases for it.

Re: PathFinding

Posted: Thu Jul 21, 2016 4:12 pm
by bjgrt
Ufnv wrote:there are no much use cases for it
Don't know how many people playing on a huge galaxy, but sending an "cloaked" scout far away or returning it with "the box" could be annoying.

Re: PathFinding

Posted: Thu Jul 21, 2016 9:17 pm
by Ufnv
bjgrt wrote:
Ufnv wrote:there are no much use cases for it
Don't know how many people playing on a huge galaxy, but sending an "cloaked" scout far away or returning it with "the box" could be annoying.
You are right. But cloaked scouts are usually highly dependent on the "illegal refuelling" and this is the action that cannot be safely automated. Another way is to make is self-refuelling with the solar module, but this gives too many variants, like when to resume movement - only after a complete refuelling, or after the possibility to make a next move or somewhere in between. This is better to leave on a human to decide, because such decision is often influenced by the information - like the probability of being detected at a specific system.

Re: PathFinding

Posted: Fri Jul 22, 2016 4:05 pm
by bjgrt
Ufnv wrote:
bjgrt wrote:
Ufnv wrote:there are no much use cases for it
Don't know how many people playing on a huge galaxy, but sending an "cloaked" scout far away or returning it with "the box" could be annoying.
You are right. But cloaked scouts are usually highly dependent on the "illegal refuelling" and this is the action that cannot be safely automated. Another way is to make is self-refuelling with the solar module, but this gives too many variants, like when to resume movement - only after a complete refuelling, or after the possibility to make a next move or somewhere in between. This is better to leave on a human to decide, because such decision is often influenced by the information - like the probability of being detected at a specific system.
I use only the "solar module". Thought about adding something like "wait till completely refueled" at manual waypoints (you already have in plans), maybe allowing it only if you have a 100% "cloaking".