A* solution for 2d isometric game
Jan 30, 2021
I needed to make a path finding solution for for the isometric game called Escape from Purrrgatory. I chose A* as it can provide optimal solution to the seeked problem, have several good references.

Main challenge with this task is that mostly examples of A* solution work with a simple grid maps, like on the picture to the right.

In order to do so I would have to understand the algorithm and modify its realization to the needs of an isometric grid.


A* allows to find the shortest path by dividing the area into nodes and then determining from which node we start the path search and to which node we are seeking path to.

At the begging we need to evaluate the nodes around the start node and assign F cost value to them. The node with the least value will be the one we are looking as a potential next step.

F value is calculated by simply adding the G and H cost values. G represents how far from the start the node is and H is how far from the end goal it is.


F value is calculated by simply adding the G and H cost values. G represents how many steps from the start node is and H is how many steps from the end node.

The values that we use to determine how much each node move costs are depending on how consuming we want them to be. For example we can make the cost of moving diagonally higher than moving vertically or horizontally. This will make it more efficient for algorithm and it will build a path accordingly.


Step by step A* is going to explore the grid by filling the nodes with the least F value. Each selected node sets selected nodes to have him as a parent. This way when A* is finally reached the end Node we can trace the path back by simply starting to access the path node parents until we reached start. The array of traced back nodes will be our seeked shortest destination.
In order to map the grid in code it is necessary to create a base node class that we will have an array of to represent out map.


public class Node
{
    public int x, y;
    public bool walkable;
    public Vector3 position;

    public int gCost;
    public int hCost;
    public Node parent;

    public int fCost { get { return gCost + hCost; } }
}
  • x,y - are simply the indexes that this node has in 2d array. // why needed
  • walkable - defines if its possible to build a path through this node or not
  • position - simply represents the node position in the real world
  • gCost is the
  • fCost
  • parent - parent of the node that will allows tracing back ones the path is found.
  • fCost is simply the sum of gCost and hCost;

Now we are able to instantiate the node map class which would be responsible for creating and accessing the 2d nodes array.

public class IsoGridMap : MonoBehaviour
{
    public Node[,] GridMap;

    [SerializeField]
    private int m_X, m_Y;

    private DirectionsModel m_DirectionsModel;

    [SerializeField]
    private Grid m_Grid;

    [SerializeField]
    private LayerMask m_LayerMask;

    public List<Node> path;

    [SerializeField]
    private bool m_ShowGrid = false;

    public void InstantiateGridMap();

    public Node NodeFromPos(Vector3 pos);

    public List<Node> GetNeighbours(Node node);

    private void OnDrawGizmos();
}
  • Node[ , ] GridMap - is the node map in a form of a 2d array
  • m_X, m_Y - is integers that define map size
  • m_DirectionsModel - is a struct that defines the vectors needed for traversing the current grid. By specifying this class we are able to abstract path finding solution from the game set up, thus when the grid size is changed or the path finding module wont be affected and will not need to be changed.
  • m_Grid - is the reference to the visual isometric unity grid we are using in the game. This way we are able to create a visual debug map in the viewport and see if the map gets created correct in relation grid.
  • int gCost is the
  • int fCost
  • Node parent - parent of the node that will allows tracing back ones the path is found.
  • int fCost is simply the sum of gCost and hCost;

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

public class PathFinding : MonoBehaviour
{
    //public Transform seeker, target;
    IsoGridMap m_IsoGridMap;
    public IsoGridMap IsoGridMap { get { return m_IsoGridMap; } }

    Transform m_PlayerPos;

    DirectionsModel m_DirectionsModel;

    //[SerializeField]
    //Transform n1, n2;


    private void Awake()
    {
        m_IsoGridMap = GetComponent<IsoGridMap>();
        m_PlayerPos = IsoGame.Access.Player;
        m_DirectionsModel = IsoGame.Access.Directions;
    }

    //find a path between two test seekers



    private void Update()
    {
        //FindPath(seeker.position, target.position);
        //soooo
        //make it possible for enemy to access it 
        //realise enemy movement
        //GetDirectionEnemy(test.position);
        //FindPath(n1.position,n2.position);
    }

    public Vector3 GetDirectionEnemy(Vector3 pos)
    {
        FindPath(pos, m_PlayerPos.position);

        if (m_IsoGridMap.path == null || m_IsoGridMap.path.Count <= 0)
        {
            return transform.position;
        }

        //convert into directions
        //m_IsoGridMap.path[0].position;

        Vector3 dir = pos - m_IsoGridMap.path[0].position;

        //m_IsoGridMap.InstantiateGridMap();

        for (int nInd = 0; nInd < 4; nInd++)
        {
            float dist = Vector3.Distance(dir, m_DirectionsModel.directionsArr[nInd]);
            if (dist <= 0.5)
            {
                return m_DirectionsModel.directionsArr[nInd];
            }
        }

        return new Vector3();
    }

    void FindPath(Vector3 startPos, Vector3 targetPos)
    {
        Node startNode = m_IsoGridMap.NodeFromPos(startPos);
        Node targetNode = m_IsoGridMap.NodeFromPos(targetPos);

        if (startNode == null || targetNode == null)
        {
            return;
        }

        List<Node> openSet = new List<Node>();
        HashSet<Node> closedSet = new HashSet<Node>();
        openSet.Add(startNode);

        while (openSet.Count > 0)
        {
            Node node = openSet[0];
            for (int i = 1; i < openSet.Count; i++)
            {
                if (openSet[i].fCost < node.fCost || openSet[i].fCost == node.fCost)
                {
                    if (openSet[i].hCost < node.hCost)
                        node = openSet[i];
                }
            }

            openSet.Remove(node);
            closedSet.Add(node);

            if (node == targetNode)
            {
                RetracePath(startNode, targetNode);
                return;
            }

            foreach (Node neighbour in m_IsoGridMap.GetNeighbours(node))
            {
                if (!neighbour.walkable || closedSet.Contains(neighbour))
                {
                    continue;
                }

                int newCostToNeighbour = node.gCost + GetDistance(node, neighbour);
                if (newCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
                {
                    neighbour.gCost = newCostToNeighbour;
                    neighbour.hCost = GetDistance(neighbour, targetNode);
                    neighbour.parent = node;

                    if (!openSet.Contains(neighbour))
                        openSet.Add(neighbour);
                }
            }
        }
    }

    void RetracePath(Node startNode, Node endNode)
    {
        List<Node> path = new List<Node>();
        Node currentNode = endNode;

        while (currentNode != startNode)
        {
            path.Add(currentNode);
            currentNode = currentNode.parent;
        }
        path.Reverse();

        m_IsoGridMap.path = path;

    }

    private int GetDistance(Node A, Node B)
    {
        if (A == null || B == null)
        {
            return default;
        }

        int dstX = Mathf.Abs(A.x - B.x);
        int dstY = Mathf.Abs(A.y - B.y);

        if (dstX > dstY)
        {
            return 10 * dstY + 10 * (dstX - dstY);
        }
        return 10 * dstX + 10 * (dstY - dstX);
    }
}
Mechanics
Raven follower
In Paula Wilder Ritt version main task was to realize a companion which follows the game character with a slight delay and when player uses special ability spins around while continuing to follow. While the following itself could be simply done by lerping the raven model towards the point with offset from the character model it creates issues when we need to rotate it around without involving complex calculations. This is solved by creating a parent for the raven model that has the player position. So by rotating it we can make raven to fly around Paula in circles without complicated positional calculations.

In order to control the precise amount of turns around the player I track how much half turns raven made and when it reached the specified amount the rotation stops.
Obstacle replacement
Main new feature that I had to implement was player super power that allows to replace all obstacles present in the screen with collectable coins. In order to do so I had to extend the obstacle and coin management systems.

I have created a separate pool for the coins to be spawned instead of obstacles. This allowed to change the variety of the spawned coins and avoid unnecessary object respawn. By triggering the ability method I am replacing the coins in the positions of the currently active obstacles while disabling them.
Beam mechanic
In Paula: Meeres Abenteurer instead of replacing all of the currently active obstacles player activates the beam which by touching obstacles destroys them. In order to avoid costly raycast I simply check if current player Y value is close enough with any of the active obstacles and if it is I move them out of the players way. This is possible because the amount of active obstacles in the scene is low and its way cheaper to check with all of them instead of calling raycast on update.
Features
Platform
Multi-platform
Genre
Endless runner
Dev environment
HTML5
Level uprectability
Levels are built upon predefined patterns and spawned in a random sequence built with a notion of non repentance.
Replay-oriented game design
Each play-through adds coins to your collection which you can spend and increase the outcome of the next run.
Online competition
Players get to compete with each other via high score tables.
Paula Wilder Ritt
Gameplay video
Development process
Initial idea
Rebuild of the Paula endless runner with new models and some game mechanic changes.
First concept
Several game setups build upon the same base. Each setup has visual and gameplay changes that have to be implemented.
First builds
Finalisation of the visual rework and main gameplay changes.
Evaluation of mechanical and visual changes
Solving the issues faced with building the game with new assets, such as effects rendering, order and stitches between spawned levels.
Beta build testing
Testing of a solid project, finding incompatibilities of mechanics and minor visual reworks. Check the game on all required platforms. Check for recurring bugs on other platforms.
Final build
Finalising and polishing followed by optimisation of the build. Final design and art changes implemented.
Daniil Khokhonov
Programming

daniilkhokho@gmail.com
Cologne, Germany
Twitter
LinkedIn
Made on
Tilda