# Self-avoiding Random Walk

A random walk is a walk where you move in random directions. A self-avoiding random walk is very similar but you are not allowed to walk to a position where you have already been. They look like this:   To make it work, you just have to attach the script to a gameobject in Unity. Then you just press enter to generate new random walks.

```using System.Collections;
using System.Collections.Generic;
using UnityEngine;

//Self-Avoiding Random Walk algorithm
public class RandomWalk : MonoBehaviour
{
//How many steps do we want to take before we stop?
public int stepsToTake;

//Final random walk positions
List<Vector3> randomWalkPositions;

//The walk directions we can take
List<Vector3> allPossibleDirections = new List<Vector3> {
new Vector3(0f, 0f, 1f),
new Vector3(0f, 0f, -1f),
new Vector3(-1f, 0f, 0f),
new Vector3(1f, 0f, 0f)
};

void Update()
{
if (Input.GetKeyDown(KeyCode.Return))
{
randomWalkPositions = GenerateSelfAvoidingRandomWalk();

//Debug.Log(randomWalkPositions.Count);
}

//Display the path with lines
if (randomWalkPositions != null && randomWalkPositions.Count > 1)
{
for (int i = 1; i < randomWalkPositions.Count; i++)
{
Debug.DrawLine(randomWalkPositions[i - 1], randomWalkPositions[i]);
}
}
}

public List GenerateSelfAvoidingRandomWalk()
{
//Create the node we are starting from
Vector3 startPos = Vector3.zero;

WalkNode currentNode = new WalkNode(startPos, null, new List<Vector3>(allPossibleDirections));

//How many steps have we taken, so we know when to stop the algorithm
int stepsSoFar = 0;

//So we dont visit the same node more than once
List<Vector3> visitedNodes = new List<Vector3>();

while (true)
{
//Check if we have walked enough steps
if (stepsSoFar == stepsToTake)
{
//Debug.Log("Found path");

break;
}

//Need to backtrack if we cant move in any direction from the current node
while (currentNode.possibleDirections.Count == 0)
{
currentNode = currentNode.previousNode;

//Dont need to remove nodes thats not a part of the final path from the list of visited nodes
//because there's no point in visiting them again because we know we cant find a path from those nodes

stepsSoFar -= 1;
}

//Walk in a random direction from this node
int randomDirPos = Random.Range(0, currentNode.possibleDirections.Count);

Vector3 randomDir = currentNode.possibleDirections[randomDirPos];

//Remove this direction from the list of possible directions we can take from this node
currentNode.possibleDirections.RemoveAt(randomDirPos);

//Whats the position after we take a step in this direction
Vector3 nextNodePos = currentNode.pos + randomDir;

//Have we visited this position before?
if (!HasVisitedNode(nextNodePos, visitedNodes))
{
//Walk to this node
currentNode = new WalkNode(nextNodePos, currentNode, new List<Vector3>(allPossibleDirections));

stepsSoFar += 1;
}
}

//Generate the final path
List<Vector3> randomWalkPositions = new List<Vector3>();

while (currentNode.previousNode != null)
{

currentNode = currentNode.previousNode;
}

//Reverse the list so it begins at the step we started from
randomWalkPositions.Reverse();

return randomWalkPositions;
}

//Checks if a position is in a list of positions
private bool HasVisitedNode(Vector3 pos, List<Vector3> listPos)
{
bool hasVisited = false;

for (int i = 0; i < listPos.Count; i++)
{
float distSqr = Vector3.SqrMagnitude(pos - listPos[i]);

//Cant compare exactly because of floating point precisions
if (distSqr < 0.001f)
{
hasVisited = true;

break;
}
}

return hasVisited;
}

//Help class to keep track of the steps
private class WalkNode
{
//The position of this node in the world
public Vector3 pos;

public WalkNode previousNode;

//Which steps can we take from this node?
public List<Vector3> possibleDirections;

public WalkNode(Vector3 pos, WalkNode previousNode, List<Vector3> possibleDirections)
{
this.pos = pos;

this.previousNode = previousNode;

this.possibleDirections = possibleDirections;
}
}
}

```