Encyclopedia of Drunken Walks

- A New Paradigm -

"God does not play dice" vs "God does not waste computational resources"

Drunken walks are ideal for map generation for 3 reasons:

1. The generated map is inherently fractal.
2. The generated map is definitively random.
3. The map can be generated dynamically (on the fly).  This dynamic map generation allows for unlimited map size (boundless and infinite).

Drunken walks can be biased to favor any combination of the 6 cardinal/absolute directions (NW, NE, East, SE, SW, West) and the 6 relative directions (straight forward = 12:00, right forward = 2:00, right backward = 4:00, straight backward = 6:00, left backward = 8:00, left forward = 10:00).

These biases can be encoded in 6 weights for cardinal/absolute directions, and 6 weights for relative directions (relative to the current direction of movement).

A drunken walk pattern can thus be defined by 12 weights, and we call this collection of weights the "Direction Tensor".  The word "tensor" is used here to mean roughly "an object whose shadow is a vector".  At any given point in time, the likelihood of moving in each direction is proportional to the product of the cardinal/absolute weight, and the corresponding relative weight (each relative direction corresponds to an absolute direction, with respect to the current direction of movement).

The effects of chaging the 6 cardinal/absolute weights are fairly predictable, so this study examines only the effects of relative weightings (the 6 cardinal/absolute weights are taken to be equal to each other, so there are no cardinal biases).

- Example Patterns -

Limiting movement to backwards right and left (4:00 and 8:00) leads to a relatively compact but elongated form:

50% right backwards (4:00), 50% left backwards (8:00).

66% right backwards (4:00), 33% left backwards (8:00).

Limiting movement to straight and right forward (12:00 and 2:00) generates a less compact form:

66% straight forward (12:00), 33% right forward (2:00).

Limiting motion to right forward and left forward (2:00 and 10:00) - aka clockwise and counter-clockwise - results in characteristic "holes".  This can be used for maps where regularly spaced lakes, islands, or oases are desired:

50% right forward (2:00), 50% left forward (10:00).  [example 1/2]

50% right forward (2:00), 50% left forward (10:00).  [example 2/2]

Allowing movement in any direction except for straight backwards leads to the following "balanced" typologies:

20% straight forward (12:00), 20% right forward (2:00), 20% right backward (4:00), 20% left backward (8:00), 20% left forward (10:00).  [example 1/3] 

20% straight forward (12:00), 20% right forward (2:00), 20% right backward (4:00), 20% left backward (8:00), 20% left forward (10:00).  [example 2/3] 

20% straight forward (12:00), 20% right forward (2:00), 20% right backward (4:00), 20% left backward (8:00), 20% left forward (10:00).  [example 3/3] 

- VBA Code (Class Module) -

'6 weights for the 6 absolute directions:
Public NW As Single
Public NE As Single
Public East As Single
Public SE As Single
Public SW As Single
Public West As Single

'6 weights for the 6 relative directions:
Public StraightForward As Single
Public RightForward As Single
Public RightBackward As Single
Public StraightBackward As Single
Public LeftBackward As Single
Public LeftForward As Single

'6 numbers for current fractional likelihood of each absolute direction:
Public ProbabilityNW As Single
Public ProbabilityNE As Single
Public ProbabilityEast As Single
Public ProbabilitySE As Single
Public ProbabilitySW As Single
Public ProbabilityWest As Single

Public Function GetDirection(ByVal Previous As Location, ByVal Current As Location)
    Dim Direction As String
    Dim SouthShift, EastShift As Integer
   
    SouthShift = Current.Row - Previous.Row
    EastShift = Current.Col - Previous.Col
   
    Direction = "resting"
    If SouthShift = 0 And EastShift = 1 Then Direction = "East"
    If SouthShift = 0 And EastShift = -1 Then Direction = "West"
    If SouthShift = 1 And EastShift = 0 Then Direction = "SE"
    If SouthShift = 1 And EastShift = -1 Then Direction = "SW"
    If SouthShift = -1 And EastShift = 1 Then Direction = "NE"
    If SouthShift = -1 And EastShift = 0 Then Direction = "NW"
   
    GetDirection = Direction
End Function

Public Sub CalculateProbabilities(ByVal Direction As String)
'The public variable "Direction" should be set before calling this sub.
    Dim AbsoluteWeights(6) As Single
    Dim RelativeWeights(6) As Single
    Dim CombinedWeights(6) As Single
    Dim Counter, RotatingCounter As Integer
    Dim TotalWeights As Single
   
    AbsoluteWeights(0) = Me.NW
    AbsoluteWeights(1) = Me.NE
    AbsoluteWeights(2) = Me.East
    AbsoluteWeights(3) = Me.SE
    AbsoluteWeights(4) = Me.SW
    AbsoluteWeights(5) = Me.West
   
    RelativeWeights(0) = Me.StraightForward
    RelativeWeights(1) = Me.RightForward
    RelativeWeights(2) = Me.RightBackward
    RelativeWeights(3) = Me.StraightBackward
    RelativeWeights(4) = Me.LeftBackward
    RelativeWeights(5) = Me.LeftForward
   
    TotalWeights = 0
    'Rotate RelativeWeights depending on Direction:
    Select Case Direction
    Case "NW"
        For Counter = 0 To 5
            CombinedWeights(Counter) = AbsoluteWeights(Counter) * RelativeWeights(Counter)
            TotalWeights = TotalWeights + CombinedWeights(Counter)
        Next Counter
    Case "NE"
        For Counter = 0 To 5
            RotatingCounter = (Counter - 1) Mod 6  
            'We need the next line, because vba does "mod" wrong.
            If RotatingCounter < 0 Then RotatingCounter = RotatingCounter + 6
            CombinedWeights(Counter) = AbsoluteWeights(Counter) * RelativeWeights(RotatingCounter)
            TotalWeights = TotalWeights + CombinedWeights(Counter)
        Next Counter
    Case "East"
        For Counter = 0 To 5
            RotatingCounter = (Counter - 2) Mod 6
            If RotatingCounter < 0 Then RotatingCounter = RotatingCounter + 6
            CombinedWeights(Counter) = AbsoluteWeights(Counter) * RelativeWeights(RotatingCounter)
            TotalWeights = TotalWeights + CombinedWeights(Counter)
        Next Counter
    Case "SE"
        For Counter = 0 To 5
            RotatingCounter = (Counter - 3) Mod 6
            If RotatingCounter < 0 Then RotatingCounter = RotatingCounter + 6
            CombinedWeights(Counter) = AbsoluteWeights(Counter) * RelativeWeights(RotatingCounter)
            TotalWeights = TotalWeights + CombinedWeights(Counter)
        Next Counter
    Case "SW"
        For Counter = 0 To 5
            RotatingCounter = (Counter - 4) Mod 6
            If RotatingCounter < 0 Then RotatingCounter = RotatingCounter + 6
            CombinedWeights(Counter) = AbsoluteWeights(Counter) * RelativeWeights(RotatingCounter)
            TotalWeights = TotalWeights + CombinedWeights(Counter)
        Next Counter
    Case "West"
        For Counter = 0 To 5
            RotatingCounter = (Counter - 5) Mod 6
            If RotatingCounter < 0 Then RotatingCounter = RotatingCounter + 6
            CombinedWeights(Counter) = AbsoluteWeights(Counter) * RelativeWeights(RotatingCounter)
            TotalWeights = TotalWeights + CombinedWeights(Counter)
        Next Counter
    Case "resting"
        'If the animal rested on the last turn, absolute/cardinal movement bias controls:
        For Counter = 0 To 5
            CombinedWeights(Counter) = AbsoluteWeights(Counter)
            TotalWeights = TotalWeights + CombinedWeights(Counter)
        Next Counter
    End Select
   
    'Normalize the probabilities so they add up to 1:
    If TotalWeights <> 0 Then
        For Counter = 0 To 5
            CombinedWeights(Counter) = CombinedWeights(Counter) / TotalWeights
        Next Counter
    End If
   
    Me.ProbabilityNW = CombinedWeights(0)
    Me.ProbabilityNE = CombinedWeights(1)
    Me.ProbabilityEast = CombinedWeights(2)
    Me.ProbabilitySE = CombinedWeights(3)
    Me.ProbabilitySW = CombinedWeights(4)
    Me.ProbabilityWest = CombinedWeights(5)
End Sub

Public Sub NormalizeProbabilities(ByVal TotalWeights As Single)
    'Use zero to indicate "recalculate TotalWeights":
    If TotalWeights = 0 Then
        TotalWeights = Me.ProbabilityNW + Me.ProbabilityNE + Me.ProbabilityEast _
        + Me.ProbabilitySE + Me.ProbabilitySW + Me.ProbabilityWest
    End If
   
    'If it actually is zero (based on math), then use "absolute values":
    If TotalWeights = 0 Then
        Me.CalculateProbabilities ("resting")
    Else
        Me.ProbabilityNW = Me.ProbabilityNW / TotalWeights
        Me.ProbabilityNE = Me.ProbabilityNE / TotalWeights
        Me.ProbabilityEast = Me.ProbabilityEast / TotalWeights
        Me.ProbabilitySE = Me.ProbabilitySE / TotalWeights
        Me.ProbabilitySW = Me.ProbabilitySW / TotalWeights
        Me.ProbabilityWest = Me.ProbabilityWest / TotalWeights
    End If
End Sub

Copyright 2016 Matthew J Curran.  

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this code except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.