Code Critique Request - Random Path Generator

Unity Engine
1

Hi everyone,

I’ve completed the random path generator I was trying to do and was just hoping to get a critique or two. I know it’s pretty much all basic commands, but that’s about where my knowledge currently is.

The code will generate a path across a 10 wide x 8 tall grid. The code will back itself up out of a dead end situation and when it reaches row 8 it will end the path. So far after about 20 test runs it has not failed and path length has ranged between 15 - 54 moves to complete.

Any suggestions on how I could improved the code would be greatly appreciated. Especially in the BackUp method where I used a ton of IF Else If statements to sort 4 int’s by value.

As always, thanks in advance. (And yes I am posting because I’m a bit proud I was able to do it, but really am looking for critique)

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

public class GameController : MonoBehaviour
{
    public int[,] mazeArray;
    public int startRow = 0;
    public int startCol = 0;
    public int playerRow = 0;
    public int playerCol = 0;

    private int mapCode = 0;
    private int finalCode = 0;

    private List<string> dirction = new List<string>();
    
    void Start ()
    {
        mazeArray = new int[8, 10]; // rows, columns
        dirction.Clear();           // clear list
        ResetArray();               // set all elements to 0
        GeneratePath();             // generate random path

    }
   
    void Update ()
    {
       
    }

    void ResetArray()               // Set all elements to 0 which = available space
    {
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                mazeArray[i, j] = 0;
            }
        }

        finalCode = 0;              // final code = last space in path
        return;
    }          

    void GeneratePath()
    {
        startCol = Random.Range(0, 10);             // pick starting coloumn, row is 0
        mazeArray[startRow, startCol] = mapCode = 1; // assign 1 to start square
        playerCol = startCol;
        while ( finalCode == 0 )   
        {       
            South();        // determine if directions are available
            North();
            East();
            West();
           
            SelectDir();          // random selection of available directions
        }

        Debug.Log(startRow);
        Debug.Log(startCol);
        Debug.Log(playerRow);
        Debug.Log(playerCol);
        Debug.Log(finalCode);
        return;
    }

    void North()
    {
        if (playerRow + 1 == 8)  // Array out of range
        {          
            return;
        }
        else if (mazeArray[playerRow + 1, playerCol] != 0) // space used
        {
            return;
        }
        else dirction.Add("north"); // add north to list
        return;
    }

    void South()
    {
        if (playerRow - 1 < 0)
        {
            return;
        }
        else if (mazeArray[playerRow - 1, playerCol] != 0)
        {
            return;
        }
        else dirction.Add("south");
        return;
    }

    void East()
    {
        if (playerCol + 1 > 9)
        {
            return;
        }
        else if (mazeArray[playerRow, playerCol + 1] != 0)
        {
            return;
        }
        else dirction.Add("east");
        return;
    }

    void West()
    {
        if (playerCol - 1 < 0)
        {
            return;
        }
        else if (mazeArray[playerRow, playerCol - 1] != 0)
        {
            return;
        }
        else dirction.Add("west");
        return;
    }

    void SelectDir()
    {
        int select = 0;
        string selection = "";
        if (dirction.Count != 0) // select random direction from list
        {
            select = Random.Range(0, dirction.Count);
            selection = dirction[select];
        }
        else selection = "blocked"; // no moves available

        switch (selection)
        {
            case "blocked":
                BackUp();       // back up to last avail square with move options
                break;
            case "north":
                playerRow = playerRow + 1;
                mapCode = mapCode + 1;
                mazeArray[playerRow, playerCol] = mapCode;
                if (playerRow == 7)
                {
                    finalCode = mapCode;    // set final square if row 7
                }
                dirction.Clear();
                break;
            case "south":
                playerRow = playerRow - 1;
                mapCode = mapCode + 1;
                mazeArray[playerRow, playerCol] = mapCode;
                dirction.Clear();
                break;
            case "east":
                playerCol = playerCol + 1;
                mapCode = mapCode + 1;
                mazeArray[playerRow, playerCol] = mapCode;
                dirction.Clear();
                break;
            case "west":
                playerCol = playerCol - 1;
                mapCode = mapCode + 1;
                mazeArray[playerRow, playerCol] = mapCode;
                dirction.Clear();
                break;
            default:
                break;          
        }
        return;
    }

    void BackUp()
    {
        mazeArray[playerRow, playerCol] = -1; // set element to indicate no movement
        mapCode = mapCode - 1;      // set to previous map code
        dirction.Clear();

        int tempN = 0;
        int tempS = 0;
        int tempE = 0;
        int tempW = 0;
       
        // start logic to determine last space before dead end.
        // gets mapCode for surroundind square, assign to temp int.

        if (playerRow < 7)
        {
            tempN = mazeArray[playerRow + 1, playerCol];
        }

        if (playerRow > 0)
        {
            tempS = mazeArray[playerRow - 1, playerCol];
        }

        if (playerCol < 9)
        {
            tempE = mazeArray[playerRow, playerCol + 1];
        }

        if (playerCol > 0)
        {
            tempW = mazeArray[playerRow, playerCol - 1];
        }

        // determine highest value of temp int's. Highest value is the
        // square previous to dead end. Set playerRow or or playerCol accordingly.
        
        if (tempN > tempS)
        {
            if (tempN > tempE)
            {
                if (tempN > tempW)         
                {
                    playerRow = playerRow + 1;
                    return;
                }
                else
                {
                    playerCol = playerCol - 1; 
                    return;
                }
            }
            else if (tempE > tempW)
            {
                playerCol = playerCol + 1;
                return;    
            }
            else
            {
                playerCol = playerCol - 1;
                return;
            }
        }
        else if (tempS > tempE)
        {
            if (tempS > tempW)
            {
                playerRow = playerRow - 1;
                return;
            }
            else
            {
                playerCol = playerCol - 1;
                return;
            }
        }
        else if (tempE > tempW)
        {
            playerCol = playerCol + 1;
            return;
        }
        else
        {
            playerCol = playerCol - 1;
            return;
        }
    }
}
2

Just to be clear that I understand what the algorithm is doing:

  1. Creates an n x m array of ints all set to 0.
  2. Randomly pick a start square on top row at (0,random) . set its value to 1.
  3. Find all valid squares around the current square such that valid :
  • Its inside the grid
  • its value is 0. You haven’t visited this square
  1. Pick a random direction among the valid ones.
  • Set its value to the next value (n+1)
  • loop back to 3

  1. If there is no valid random direction backup to the last square before this one and pick a valid direction. Repeat the backup process till we find a random direction that works

  2. when we hit the bottom row call that our end square and finish. The numbers 1…n. will show our random path inside this open grid.

There is no need to worry about obstacles such as walls, our only blocks are we can’t go somewhere we already walked.

3

A few things stand out straight away:

  • You mispelled direction
  • You have your array a set size that can never be changed, this should be settable from the editor
  • You have a bunch of hardcoded values, so if you did ever change the array size you have a bunch of changes to make. With the array you can call GetLength and pass through a number, 0 being for the first value and 1 for the second
  • Your backup function does alot to remember the previous position, why not just store it?
  • Instead of strings use enums for your directions, they are easier to add to and get autocompleted unlike strings
  • Why do you store directions and not the nodes position?
  • You run the risk of getting trapped in your while loop, maybe randomly pick the amount of moves it will take to get to the , that way if you ever wanted to limit it you have some control.
  • your path can easily end up going back on itself
3 Likes
4

lordconstant is pretty spot on. The point about hard-coded size is really important. Modifying the size of your maze is a drag now… There’s a couple of more things:

Don’t keep the empty Update method around. There’s actually a (very, very) slight overhead to having it there, but more importantly don’t have empty methods around for no reason.

You have a lot of unneccessary return statements. You can return every single of the 23 returns from your code, and it’d be doing exactly the same thing. This is because you’re doing this a lot:

void SomeMethod() {
    if (a) {
        //Do something)
        return;
    }
    else if (b) {
        //Do something else
        return;
    }
    else {
        //Do the third thing
        return;
    }
}

Which is redundant. See BackUp, it has a ton of return statements, and none of them do anything.

You don’t need to have “array” in the name of your arrays. mazeArray could simply be “maze”, but “grid” is better. This will also cause your methods to get better names; ResetArray is very generic, and could be any array.

The “direction” list also has a bad name. It’s a list of clear directions, which should be baked into the name.

Your coordinate system is strange. Rows are horizontal, which means that they’re different from each other on the y-axis. So the x-coordinate is usually the column coordinate, and the y-coordinate is usually the column coordinate. You’ve inversed that.

Don’t encode information in ints and strings unless the information is about ints and strings. finalCode is either 0 or some other value, and you only check wheter it’s 0 or not. That’s a bool. The strings you’re encoding information in could be an enum.

Your North, South, East and West methods are the same method, which checks two things; if the index is in bounds, and if the index is blocked. You can simplify that by writing methods that check if a position is in bounds, and if an index is blocked.Then you don’t have four methods that are basically copies of each other with some different indexes.
In the same way, your SelectDir method’s switch statement does exactly the same thing four times, just with different indexes. That can be simplified.

Finally, you should really create a data structure for your player position. Here’s an idea:

public struct Position
{
    public int x, y;

    public Position(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public static Position operator +(Position a, Position b)
    {
        return new Position
               {
                   x = a.x + b.x,
                   y = a.y + b.y
               };
    }

    public override string ToString()
    {
        return string.Format("(x = {0} | y = {1}", x, y);
    }
}

The operator there makes you able to add positions, so you can do something like:

Position north = new Position(1, 0);
playerPos = playerPos + north;

Now you’ve moved the player to the north!

Using that, your while-loop can be replaced with this:

while ( finalCode == 0 )
{
    if(CanMoveTo(playerPos + South))
        direction.Add(South);

    if(CanMoveTo(playerPos + North))
        direction.Add(North);

    if(CanMoveTo(playerPos + East))
        direction.Add(East);

    if(CanMoveTo(playerPos + West))
        direction.Add(West);

    SelectDir();
}

It’s just as easy (probably easier) to read than North(); East(), etc, pluss it removes a lot of almost identical code. Using that and the removal of redundant returns, I reduced your code length by 1/5th

Note that I’ve replaced the direction list with a list of Position. This allows for removing the entire switch-statement from your SelectDir. I’ll leave figuring that out to you.

(Not quite sure about the “Position” name - it’s also used to indicate a direction. But I just got up and haven’t had breakfast, so I’m not able to come up with anything better)

1 Like
5

First of all I want to thank everyone that took time to look at my code and format a reply. If your lives are anywhere as busy as mine I realize how important your time is. I will try to address each post though it may take a little time to comprehend a few thing from just a quick glance through.

takatok’s post made me think that I probably should have explained things a little better. About 4 years ago I made a Mod for a dungeon crawler which featured a room where the player had to cross a grid in a particular path. The path is unknown, other than the starting square. The player had to guess the next square to step on. If they guessed right the square turned green, wrong and it turned red and they were sent back to the start, no penalty for guessing wrong. The grid reset and they start over. If they step on the same incorrect grid again, Then they would take damage. In effect a glorified memory game. But with the Mod it was done mostly with triggers built into the editor, not much programming.

I have been trying to think of small projects to work on to build up some working knowledge and figured I would try to recreate that room in Unity. As started thinking about how to go about it I thought why use a fixed path and thus the attempt to find a way to make the level generate a random path for replayability. Not quite sure how to implement everything in Unity yet, but will figure that out as I go. I’m just happy I was able to get the path generator working as I questioned my abilities.

And with that summary, I will address everyone’s thoughtful replies throughout the day as time allows.

takatok, you pretty much nailed what the code is doing. Thanks for the input.

6

Thanks for the input lordconstant.

Good catch on the misspelling of direction. That explains why sometimes intellisense didn’t always have it listed. It also shows I probably rely on intellisense too much. Item 1 on my list is to correct the spelling and change it to clearDirection as Baste recommends.

As for the array size, I actually started experimenting in Visual Studio before Unity and I made my array size randomized, but when I moved to Unity I made it fixed because I didn’t think the room size is going to change. Item 2 and 3 - make array adjustable and lose the hard coded values. Single dimension arrays are easy, but I will need to read up on multi dimension arrays to see how length works. Arrays are actually in the next chapter of the book I’m working through.

In BackUp(), not sure how I would go about storing the previous position, especially when it may have to back up out of multiple positions. In one test is successfully backed out of 14 positions before it found a viable choice. All back up is doing is reading the four squares around the current position to find which has the highest mapCode value, which would be the previous position. I’m sure there is a better way to code it. As for storing it, what would be some possibilities, a new array to store the path, or a list maybe? I haven’t got into writing files yet. Item 4 - re evaluate BackUp method.

Ah, the dread enum. I had a post here a few days ago about them in fact. I just went through those in the book and was somewhat confused by them. I did stop and think about finding a place to use them, but bailed on the idea.
Guess it’s time I buckle down and figure them out. Item 5 - use enums.

I do not understand your next question about storing node positions. Is that not what the array is equivalent to, a node position?

During my testing I kept a test int incrementing in the loop and made it part of the conditional to break the loop if needed. At first I would use it to limit to a few moves then I would graph the results, check behavior, make adjustments as needed, the retest. And yes, it did save me from an endless loop a couple times. But once it tested out fine a dozen times I took it out. But I understand the concern, so I will put it back in as a safety and have it through a Debug if it reaches the limit. Item 6 - add loop safety.

Not sure I understand your last statement. If you are saying the path can go back on itself during generation, that is true. That is the entire point of the BackUp method. If you are saying it will create path over the exiting path generated so far, not sure how that will happen. It will only generate the path if the array element has a value of 0.

Again I appreciate the time you took and value your suggestions. I will make the changes, after analyzing Baste’s post and re submit the code. Will probably take a few days to get around to it. Busy weekend planned.

7

Baste,

Thank you for taking the time to reply.

I have been removing Start & Update from scripts where I don’t need it, but in this case it will be used eventually. I am probably going to move this entire generation process onto it’s own script once I get it honed down.

I wasn’t sure about the return statements. I wasn’t using them before, but I read somewhere in the forums it helps to have them in. But I must have misunderstood the post and maybe there is a specific case where it helps. Good to know I can go back to using them only when needed.

Thanks for all the naming suggestions. I will make the appropriate changes and look for better ways to name future scripts.

As for the coordinate system, I didn’t know there was a specific way they had to be organized. Arrays are in the next chapter of the book I’m reading, so I just looked up the basic syntax on how to write it and figured out how to use it in the way that made sense to me. Hopefully I’ll the proper way when I get to the next chapter.

I try to use bools when I can, but in the case of finalCode I will eventually need to compare it to another int and if I make it a bool now, I don’t know how I could compare it later.

Looking over the code now I see the many places I could have simplified as you so kindly point out. I did it in the BackUp method by putting the 3 lines at the top and not in each if statement, (after I started typing it in for the 3rd time I realized it was the same in all cases). And after you pointed it out I see it in the other areas as well.

Not sure what you are doing with the struct yet, but it is the next subject in the book, so I will look closer at that part of your post once I read the section on structs. It should make more sense then.

Again I appreciate your input.

1 Like
8

I made a few mistakes when I read your code, was on my phone so I got slightly confused with how it was working.

For the array size issue you can do something like:

//The number is the dimension of the array
int colCount = maze.GetLength(0);
int rowCount = maze.GetLength(1);

For the back up to be more efficient, if you store the positions as you find them in a list then you can simply go back through the array:

using System.Collections.Generic;

List<Vector2> path = new List<Vector2>();

void SelectDir()
{
//Code to decide dir here

//you may want these as playerRow then playerCol as baste pointed out you have these the wrong way around currently
path.Add(new Vector2(playerCol, playerRow));
}

void BackUp()
{
if(path.Count <= 0)
return;

Vector2 lastNode = path[path.Count-1];
playerCol = lastNode.x;
playerRow = lastNode.y;
path.RemoveAt(path.Count-1];
}

Onto enums! When I first started I couldn’t work out why they were useful or remember how they worked, then I realised they are just easier for making things more manageable.

Enums are just numbers with names. The first on in a list will generally be 0, then the next 1, then 2, etc…
The names are unique in the current enum, so you can’t have “enum MYENUM{ VAL, VAL, VAL }”, but you can do:

enum ENUMONE { VAL, CAKE, SHEEP }
enum ENUMTWO { CAKE }

Heres a simple enum declaration:

class PathGenerator
{
//Declaring our enum
//MOVEDIRS is its name (capitals are optional, but I use them to help remember it's an enum)
//NORTH = 0 -  It should generally start at 0 by itself, but for safety setting the first one to 0 will make sure of it
enum MOVEDIRS {NORTH = 0, SOUTH, EAST, WEST};

//Declare a variable for using our enum
//This could just be an int (int curMoveDir) but this way intellisense will work with it
MOVEDIRS curMoveDir;

void SomeFunction()
{
    curMoveDir = MOVEDIRS.NORTH;

    switch(curMoveDir)
    {
        case MOVEDIRS.NORTH:
        {
            //Some code here
         }
         break;
        case MOVEDIRS.SOUTH:
        {
            //Some other code here
         }
         break;
    }
}
}
}

I’ve covered storing the node positions in the back up bit above.

I don’t think it’s possible to trapped in your loop now, unless you ever wanted to add walls or anything of the sort.
This is due to how you handle backing up. If you ended up backing all the way to the start with no way to go you would end up stuck in an endless loop.

After reading the code again the point about a set amount of moves is less important & the actual implementation for generating a path given the amount of steps wanted would require more complex pathfinding.

I was wrong about your path being able to go back on itself, that was a mistake in understanding what was going on.

If you need any more clarification on anything just ask :slight_smile:

9

Thanks for the update lordconstant.

I didn’t think I was going to get a chance to work with it this weekend, but managed to squeeze in a little time last night (before I noticed your update). Here is the updated code, without addressing the BackUp method yet. I used a enum for the directions, got rid of some duplicate code, got rid of some hard coded stuff, hopefully made some better naming, moved it to it’s own script (now called from game manager instead of being on the game manager). I left the array layout as is, even though it is backwards, because it is functioning in it’s own little scope and would require a whole bunch of rewriting the script.

edit: Also in the process I realized whenever the position hit a outside column, if it went south it would always be a dead end, so added code to disable south on an outside column.

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


public class PathGenerator : MonoBehaviour
{

    public int[,] grid;             //path storage array

    public int startRow = 0;        //start quad - needed to reset player to start
    public int startCol = 0;        //after incorrect guess

    public int playerRow = 0;       //player position in grid,
    public int playerCol = 0;       //doubles as path generation marker

    public int gridRows = 8;        //set grid rows & columns
    public int gridColumns = 10;

    public int mapCode = 0;         //store quad position in path and availability during generation
    public int finalCode = 0;       //indicates final quad - match with mapcode to indicate success

    public int loopSafetyMax = 300;  //control while loop safety

    public enum Direction { North, South, East, West, Blocked };
    private List<Direction> clearDirection = new List<Direction>();


    void Start()
    {
        grid = new int[gridRows, gridColumns];  //rows, columns
        clearDirection.Clear();                 //clear list
        ResetGrid();                            //set all elements to 0
    }

    void ResetGrid()    //Set all elements to 0 which = available space
    {
        for (int i = 0; i < gridRows; i++)
        {
            for (int j = 0; j < gridColumns; j++)
            {
                grid[i, j] = 0;
            }
        }

        finalCode = 0;              //final code = last space in path
    }

    public void GeneratePath()
    {
        playerCol = startCol = Random.Range(0, gridColumns);    // pick starting coloumn, row is 0
        grid[startRow, startCol] = mapCode = 1;     // assign 1 to start square

        int loopSafety = 0;                 //use for preventing endless loop
     
        while (finalCode == 0 && loopSafety < loopSafetyMax)
        {
            AvailableMoveCheck();           //determine if directions are available
            SelectDir();                    // random selection of available directions

            loopSafety++;
            if (loopSafety >= loopSafetyMax)
                Debug.Log("Loop exceeded maximim allowed attempts.");

            Debug.Log(finalCode);
            Debug.Log(grid[playerRow, playerCol]);
        }
    }

    void AvailableMoveCheck()
    {
        if ((playerRow + 1 < gridRows) && (grid[playerRow + 1, playerCol] == 0))
            clearDirection.Add(Direction.North);

        if ((playerRow - 1 >= 0) && (grid[playerRow - 1, playerCol] == 0))
        {
            if (playerCol != 0 && playerCol != gridColumns - 1) //prevent going south into dead end
                clearDirection.Add(Direction.South);
        }

        if ((playerCol + 1 < gridColumns) && (grid[playerRow, playerCol + 1] == 0))
            clearDirection.Add(Direction.East);

        if ((playerCol - 1 >= 0) && (grid[playerRow, playerCol - 1] == 0))
            clearDirection.Add(Direction.West);         
    }

    void SelectDir()
    {
        int select = 0;
        Direction selection;
        if (clearDirection.Count != 0) // select random direction from list
        {
            select = Random.Range(0, clearDirection.Count);
            selection = clearDirection[select];
        }
        else selection = Direction.Blocked; // no moves available

        if (selection != Direction.Blocked)
        {
            if (selection == Direction.North)
                playerRow = playerRow + 1;
            else if (selection == Direction.South)
                playerRow = playerRow - 1;
            else if (selection == Direction.East)
                playerCol = playerCol + 1;
            else if (selection == Direction.West)
                playerCol = playerCol - 1;

            mapCode = mapCode + 1;
        }
        else if (selection == Direction.Blocked)
        {
            grid[playerRow, playerCol] = -1; // set element to indicate no movement available
            BackUp();                   // find previous quad
            mapCode = mapCode - 1;      // set to previous map code

        }
        else
            Debug.Log("Path Failed");
 
        grid[playerRow, playerCol] = mapCode;
        clearDirection.Clear();

        if (playerRow == gridRows - 1)
            finalCode = mapCode;
    }

    void BackUp()
    {
        Debug.Log("In Back Up");
        int tempN = 0;
        int tempS = 0;
        int tempE = 0;
        int tempW = 0;

        if (playerRow < 7)
        {
            tempN = grid[playerRow + 1, playerCol];
        }

        if (playerRow > 0)
        {
            tempS = grid[playerRow - 1, playerCol];
        }

        if (playerCol < 9)
        {
            tempE = grid[playerRow, playerCol + 1];
        }

        if (playerCol > 0)
        {
            tempW = grid[playerRow, playerCol - 1];
        }

        // determine highest value of temp int's. Highest value is the
        // square previous to dead end. Set playerRow or or playerCol accordingly.

        if (tempN > tempS)
        {
            if (tempN > tempE)
            {
                if (tempN > tempW)
                {
                    playerRow = playerRow + 1;
                }
                else
                {
                    playerCol = playerCol - 1;
                }
            }
            else if (tempE > tempW)
            {
                playerCol = playerCol + 1;
            }
            else
            {
                playerCol = playerCol - 1;
            }
        }
        else if (tempS > tempE)
        {
            if (tempS > tempW)
            {
                playerRow = playerRow - 1;
            }
            else
            {
                playerCol = playerCol - 1;
            }
        }
        else if (tempE > tempW)
        {
            playerCol = playerCol + 1;
        }
        else
        {
            playerCol = playerCol - 1;
        }
    }
}