0

I'm doing a job for school purpose, and then it was required into the Game I'm creating with a friend to use some sort by Ascending the points in a Rank every time the Space Ship destroy a target and Update the Score, and after this happen, implement the method binary search (recursive) or even a new method of binary search and return the exact position of the actual points of the player in the Rank. But I tried to insert the Method into the Update, but every time the position returned is -1.

Besides that, an important thing to say is 2 things: First, the Sort by Ascending and Binary Search need to be done manually with every if, else, for, etc to do the sort and the search, this is one important requirement that I have been asked to do, nothing of array.sort() methods equals that I have done to test into the code, or ready unity methods to do the thing in just one line of command.

And second and more important, I'm trying everyday to seek and learn solutions to move the elements in and array to use conditional cases and binary search, but i assume that to me (who study arts and have a basic programming logic to understand how the codes work), was and yet still hard to understand how and why the codes to do this things works, and I'm doing my best to understand and learn about it, and all this reasons that I have pointed out above are the main reasons that I ask the help, because I think that this two implementations can be easy for someone who have more knowledge in this than me and my partner (an artist too). Now, follow the code:

public class GameController : MonoBehaviour
{

    public GameObject Hazard;
    public Vector3 SpawnValues;
    public int HazardCount;
    public float SpawnWait;
    public float StartWait;
    public float WaveWait;
    public GUIText ScoreText;
    private int Score;
    public GUIText RestartText;
    public GUIText GameOverText;
    public bool GameOver;
    private bool Restart;
    public List<int> Lista_Array;
    public int[] arr = { 0, 1, 2, 3, 4, 5 };

    IEnumerator SpawnWaves()
    {

        yield return new WaitForSeconds(StartWait);
        while (true)
        {
            for (int i = 0; i < HazardCount; i++)
            {
                Vector3 SpawnPosition = new Vector3(UnityEngine.Random.Range(-SpawnValues.x, SpawnValues.x), SpawnValues.y, SpawnValues.z);
                Quaternion SpawnRotation = Quaternion.identity;
                Instantiate(Hazard, SpawnPosition, SpawnRotation);
                yield return new WaitForSeconds(SpawnWait);
            }
            yield return new WaitForSeconds(WaveWait);

            if (GameOver)
            {
                RestartText.text = "Press 'B' to return to main menu or 'R' to restart";
                Restart = true;
                break;
            }
        }

    }

    public void UpdateScore()
    {
        ScoreText.text = "Score: " + Score;
        for (int i = 0; i < 1; i++)
        {
            //Lista_Array = new List<int>(Score);
            Lista_Array.Insert(0, Score);
            Lista_Array.Insert(0, 0);
            Lista_Array.Insert(0, 999);
            Lista_Array.Insert(0, 1999);
            Lista_Array.Insert(0, 2999);
            Lista_Array.Insert(0, 3999);
            arr = Lista_Array.ToArray();
            Lista_Array = new List<int>(Score);
            Array.Sort(arr); // Need to implement here manually some kind of sort by Ascending the Points in the Rank (Rank = Array and Points = Elements and Position = Position of Elements in the Array)
        }
    }

    public int BuscaBinaria(int[] arr, int l, int r, int x) //This is the Method of a Recursive Binary Search, but always return the position of -1
    {
        if (r >= 1)
        {
            int mid = 1 + (r - l) / 2;
            if (arr[mid] == x)
            {
                return mid;
            }
            if (arr[mid] > x)
            {
                return BuscaBinaria(arr, 1, mid - 1, x);
            }
            return BuscaBinaria(arr, mid + 1, r, x);
        }
        return -1; //Aqui era -1
    }


    public void AddScore(int NewScoreValue)
    {
        Score += NewScoreValue;
        UpdateScore();
        int n = arr.Length;
        int x = 10;
        int result = BuscaBinaria(arr, 0, n - 1, x);
        if (result == -1)
        {
            Debug.Log("Posicao nao encontrada");
        }
        else
        {
            Debug.Log("Posicao encontrada no Ranking " + result);
        }
    }

    public void gameOver()
    {
        GameOverText.text = "Game Over";
        GameOver = true;
    }

    public void Start()
    {
        GameOver = false;
        Restart = false;
        RestartText.text = "";
        GameOverText.text = "";
        Score = 0;
        StartCoroutine(SpawnWaves());
        UpdateScore();
    }

    void Update()
    {
        if(Restart){
            if(Input.GetKeyDown (KeyCode.B)){
                SceneManager.LoadScene ("Menu");
            }
        }

        if(Restart){
            if(Input.GetKeyDown (KeyCode.R)){
                Application.LoadLevel (Application.loadedLevel);
            }
        }

    }

}
4
  • 3
    A well spaced text is a lot more pleasant to read.
    – Cid
    Nov 7, 2018 at 13:28
  • In UpdateScore() you always recreate the array arr. It contains the values 0, 999, 1999, 2999, 3999 and the current content of Score. Then you set the value of x to 10 and search the array with binary search for the position of the array, that contains the value 10, because the condition, when you leave the binary search with a result other than -1 is, when arr[mid] == x, so when the element is the same value as x. But you array does not contain the value 10, this is why -1 is returned.
    – gofal3
    Nov 7, 2018 at 19:36
  • @gofal3 i have changed the code where x = Score; and now return the Element Position of the Score, but just if the points are in pair element position as element 2 or 4, cause the following error happens: StackOverflowException: The requested operation caused a stack overflow. GameController.BuscaBinaria (System.Int32[] arr, Int32 l, Int32 r, Int32 x) (at Assets/Scripts/GameController.cs:86) ------ Content of Line 86: return BuscaBinaria(arr, mid + 1, r, x);
    – RoberthSS
    Nov 12, 2018 at 3:55
  • Yes, I see. After I saw the thing with the array, I did not take a closer look at the binary search itself, but not I did. Found some issues. For formating reason I will post is as an answer.
    – gofal3
    Nov 12, 2018 at 7:24

2 Answers 2

0

Some issues with your binary search method:

public int BuscaBinaria(int[] arr, int l, int r, int x) //This is the Method of a Recursive Binary Search, but always return the position of -1
{
    if (r >= 1) // You do a recursive algorithm, so the exit criteria should not be,
                // as long as the right border is larger than 1, but the exit should
                // be if there is still a range, like if (r-l>0) or similar.
                // Otherwise you could end in a endless loop
    {
        int mid = 1 + (r - l) / 2; // the middle of r and l is (r+l)/2 !!!! 
                                   // try with l = 3 and r = 5. middle should be 4.
                                   // 1 + (5-3) /2 = 2; (5+3)/2 = 4;
        if (arr[mid] == x)
        {
            return mid;
        }
        if (arr[mid] > x)
        {
            return BuscaBinaria(arr, 1, mid - 1, x); // Index, problem. Your array has
                                      // a 0-based index, so you should call (arr, 0, mid-1, x)
        }
        return BuscaBinaria(arr, mid + 1, r, x);
    }
    return -1; //Aqui era -1
}

Take this changes into account and try again. Debug your code with selveral input parameters (write a unittest method!), then you will see if your binary search does what you desire.

0

Thank you @gofal3 for all your help and sorry for the delay to reply the answer and the final version of the code that me and my team mate done. Now, follow the code:

using System;
using System.Linq;
using System.Text;
using System.Threading;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.SceneManagement;

public class GameController : MonoBehaviour
{

    public GameObject [] Hazards;
    public Vector3 SpawnValues;
    public int HazardCount;
    public float SpawnWait;
    public float StartWait;
    public float WaveWait;
    public GUIText ScoreText;
    private int Score;
    public GUIText RestartText;
    public GUIText GameOverText;
    public bool GameOver;
    private bool Restart;
    public List<int> Lista_Array;
    public int[] arr = { 0, 1, 2, 3, 4, 5 };

    IEnumerator SpawnWaves()
    {

        yield return new WaitForSeconds(StartWait);
        while (true)
        {
            for (int i = 0; i < HazardCount; i++)
            {
                GameObject Hazard = Hazards[UnityEngine.Random.Range(0, Hazards.Length)];
                Vector3 SpawnPosition = new Vector3(UnityEngine.Random.Range(-SpawnValues.x, SpawnValues.x), SpawnValues.y, SpawnValues.z);
                Quaternion SpawnRotation = Quaternion.identity;
                Instantiate(Hazard, SpawnPosition, SpawnRotation);
                yield return new WaitForSeconds(SpawnWait);
            }
            yield return new WaitForSeconds(WaveWait);

            if (GameOver)
            {
                RestartText.text = "Press 'B' to return to main menu or 'R' to restart";
                Restart = true;
                break;
            }
        }

    }

    public void UpdateScore()
    {
        ScoreText.text = "Score: " + Score;
        for (int i = 0; i < 1; i++)
        {
            //Lista_Array = new List<int>(Score);
            Lista_Array.Insert(0, Score);
            Lista_Array.Insert(0, 0);
            Lista_Array.Insert(0, 999);
            Lista_Array.Insert(0, 1999);
            Lista_Array.Insert(0, 2999);
            Lista_Array.Insert(0, 3999);
            arr = Lista_Array.ToArray();
            Lista_Array = new List<int>(Score);
            BubbleSort(arr);
            //Array.Sort(arr);
            //Lista_Array = arr.ToList();
            //Array_Lista = Lista_Array.ToArray();
        }
    }

    public int BuscaBinaria(int[] arr, int l, int r, int x)
    {
        if (r >= 1)
        {
            int mid = (r + l) / 2;
            if (arr[mid] == x)
            {
                return mid;
            }
            if (arr[mid] < x)
            {
                return BuscaBinaria(arr, 0, mid - 1, x); //aqui tbm
            }
            return BuscaBinaria(arr, mid + 1, r, x); //aqui tbm
        }
        return -1; //Aqui era -1
    }

    public static int[] BubbleSort(int[] arr1)
    {
        int length = arr1.Length;

        int temp = arr1[1];

        for (int i = 0; i < length; i++)
        {
            for (int j = i + 1; j < length; j++)
            {
                if (arr1[i] < arr1[j]) //mudei aqui
                {

                        temp = arr1[i];

                        arr1[i] = arr1[j];

                        arr1[j] = temp;
                }
            }
        }

        return arr1;
    }

    public void AddScore(int NewScoreValue)
    {
        Score += NewScoreValue;
        UpdateScore();
    }

    public void gameOver()
    {
        int n = arr.Length;
        int x = Score;
        int result = BuscaBinaria(arr, 0, n - 1, x);
        if (result == -1)
        {
            Debug.Log("Posicao nao encontrada");
        }
        else
        {
            Debug.Log("Posicao encontrada no Ranking " + result);
        }
        GameOverText.text = "Game Over";
        GameOver = true;
    }

    public void Start()
    {
        GameOver = false;
        Restart = false;
        RestartText.text = "";
        GameOverText.text = "";
        Score = 0;
        StartCoroutine(SpawnWaves());
        UpdateScore();
    }

    void Update()
    {
        if(Restart){
            if(Input.GetKeyDown (KeyCode.B)){
                SceneManager.LoadScene ("Menu");
            }
        }

        if(Restart){
            if(Input.GetKeyDown (KeyCode.R)){
                //Application.LoadLevel (Application.loadedLevel);
                SceneManager.LoadScene("Main");
            }
        }

    }

}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.