Microsoft Small Basic

Program Listing: CFR384
' Parallel executions of Tremaux's algorithm
' Stevan Tosic
' 26/05/2020
' 03/06/2020 (multi turtle added)
' Turtle is replaced as Tryhest proposed in KRX737 (turtleMove and initTurtleUI here)
mazeTable[1][1] = "XXXXOXXXXXX"
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 XOX"
mazeTable[2][3] = "XXXOXX X X"
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()
initTurtles()

While(isSearchAlive[1][1] = "True" Or isSearchAlive[1][2] = "True" Or isSearchAlive[2][1] = "True" Or isSearchAlive[2][2] = "True" Or isSearchAlive[3][1] = "True" Or isSearchAlive[3][2] = "True" Or isSearchAlive[3][3] = "True")
'search(room, turtleID)
LDCall.Function2("search", 1, 1)
LDCall.Function2("search", 2, 1)
LDCall.Function2("search", 3, 1)
LDCall.Function2("search", 1, 2)
LDCall.Function2("search", 2, 2)
LDCall.Function2("search", 3, 2)
LDCall.Function2("search", 3, 3)
Program.Delay(20)
EndWhile

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

Sub search
room = args[1]
turtleID = args[2]
If(isSearchAlive[room][turtleID] = "True") Then
If(searchState[room][turtleID] = dirSouth) Then
stepCounter[room][turtleID] = stepCounter[room][turtleID] + 1
alterState = "S01"
goSouth()
ElseIf(searchState[room][turtleID] = dirEast) Then
stepCounter[room][turtleID] = stepCounter[room][turtleID] + 1
alterState = "E01"
goEast()
ElseIf(searchState[room][turtleID] = dirNorth) Then
stepCounter[room][turtleID] = stepCounter[room][turtleID] + 1
alterState = "N01"
goNorth()
ElseIf(searchState[room][turtleID] = dirWest) Then
stepCounter[room][turtleID] = stepCounter[room][turtleID] + 1
alterState = "W01"
goWest()
ElseIf(searchState[room][turtleID] = "S01") Then
alterState = "S02"
angle[room][turtleID] = angle[room][turtleID] - 90
goEast()
ElseIf(searchState[room][turtleID] = "S02") Then
alterState = "S03"
angle[room][turtleID] = angle[room][turtleID] + 180
goWest()
ElseIf(searchState[room][turtleID] = "S03") Then
angle[room][turtleID] = angle[room][turtleID] - 90
stepCounter[room][turtleID] = stepCounter[room][turtleID] - 1
returnFromDeadEnd()
ElseIf(searchState[room][turtleID] = "E01") Then
alterState = "E02"
angle[room][turtleID] = angle[room][turtleID] + 90
goSouth()
ElseIf(searchState[room][turtleID] = "E02") Then
alterState = "E03"
angle[room][turtleID] = angle[room][turtleID] - 180
goNorth()
ElseIf(searchState[room][turtleID] = "E03") Then
angle[room][turtleID] = angle[room][turtleID] + 90
stepCounter[room][turtleID] = stepCounter[room][turtleID] - 1
returnFromDeadEnd()
ElseIf(searchState[room][turtleID] = "N01") Then
alterState = "N02"
angle[room][turtleID] = angle[room][turtleID] + 90
goEast()
ElseIf(searchState[room][turtleID] = "N02") Then
alterState = "N03"
angle[room][turtleID] = angle[room][turtleID] - 180
goWest()
ElseIf(searchState[room][turtleID] = "N03") Then
angle[room][turtleID] = angle[room][turtleID] + 90
stepCounter[room][turtleID] = stepCounter[room][turtleID] - 1
returnFromDeadEnd()
ElseIf(searchState[room][turtleID] = "W01") Then
alterState = "W02"
angle[room][turtleID] = angle[room][turtleID] - 90
goSouth()
ElseIf(searchState[room][turtleID] = "W02") Then
alterState = "W03"
angle[room][turtleID] = angle[room][turtleID] + 180
goNorth()
ElseIf(searchState[room][turtleID] = "W03") Then
angle[room][turtleID] = angle[room][turtleID] - 90
stepCounter[room][turtleID] = stepCounter[room][turtleID] - 1
returnFromDeadEnd()
EndIf
EndIf
EndSub

Sub toFieldIfFree
checkEdge()
checkWallUsedField()
checkSearchLimit()
checkTarget()

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

Stack.PushValue(stacks[room][turtleID], alterState)
addUsedFieldToPath()
Else
searchState[room][turtleID] = alterState
EndIf
EndSub

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

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

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

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

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

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

Sub returnFromDeadEnd
If stepCounter[room][turtleID] > 0 Then
row = turtlePath[room][turtleID]["Y"][stepCounter[room][turtleID]+1]
col = turtlePath[room][turtleID]["X"][stepCounter[room][turtleID]+1]
tableState[room][row][col] = charUsedField
LDCall.Function("turtleMove", -cellSize)
searchState[room][turtleID] = Stack.PopValue(stacks[room][turtleID])
Else
isSearchAlive[room][turtleID] = "False"
'TextWindow.WriteLine("Room" + room + ", turtle:" + turtleID + " end.")
EndIf
EndSub

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

Sub checkWallUsedField
isUsedField = "False"
isWall = "False"

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

If(tableState[room][row][col] = charUsedField) Then
isUsedField = "True"
ElseIf(tableState[room][row][col] = charWall) Then
isWall = "True"
Else
col = turtlePath[room][turtleID]["X"][stepCounter[room][turtleID]]
row = turtlePath[room][turtleID]["Y"][stepCounter[room][turtleID]]
tableState[room][row][col] = charUsedField
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][turtleID]["X"][stepCounter[room][turtleID]] = targets[room]["X"][i] And turtlePath[room][turtleID]["Y"][stepCounter[room][turtleID]] = targets[room]["Y"][i]) Then
setTargetColor()
EndIf
EndFor
EndSub

Sub writeLimitedturtlePath
TextWindow.Write(msgEnd)
For i = 1 To depthSearchLimit[room][turtleID]
TextWindow.Write(" " + turtlePath[room][turtleID]["Y"][i] + "," + turtlePath[room][turtleID]["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 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"

'***** 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 = 32
numRooms = Array.GetItemCount(mazeTable)
tableOffsetX[1] = 0

isEdge ="False"
isWall = "False"
isUsedField = "False"
isSearchLimit = "False"
EndSub

Sub initRooms
For room=1 To numRooms
readTable()
fileName = Program.Directory + "\maze" + room + ".txt"
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"

For room = 1 To numRooms
drawTable()
EndFor

EndSub

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

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

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

Sub initTurtle
turtleID = args[1]
turtlePath[room][turtleID]["X"][1] = args[2]
turtlePath[room][turtleID]["Y"][1] = args[3]
searchState[room][turtleID] = args[4]
angle[room][turtleID] = args[5]
depthSearchLimit[room][turtleID] = 45
stacks[room][turtleID] = " room" + room + turtleID
stepCounter[room][turtleID] = 0
isSearchAlive[room][turtleID] = "True"

initTurtleUI()
EndSub

Sub initTurtles
For room=1 To numRooms
LDCall.Function5("initTurtle", 1, 6 ,11, dirNorth, 0)
EndFor

room = 1
LDCall.Function5("initTurtle", 2, 2, 2, dirEast, 90)

room = 2
LDCall.Function5("initTurtle", 2, 12, 2, dirSouth, 180)

room = 3
LDCall.Function5("initTurtle", 2, 2, 2, dirEast, 90)

room = 3
LDCall.Function5("initTurtle", 3, 10, 4, dirWest, -90)
EndSub