Announcement

Collapse
No announcement yet.

Shortest Path Problem - Conversion from QBasic to PBCC

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Shortest Path Problem - Conversion from QBasic to PBCC

    Hello all!

    I've been beating my head against this bit of code unsuccessfully and I'm hoping a fresh set of eyes might provide some insight. The end goal is to provide an adjacency matrix so the program could output the shortest path between two locations of an RPG, while also utilizing teleports.

    Remembering that there was some example code in my old copy of the Revolutionary Guide to QBasic, I started with that and compiled it with QB64 and it works beautifully and would serve my purpose perfectly. With a quick skim, I thought that it seemed easily converted to PBCC and I started out. I also included a picture of their graph, but it's already embedded in the source.

    The PBCC program compiles after my conversion, but the results are very wrong. Could someone review the attached code and compiled examples to correct whatever I've done incorrectly? I'm quite sure it's my lack of understanding to what the shortest path code is doing that contributes to this while converting. However, I'm at a point that I'd rather ask or even pay for the convenience of a solution versus learning to overcome it myself.
    Attached Files
    Donnie Ewald
    [email protected]

  • #2
    For a start, this does not do a sequential READ$ through the DATA:
    matrix(x,y) = VAL(READ$(x*y))
    Try
    Code:
    LOCAL x AS INTEGER
    ...
    INCR z
    matrix(x,y) = VAL(READ$(z))
    But that's not the only issue

    Comment


    • #3
      Don't know why you changed this since I don't have the book::
      Code:
      'XY.X = NumberEnd 'Initializing the first step
      XY.X = NumberBegin 'Initializing the first step. This change is based on text in the book.
      but the original works (once you correct the matrix load)
      Code:
      XY.X = NumberEnd 'Initializing the first step

      Comment


      • #4
        Much thanks Stuart! I've incorporated your edits and you're absolutely right; it's working beautifully!
        Donnie Ewald
        [email protected]

        Comment


        • #5
          Just downloaded the zip to take a look, but haven't gotten into the code yet.

          Looking at the files, I had to chuckle: the QB exe is 2.1MB, whereas the PB exe is 20K... a factor of 100 times smaller!

          Happy Thanksgiving, all y'all!
          -John

          Comment


          • #6
            Originally posted by John Montenigro View Post
            Just downloaded the zip to take a look, but haven't gotten into the code yet.

            Looking at the files, I had to chuckle: the QB exe is 2.1MB, whereas the PB exe is 20K... a factor of 100 times smaller!

            Happy Thanksgiving, all y'all!
            -John
            Didn't notice the QB exe size, but yep, that would be typical

            (And the code takes a bit of time to digest - it's QB roots are obvious. I'm thinking that when I get a bit of spare time, I'd like to re-factor it for PB.
            It's not actually a "shortest path" algorithm since it assumes all edges are the same length. )

            If you're inetersted in the wider aspects of "shortest path", here's a good reference:

            https://www.freecodecamp.org/news/di...-introduction/

            Comment


            • #7
              Yep, though it was easy to compile with QB64, it doesn't result in a very small executable. I don't have QB45 handy to check it's compiled size, but if you use PDS71 to compile the program it's size is 35.7k which is still larger than the PBCC executable.

              There is an implementation by Daniel Penney of A* for pathfinding, but my brain wasn't understanding how I could translate the RPG map of locations that had adjacent nodes but also teleports to far flung nodes. With this QB code, I can create an array of all of these locations and view them as adjacent even though they're not physically nearby due to teleports.
              Donnie Ewald
              [email protected]

              Comment

              Working...
              X