# Letting an Pathfinding Algorithm generate movement paths for all possible Connections in a Starsystem-based Universe

First of all I want you to forgive me when I make mistakes in my writing, english isn't my first language, and also: If this is the wrong place to ask, please direct me to the right place then.

So, the Question above may be a bit long, but I will try to explain it a bit better: what im trying to do, is to write a program mainly in VB.Net which uses some kind of function or pathfinding algorithm to get the shortest paths from, lets say, System "A" to System "AY", which may or may not be pretty far away from each other.

The thing Im trying to achieve then is to make use of those generated paths, and convert them to an LUA Table, which would look like that: {"DESTINATION-SYSTEMNAME-HERE", "TARGET-SYSTEMNAME-HERE", {"SYSTEM1", "SYSTEM2"}}, where "SYSTEM1" and "SYSTEM2" are Systems inbetween the Destination and Targetsystem, and then to use those generated tables which hold all paths available in a modification, which I am creating for a game.

Here is a Picture of the Game World generated by a little program I wrote with the help of the Universe Map texture of the Game and an XML file which holds all System's x,y coordinates, their names and their Connections to each other. here: I only have this XML File which contains all the Connections of all Systems in the universe and also their X, Y coordinates on the Map: https://pastebin.com/K5dNdigU

One thing I still have to mention is, that it shouldn't matter for the Searching Algorithm how great the "distance" is visually, since the distance between each star on the Picture I posted is only visually there, but not really technically. The connections between those Systems are all connected by Portals which will teleporte something immediatley to the Destination one has chosen.

I will appreciate any kind of help one could give me, even greater so if the "help" is some sample code which I can implement in my program.

Here is my Code so far:

Private Function GetJumpList(ByVal StarSystem As String)
Dim StarDestinations As New ArrayList
Dim Connections As Integer = Data.XMLData(StarSystem & ":Connections")
For i = 1 To Connections Step 1
StarDestinations.Add(Data.XMLData(StarSystem & ":Connections:" & i))
Next
Return StarDestinations
End Function
Private Function ds_list_size(ByVal ArLst As ArrayList)
Dim size As Integer = (ArLst.Count - 1)
Return size
End Function

Dim jump_checklist As New ArrayList
Private Function JumpPath(ByVal CurrentStar As String, ByVal DestinationStar As String)
'///jumppath(current star, destination star)
'//this Is a recursive function that will find the SHORTEST path to a star
'//returns a list of the jump points to get to destination star from the current star
Dim c_star As String = CurrentStar '//current star
Dim d_star As String = DestinationStar '//destination star
Dim j_list As New ArrayList '//list of jump points to get to destination
Dim jumplist As ArrayList = GetJumpList(c_star) '//list of names of the neighboring starsystems
jump_checklist.Add(c_star)

'//Go through each of the jump points in the current system
For i = 0 To ds_list_size(jumplist) Step 1
Dim jp As String = jumplist(i)
'jp = System Neighbor (i)nth of c_star

'//this jump point goes straight to the destination, end our search
If (jp = d_star) Then
j_list.Clear() '//clear the path
j_list.Add(jp) '//add current jump point
Exit For

End If

'//this jump point doesn't go straight to the destination, search beyond
If jump_checklist.Contains(jp) = False Then '//make sure this jump point doesn't go to a previously visited system
Dim tj_list As New ArrayList

tj_list = JumpPath(jp, d_star)

'//the destination has been found
If (ds_list_size(tj_list) > 0) Then

'//if the New path Is smaller than previous paths Or Is the first path found
If ((ds_list_size(tj_list) + 1) < ds_list_size(j_list)) Or (ds_list_size(j_list) = 0) Then

j_list.Clear() '// clear the path
j_list.Add(jp) '//add current jump point

'//add all proceeding jump points
For j = 0 To ds_list_size(tj_list) Step 1
j_list.Add(tj_list(j))
Next

End If
End If
End If
Next
Return j_list

End Function

1. Note: The Function does its job if the destination -is- a neighbor, but if it isn't and it needs to look around some more, it will just find nothing, it won't end up in an endless loop, but it just returns a list which has nothing in it.

2. Note2: Data.XMLData is Dictionary which holds all the data from the xml file.

3. Note3: This was originally an GameMaker script which I have found on a forum, since it seemed very close to what I did seek, I hoped I could modify it and make use of it.

4. Note4: I have absolutely NO experience in Pathfinding Algorithms in any shape or form, and I only have limited knowledge in C# out of VB.Net and lua, and also 0 knowledge in C++.

5. Note5: I have tried to somehow implement A* Pathfinding or Dijkstra's Pathfinding, but it always results in just hours of agony and pain to get an Idea on how to implement this in such a way.

TL;DR: All I want is a Searching Algorithm/Function to get me the shortest path from lets say, "taira", to "x220", then Im fine. OR: Someone to point out whats wrong with the Function I've provided.

• This is called the all-pairs shortest paths problem. When your edges have non-negative lengths, running Dijkstra's Algorithm from each starting point is actually a pretty good way to solve it if your edges are sparse. If you have dense interconnections, then the Floyd-Warshall algorithm can be a better choice. If you can describe where you've run into trouble implementing these standard algorithms, we may be able to help you over that obstacle. – DMGregory Apr 19 '17 at 2:19
• I looked at the Floyd-Warshall algorithm, but it seems to also use "lengths", which are non-existent here, the systems here are simply "connected" with each other as seen in the xml file, I have no other resources other than that. A* and Dijkstras Method is just a bit too complex for this kind of simple task I think, there must be an alternative, right?. It can't possibly be that something that seems to simple at first evolves to such a cluster of a problem, atleast for me. – Nocalora Apr 19 '17 at 3:26
• Then every length is just one, no added complexity. You could even do this with n breadth-first search invocations. :) – DMGregory Apr 19 '17 at 3:28
• That works?, Im gonna try that when im at home, thanks for the tip! – Nocalora Apr 19 '17 at 3:30
• Im a bit baffled about the Floyd–Warshall Algorithm, I found an Implementation of it here "programmingalgorithms.com/algorithm/…" And there it seems to not really have a "Destination" or anything like that, excuse me if Im missing the obvious here, but I really have no experience in this, the thing which also bothers me a bit is how Exactly I go implementing my scenario here into a "graph" which like, for example: the FW Algorithm in that site uses in Example section. Dijkstra's also seems to use this kind of graph. – Nocalora Apr 19 '17 at 4:29