Microsoft Small Basic

Program Listing: SGW427

List Program

' Parallel executions of Tremaux's algorithm
' Stevan Tosic
' 26/05/2020
' 03/06/2020 (multi turtle added)
' 05/06/2020
' - turtlePath and stepCounter removed
' - stack value: (alterState, -dX, -dY) to return
' Turtle is replaced as Tryhest proposed in KRX737 (turtleMove,initTurtle 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")
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

GraphicsWindow.ShowMessage("That's all!" "Done")

Sub search
room = args[1]
turtleID = args[2]
If(isSearchAlive[room][turtleID] = "True") Then
If(searchState[room][turtleID] = dirSouth) Then
alterState = "S01"
goSouth()
ElseIf(searchState[room][turtleID] = dirEast) Then
alterState = "E01"
goEast()
ElseIf(searchState[room][turtleID] = dirNorth) Then
alterState = "N01"
goNorth()
ElseIf(searchState[room][turtleID] = dirWest) Then
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
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
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
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
returnFromDeadEnd()
EndIf
EndIf
EndSub

Sub toFieldIfFree
checkEdge()
checkField()
checkSearchLimit()

If(isEdge="False" And isWall = "False" And isUsedField = "False" And isSearchLimit = "False") Then
LDCall.Function("turtleMove", cellSize)
Stack.PushValue(stacks[room][turtleID], "1=" + alterState + ";2=" + -dX + ";3=" + -dY)
Else
searchState[room][turtleID] = alterState
EndIf
EndSub

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

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

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

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

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

Sub checkSearchLimit
isSearchLimit = "False"
If(Stack.GetCount(stacks[room][turtleID]) = depthSearchLimit[room][turtleID]) Then
isSearchLimit = "True"
EndIf
EndSub

Sub returnFromDeadEnd
If(Stack.GetCount(stacks[room][turtleID]) > 0 ) Then
row = turtleY[room][turtleID]
col = turtleX[room][turtleID]
tableState[room][row][col] = charUsedField

lastState = Stack.PopValue(stacks[room][turtleID])
searchState[room][turtleID] = lastState[1]
dX = lastState[2]
dY = lastState[3]
LDCall.Function("turtleMove", -cellSize)
Else
isSearchAlive[room][turtleID] = "False"
EndIf
EndSub

Sub checkField
isUsedField = "False"
isWall = "False"

row = turtleY[room][turtleID] + dY
col = turtleX[room][turtleID] + dX

If(tableState[room][row][col] = charTarget) Then
GraphicsWindow.BrushColor = colorMarkedTarget
cellTable = Shapes.AddRectangle(cellSize, cellSize)
Shapes.Move(cellTable, col * cellSize + tableOffsetX[room] * cellSize, row * cellSize)
EndIf

If(tableState[room][row][col] = charUsedField) Then
isUsedField = "True"
ElseIf(tableState[room][row][col] = charWall) Then
isWall = "True"
Else
col = turtleX[room][turtleID]
row = turtleY[room][turtleID]
tableState[room][row][col] = charUsedField
EndIf
EndSub

Sub readTable
row = 1
line = mazeTable[room][row]
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
tableState[room][row][col] = charWall
ElseIf(char = charTarget) Then
tableState[room][row][col] = charTarget
Else
tableState[room][row][col] = charFreeField
EndIf
EndFor

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

numRow[room] = row
row = row + 1
line = mazeTable[room][row]
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"

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

args=0
cellSize = 32
tableOffsetX[1] = 0

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

Sub initRooms
numRooms = Array.GetItemCount(mazeTable)
For room=1 To numRooms
readTable()
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--------
x0 = turtleX[room][turtleID] * cellSize + cellSize/2 + tableOffsetX[room] * cellSize
y0 = turtleY[room][turtleID] * cellSize + cellSize/2

rrs=LDMath.Convert2Cartesian(x0 y0 args[1] angle[room][turtleID]-90)

If tpenup[room][turtleID] Then
Else
Shapes.AddLine(x0 y0 rrs[1] rrs[2])
EndIf

LDShapes.ZIndex(trt[room][turtleID] 1111)
Shapes.Rotate(trt[room][turtleID] angle[room][turtleID])
Shapes.move(trt[room][turtleID] rrs[1] rrs[2])

turtleX[room][turtleID] = turtleX[room][turtleID] + dX
turtleY[room][turtleID] = turtleY[room][turtleID] + dY
EndSub

Sub initTurtleUI
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
room = args[1]
turtleID = args[2]

searchState[room][turtleID] = args[5]
angle[room][turtleID] = anglesSENW[args[5]]

depthSearchLimit[room][turtleID] = 45
stacks[room][turtleID] = "room" + room + turtleID

isSearchAlive[room][turtleID] = "True"

turtleX[room][turtleID] = args[3]
turtleY[room][turtleID] = args[4]

tpenup[room][turtleID] = "False"
trt[room][turtleID]=Shapes.AddTriangle(0 0 10 30, -10 30)

initTurtleUI()
EndSub

Sub initTurtles
anglesSENW = dirSouth + "=180;" + dirEast + "=90;" + dirNorth + "=0;" + dirWest + "=-90"
LDCall.Function5("initTurtle", 1, 1, 6 ,11, dirNorth)
LDCall.Function5("initTurtle", 2, 1, 6 ,11, dirNorth)
LDCall.Function5("initTurtle", 3, 1, 6 ,11, dirNorth)
LDCall.Function5("initTurtle", 1, 2, 2, 2, dirEast)
LDCall.Function5("initTurtle", 2, 2, 12, 2, dirSouth)
LDCall.Function5("initTurtle", 3, 2, 2, 2, dirEast)
LDCall.Function5("initTurtle", 3, 3, 10, 4, dirWest)
EndSub