Djkstra's Pathfinding in QBASIC 4.5

[TheIronPainter]

Hello, I'm new to the forum so be gentle.

I have chosen QuickBasic 4.5 as my programming language. Now before you all moan and groan hear me out.

I started programming at 12 and QBasic was what I learned on. For years and years I made tid-bits of games for Qbasic but never followed through. I now want to prove to myself and the world that you CAN make a decent Roguelike in this language even if it cannot come close to the complexity of a C# or C++ game.

Anyway... my real question is that I am converting the Djkstra's pathfinding pseudo-code into Qbasic but I ran into a problem. The step is here:

3.) If the successor doesn't exist on either the OPEN list or the CLOSED list, add it to the OPEN list.

We're fine.... but further...

Otherwise, if the successor's movement cost is lower than the movement cost of the same tile on one of the lists, delete the occurrences of the successor from the lists and add the successor to the OPEN list.

Problem!

I A.) Don't know what that means exactly, and B.) Have a problem deleting from my lists because instead of pointer stacks they are arrays (since qbasic doesn't use pointers)

I have samples of code for anybody that are commented out the ying yang if anybody cares to help me out.

Thanks in advance

[konijn_]

Greetings,

This list of not very coherent thoughts popped up :

 * I understand your quest, but it might get rough
 * What OS are you running, where did you even find the binary ?
 * I did once the same, the problem for me was the limit of code you can have and the size-limit of arrays :
http://www.qbasicnews.com/qboho/qckadvr@l8206.shtml

For your particular question, it should be relatively easy to build a subroutine where you pass the array and the index of the element to remove.
You then rebuild a new array from the old array, leaving out that one index..
Or ( bad idea given how limited your memory is ) you could set the value to -1 or something that means 'this element is deleted'

T.

[requerent]

Otherwise, if the successor's movement cost is lower than the movement cost of the same tile on one of the lists, delete the occurrences of the successor from the lists and add the successor to the OPEN list.

Okay-- I don't like this OPEN and CLOSED business, but basically you've got your connected graph. The Dijsktra's traversal always takes the shortest total path to get to nodes.

The order of nodes on the frontier corresponds to the distance from the origin. All that quote is saying is that if a node already exists on the frontier but a shorter path is found, ditch the original and add the new one. I don't like that wording though-- you should be updating the known distance.

We have an array that stores the distance from origin to each node. Since we don't know the total distance, we set each node's distance to default at infinity (or max integer), with the origin at 0. We know what nodes connect to origin, so we update total distances of each node.

We then have an array of booleans that stores whether we've visited a node or not. Nodes that have a non-infinite distance but have yet to be visited are on the 'frontier.' We take the node with the smallest distance on the frontier and visit it, updating the distances of each node visited. If a node already has a distance, we need to replace it with the new one if it is shorter.

Dijsktra's never needs to think about nodes that are already visited. Once visited, their distance is never changed.

[Ancient]

Not directly related but there is a tiny fun roguelike in FreeBASIC. About time

That said problem B can be solved by shifting the arrays or making a pass similar to what FreePascal does. FP implements lists as arrays.

To delete X elements from the list do the following:

Pass through the list maintaining two variables: current position and number of deleted elements.

1. Set position to first element and deleted to zero.

2. If you stumble on a element to be kept, copy it to list position [position - deleted]. Until you have deleted something this will overwrite elements with themselves -- in other words do nothing.

3. If you stumble on a element to be deleted increase deleted by one.

4. Increase position by one.

5. Loop to step 2 if you have not reached end of the list yet.

The effect will be copying elements 1 to 1, 2 to 2, 3 to 3. Lets say element 4 you want deleted. In point 2. nothing is done. Point 3. assures copying will be shifted from now on. So copying continues with element 5 to 4, 6 to 5 etc. After the pass finishes you need to subtract deleted from number of elements in your list. Done!

For problem A I need more detailed explanation from you to really be able to help.

[jocke the beast]

Fellow basic-coder! I urge you to check out the http://freebasic.net/forum. Trafficed and helpfull coders.
http://www.freebasic.net/forum/viewtopic.php?f=15&t=9952&hilit=Pathfinding covers a pretty good A*pathfinding example...
Good luck!

[TheIronPainter]

Wow... I was not expecting the kind replies like this. A great thanks is in order. Thanks!

You all have solved my problem, in one way or another. And I greatly appreciate the clarification of the pseudo-code as well as a good delete alternative for non-pointered stacks. Already converted and implemented!

What I have feared is happening, however. I have a 40kb program before combat and sound... perhaps it is just time to tuck tail and convert it all to C++. The last thing I want to do is keep putting more time into this project and then get held back at the last second by a measly few kbs of code.

To answer a few other questions. I don't have the binary, and I'm running in the emulated console DosBox. I like DosBox because you can crank up the frame-rate making an already slow Qbasic program run almost as if it were programmed by a better programmer 

In the next few coming months I look forward to sharing with you all my version of a roguelike I have been wanting to program for AGES... thankfully none of you have thought about the idea yet so I'm eager to implement and be the first! It was a good fight but I think I've reached my limit with QBasic 4.5....

*sigh*

[jocke the beast]

What I have feared is happening, however. I have a 40kb program before combat and sound... perhaps it is just time to tuck tail and convert it all to C++. The last thing I want to do is keep putting more time into this project and then get held back at the last second by a measly few kbs of code.

Why not give Freebasic a try. If you're used to Qbasic 4.5 it's really simple to start using Freebasic. Same thing but better/faster/stronger 
Anyway you choose, good luck man!!!!

[Ancient]

Yes, good luck and don't forget to tell us when you have something for us to try!

Like Jocke says try Free BASIC first. C++ is not magic pixie dust (no programming language is) and trying out something familiar before you go check out other stuff is good idea.

[TheIronPainter]

You have made somebody really happy and for that I thank you Jocke. Already chugging away now under the new editor, FBIde. Happy they even have a "borland" graphics theme.

For YEARS I always had the desire to build a respectable QBASIC game even without objects, etc... call it a touch of nostalgia, call it what you will. I mean, let's face it, GW-BASIC has a place in history, however small.

If I have any further questions (which I will) should I append them to this subject or start a new thread. As I am new to the forum I don't want to be that guy, we all know who 'that guy' is, who doesn't play by the rules and invariably becomes a pest.

Thanks again, really.

One question. Whenever I load an old .bas file I get a blank screen with "ü" on line 1 and nothing else...

[jocke the beast]

Hmm... Is the old .bas file saved usling Qbasic 4.5 or a texteditor? If u saved it using Qbasic you might saved it as ansi. Try open the .bas in a texteditor save it there.

Btw, now while you use freebasic I strongly suggest you to check out this great roguelike tutorial made by Rick Clark. Covers the most from dungeon generation,LOS, items, melee, ranger attacks, magic, shops etc.

http://users.freebasic-portal.de/rdc/tutorials.html

Good luck!!!

[TheIronPainter]

Jocke,

Got it to work. Thanks a ton. I'm having some cross-over problems though.

Here is a small sample of code. Hopefully.

I am having scope issues that I never had in QuickBasic 4.5...  for some reason the array Map$ is not getting translated to either of the sub-routines... I have no idea what's the problem other than a potential FreeBASIC related issue. Thanks,

'$lang: "fblite"

''----------------Program Initialization-------------------------
CLS
SCREEN 18, 32
WIDTH 80, 60
RANDOMIZE TIMER

''-----------------Cavern Subroutines----------------------------

DECLARE SUB CavernInit
DECLARE SUB FirstCavernRoomInit
DECLARE SUB BuildCavern(RoomCenterX as Integer, RoomCenterY as Integer, RoomWidth as Integer, RoomHeight as Integer)

''-----------------Map-Related Subroutines-----------------------

DECLARE SUB PrintTile(X as Integer, Y as Integer)

''-------------Map-Related Variable Declarations-----------------

DIM SHARED Map$()   'The main dungeon map
DIM SHARED Item$()  'The main "item" map
DIM SHARED Monster$() 'The main "monster" map


DIM Shared MaxScreenWidth = 50
DIM Shared MaxScreenHeight = 50
ReDIM Map$(1 to MaxScreenWidth, 1 to MaxScreenHeight)
ReDIM Item$(1 to MaxScreenWidth, 1 to MaxScreenHeight)

''---------------------------------------------------------------

''XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
''X                     MAIN PROGRAM MODULE                     X
''XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


''----------------Fill the whole map in with rock----------------

CavernInit
sleep

FirstCavernRoomInit
sleep



'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
'/ Fill the entire map in with solid rock     \
'----------------------------------------------
'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

SUB CavernInit
   
FOR X = 1 TO MaxScreenWIDTH
   FOR Y = 1 TO MaxScreenHEIGHT
      Map$(X, Y) = "0"     
   NEXT Y
NEXT X

FOR X = 1 TO MaxScreenWIDTH
   FOR Y = 1 TO MaxScreenHEIGHT
      Item$(X, Y) = "0"
   NEXT Y
NEXT X

END SUB


SUB FirstCavernRoomInit

'-----------------Randomly determine the room size------------------

RoomWIDTH = INT(RND * 3) + 1
RoomHEIGHT = INT(RND * 3) + 1


RoomCenterX = MaxScreenWIDTH / 2     
RoomCenterY = MaxScreenHEIGHT / 2   

Map$(RoomCenterX, RoomCenterY) = "1"

'-----------------Dig out the first room from the rock--------------

BuildCavern (RoomCenterX, RoomCenterY, RoomWIDTH, RoomHEIGHT)

END SUB


SUB BuildCavern (RoomCenterX, RoomCenterY, RoomWIDTH, RoomHEIGHT)

'-----------------FIRST FILL IN THE FLOORING------------------------------

FOR X = (RoomCenterX - RoomWIDTH) TO (RoomCenterX + RoomWIDTH)
   FOR Y = (RoomCenterY + -RoomHEIGHT) TO (RoomCenterY + RoomHEIGHT)
      Map$(X, Y) = "·"     
      PrintTile X, Y
   NEXT Y
NEXT X

'-----------------NOW FILL IN THE WALLS-----------------------------------

'-----------------MAKE THE RIGHT WALL-------------------------------------
X = RoomCenterX + RoomWIDTH + 1
FOR Y = (RoomCenterY - RoomHEIGHT - 1) TO (RoomCenterY + RoomHEIGHT + 1)
   Map$(X, Y) = "#"
   PrintTile X, Y
NEXT Y

'-----------------MAKE THE LEFT WALL--------------------------------------
X = RoomCenterX - RoomWIDTH - 1
FOR Y = (RoomCenterY - RoomHEIGHT - 1) TO (RoomCenterY + RoomHEIGHT + 1)
   Map$(X, Y) = "#"
   PrintTile X, Y
NEXT Y

'-----------------MAKE THE BOTTOM WALL------------------------------------
Y = RoomCenterY + RoomHEIGHT + 1
FOR X = (RoomCenterX - RoomWIDTH - 1) TO (RoomCenterX + RoomWIDTH + 1)
   Map$(X, Y) = "#"
   PrintTile X, Y
NEXT X

'-----------------MAKE THE TOP WALL---------------------------------------
Y = RoomCenterY - RoomHEIGHT - 1
FOR X = (RoomCenterX - RoomWIDTH - 1) TO (RoomCenterX + RoomWIDTH + 1)
   Map$(X, Y) = "#"
   PrintTile X, Y
NEXT X

END SUB


SUB PrintTile (X, Y)

IF Item$(X, Y) <> "0" THEN GOTO PrintItem  'If there is an item here print that
                                           'first.
SELECT CASE Map$(X, Y)

        CASE "#"                  'A stone wall
          COLOR 8
          LOCATE Y, X: PRINT "#"
       
        CASE "·"                  'A stone floor
          COLOR 15
          LOCATE Y, X: PRINT "·"
       
        CASE "+"                  'A stone door
          COLOR 7
          LOCATE Y, X: PRINT "+"
       
        CASE ">"                  'Stairs Down
          COLOR 7
          LOCATE Y, X: PRINT ">"

        CASE "<"                  'Stairs Up
          COLOR 7
          LOCATE Y, X: PRINT "<"

        CASE "þ"                  'Wooden Crate
          COLOR 6
          LOCATE Y, X: PRINT "þ"
       
        CASE "_"                  'Spawn Portal
          COLOR 13
          LOCATE Y, X: PRINT "_"

        CASE "$"                  'Gold Coins
          COLOR 14
          LOCATE Y, X: PRINT "$"

        CASE "-"
          COLOR 7
          LOCATE Y, X: PRINT "-"  'Open Up/Down Stone Door

        CASE "/"
          COLOR 7
          LOCATE Y, X: PRINT "/"  'Open Right/Left Stone Door
     
        CASE "3"
          COLOR 8, 2
          LOCATE Y, X: PRINT "²"  'Mossy Wall

        CASE "'"
          COLOR 2
          LOCATE Y, X: PRINT "ú"   'Mossy floor

        CASE ELSE

END SELECT
COLOR 0, 0

PrintItem:
SELECT CASE Item$(X, Y)

        CASE "c"                  'A wooden crate
          COLOR 6
          LOCATE Y, X: PRINT "þ"
     
        CASE "$"                  'Gold Coins
          COLOR 14
          LOCATE Y, X: PRINT "$"

END SELECT
COLOR 0, 0
END SUB

[guest509]

  I keep kicking around the idea of making a game in Turbo Pascal...those were the days!

[TheIronPainter]

Nostalgia... it gets the best of us 

[Ancient]

Here is a small sample of code. Hopefully.

I am having scope issues that I never had in QuickBasic 4.5...  for some reason the array Map$ is not getting translated to either of the sub-routines... I have no idea what's the problem other than a potential FreeBASIC related issue. Thanks,

I had a look today. After installing fbc your program compiles and displays a randomized size room. I wondered whats wrong until I tried to execute the program in a terminal under graphical environment. True Linux console has properties of DOS console which allows your program to perform adequately. To have it working in xterm I had to comment out your SCREEN statement. It worked but without color. The Map$ is handed over properly. The problem is in screen handling. I think you need to feed other values to SCREEN and everything should start to work.

Ah, in future please put code between [code] [/code] tags. It renders the text in monospace font.