Network synchronized random maze generator for VRChat. Powered by UdonSharp.

MazeGen.cs

using System;
using UnityEngine;
using VRC.SDKBase;
using VRC.Udon;
using UdonSharp;

namespace JLChnToZ.VRC.Maze {
    [RequireComponent(typeof(MeshFilter)), UdonBehaviourSyncMode(BehaviourSyncMode.Manual)]
    public class MazeGen : UdonSharpBehaviour {
        // Constants
        const byte LEFT = 0x1;
        const byte BACKWARD = 0x2;
        const byte RIGHT = 0x4;
        const byte FORWARD = 0x8;
        const byte ALT_LEFT = 0x10;
        const byte ALT_BACKWARD = 0x20;
        const byte ALT_RIGHT = 0x40;
        const byte ALT_FORWARD = 0x80;
        int[] hammingLookup = new [] { // Hamming distance lookup table from 0x0 to 0xF.
            4, 3, 3, 2, 3, 2, 2, 1,
            3, 2, 2, 1, 2, 1, 1, 0,
        };

        // Properties
        public int mazeWidth = 20;
        public int mazeHeight = 20;
        [SerializeField] Rect wallTextureST = new Rect(0, 0, 1, 1);
        [SerializeField, Range(0, 1)] float altWallTextureProb;
        [SerializeField] Rect altWallTextureST = new Rect(0, 0, 1, 1);
        [SerializeField] bool withCeiling;
        [SerializeField] Rect ceilingTextureST = new Rect(0, 0, 1, 1);
        [SerializeField] bool withFloor;
        [SerializeField] Rect floorTextureST = new Rect(0, 0, 1, 1);

        // Local References
        MeshFilter meshFilter;
        new MeshCollider collider;
        Mesh generatedMesh;
        Vector3[] vertices;
        Vector3[] normals;
        Vector2[] uv;
        int[] triangles;

        // Network synced states
        [UdonSynced] byte rowSize;
        [UdonSynced] byte[] states;

        void Start() {
            meshFilter = GetComponent<MeshFilter>();
            collider = GetComponent<MeshCollider>();
        }

        // Cleanup logic
        void OnDestroy() {
            if (generatedMesh != null) Destroy(generatedMesh);
        }

        public override void OnDeserialization() => GenerateMesh();

        // Generate maze data and sync it to everyone.
        // This will trigger everyone to build the mesh locally by the data.
        // Only mazegen object owner (should be room master) can call this.
        public void Generate() {
            if (!Networking.IsOwner(gameObject)) return;
            states = new byte[mazeWidth * mazeHeight];
            rowSize = (byte)mazeWidth;
            int[] path = new int[states.Length];
            int[] visited = new int[states.Length];
            byte[] targets = new byte[4];
            int pathLength = 1;
            int visitedCount = 1;
            while (pathLength > 0) {
                int i = path[pathLength - 1];
                int x = i % rowSize;
                int z = i / rowSize;

                // Fetch all unvisited neighbour cells to the random pool
                int targetCount = 0;
                if (x > 0 && Array.IndexOf(visited, i - 1, 0, visitedCount) < 0)
                    targets[targetCount++] = LEFT;
                if (x < rowSize - 1 && Array.IndexOf(visited, i + 1, 0, visitedCount) < 0)
                    targets[targetCount++] = RIGHT;
                if (z > 0 && Array.IndexOf(visited, i - rowSize, 0, visitedCount) < 0)
                    targets[targetCount++] = BACKWARD;
                if (z < mazeHeight - 1 && Array.IndexOf(visited, i + rowSize, 0, visitedCount) < 0)
                    targets[targetCount++] = FORWARD;

                // No available neighbours, walk back 1 cell to try again.
                if (targetCount == 0) {
                    pathLength--;
                    continue;
                }

                // Get 1 random neighbour from the pool and dig the wall to it.
                switch (targets[UnityEngine.Random.Range(0, targetCount)]) {
                    case LEFT:
                        states[i] |= LEFT;
                        i--;
                        states[i] |= RIGHT;
                        break;
                    case RIGHT:
                        states[i] |= RIGHT;
                        i++;
                        states[i] |= LEFT;
                        break;
                    case BACKWARD:
                        states[i] |= BACKWARD;
                        i -= rowSize;
                        states[i] |= FORWARD;
                        break;
                    case FORWARD:
                        states[i] |= FORWARD;
                        i += rowSize;
                        states[i] |= BACKWARD;
                        break;
                }

                // Walk to the target neighbour and mark it visited.
                path[pathLength++] = i;
                visited[visitedCount++] = i;
            }
            GenerateAltWalls();
            RequestSerialization();
            GenerateMesh();
        }

        // Change some walls to alternative ones.
        void GenerateAltWalls() {
            if (altWallTextureProb <= 0) return;
            for (int i = 0; i < states.Length; i++) {
                if ((states[i] & LEFT) == 0 && altWallTextureProb > UnityEngine.Random.value)
                    states[i] |= ALT_LEFT;
                if ((states[i] & BACKWARD) == 0 && altWallTextureProb > UnityEngine.Random.value)
                    states[i] |= ALT_BACKWARD;
                if ((states[i] & RIGHT) == 0 && altWallTextureProb > UnityEngine.Random.value)
                    states[i] |= ALT_RIGHT;
                if ((states[i] & FORWARD) == 0 && altWallTextureProb > UnityEngine.Random.value)
                    states[i] |= ALT_FORWARD;
            }
        }

        // Generate the actual maze mesh locally and assign the mesh to the MeshFilter and MeshCollider if applicable.
        // Mesh data is not efficient to be synced, so in here we are using the synced state to rebulid.
        void GenerateMesh() {
            int featCount = 0;
            foreach (byte s in states) featCount += hammingLookup[s & 0xF];
            if (withCeiling) featCount += states.Length;
            if (withFloor) featCount += states.Length;
            if (vertices == null || vertices.Length != featCount * 4) vertices = new Vector3[featCount * 4];
            if (normals == null || normals.Length != featCount * 4) normals = new Vector3[featCount * 4];
            if (uv == null || uv.Length != featCount * 4) uv = new Vector2[featCount * 4];
            if (triangles == null || triangles.Length != featCount * 6) triangles = new int[featCount * 6];
            quadOffset = 0;
            for (int i = 0; i < states.Length; i++) {
                byte s = states[i];
                int x = i % rowSize;
                int z = i / rowSize;
                if ((s & LEFT) == 0)
                    AppendWall(new Vector2(x, z), new Vector2(x, z + 1), Vector3.right, (s & ALT_LEFT) != 0);
                if ((s & RIGHT) == 0)
                    AppendWall(new Vector2(x + 1, z + 1), new Vector2(x + 1, z), Vector3.left, (s & ALT_RIGHT) != 0);
                if ((s & BACKWARD) == 0)
                    AppendWall(new Vector2(x + 1, z), new Vector2(x, z), Vector3.forward, (s & ALT_BACKWARD) != 0);
                if ((s & FORWARD) == 0)
                    AppendWall(new Vector2(x, z + 1), new Vector2(x + 1, z + 1), Vector3.back, (s & ALT_FORWARD) != 0);
                if (withCeiling)
                    AppendQuad(
                        new Vector3(x, 1, z), new Vector3(x, 1, z + 1),
                        new Vector3(x + 1, 1, z), new Vector3(x + 1, 1, z + 1),
                        Vector3.down, ceilingTextureST
                    );
                if (withFloor)
                    AppendQuad(
                        new Vector3(x + 1, 0, z + 1), new Vector3(x + 1, 0, z), 
                        new Vector3(x, 0, z + 1), new Vector3(x, 0, z),
                        Vector3.up, floorTextureST
                    );
            }
            if (generatedMesh == null) generatedMesh = new Mesh();
            generatedMesh.vertices = vertices;
            generatedMesh.normals = normals;
            generatedMesh.triangles = triangles;
            generatedMesh.uv = uv;
            generatedMesh.UploadMeshData(false);
            meshFilter.sharedMesh = generatedMesh;
            if (collider != null) collider.sharedMesh = generatedMesh;
        }

        // Shortcut method for append a wall at coordinates provided.
        void AppendWall(Vector2 pos1, Vector2 pos2, Vector3 normal, bool altTexture) => AppendQuad(
            new Vector3(pos1.x, 0, pos1.y), new Vector3(pos2.x, 0, pos2.y),
            new Vector3(pos1.x, 1, pos1.y), new Vector3(pos2.x, 1, pos2.y),
            normal, altTexture ? altWallTextureST : wallTextureST
        );

        // Append a quad to the mesh
        void AppendQuad(Vector3 lb, Vector3 rb, Vector3 lt, Vector3 rt, Vector3 normal, Rect uvCoord) {
            // We don't reuse exists vertices and just append to the end
            // becuase it needs too much work load to seek the matching one,
            // and the one might not have correct UV coordinate.
            vertices[quadOffset * 4    ] = lb;
            vertices[quadOffset * 4 + 1] = rb;
            vertices[quadOffset * 4 + 2] = lt;
            vertices[quadOffset * 4 + 3] = rt;

            // Normal map, as this is just a flat quad so we only need to points to one direction.
            normals[quadOffset * 4    ] = normal;
            normals[quadOffset * 4 + 1] = normal;
            normals[quadOffset * 4 + 2] = normal;
            normals[quadOffset * 4 + 3] = normal;

            // UV mapping from provided rect.
            uv[quadOffset * 4    ] = uvCoord.min; // LB (--)
            uv[quadOffset * 4 + 1] = new Vector2(uvCoord.xMax, uvCoord.yMin); // RB (+-)
            uv[quadOffset * 4 + 2] = new Vector2(uvCoord.xMin, uvCoord.yMax); // LT (-+)
            uv[quadOffset * 4 + 3] = uvCoord.max; // RT (++)

            // Assume the input vertex order is lb-rb-lt-rt,   2→3
            // and Unity's winding order is clockwise,         ↑\↓
            // therefore the mapping is 0-2-1; 2-3-1.          0←1
            triangles[quadOffset * 6    ] = quadOffset * 4;
            triangles[quadOffset * 6 + 1] = quadOffset * 4 + 2;
            triangles[quadOffset * 6 + 2] = quadOffset * 4 + 1;
            triangles[quadOffset * 6 + 3] = quadOffset * 4 + 2;
            triangles[quadOffset * 6 + 4] = quadOffset * 4 + 3;
            triangles[quadOffset * 6 + 5] = quadOffset * 4 + 1;
            quadOffset++;
        }

        // Serialize the maze data to a string which can be copied and/or restored by a user (player).
        public string SerializeToString() {
            byte[] result = new byte[states.Length / 2 + 6];
            for (int i = 0; i < states.Length; i++) {
                byte v = (states[i] & 0xF) << (i % 2 * 4);
                result[i / 2 + 6] |= v;
                result[(i + 2) * 7 % 4] ^= v;
            }
            result[4] = (byte)mazeWidth;
            result[5] = (byte)mazeHeight;
            result[0] ^= result[4] | (result[5] << 4);
            return Convert.ToBase64String(result);
        }

        // Deserialize the string data back to a maze.
        // This will trigger everyone to build the mesh locally by the data.
        // Only mazegen object owner (should be room master) can call this.
        public void DeserializeFromString(string serializedState) {
            if (!Networking.IsOwner(gameObject)) return;
            byte[] temp = Convert.FromBase64String(serializedState);
            if (temp.Length <= 6) return;
            byte[] newState = new byte[temp[4] * temp[5]];
            if (newState.Length > (temp.Length - 6) / 2) return;
            byte[] hashCode = new byte[4];
            for (int i = 0; i < newState.Length; i++) {
                newState[i] = (temp[i / 2] >> (i % 2 * 4)) & 0xF;
                hashCode[(i + 2) * 7 % 4] ^= temp[i / 2] & (0xF << (i % 2 * 4));
            }
            hashCode[0] ^= temp[4] | (temp[5] << 4);
            for (int i = 0; i < 4; i++)
                if (hashCode[i] != temp[i]) return;
            mazeWidth = rowSize = temp[4];
            mazeHeight = temp[5];
            states = newState;
            GenerateAltWalls();
            RequestSerialization();
            GenerateMesh();
        }
    }
}

This is the simple script for creating randomized and network synchronized maze in VRChat worlds.

• It generates a single wall mesh, it does not take much performance for results except when generating.
• It is network synchronized, every users in the same instance will see the same result.
• It uses randomized depth-first search algorithm for generating.
• It only depends on a single MeshFilter and MeshRenderer, optionally MeshCollider for walls collision with players.
• Maze size could be adjust by mazeWidth and mazeHeight parameter within inspector or by setting it from other UDON scripts.
• For triggering it to generate new maze, just send Generate custom event to it.
• To see this script in action, you can head to this world: 3D Maze Screensaver