1
\$\begingroup\$

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:The Game World 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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – DMGregory Apr 19 '17 at 2:19
  • \$\begingroup\$ 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. \$\endgroup\$ – Nocalora Apr 19 '17 at 3:26
  • \$\begingroup\$ Then every length is just one, no added complexity. You could even do this with n breadth-first search invocations. :) \$\endgroup\$ – DMGregory Apr 19 '17 at 3:28
  • \$\begingroup\$ That works?, Im gonna try that when im at home, thanks for the tip! \$\endgroup\$ – Nocalora Apr 19 '17 at 3:30
  • \$\begingroup\$ 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. \$\endgroup\$ – Nocalora Apr 19 '17 at 4:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.