Hi Im having a problem with my code. I have a Quicksort algorythm that sorts unity gameobject by their scale. It is working fine but i need to delay it somehow to show how the objects swap. I think I cant use corutines, becouse the method i recursive and Invoke() either, becouse my Switch() method uses parameters. Can someone help?
void QuickSort(GameObject[ ] array, int leftIndex, int rightIndex)
{
int i = leftIndex;
int j = rightIndex;
var pivot = array[leftIndex].transform.localScale.y;
while (i <= j)
{
while (array*.transform.localScale.y < pivot)*
*{*
*i++;*
*}*
*while (array[j].transform.localScale.y > pivot)*
*{*
*j--;*
*}*
*if (i <= j)*
*{*
*Switch(array, i, j);*
*i++;*
*j--;*
*}*
*}*
*if (leftIndex < j)*
*QuickSort(array, leftIndex, j);*
*if (i < rightIndex)*
*QuickSort(array, i, rightIndex);*
*}*
*```*
That is an interesting problem. Could you decouple the sorting from the animation? Something like:
- Create a new array and copy localScale.y from all objects in your array[ ].
- Perform QuickSort on the new array
- In your Switch function, add each (i, j) pair to a List to keep track of the order of swaps.
- After QuickSort is done, iterate over the list to actually swap the game objects or do any animations you want with the swaps.
1 Like
Wow, that is smart. Thanks a lot
Wow, that is smart. Thanks a lot. Im going to try that.
Aaah, this brings back fond memories of hacking in MS-DOS in the 320x200 VGA mode 0x13, probably circa 1990 or 1991?? I remember filling the video pixel buffer with random data and then sorting it in various ways. Good times, good times.
I just took the naive approach of turning your quicksort method into a coroutine and fiddling a few other bits, including an optional tweened vs instant movement in Switch().
Enjoy!!
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
// @kurtdekker - visual Quicksort
//
// Inspired and derived directly from code in this Unity forum post:
//
// https://forum.unity.com/threads/how-to-delay-recursive-funcion.1593198
//
// To use: drop it on a blank GameObject that can be seen by a Camera, press PLAY
//
public class QsortDemo : MonoBehaviour
{
[Header( "Tween to destination or go instantly?")]
public bool tween = true;
IEnumerator Start()
{
List<GameObject> all = new List<GameObject>();
float hueOffset = Random.value;
float hueRate = Random.Range(1.0f, 4.0f);
for (int j = -5; j <= +5; j++)
{
for (int i = -8; i <= +8; i++)
{
GameObject item = GameObject.CreatePrimitive(PrimitiveType.Sphere);
float size = Random.value;
item.transform.localScale = Vector3.one * size;
Vector3 pos = new Vector3(i, j);
item.transform.position = pos;
// just for my Mom, who loved color: colorize with hue from a random scaling / offsetting of size.
// Caution: this causes it to make like a fazillion drawcalls!
Renderer rndrr = item.GetComponent<Renderer>();
float hue = (hueOffset + hueRate * size) % 1.0f;
Color c = Color.HSVToRGB(hue, 1, Random.value * 0.5f + 0.5f);
rndrr.material.color = c;
all.Add(item);
}
}
GameObject[] array = all.ToArray();
yield return StartCoroutine(QuickSort(array, 0, array.Length - 1));
Debug.LogWarning("All pau!");
}
// this is slightly tricky: it swaps their positions in the array,
// and also swaps their positions in the grid
IEnumerator Switch( GameObject[] array, int i, int j)
{
Vector3 p1 = array[i].transform.position;
Vector3 p2 = array[j].transform.position;
var t = array[i];
array[i] = array[j];
array[j] = t;
if (tween)
{
float distance = Vector3.Distance(p1, p2);
// choose how distance maps to steps taken to move over
int steps = 4 + (int)(distance / 3);
for (int step = 0; step < steps; step++)
{
float fraction = (float)step / steps;
// one coming, one going
Vector3 v1 = Vector3.Lerp(p1, p2, fraction);
Vector3 v2 = Vector3.Lerp(p2, p1, fraction);
array[i].transform.position = v1;
array[j].transform.position = v2;
yield return null;
}
}
// always assume the final resting spot
{
array[i].transform.position = p1;
array[j].transform.position = p2;
}
}
IEnumerator QuickSort(GameObject[] array, int leftIndex, int rightIndex)
{
int i = leftIndex;
int j = rightIndex;
float pivot = array[leftIndex].transform.localScale.y;
while (i <= j)
{
yield return null;
while (array[i].transform.localScale.y < pivot)
{
i++;
}
while (array[j].transform.localScale.y > pivot)
{
j--;
}
if (i <= j)
{
yield return Switch(array, i, j);
i++;
j--;
}
}
if (leftIndex < j)
yield return QuickSort(array, leftIndex, j);
if (i < rightIndex)
yield return QuickSort(array, i, rightIndex);
}
}
3 Likes
Oh, I did not know that you could pass another IEnumerator into the yield instruction. That’s good information for the future.
1 Like
you also could use await, and task.delay
Oh yes you do. You can do pretty neat time-slicing on the spot. It’s not only neat for feature design and eye candy, but it’s mighty useful for debugging and editing tools as well, because you can essentially visualize some procedure across frames. It is especially neat because you don’t have to refactor and do the whole algorithm again, you can basically upgrade the existing (fully synchronous) one to an IEnumerator spliced with yields (time- or event-based) and start it as a coroutine.
1 Like