problem with the automatic path creation is that previous generated paths are not checked and therefore the path can change as soon you jump into the next system... leading to the same destination but taking another way

Also, a system that only has jump holes will tend to either tell you 'no best path' or lead you around in random circles, heh.

I'm afraid it isn't a perfect way to set paths, but it works for the most part. I have also experimented with the hole-gate slider and found little difference. My mod has 108 brand new systems and no crashes resulting from setting paths.

Edited by - DwnUndr on 9/15/2007 2:00:55 AM

DwnUnder, good to know.

Swat: you mean it comes up with different path each time it moves a system during path construction? But the original game files work ok though...?

Well I need to fix it one way or another because I need to release my mod! Ugh...!!

Question

If you delete the contents of each ini then run it would it give the proper pathing?

It should overwrite the files, hence why it gives option to create backups.

Note "should" - been a while since I used it.

Suprised about the incorrect paths, should (from next one on) give the same path if the algorithm is right. Must admit, we never had any crashes - we did get the odd "path not found" error though.

Not sure if it takes into account locked gates or not... as you may notice, it's been quite a while since I looked in any FL files (nigh on two years so I cannot remember what FLScan actually does anymore :/

lol Chips, get back to modding ya widget

Universal Modding Forums

Paths belong to the few things that have not been solved in all the time (even if ppl thought so)

yes we all know that paths are nothing more than
"startsystem, destinationsystem, startsystem, path, path, path, destinationsystem"
pretty simple looking but unfortunatly only half of the truth since obviously we often get errors such as "path not found" or crashes even if the path itself seems to be correct

flscan does nothing else than search the jumpgates and jumpholes in the system files and read out where they do lead
there is no check if a similar route is already covered by another path nor do i believe that the best path is always choosen (since the system is not analyzed and distances calculated)
the way digital anvil calculated path must have been different and since many mods have this problem (if not all) this is one of the most important fixes for those mods that has to be done

---

flscan does nothing else than search the jumpgates and jumpholes in the system files and read out where they do lead
there is no check if a similar route is already covered by another path nor do i believe that the best path is always choosen (since the system is not analyzed and distances calculated)
the way digital anvil calculated path must have been different and since many mods have this problem (if not all) this is one of the most important fixes for those mods that has to be done

---

I do not know what Accushot did in creating it, but I can assure you that he did use a search algorithm - that he did say.

"There is no check if a similiar route is already covered" - I don't understand what you mean... You mean it plots the path from start to finish, then each system you jump into it re-evaluates the path again and re-sets if different? Hence how path may keep changing, although this shouldn't happen if the algorithm is right...

One thing DA may have taken into account is what the player can see - I don't remember it ever plotting waypoints through holes I don't know about, I do NOT know if this tool does that, at which point - if you don't know the system/jumpgate, I don't know what happens.

As for distance calculated - I don't think Rob imagined he'd create the perfect tool in it's first itteration, he was relying upon feedback. Sadly, 2 years later, people are finally giving feedback. I can't assume, but do think you are correct - no calculations of distances between jumpgates / holes is done, and therefore it chooses a shortest path simply by number of jumps taken... not distance covered.

The "no path found" - that's easy. If the calcs are done on a depth search, and the depth (by the sliders ) is limited to say... 10, then after it's done a search to a depth of 10 looking for the best path, it will stop... so if there's 12 systems between two systems (ie 12 jumps) it won't have a path set in the files.

---

One thing DA may have taken into account is what the player can see - I don't remember it ever plotting waypoints through holes I don't know about, I do NOT know if this tool does that, at which point - if you don't know the system/jumpgate, I don't know what happens.

---

I know for sure that you can plot paths between systems (using FLscan path building) that you have not visited yet (through gates, it won't plot through holes). When you look at the universe map you will even see breaks in the purple path lines for systems you have not yet visited. Pretty cool stuff. Basically you can jump into a mod you have never seen and plot a path to a visible far-away system and it will take you there.

Granted, my tests have been through jump gates, not holes. The biggest hurdle most of us face when we create a TC mod is the start system. Mine has jumpholes out. For beta testing I have these currently set as two-way to expedite the testing. When done, I will turn the start system back to one way holes (to prevent an extremely undesired shortcut for transit or attack). My plan (before release) is to remove the start system and rebuild the paths with FLscan, then re-add the start system and manually add the paths for it (saved from before).


Edited by - DwnUndr on 9/16/2007 5:33:26 AM

Hmm, issue with distance between jumpgates.. something I should have thought about instantly.

Shortest distances != quickest path.

Tradelanes.

Well I'm pushed for time at the moment but I will make a manual set of path files when I do get time and see what happens.

Unfortunately I have no idea how to write in C++, which would be a great help here. Can anyone give me some pointers to an easy compiler and help me get started in C++ (or is C# better??).

Look for this algorithm: Dijkstra's algorithm
I have solved the generating of the paths with that in VB.
But, as I wrote, although the paths where correct and short, it didnt helped me with crashes.

Maybe crashes are unrelated?

I'm currently writing my own as well, mainly as it's a good use of searching algorithms.

At the mo, gotta debug my lil parser i made. Reads universe.ini file correctly, and finds all the system files too... but right now a bug means it gets the links between some, but completely misses others Just not had time to track it down yet

Whether it'll ever get finished, let alone work, remains to be seen - however, thankyou for the name of the algorithm i'll need Was wondering how to find the right one

Probably better to use the Floyd-Warshall APSP (all-points-shortest-path) algorithm. This gives you all the shortest paths from all the possible origins to all the possible destinations, which I think is what you want.

On the other hand, it's rather confusing to work with. If you're going to need to fine tune it, and you may want to, then I wouldn't recommend it unless you have a lot of experience with search algorithms, you're a really smart programmer, or you have an uncommonly strong imagination for multi-dimensional geometry. (Failing at all three of those myself, I find it difficult to work with. )

If you haven't written a search algorithm before, I would not recommend Dijkstra's either. Instead I'd say use the simpler "breadth first" search.

It will be easy to get it working, and you can fine-tune it after that. Once you're done fine-tuning it, it will arguably look something like Dijkstra's. (Dijkstra's is a breadth-first search but with an extra consideration: some connections are costlier than others.) But if you're just starting out, I think it would be easier for you to add small sophistications to a simpler algorithm, rather than adjust a more complicated algorithm.

If it's just a modder's tool, to analyze star-system files and produce the shortest-paths file, then I wouldn't see any urgent need to optimize the tool for processing speed. (If there were, you'd be using Floyd-Warshall anyway.) But if this were a concern, and you were using a breadth-first approach, you'd want to use a heuristic to cancel obviously-bad paths before they're added to the queue. (When you do this with Dijkstra, you get what is called the A-star algorithm.)

Well let me know if you need any further advice, or if you get into trouble. This is one of my few areas of specialization, and I'm always happy to help.


Edited by - breslin on 9/18/2007 5:47:01 AM