Microsoft Small Basic

Program Listing: DSM444

List Program

' Parallel execution of Tremaux's algorithm
' Stevan Tosic
' 26/05/2020
' Turtle is replaced as tryhest proposed in KRX737 (turtleMove and initTurtle here)
mazeTable[1][1] = "XOXXXOXXXXXX"
mazeTable[1][2] = "X X O"
mazeTable[1][3] = "X XXXXX X X"
mazeTable[1][4] = "X X "
mazeTable[1][5] = "XXX X X X X"
mazeTable[1][6] = "O X X"
mazeTable[1][7] = "X XXXXXXX X"
mazeTable[1][8] = "X X X OX"
mazeTable[1][9] = "X X X X XXX"
mazeTable[1][10] = "X X X X"
mazeTable[1][11] = "XXXXX XXXXX"

mazeTable[2][1] = "XOXXXOXXXXXX"
mazeTable[2][2] = "X X O"
mazeTable[2][3] = "XXXOXX X XX"
mazeTable[2][4] = "X X "
mazeTable[2][5] = "XXX X X X "
mazeTable[2][6] = "X X "
mazeTable[2][7] = "X XXX XX X"
mazeTable[2][8] = "X X X XX"
mazeTable[2][9] = "X X X XXX"
mazeTable[2][10] = "X X XO X"
mazeTable[2][11] = "XXXXX XXXXX"

mazeTable[3][1] = "XXXXXOXXXXX"
mazeTable[3][2] = "X X "
mazeTable[3][3] = "XXXOXX X X"
mazeTable[3][4] = "X X "
mazeTable[3][5] = "XXX X X X "
mazeTable[3][6] = "O X "
mazeTable[3][7] = "X XXXX XX X"
mazeTable[3][8] = "X X OX"
mazeTable[3][9] = "X X X XXX"
mazeTable[3][10] = "X X X X"
mazeTable[3][11] = "XXXXX XXXXX"

initVariables()
initRooms()

While(aliveSearch[1] = "True" Or aliveSearch[2] = "True" Or aliveSearch[3] = "True")
For room = 1 To numRooms
search()
EndFor
Program.Delay(20)
EndWhile

TextWindow.WriteLine("That's all!")

Sub initTurtle
tpenup[room] = "False"
trt[room]=Shapes.AddTriangle(0 0 10 30, -10 30)
LDShapes.BrushColour(trt[room] "lime")
LDShapes.PenColour(trt[room] "black")
LDShapes.PenWidth(trt[room] 1)
LDEffect.DropShadow(trt[room] "")

turtlePath[room]["X"][1] = 6
turtlePath[room]["Y"][1] = 11

turtleX[room] = turtlePath[room]["X"][1] * cellSize + cellSize/2 + tableOffsetX[room] * cellSize
turtleY[room] = turtlePath[room]["Y"][1] * cellSize + cellSize/2
EndSub

Sub turtleMove'---------- turtle replacement sub--------
rrs=LDMath.Convert2Cartesian(turtleX[room] turtleY[room] args[1] angle[room]-90)
If tpenup[room] Then
Else
Shapes.AddLine(turtleX[room] turtleY[room] rrs[1] rrs[2])
EndIf
turtleX[room]=rrs[1]
turtleY[room]=rrs[2]
LDShapes.ZIndex(trt[room] 1111)
Shapes.Rotate(trt[room] angle[room])
Shapes.move(trt[room] turtleX[room] turtleY[room])
EndSub

Sub search
If(aliveSearch[room] = "True") Then
If(isFree[room] = "True") Then
stepCounter[room] = stepCounter[room] + 1
If(direction[room] = dirSouth) Then
searchState[room] = "S01"
goSouth()
ElseIf(direction[room] = dirEast) Then
searchState[room] = "E01"
goEast()
ElseIf(direction[room] = dirNorth) Then
searchState[room] = "N01"
goNorth()
Else
searchState[room] = "W01"
goWest()
EndIf
Else
isFree[room] = "True"
If(searchState[room] = "S01") Then
searchState[room] = "S02"
angle[room] = angle[room] - 90
goEast()
ElseIf(searchState[room] = "S02") Then
searchState[room] = "S03"
angle[room] = angle[room] + 90
angle[room] = angle[room] + 90
goWest()
ElseIf(searchState[room] = "S03") Then
angle[room] = angle[room] - 90
stepCounter[room] = stepCounter[room] - 1
returnFromDeadEnd()
ElseIf(searchState[room] = "E01") Then
searchState[room] = "E02"
angle[room] = angle[room] + 90
goSouth()
ElseIf(searchState[room] = "E02") Then
searchState[room] = "E03"
angle[room] = angle[room] - 90
angle[room] = angle[room] - 90
goNorth()
ElseIf(searchState[room] = "E03") Then
angle[room] = angle[room] + 90
stepCounter[room] = stepCounter[room] - 1
returnFromDeadEnd()
ElseIf(searchState[room] = "N01") Then
searchState[room] = "N02"
angle[room] = angle[room] + 90
goEast()
ElseIf(searchState[room] = "N02") Then
searchState[room] = "N03"
angle[room] = angle[room] - 90
angle[room] = angle[room] - 90
goWest()
ElseIf(searchState[room] = "N03") Then
angle[room] = angle[room] + 90
stepCounter[room] = stepCounter[room] - 1
returnFromDeadEnd()
ElseIf(searchState[room] = "W01") Then
searchState[room] = "W02"
angle[room] = angle[room] - 90
goSouth()
ElseIf(searchState[room] = "W02") Then
searchState[room] = "W03"
angle[room] = angle[room] + 90
angle[room] = angle[room] + 90
goNorth()
ElseIf(searchState[room] = "W03") Then
angle[room] = angle[room] - 90
stepCounter[room] = stepCounter[room] - 1
returnFromDeadEnd()
EndIf
EndIf
EndIf
EndSub

Sub Debug
TextWindow.WriteLine(x + ":(" + row + ", " + col + ")="+ tableState[room][row][col] + "; " + searchState[room] + " " + stepCounter[room])
TextWindow.Read()
EndSub

Sub toFieldIfFree
checkEdge()
checkUsedField()
checkWall()
checkSearchLimit()

If(isEdge[room]="False" And isWall[room] = "False" And isUsedField[room] = "False" And isSearchLimit[room] = "False") Then
LDCall.Function("turtleMove", cellSize)

s1 = "1=" + searchState[room] + ";2=" + dX[room] + ";3=" + dY[room]
Stack.PushValue(stacks[room], s1)
addUsedFieldToPath()
isFree[room] = "True"
Else
isFree[room] = "False"
EndIf
checkTarget()
EndSub

Sub goSouth
direction[room] = dirSouth
dY[room] = 1
dX[room] = 0
edgeCondition[room] = turtlePath[room]["Y"][stepCounter[room]] + dY[room] - numRow[room] - 1
toFieldIfFree()
EndSub

Sub goEast
direction[room] = dirEast
dX[room] = 1
dY[room] = 0
edgeCondition[room] = turtlePath[room]["X"][stepCounter[room]] + dX[room] - numColumn[room] - 1
toFieldIfFree()
EndSub

Sub goNorth
direction[room] = dirNorth
dY[room] = -1
dX[room] = 0
edgeCondition[room] = -(turtlePath[room]["Y"][stepCounter[room]] + dY[room])
toFieldIfFree()
EndSub

Sub goWest
direction[room] = dirWest
dX[room] = -1
dY[room] = 0
edgeCondition[room] = -(turtlePath[room]["X"][stepCounter[room]] + dX[room])
toFieldIfFree()
EndSub

Sub checkEdge
isEdge[room] ="True"
If(edgeCondition[room] < 0) Then
isEdge[room] = "False"
EndIf
EndSub

Sub checkSearchLimit
isSearchLimit[room] = "False"
If(stepCounter[room] = depthSearchLimit[room]) Then
isSearchLimit[room] = "True"
EndIf
EndSub

Sub returnFromDeadEnd
If stepCounter[room] > 0 Then

row = turtlePath[room]["Y"][stepCounter[room]+1]
col = turtlePath[room]["X"][stepCounter[room]+1]

tableState[room][row][col] = charUsedField
LDCall.Function("turtleMove", -cellSize)

s1 = Stack.PopValue(stacks[room])
searchState[room] = s1[1]
Else
aliveSearch[room] = "False"
TextWindow.WriteLine("Room" + room + " end.")
EndIf
isFree[room] = "False"
EndSub

Sub addUsedFieldToPath
turtlePath[room]["Y"][stepCounter[room] + 1] = turtlePath[room]["Y"][stepCounter[room]] + dY[room]
turtlePath[room]["X"][stepCounter[room] + 1] = turtlePath[room]["X"][stepCounter[room]] + dX[room]
EndSub

Sub checkUsedField
isUsedField[room] = "False"

row = turtlePath[room]["Y"][stepCounter[room]] + dY[room]
col = turtlePath[room]["X"][stepCounter[room]] + dX[room]

If(tableState[room][row][col] = charUsedField) Then
isUsedField[room] = "True"
Else
col = turtlePath[room]["X"][stepCounter[room]]
row = turtlePath[room]["Y"][stepCounter[room]]
tableState[room][row][col] = charUsedField
EndIf
EndSub

Sub checkWall
isWall[room] = "False"

row = turtlePath[room]["Y"][stepCounter[room]] + dY[room]
col = turtlePath[room]["X"][stepCounter[room]] + dX[room]

If(tableState[room][row][col] = charWall) Then
isWall[room] = "True"
EndIf

EndSub

Sub setTargetColor
GraphicsWindow.BrushColor = colorMarkedTarget
tx = targets[room]["X"][i]
ty = targets[room]["Y"][i]
cellTable = Shapes.AddRectangle(cellSize, cellSize)
Shapes.Move(cellTable, tx * cellSize + tableOffsetX[room] * cellSize, ty * cellSize)
EndSub

Sub checkTarget
For i=1 To numTarget[room]
If(turtlePath[room]["X"][stepCounter[room]] = targets[room]["X"][i] And turtlePath[room]["Y"][stepCounter[room]] = targets[room]["Y"][i]) Then
setTargetColor()
EndIf
EndFor
EndSub

Sub writeLimitedturtlePath
TextWindow.Write(msgEnd)
For i = 1 To depthSearchLimit[room]
TextWindow.Write(" " + turtlePath[room]["Y"][i] + "," + turtlePath[room]["X"][i] + " ")
EndFor
TextWindow.WriteLine("")
TextWindow.WriteLine("********")
EndSub

Sub setWallField
tableState[room][row][col] = charWall
EndSub

Sub setTarget
tableState[room][row][col] = charTarget
EndSub

Sub setFreeField
tableState[room][row][col] = charFreeField
EndSub

Sub addTargetXY
targets[room]["Y"][numTarget[room]] = row
targets[room]["X"][numTarget[room]] = col
EndSub

Sub readTableFromFile
row = 1
' The following line could be harmful and has been automatically commented.
' line = File.ReadLine(fileName, row)
numTarget[room]=0
maxCol = 0
While(line <> "")
numColumn[room] = Text.GetLength(line)
For col=1 To numColumn[room]
char = Text.GetSubText(line,col,1)
charCode = Text.GetCharacterCode(char)

If(charCode = asciiWall) Then
setWallField()
ElseIf(charCode = asciiTarget) Then
setTarget()
numTarget[room] = numTarget[room] + 1
addTargetXY()
Else
setFreeField()
EndIf
EndFor

If(numColumn[room] > maxCol) Then
maxCol = numColumn[room]
EndIf

row = row + 1
' The following line could be harmful and has been automatically commented.
' line = File.ReadLine(fileName, row)

numRow[room] = row - 1
EndWhile
numColumn[room] = maxCol
tableOffsetX[room+1] = tableOffsetX[room] + 1 + numColumn[room]
EndSub

Sub readTable
row = 1
line = mazeTable[room][row]
numTarget[room]=0
maxCol = 0

While(row <= Array.GetItemCount(mazeTable[room]))
numColumn[room] = Text.GetLength(line)
For col=1 To numColumn[room]
char = Text.GetSubText(line,col,1)
If(char = charWall) Then
setWallField()
ElseIf(char = charTarget) Then
setTarget()
numTarget[room] = numTarget[room] + 1
addTargetXY()
Else
setFreeField()
EndIf
EndFor

If(numColumn[room] > maxCol) Then
maxCol = numColumn[room]
EndIf

row = row + 1
line = mazeTable[room][row]

numRow[room] = row - 1
EndWhile

numColumn[room] = maxCol
tableOffsetX[room+1] = tableOffsetX[room] + 1 + numColumn[room]
EndSub

Sub drawTable
For y = 1 To numRow[room]
For x = 1 To numColumn[room]
If(tableState[room][y][x] = charWall) Then
GraphicsWindow.BrushColor = colorWall
cellTable = Shapes.AddRectangle(cellSize, cellSize)
Shapes.Move(cellTable, x * cellSize + tableOffsetX[room] * cellSize, y * cellSize)
ElseIf(tableState[room][y][x] = charTarget) Then
GraphicsWindow.BrushColor = colorTarget
cellTable = Shapes.AddRectangle(cellSize, cellSize)
Shapes.Move(cellTable, x * cellSize + tableOffsetX[room] * cellSize, y * cellSize)
Else
GraphicsWindow.BrushColor = colorFreeField
cellTable = Shapes.AddRectangle(cellSize, cellSize)
Shapes.Move(cellTable, x * cellSize + tableOffsetX[room] * cellSize, y * cellSize)
EndIf
EndFor
EndFor
EndSub

Sub initVariables
'***** DIRECTIONS ********'
dirSouth = 1
dirEast = 2
dirNorth = 3
dirWest = 4

subSouth = "goSouth()"
subEast = "goEast()"
subNorth = "goNorth()"
subWest = "goWest()"
'***** MESSAGES *******'
msgBack = "BACK"
msgWest = "WEST"
msgEast = "EAST"
msgNorth = "NORTH"
msgSouth = "SOUTH"

msgWall = "WALL"
msgEdge = "EDGE"
msgUsed = "USED"

msgTarget = "TARGET"
msgEnd = "END"
'******* COLORS *********'
colorWall = "Red"
colorTarget = "Green"
colorMarkedTarget = "Yellow"
colorFreeField = "Lavender"
'*** STATES OF TABLE FIELD***'
charWall = "X"
charTarget = "O"
charUsedField = "U"
charFreeField = "-"

'****** ASCII CODES IN FILE ******'
asciiWall = 88 'X
asciiTarget = 79 'O

'**********************************'
args=0
cellSize = 30
numRooms = Array.GetItemCount(mazeTable)
tableOffsetX[1] = 0

'****** ROOM VARIABLES (NOT ALL) ******'
For room=1 To numRooms
aliveSearch[room] = "True"
stacks[room] = " room1" + room
stepCounter[room] = 0
angle[room] = 0

isEdge[room] ="False"
isWall[room] = "False"
isUsedField[room] = "False"
isSearchLimit[room] = "False"
isFree[room] = "True"

direction[room] = dirNorth
depthSearchLimit[room] = 45
EndFor

EndSub

Sub initRooms
For room=1 To numRooms
readTable()
fileName = Program.Directory + "\maze" + room + ".txt"
'readTableFromFile()
EndFor

'Whole width of rooms and spaces
tableWidth = 1
For room = 1 To numRooms
tableWidth = tableWidth + 1 + numColumn[room]
EndFor
tableWidth = tableWidth * cellSize

'First table is the highest room or equal to others
GraphicsWindow.Height = (Array.GetItemCount(mazeTable[1]) + 2) * cellSize
GraphicsWindow.Width = tableWidth
GraphicsWindow.Title = "Parallel execution of Trémaux's algorithm"

'Draw all rooms
For room = 1 To numRooms
initTurtle()
drawTable()
EndFor
EndSub