Implementation of the wave algorithm for finding the shortest path to dynamically moving objects in unity3d on C # in a 2d game

In this article I want to show how to implement the wave algorithm and my modification of it to work with dynamic objects in unity3d.

Application area

This method is suitable for 2D games. And its modification to find the path to moving objects. The scope is very extensive and covers many game genres and situations, for example:

1. Games genre TD. Where game locations are conveniently represented in the form of a cross-country matrix, for example, 0 is the area along which you can move, -1 is the area unavailable for movement, -2 is a trap, etc .;
2. Strategy games, especially turn-based. For example, fighting in the series of games “Heroes of Might and Magic”;
3. Platformers;
4. Checkers, chess, snake and others.

Justification for writing an article

There are quite a lot of articles on working with algorithms for finding the shortest path on the Internet, but all the same they constantly create topics on the forums and ask questions “how to find the way to the object”. I highlighted several reasons why this article has the right to exist:

1. For unity3d, there are many algorithms for finding the shortest paths in the form of assets, that is, ready-made solutions. But sometimes it is worth not to take a ready-made solution, but write your own, optimal specifically for your case. Especially if there are many objects in the game, then a poor implementation of the algorithm can greatly affect performance. And the more performance will suffer if these objects are many and they change their location;
2. The standard version of the wave algorithm is not the best option for dynamic objects, so I want to show its modification, which I developed while working on my strategic game;
3. On the Internet, there are no good, simple, articles on the implementation of the wave algorithm in unity3d.

Description of the wave algorithm

There is a starting position S and a point F, which you need to reach avoiding obstacles by the shortest route. The wave algorithm is one of the fastest and most efficient, but running ahead will tell you why it is not ideal for finding a way to moving objects. In case the object stands still, we can once find the path to it and start moving. But if this object moves, then we need to recalculate the path to it every game tact, that is, every call to the Update () method.

And if you have in the game involved hundreds or thousands of units? And everyone counts the path, and even each call to the Update () method? For example, a battle of 500 by 500, at 30 frames per second, will have to call the FindPath () method 1000 * 30 = 30,000 times per second.
')
To work we need a discrete working field, or just a map of the location presented in a matrix form.

 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
 -1 0 0 0 0 0 0 0 -1
 -1 0 0 0 0 0 0 0 -1
 -1 0 0 0 0 0 0 0 -1
 -1 0 0 -1 -1 -1 -1 0 0 -1
 -1 0 0 0 0 0 0 0 -1
 -1 0 0 0 0 0 0 0 -1
 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Example of location map (or cross-country matrix):
-1 - impassable area, wall or log.
0 - passable area.

Algorithm

Initialization

   0 d := 0 

Wave propagation

     loc,   d         d + 1  d := d + 1  (   )  (   ,  <  ) 

Recovery path

              ,    1                  —           

Algorithm implementation in unity3d

The demonstration will be held on the example of a prototype of my strategic game. There is a player’s side and an opponent’s side, the task of the warriors is to find the nearest enemy, reach it bypassing other warriors and obstacles and start the battle.

1. For debugging it will be convenient to divide the playing field into cells and display them. For convenience, at this step you can make the coordinates of the first cell equal to (0,0), adjacent to the right (0.1), and so on.
   
2. Now create a class Battlefield.cs and attach it to the object "field" using the inspector.
   
   Battlefield.cs

    using UnityEngine; using System.Collections; public class Battlefield2 : MonoBehaviour { public static int[,] battlefield; //   public int enemyNumber = 6, playerNumber = 3; //public      public static int x, y; //     public GameObject enemyMilitiaman; //   public GameObject swordsmanGO; // . public static bool ready = false; //     ,      . void Start () { battlefield = new int[,]{ //   . 1 - . 0 -   {1,1,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; setEnemyPosition (enemyNumber); //     setPlayerPosition (playerNumber); //    ready = true; //     } // Update is called once per frame void Update () { } void setEnemyPosition(int numberEnemies){ ////// //////     ,      1   (14,2) ///// //    GameObject go = Instantiate(enemyMilitiaman, new Vector3(14, 2, 10), Quaternion.identity) as GameObject; battlefield[14, 2] = 1; //     ,  ,    , . } void setPlayerPosition(int numberPlayerWarior){ ////// //////     ,      1   (2,6) ///// GameObject go = Instantiate(swordsmanGO, new Vector3(2, 6, 10), Quaternion.identity) as GameObject; battlefield[2, 6] = 1; } public static void printMatrix(){ string arr = ""; for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { arr += battlefield[i,j] + ","; } arr += "\n"; } print (arr); } } 

   
   
   
   The code is commented out and should not cause you any difficulties.
   
   In the Battlefield class, we create a location map (matrix) describing our location. Dale call the methods that place the player and the enemy units on the playing field. In the same methods, write to the cell of the matrix on which the unit was placed, that it is already occupied and make it impassable by changing the value from 0 to 1. That is why it was important to make cell coordinates in the playing field integers and start counting from (0,0). Then when creating an object, its coordinates will coincide with the coordinates of the cell in the matrix.
   
3. Now create the swordsman class Swordsman.cs and hang it on the swordsman’s prefab
   
   Swordsman.cs

    using UnityEngine; using System.Collections; using System; public class Swordsman2 : Warrior { private Vector3 currentPosition; private Vector3 lastPosition; private bool ready = true; private bool readyAttack = true; private bool endBattle = false; private GameObject closestEnemy; //  GameObject[] gos; //    private float waitMove; //      void Start () { currentPosition = transform.localPosition; //    lastPosition = currentPosition; //    . //        waitMove = UnityEngine.Random.Range (0.4f, 0.65f); } void Update () { //        if (Battlefield.ready) { if(ready){ //  ,     Enemy gos = GameObject.FindGameObjectsWithTag("Enemy"); if(gos.Length == 0){ endBattle = true; //   ,    print ("End Battle"); } //і  і,  і if(!endBattle){ //      GameObject goClosestEnemy = findClosestEnemy(); int targetX, targetY; targetX = (int)goClosestEnemy.transform.localPosition.x; targetY = (int)goClosestEnemy.transform.localPosition.y; int[,] cMap = findWave(targetX, targetY); //      if(!stopMove(targetX, targetY)) // ,       //       StartCoroutine(move(cMap, targetX, targetY)); if(readyAttack){//,     if(stopMove(targetX, targetY)){ StartCoroutine(attack()); } } } //          currentPosition = transform.localPosition; //,     Battlefield.battlefield[(int)currentPosition.x, (int)currentPosition.y] = 1; //  ,     ,    if (currentPosition != lastPosition) { Battlefield.battlefield[(int)lastPosition.x, (int)lastPosition.y] = 0; lastPosition = currentPosition; //      } } } } private IEnumerator attack(){ readyAttack = false; //  ,    1   0.8  yield return new WaitForSeconds(0.8f); //////// ////////    //////// readyAttack = true; } /// <summary>   /// </summary> /// <param name="cMap">  </param> /// <param name="targetX">  x</param> /// <param name="targetY">  y</param> private IEnumerator move(int[,] cMap, int targetX, int targetY){ ready = false; int[] neighbors = new int[8]; //    //           Vector3 moveTO = new Vector3(-1,0,10); //   ,      for neighbors[0] = cMap[(int)currentPosition.x+1, (int)currentPosition.y+1]; neighbors[1] = cMap[(int)currentPosition.x, (int)currentPosition.y+1]; neighbors[2] = cMap[(int)currentPosition.x-1, (int)currentPosition.y+1]; neighbors[3] = cMap[(int)currentPosition.x-1, (int)currentPosition.y]; neighbors[4] = cMap[(int)currentPosition.x-1,(int) currentPosition.y-1]; neighbors[5] = cMap[(int)currentPosition.x, (int)currentPosition.y-1]; neighbors[6] = cMap[(int)currentPosition.x+1,(int) currentPosition.y-1]; neighbors[7] = cMap[(int)currentPosition.x+1,(int) currentPosition.y]; for(int i = 0; i < 8; i++){ if(neighbors[i] == -2) //    ,  ,        //     ,         //     neighbors[i] = 99999; } Array.Sort(neighbors); //         //     . for (int x = (int)currentPosition.x-1; x <= (int)currentPosition.x+1; x++) { for (int y = (int)currentPosition.y+1; y >= (int)currentPosition.y-1; y--) { if(cMap[x,y] == neighbors[0]){ //     ,      moveTO = new Vector3(x,y,10); } } } //      ,      . //  ,   ,   8 ,     if(moveTO == new Vector3(-1,0,10)) moveTO = new Vector3(currentPosition.x, currentPosition.y, 10); // , -     //    1     transform.localPosition = moveTO; // . yield return new WaitForSeconds(waitMove); ready = true; } //    //TargetX, TargetY -    public int[,] findWave(int targetX, int targetY){ bool add = true; //     //    ,     int[,] cMap = new int[Battlefield.X, Battlefield.Y]; int x, y, step = 0; //    0 for (x = 0; x < Battlefield.x; x++) { for (y = 0; y < Battlefield.y; y++) { if(Battlefield.battlefield[x,y] == 1) cMap[x,y] = -2; //   1,    ( -2) else cMap[x,y] = -1; //     } } //   ,      cMap[targetX,targetY] = 0; while (add == true) { add = false; for (x = 0; x < Battlefield.x; x++) { for (y = 0; y < Battlefield.y; y++) { if(cMap[x,y] == step){ //     ,       //      + 1 if(y - 1 >= 0 && cMap[x, y - 1] != -2 && cMap[x, y - 1] == -1) cMap[x, y - 1] = step + 1; if(x - 1 >= 0 && cMap[x - 1, y] != -2 && cMap[x - 1, y] == -1) cMap[x - 1, y] = step + 1; if(y + 1 >= 0 && cMap[x, y + 1] != -2 && cMap[x, y + 1] == -1) cMap[x, y + 1] = step + 1; if(x + 1 >= 0 && cMap[x + 1, y] != -2 && cMap[x + 1, y] == -1) cMap[x + 1, y] = step + 1; } } } step++; add = true; if(cMap[(int)transform.localPosition.x, (int)transform.localPosition.y] > 0) //  add = false; if(step > Battlefield.X * Battlefield.Y) //  ,      add = false; } return cMap; //   ,      move() } //      ,   public bool stopMove(int targetX, int targetY){ bool move = false; for (int x = (int)currentPosition.x-1; x <= (int)currentPosition.x+1; x++) { for (int y = (int)currentPosition.y+1; y >= (int)currentPosition.y-1; y--) { if(x == targetX && y == targetY){ move = true; } } } return move; } //    GameObject findClosestEnemy() { float distance = Mathf.Infinity; Vector3 position = transform.position; foreach (GameObject go in gos) { float curDistance = Vector3.Distance(go.transform.position,position); if (curDistance < distance) { closestEnemy = go; distance = curDistance; } } return closestEnemy; } } 

   
   
   
   Each step is described in detail in the comments to the code.
   
   In the Update () method we check if there is an enemy, then we are looking for the nearest one. Next, call the findPath () method, which searches for the path. Behind it we call the method move (), which moves an object 1 cell towards the enemy, if the object has not yet reached the target. If the object has already reached the target, then we call the attack () method.
   

Modification of the wave algorithm for dynamic objects

As I wrote earlier, the findPath () method has to be called for each unit in the Update () method. Because the enemies move in the same way as the player’s units. And after 1 game tact, the enemy can change position, and the old path will not be relevant.

The following situation turns out, we found a way to the enemy. moved into a cage with a minimum weight. The enemy changed his location, we again calculated the way to him, again moved into the cage with a minimum of weights.

In this case, we use only those cells that are adjacent to our unit, and we do not need the rest of the way. Then we do not need to calculate all the way to the enemy. And you just need to find out on which neighboring cell to move the unit, so that it is closest to the enemy.

The object we need to reach is called F. And the object that is looking for a path to F is called S. In unity3d it is very easy to calculate the distance from S to F.

 float curDistance = Vector3.Distance(F.transform.position, S.transform.position); 

Now we just need to go through the adjacent cells. Calculate the distance from each neighboring cell to the object F and move into the cell with the minimum distance.

  float[] neighbors = new int[9]; int n = 0; Vector3 goTo; for (int x = (int)currentPosition.x-1; x <= (int)currentPosition.x+1; x++) { for (int y = (int)currentPosition.y+1; y >= (int)currentPosition.y-1; y--) { float curDistance = Vector3.Distance(new Vector3(x,y,0), S.transform.position); neighbors[n] = curDistance; } } 

Find the minimum value and cell index in the neighbors array. Further, by the cell index, we determine the coordinates of the cell where the object S is to be moved. Repeat until we reach the goal F.

Demonstration