Maze Solving

So this is my first post. Whoot whoot! 🙂
As a result I have no idea what I am doing but I really wanted to give writing a few tutorially/dev-bloggy type posts a go as I was working on things.

This post will be about implementing the pledge algorithm in unity2d using C#, and will include code examples as we go. I’ll be writing the code and working through the process as I’m writing this post, so I will just write things out as I do them. Let’s see if the process works. If not, I’ll try something new next time.

So, for the game we are currently working on we have four knights traversing a maze. This maze will be constantly changing with user interaction and our heroes must find their way home.

Well, we tried different – what we thought were predictable – ways that the agent would move when coming to a certain tile junction, but after some play testing this seemed to be the cause of a lot of frustration for players as there was no context of the maze as a whole and the agents moved in a non intuitive manner. In this iteration, one of the big changes we will therefore be making is the agent AI, and I will be rambling about it here.

What is the Pledge Algorithm and why would we use it?

The aim of our AI is not to have a perfect maze solving algorithm but more to have our agents move in a way that represents normal human traversal. We wanted a maze solving method that is able to be used inside of the maze with no context of the maze as a whole. We wanted the agents to react directly to what is in front of them and to move towards their end goal without making (too many) stupid and seemingly random decisions. The problem with using most traditional maze solving algorithms is that they rely a lot on memory. A good example of this is the tremaux algorithm in which the agent draws a line behind them as they move down a passage to mark the path and tries not to move down the same passage more than twice at a maximum. If a method like this were to be employed for us the information would far too quickly be out of date and what is now a new route would not be taken as it would be marked as having previously been taken. Another standard algorithm for maze solving is the A* algorithm. This gives a nice elegant solution for finding the shortest distance between two points. Unfortunately, with our game, there will not necessarily be even one full path between the start and end position at any point therefore we can’t employ this method.

The most basic memoryless maze solving algorithm is the wall follower. This is a very simple algorithm, Essentially, the agent just follows passages and whenever they reach a junction they always take a predefined direction (the human equivalent is putting your hand on the right (or left) wall and leaving it there as you walk through). The pledge algorithm is a modified version of the wall follower. The difference here is that it is able to jump between islands which allows it to solve mazes that the wall follower cannot and is guaranteed to reach an exit on the outer edge of any 2D maze, such as our use case! Hurray! 🙂 Another thing that makes this method appropriate is that it can find the exit from any point inside of the maze; as the tiles will be moving around we cannot rely on the criteria of the basic wall follower which is that your starting point is at an outer edge of the maze. As any given tile is moved we can consider the character location as it’s starting position. If you are thinking of using this method however you should note that this method will not allow you to find an end point that is located within the maze.

This solution appears to be ideal for the AI of our homing knights as they can get out of any maze without having to mark or remember the path in any way. This will hopefully solve the issue with the changing nature of our maze. Of course if the maze is always changing the characters may end up wandering forever but each new route will not require reinitialisation of the algorithm and will keep memory overhead low. As I said before, we’re not looking for perfect maze solving, just natural movement.

Movement rules

What follows are the rules I intend to implement in our game, based on the pledge algorithm.

  1. Choose a direction (in our case, straight ahead)
  2. Always move in this direction when possible
  3. Hit a wall -> wall follow until chosen direction is available again, which means
    1. count the number of turns you make while keeping the obstacle on one side (to the left in our case)
      e.g left turns = -1 and right turns = +1 (these assignations are arbitrary)
    2. When count = 0 go back to moving in chosen direction
      (This counting ensures you can get around any island and not just go back the way you came from as would happen with the traditional wall follower method)

In essence, move in a given direction then wall follow until you get around it, go back to moving in the chosen direction.

Laying out a tile based maze in unity.

Our game consists of 5 different tile types. Some of these may be arranged with different rotations which will affect their path in the maze.

1. Block ( One orientation only)

block

2. Crossroad (one orientation only)

crossroad

3. turn ( Four different orientations)

right-angle right-angle - Copy (2) right-angle - Copy right-angle - Copy (3)

4. T-junction (4 different orientations)

t-junction t-junction - Copy t-junction - Copy (2) t-junction - Copy (3)

5. straight (vertical or horizontal)
straight straight - horiz

The grid we plan to use is 5×5 therefore we need 24 tiles in total for our grid (plus the one missing tile for sliding). The above gives 12 different combinations, so for now we will just use two of each tile. Later we may look at some maze generation algorithms in order to ensure every board is solvable.

Right now we will work with a maze that I threw together in unity. You can see this board below. I have made sure there is a clear path from our yellow knight’s start position at the red castle to his end position at the yellow castle. This is just to simplify implementation for now.

ExampleBoard

Character movement and traversing the maze

To simplify character movement we will break each tile into a 9×9 grid of 1s and 0s where a 0 represents a wall and a 1 represents a path.

For example, our t-junction t-junction - Copy will turn into 3by3grid.

In unity I have simulated this by creating a tile, this is a 2d sprite game object, with 9 child objects laid out in the above configuration.

crossroad

Each child node has a 2d box collider and a script attached to it which merely returns an enum value stating what kind of node it is. For my purposes a node can have one of four values, that is wall, path, slot or home. For the purposes of this post we will only be using wall and path (though slot refers to the missing tile for sliding into with home being the end destination and goal).

node
Here is the tile script (in hindsight, I should probably have called this script node rather than tile – sorry for any confusion caused):

using UnityEngine;
using System.Collections;
public class Tile : MonoBehaviour
{
    public Type type;
    public enum Type
    {
        Wall,
        Path,
        Home,
        Slot
    };
    
    public Type GetType ()
    {
        return this.type;
    }
    
    public static bool CanTraverse (Tile node)
    {
        return node.type == Type.Path || node.type == Type.Home;
    }
} 

Our movement currently consists of:

1. Check next tile

For this we need to simulated sensing in the 3 directions: forward, left and right. To do this I chose to use 2d raycasting. I need to disable the collider of the node I am standing on then cast a ray in the directions I am interesting in. This will return a boolean response based on if the node is a path or not. The collider is then re-enabled on the node. It seems like there is probably a better way to do this, I thought of maybe using layer masks or something but it seems to be much of a muchness. If you have any suggestions, let me know in the comments 🙂

2. Make a decision

There are two states of motion here. We are either moving normally, (i.e. in our chosen direction) or we have hit an obstacle and are thus now in the pledge algorithm. The first state is obvious enough, just keeping moving forward. The second state is entered upon meeting the first obstacle.

On hitting the obstacle the first thing we want to do is to put this obstacle on our chosen side.  We have chosen the right hand side algorithm which means we want to keep the obstacle on our left. To do this, the first thing we will do is turn right. Every time a turn is made we increment or decrement a counter, +1 for a right turn and -1 for a left turn for example. We continue sensing and moving with the objective of keeping the obstacle on our left until the counter gets back to zero. At this point we have traversed the obstacle and continue moving in our chosen direction until another obstacle is encountered.

The script for movement is here. Feel free you use or discard at your own want 😉

using UnityEngine;
using System.Collections;

public class Controller : MonoBehaviour
{
    public static float STOPPED = 0.0f;
    private Vector2 direction;
    private Animator animator;
    public static Vector2 RIGHT = new Vector2 (1.0f, 0.0f);
    public static Vector2 LEFT = new Vector2 (-1.0f, 0.0f);
    public static Vector2 UP = new Vector2 (0.0f, 1.0f);
    public static Vector2 DOWN = new Vector2 (0.0f, -1.0f);
    public static Vector2 STOP = new Vector2 (0.0f, 0.0f);
    public Vector3 startDirection;
    new string name;
    private Vector3 endPosition;
    private bool moving = false;
    private float duration = 50f;
    
    // Pledge Algorithm
    private bool rightSensor;
    private bool leftSensor;
    private bool frontSensor;
    private bool isPledge = false;
    private int pledgeCounter = 0;
    private Vector3 nextNodePosition;
    
    void Start ()
    {
        animator = this.GetComponent ();
        direction = startDirection;
    }
    
    void Update ()
    {
        UpdateAnimation ();
        if(moving) {
            MoveToNextNode ();
            } else {
            DoSense ();
            if (isPledge) {
                MovePledge ();
                } else {
                MoveNormally ();
            }
        }
    }
    
    private void MoveToNextNode ()
    {
        if (!Mathf.Approximately (gameObject.transform.position.magnitude, endPosition.magnitude)) {
            gameObject.transform.position = Vector3.Lerp (gameObject.transform.position, endPosition, 1 / (duration * (Vector3.Distance (gameObject.transform.position, endPosition))));
            } else {
            moving = false;
        }
    }
    
    private void MoveNormally ()
    {
        if (frontSensor) {
            MoveForward ();
            } else {
            TurnRight (); // obstacle is now on left
            isPledge = true;
        }
    }
    
    private void MovePledge ()
    {
        if (leftSensor) { // obstacle is not on my left
            TurnLeft ();
            MoveForward ();
            
            } else { // obstacle is on my left
            
            if (frontSensor) {
                MoveForward ();
                } else {
                TurnRight ();
            }
        }
        isPledge = pledgeCounter != 0;
    }
    
    private void DoSense ()
    {
        RaycastHit2D hit = Physics2D.Raycast (transform.position, direction, 0.1f);
        hit.collider.enabled = false;
        leftSensor = LookLeft ();
        rightSensor = LookRight ();
        frontSensor = LookForward ();
        hit.collider.enabled = true;
    }
    
    private bool LookLeft ()
    {
        RaycastHit2D hit = Physics2D.Raycast (transform.position, GetLeftDirection (), 0.8f);
        if (hit.collider == null)
        return false;
        Tile node = hit.transform.gameObject.GetComponent ();
        if (node.type == Tile.Type.Path) {
            return true;
        }
        return false;
    }
    
    private bool LookRight ()
    {
        RaycastHit2D hit = Physics2D.Raycast (transform.position, GetRightDirection (), 0.8f);
        if (hit.collider == null)
        return false;
        Tile node = hit.transform.gameObject.GetComponent ();
        if (node.type == Tile.Type.Path) {
            return true;
        }
        return false;
    }
    
    private bool LookForward ()
    {
        RaycastHit2D hit = Physics2D.Raycast (transform.position, direction, 0.8f);
        if (hit.collider == null)
        return false;
        Tile node = hit.transform.gameObject.GetComponent ();
        if (node.type == Tile.Type.Path) {
            nextNodePosition = node.transform.position;
            return true;
        }
        return false;
    }
    
    void UpdateAnimation ()
    {
        if (direction.y > 0) {
            animator.SetInteger ("direction", 2);
            } else if (direction.y < 0) {
            animator.SetInteger ("direction", 0);
            } else if (direction.x > 0) {
            animator.SetInteger ("direction", 3);
            } else if (direction.x < 0) {
            animator.SetInteger ("direction", 1);
        }
    }
    
    private void ChangeDirection ()
    {
        direction = -1 * direction;
        
    }
    
    private void Stop ()
    {
        direction = STOP;
        transform.Translate (direction);
    }
    
    private void MoveForward ()
    {
        DoSense ();
        endPosition = nextNodePosition;
        moving = true;
    }
    
    private void TurnRight ()
    {
        direction = GetRightDirection ();
        pledgeCounter++;
    }
    
    private Vector3 GetRightDirection ()
    {
        if (direction == RIGHT) {
            return DOWN;
            } else if (direction == LEFT) {
            return UP;
            } else if (direction == UP) {
            return RIGHT;
            } else if (direction == DOWN) {
            return LEFT;
        }
        return STOP;
    }
    
    private void TurnLeft ()
    {
        direction = GetLeftDirection ();
        pledgeCounter--;
        
    }
    
    private Vector3 GetLeftDirection ()
    {
        if (direction == RIGHT) {
            return UP;
            } else if (direction == LEFT) {
            return DOWN;
            } else if (direction == UP) {
            return LEFT;
            } else if (direction == DOWN) {
            return RIGHT;
        }
        return STOP;
    }
    
}

Executing the code should result in movement something like this gif. As you can see he makes it home but as I haven’t included any of the win condition stuff here he’ll just see it as another wall and wander off again.

example-board

I hope this post was of some use to someone somewhere and I’d love some feedback on how to make things better so if you have any comments or questions please post below and I’ll try my best to get back to you 🙂

All the best,

Tracey Spiderwinkle x

Leave a Reply

Your email address will not be published. Required fields are marked *