To all vsnav users (and pathfinding experts): Typical usage?

A forum for the discussion and development of programs to assist working on or playing with the Vegastrike engine and data sets.
Post Reply
Wisq
ISO Party Member
ISO Party Member
Posts: 453
Joined: Sat Jul 30, 2005 10:21 am

To all vsnav users (and pathfinding experts): Typical usage?

Post by Wisq »

So here I am working on an as-yet-unreleased navigation system, and it comes time to do the pathfinding system.

One thing I never liked about vsnav's system was that, even when I said "I'll accept any path up to 2 hops longer than the optimal one", it seemed to ignore a lot of possible paths and only branch out when it got near the target. So it was ignoring things like "hop to this nearby system, then rejoin with the optimal route" -- things that are important if, say, I take a long-range cargo mission and want to know what nearby bounties I can take on the way.

Eventually, I've written an A* algorithm pathfinder, using the linkages between sectors as my heuristic. (That heuristic needs improving, but that'll just increase the speed.) It works well. Too well.

The problem is, without the artificial constraints vsnav used for its limited pathfinding, it turns out the issue is not finding the best path, but finding too many good paths. For example, unless there is something seriously wrong with my algorithm, there are 280 ways to get from Cephid 17 to Sol in 14 hops, 4948 ways to get there in 15 hops, and 49346 ways to get there in 16 hops. (And every single one goes through Crucible/War.)

So I asked for some rain, and I got flooded. Nobody has time to browse fifty thousand possible paths to the destination. Mind you, the program handles it fine, although it expands to some 70 megs of RAM. But given that kind of power, I figured it was time to update the interface a little.

So, here's the question: What do you vsnav users use the extra hops for?

Personally, I used to go to the local bulletin board, look up the most expensive cargo job, and accept it. Then I pulled up vsnav and asked it for the path from here to there. I'd look at the list of paths and compare them to the other missions on the board. If there were places along a single route that I could visit and get more cash without delaying "the Big Job" too much, I'd accept them too, up to the maximum of three. Then I follow that route.

I'm therefore thinking along the lines of a "Detour" function. First, vsnav calculates all the jump paths (or at least, how many there will be). Then, you hit Detour. It brings up a list of systems you could detour through (in alphabetical order for easy reference), and how many jumps that would extend your trip by (at the minimum). Selecting a system would limit your path selection to paths that pass through that system. The list of paths shrinks, and your list of possible detours changes (because some might now take you too far out of your way). You select as many as you want, and eventually, you have the fastest route that takes you through all of them.

Another option, possibly in addition to the other, is the concept of "hubbing". For example, there are roughly 30 ways to get to War, 2 ways to get from War to Hhrass, and some thousand ways to get from Hhrass to Sol. Combinatorics conspires against us to turn that into nearly 60k routes, but the trip could be a lot simpler if the algorithms could declare War and Hhrass as "hubs" in the route. You then only have to pick a path from Cephid 17 to War, follow one of the two paths to Hhrass, and pick a route from Hhrass to Sol. It would be like three different searches, except done automatically for you as a sort of "segmented" journey. (But this will be a little tricky, and still doesn't reduce the fact that there are a thousand routes to choose from at the end.)

Finally, any pathfinding experts out there? There's a lot of information on the web regarding finding the optimal path in a sparsely-connected network. There's far less about intentionally finding sub-optimal paths in a dense interconnected grid. I think I've done okay at finding them, but now I need to make that information useful for the user.
klauss
Elite
Elite
Posts: 7243
Joined: Mon Apr 18, 2005 2:40 pm
Location: LS87, Buenos Aires, República Argentina

Post by klauss »

All pathfinding algorithms take as a problem that archs (edges in english?) don't have the same "length" (as in cost). In VS, they do. So, the best algorithm by far is the A*, which in this case is simply a wieghed BFS. I had coded once a weighed BFS (instead of the A*) which would explore N nodes towards the target, and M points at random connected to explored nodes. It works better than A* when there are holes in the grid (where A*'s guessing only takes you away from the optimal path).

That's for optimal searches. The good thing about pure BFS (not weighed BFS), is that you traverse all points that are N hops from the source at each stage. You could check that list of open nodes, and check if one of them is one of the "hubs" you were talking about. If it is, you take the closest route to that place, and continue from there. I think it's a good heuristic to get a path that traverses all, and due to the segmentation, you will have alternative routes between hubs only - and not the hole path.

Hope it's clear, because I have to leave. Bye.
Oíd mortales, el grito sagrado...
Call me "Menes, lord of Cats"
Wing Commander Universe
Wisq
ISO Party Member
ISO Party Member
Posts: 453
Joined: Sat Jul 30, 2005 10:21 am

Post by Wisq »

Well, the pathfinding doesn't take too long (even to go from one side of the jump network to the other). A* has the benefit that I can plug in a heuristic, like (in my case) the "sector hop distance".

For example, if I know that the fastest way to get from Crucible to Sol is through Redemption (just an example), then Crucible has a heuristic of 2, Redemption has a heuristic of 1, and Sol has 0.

A better means of doing this would be to pathfind my way through a sector. For example, if I precalculate the fastest path from Rust to Sol, then I know the exact minimum cost of being in Rust. As I get to sectors that are closer to Sol, the A* algorithm focuses on those sectors, and I reach Sol much faster than a standard Dijkstra's.

Once I've found the optimal path, finding alternate paths is much easier. For example, if the optimal path takes 13 hops (so I can only report routes 15 hops or less), and I know that the fastest path from Hhrass to Sol is 10 hops, and I find a 7-hop route that lands me in Hhrass, I can immediately throw that route out and cease pursuing it -- the sum total would be 18 hops, which is more than the 15 maximum.

I forget the exact code, but suffice it to say, pathfinding itself isn't the biggest issue -- although better heuristics would speed it up a little, and a better sub-optimal algorithm (once the optimal is found) might help more. Rather, the issue is simply, "how do I reduce some sixty thousand routes into something people can actually use?"
IxianMace
Mercenary
Mercenary
Posts: 114
Joined: Mon Nov 17, 2003 5:06 am
Location: Where the action is...

Re: To all vsnav users (and pathfinding experts): Typical us

Post by IxianMace »

Wisq wrote:So, here's the question: What do you vsnav users use the extra hops for?
Apart from what you've already mentioned in finding missions that can be done while enroute from another mission accepted from the starting system, I would be looking at the factions that own the system(s) I'm interested in passing through.

For example, I might want to bypass hostile space if I'm not looking for a fight, and use some alternate routes to avoid one or more systems.

The other would be looking at installations within systems. I like to frequent Starfortresses while going from one place to another, in the hope that it may have weapons I like, or other useful military hardware to offer.

In short, I am mainly concerned about faction control over systems, and what the systems themselves have to offer in installations and commodities.
Wisq
ISO Party Member
ISO Party Member
Posts: 453
Joined: Sat Jul 30, 2005 10:21 am

Post by Wisq »

Also, I should note (upon re-reading your message) that hubs are something I was considering making computed based on the trip, rather than precalculated.

An example algorithm: Hash table of systems versus number of paths that go through that system. Sort these systems in descending order and start at the top. These are the candidates for hubbing.

Actually choosing hubs is a little more complex, since you might have hubs A, B, and C, but B is only a hub because there's only a single route between A and C (and that's B). So you drop B and look for another hub. (Maybe that's D, and C lies on a single path between A and D, so you drop C. Etc.)

In this sense, it's like squeezing a toothpaste bottle from the middle -- eventually, you compress everything into a bulge one one side, a bulge on the other, and a flat section in the middle. :)
Wisq
ISO Party Member
ISO Party Member
Posts: 453
Joined: Sat Jul 30, 2005 10:21 am

Post by Wisq »

Hm, okay. So perhaps we could create weights for each hop rather than just considering them all equal. If a sector is owned by a hostile faction (and you click the appropriate search option), its weight is increased. If a sector has a starfortress, its weight is decreased. So this sounds like the groundwork for an advanced search interface.

Also, again regarding hubbing: Another tricky part is drilling down the selection of hubs. For example, if there are two "major" routes to a particular location (i.e. that take drastically different routes) and then a whole bunch of "minor" routes on top of that (small deviations in each major route), the trip should be separated thus. So you would see two "meta paths" listed, select one, and then begin plotting how you're going to move along that route.

Essentially, once I find all possible routes, I need either a way to reduce the number of routes by a hard (rather than fuzzy) search criteria (like "must pass through this sector"), or a way to divide them up hierarchically (pick a major path, then a minor one).

The other option is just to plainly match the use case so well that, once satisfied, we give them the shortest route and that's all they need. I'm hoping weights and detours would help there.
klauss
Elite
Elite
Posts: 7243
Joined: Mon Apr 18, 2005 2:40 pm
Location: LS87, Buenos Aires, República Argentina

Post by klauss »

Ok. Have an idea:

Make the user do the work.

Compute all acceptable paths. Compute the systems they go trhough, and show them somehow with the alternatives. Most alternatives will overlap, as otherwise they would deviate too much and would not fall within the restriction of N hops.

So, it won't be that cluttered.

Then, the user clicks on a system: I want to go here. So, you filter out all paths that go through there, and keep on like that until the user finds his desired route.

Like it?
Oíd mortales, el grito sagrado...
Call me "Menes, lord of Cats"
Wing Commander Universe
Wisq
ISO Party Member
ISO Party Member
Posts: 453
Joined: Sat Jul 30, 2005 10:21 am

Post by Wisq »

So if I understand you correctly, you're suggesting something like this:

After calculating the routes, I don't immediately draw and record all routes. Instead, I just count how many routes there are, and how many go through each system, and how many hops that visiting that system will extend your trip by (if any). I immediately and automatically activate the "detour" function, which means I present them with a window with that information. They select systems, narrowing the list each time, until they're satisfied with the number / quality of their selected routes.

Sound about right?

Later on, I'm thinking I'd add an advanced trip planner. You have a source system, but you may or may not specify a target. You might say "find me a route that goes through these places in any order", or "find me a route to any system with a research base". And there'd be weight adjustments, too. Give them similar freedom to the nav computer, but a little more point-and-click. If the basic hop count is 10, I might say "owned by pirates" = +10 (so I'm willing to go twice as far to avoid pirates), or "contains starfortress" = -3 (so I'm willing to take a slightly longer route if it contains a lot of starfortresses).
klauss
Elite
Elite
Posts: 7243
Joined: Mon Apr 18, 2005 2:40 pm
Location: LS87, Buenos Aires, República Argentina

Post by klauss »

You got it. Almost. I was thinking of a more graphical interface: you see the systems and the routes plotted, like "All the blue lines are the defined jumps, and all the yellow ones are the ones you could take to get to your destination". All the clutter would actually end up generating a graph like "See the yellow blob? Thats where you have to get through... any place in particular you want to go?". Then, the user clicks that system, and you delete all routes that don't go through that system.
Yeah, basically what you said, but in a graphical interface - more intuitive.
It would naturally separate those two main routes with secondary routes you were talking about: you would see two yellow blobs. You click on one, because you see interesting things in there (you would have to show that somehow - I have no idea there), and then the other routes suddenly disappear, and the user can concentrate on further refining the selection.

About the second paragraph. Be careful. Your wandering too close to the TSP, you don't want to go that way.
Oíd mortales, el grito sagrado...
Call me "Menes, lord of Cats"
Wing Commander Universe
Wisq
ISO Party Member
ISO Party Member
Posts: 453
Joined: Sat Jul 30, 2005 10:21 am

Post by Wisq »

The which now? Anyway, that's for down the road, if ever. Right now, I mostly just want a pathfinder that gives me alternate options. ... Well, actually, right now, I just want to avoid having to blindly pick one of several thousand routes. :)

I'd like to combine the graphical and textual methods, too. Like, when you're looking at the missions and trying to pick a route that lets you complete multiple ones at once, you really just want an alphabetical sector view (since the missions are all labelled by sector). On the other hand, if you're eyeballing a course, you really just want to click on the map. So obviously, either one should be a valid way to narrow the paths.

So far, I'm surprised the engine can actually maintain 50k courses in memory and draw them all without any visible slowdowns except in the initial discovery phase. Perl/TK's done me well this time, as it did for vsnav.
Alterscape
Merchant
Merchant
Posts: 35
Joined: Tue Sep 27, 2005 12:08 am

Post by Alterscape »

Is there a way to extract the range between jump points in each system, and more importantly of any major obstructions (planets, the sun, etc) requiring additional time/navigation? I realize that with SPEC the added time is minimal, but maneuvering around gravity wells and losing speed can be a pain. If so, that might be a useful contributor to the weighting of each leg of the trip...
Halleck
Elite
Elite
Posts: 1832
Joined: Sat Jan 15, 2005 10:21 pm
Location: State of Denial
Contact:

Post by Halleck »

I'm under the impression that VS stores very basic information about all systems, and when they are visited for the first time, they are fully plotted in 3D. As such, I'm not sure that you could tell exactly what the distance between jump points is unless the user had already visited that system once before.

And still, there are considerations to be made about intersecting objects and object positioning... jump points orbit and therefore change position, and paths actually take much longer if you have to go around a planet to get there, as you mentioned.

With all these considerations in mind, I don't think that it would be very feasible to take the interior structure of systems into account.
Wisq
ISO Party Member
ISO Party Member
Posts: 453
Joined: Sat Jul 30, 2005 10:21 am

Post by Wisq »

Certainly not feasible for me, anyway. At least, not immediately, given my relatively limited math background. And even if I could figure out the time between points, there comes the issue of how to factor that into the weight of the trip; some ships want to avoid high-traffic areas as much as possible (i.e. jump points) and get there in as few jumps as possible, while others want close jump points but can easily dodge planets and the like, while still others can't afford to go anywhere near a planet, etc.

What I eventually settled on was my original detour concept. I plot all the routes and list the shortest (to a certain maximum, currently 10). Then the 'detour' button lists all the involved sectors, with number of paths and the shortest of those paths -- except those sectors that wouldn't reduce the path count, i.e. bottleneck systems and and system you've already "detour"ed on. Each time you do this, it reduces the number of paths. Eventually, you're left with either a small list of the only paths that match your criteria, or a large list but you just pick the shortest one anyway.

Other factors, like faction, etc., can come later. For now, I want to focus on making the whole thing easier to use... for example, the lack of keyboard shortcuts in vsnav always bugged me. Also, selecting your systems by Sector -> System is fine for reaching Sol/Sol or Crucible/Cephid 17, but a PITA for reaching a system you only know by name (e.g. from your mission briefing). So I had to use "Find System"... and I hated not being able to just hit "N" to get to the first N-named system, nor even be able to use pgup-pgdown to scroll fast without missing stuff like with the mouse.

Once usability is where I want it, I'll see about a release.
fizze
Confed Special Operative
Confed Special Operative
Posts: 299
Joined: Wed Mar 24, 2004 3:35 pm
Location: Austria
Contact:

Post by fizze »

wow, yes. usuability is weird, in vsnav.
but other than that, I have always liked it, once I got used to it.

as for your problems about pathfinding:

there is no "cheap" solution other than the dijkstra.its a n^n problem. blast.

I would have to have a look at the VSnac source to talk about easy (read: feasable) optimizations / changes.
Wisq
ISO Party Member
ISO Party Member
Posts: 453
Joined: Sat Jul 30, 2005 10:21 am

Post by Wisq »

A* is a modified Dijkstra that uses a heuristic to determine the best places to search next. This is what I use.

The ideal or "perfect" heuristic would be one that perfectly calculates the distance, d, between the point in question and the target. This would allow the algorithm to find the target in almost no work at all, because at every step, it automatically knows which hop to try next. Realistically, you're unlikely to have a perfect heuristic, because that would probably imply you already know how to get there.

A heuristic that gives a value greater than d (overestimates the trip length) will work just as fast, but is not "admissible" -- it may not be the fastest. This is a speed-versus-accuracy trade-off.

A heuristic that gives a value less than d (underestimates the trip length) is most common. You will still find the best path faster than Dijkstra's, unless your heuristic is so incorrect as to be actually misleading.

A heuristic that always returns the same value makes the heuristic meaningless, and the algorithm identical to Dijkstra's.

I use A* with (severe) underestimation. All I need to do is make my heuristic better, probably using some precalculation. But as it stands, pathfinding is actually decently fast. It's showing the results to the user in a meaningful way that presented me with a problem, and that's mostly solved now.
klauss
Elite
Elite
Posts: 7243
Joined: Mon Apr 18, 2005 2:40 pm
Location: LS87, Buenos Aires, República Argentina

Post by klauss »

Wisq wrote:The which now?
Wow, sorry. I never answered that, I thought I had.
TSP = Travelling Salesman Problem.

It's an open problem, or a hard one. That is, the only known solution is exponential (very bad), and noone can prove that's the best solution. And it's the flagship of the NP-Hard class - it can't get any harder than that.

There are very good heuristics, though. You may want to google up TSP (or Travelling Salesman Problem), you may find nice heuristics that could be useful to you.
Oíd mortales, el grito sagrado...
Call me "Menes, lord of Cats"
Wing Commander Universe
Wisq
ISO Party Member
ISO Party Member
Posts: 453
Joined: Sat Jul 30, 2005 10:21 am

Post by Wisq »

Ah, yes, familiar with that, just didn't recognise it by the acronym. I'll look at some of the solutions for that, yes.

So far, pathfinding has gone pretty well, though it can take a lot of memory and stuff. Making a better heuristic will help. Of course, when there really are some tens of thousands of paths, there's not much I can do about that except store things more efficiently.
tripintraveler
Merchant
Merchant
Posts: 62
Joined: Mon Feb 21, 2005 1:35 pm
Location: Cloaked, and Watching
Contact:

Post by tripintraveler »

So ... does Anyone have an Idea of why VSNav's "assets" dont work?? ...
and if so how to possibly fix it????
Get in, Sit Down, Shut Up and Hang On, .. We're Going For A Ride
Wisq
ISO Party Member
ISO Party Member
Posts: 453
Joined: Sat Jul 30, 2005 10:21 am

Post by Wisq »

It was designed for an older version of the savefiles, that's why. The author has been away for a while, so there's little hope of getting it fixed in vsnav proper.

I could try to get a working version in my own tool, but I haven't even worked on my own one for a while now. I'll get back to it when I start playing VS again. This will definitely happen after the Ogre thing is in (gotta see them new graphics), but might happen sooner if I run out of other hobbies. :)

Note that my primary goal at that point will be to work out the remaining release-critical issues and get the thing out there, first and foremost. New features come after that and are lower priority.

(Frankly, I'm not even sure what that part of vsnav ever did. I've never seen it in action. Anyone know? I'll have to spend some time examining the code otherwise.)
prestidigitator
Mercenary
Mercenary
Posts: 123
Joined: Sat Apr 22, 2006 8:54 pm
Location: California, USA

Post by prestidigitator »

Halleck wrote:I'm under the impression that VS stores very basic information about all systems, and when they are visited for the first time, they are fully plotted in 3D. As such, I'm not sure that you could tell exactly what the distance between jump points is unless the user had already visited that system once before.

And still, there are considerations to be made about intersecting objects and object positioning... jump points orbit and therefore change position, and paths actually take much longer if you have to go around a planet to get there, as you mentioned.

With all these considerations in mind, I don't think that it would be very feasible to take the interior structure of systems into account.
Actually it should be feasible if you just assign a default weight where no real data is available. So if you have never visited a system, it is simply assigned some reasonable, "average," weight for the paths, or maybe a pretty costly weight (could be a preference, I suppose).

The key would be that the start, destination, jump points, and any intermediate stops on the way (planets, stations, etc.) would become the nodes of the graph, and now the actual in-system routes would become the edges (now with definite weights, so the algorithm requirements will increase). Also, if there are S systems and N jump points, the current graph should have O(S) nodes and O(N) edges. Taking into consideration the routes through each system would change this to O(N) nodes and something like O(N^2/S) edges assuming there are roughly O(N/S) jump points per system. This will likely increase the size of the problem significantly (I don't really know how big the VS universe is, but obviously N>S by quite a bit).
Halleck
Elite
Elite
Posts: 1832
Joined: Sat Jan 15, 2005 10:21 pm
Location: State of Denial
Contact:

Post by Halleck »

I think it would be too much trouble to be worth the effort, especially having to recalculate paths as jump points and planets move in orbit.
prestidigitator
Mercenary
Mercenary
Posts: 123
Joined: Sat Apr 22, 2006 8:54 pm
Location: California, USA

Post by prestidigitator »

Most likely, yes. It would be pretty costly in terms of both development effort and performance, I think.
tripintraveler
Merchant
Merchant
Posts: 62
Joined: Mon Feb 21, 2005 1:35 pm
Location: Cloaked, and Watching
Contact:

Post by tripintraveler »

{{wisq wrote Frankly, I'm not even sure what that part of vsnav ever did. I've never seen it in action. Anyone know? I'll have to spend some time examining the code otherwise }} .. it was a simple interface that let you select What it was your looking for (star fortress, commerce center, mining base, ect) and gave a simple list of systems that Had those objects in them, along with a route to get there, ... saved a Boat load of time from weandering around going "where the heck is a star fortress when you need one?" which to me actually seems logical in a universe of privateers and commerce you would think that if a base was "open for business" then there would be some common knowledge of Where they were, who was offering what, and so on. to which end vsnav filled that void beutifully, (before the savegame file issue broke it) :( ive been looking through and trying most all of the other navigation utilities around, but for ploting a route (in simplest terms) i still use vs-nav (broken or not)
Get in, Sit Down, Shut Up and Hang On, .. We're Going For A Ride
Post Reply