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>();

        visitedNodes.Add(startPos);

        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));

                visitedNodes.Add(nextNodePos);

                stepsSoFar += 1;
            }
        }

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

        while (currentNode.previousNode != null)
        {
            randomWalkPositions.Add(currentNode.pos);

            currentNode = currentNode.previousNode;
        }

        randomWalkPositions.Add(currentNode.pos);

        //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;
        }
    }
}

Back