sorting problem

[mattk210]

(this is for a 2D overhead game)

so I have a point - say, a camera - and I have many other points (enemies, geometry objects, whatever). imagine there's a ray coming out of the camera which slowly turns, I want to sort the points based on the order the ray would pass them.

I don't know anything about computerized sorting. Something I can initially think of is to convert all the points to angles from the camera, and order them with flash's built in array sorting function, but then I can't think of any good way to transfer this sorted order to the original list of points. Plus, converting points to angles requires trig, and i'd prefer to be able to do this with lots of points so I'd want it reasonably fast.

Any ideas? Am I being clear enough?

[Exüberance]

What, exactely, do you need this function to do? Is it for a radar or something? There may be a better way to accomplish whatever you're trying to do without using arrays.

As for getting teh sorted order to the original list of points, you could change your object for points to also include a 3rd variable: the angle it makes with the camera. Then sort that array of objects directly. Here's code for a function I wrote a while ago in Actionscript 2.0 for sorting a list of objects in ascending order based on 1 property of the objects:

NOTE: This is Actionscript 2.0. If you need Actionscript 3.0, you might have to adjust a few things. I know you could change the Number type vars to int to save on memory and :Void becomes :void in AS3. Beyond that, I'm not sure what you need to change. My trial version for the new Flash ran out :(

Code: Select all

/*
	 * call this function with 2 arguments, array and varname
	 * Args:
	   * array:Array an array of objects with a common variable that you wish to search
	   * varname:String the name of the variable you want the objects to be sorted by. This is a string
	 * Returns: void
	 * Side effects: the array has been sorted by the indicated variable
	 * example: A is an array of objects containing 2 variables _x and _y. To sort the objects in ascending order of _x value use
	 *  quickSort_objectArray(A,"_x");
	 */
	function quickSort_objectArray(array:Array, varname:String, low:Number, high:Number):Void {
		var bottom:Number;
		var top:Number;
		var pivot;
		var temp:Object;
		
		if (arguments.length <= 2) {
			low = 0;
			high = array.length - 1;
		}
		
		if (high > low) {
			pivot = array[high][varname];
			bottom = low - 1;
			top = high;
			while (true) {
				while ((array[++bottom][varname] < pivot) && (bottom < array.length));
				while ((array[--top][varname] > pivot) && (top > 0));
				if (bottom >= top) {
					break;
				}
				temp = array[bottom];
				array[bottom] = array[top];
				array[top] = temp;
			}
			temp = array[bottom];
			array[bottom] = array[high];
			array[high] = temp;
			
			quickSort_objectArray(array, varname, low, bottom - 1);
			quickSort_objectArray(array, varname, bottom + 1, high);
		}
	}

[mattk210]

It's pretty easy to port from AS2 to AS3, especially when you do everything to standard like you did.

Specifically, I want to do something like http://metanet.2.forumer.com/index.php?showtopic=20674
It's an idea I gave up on before, but now my physics engine is nicer so I can just cast rays to all my corner points in geometry and join them up to represent visually the vision cone. The issue is, I need to order the points before joining them up.

I looked at your code, it's not making any sense to me right now but it works, so I'll try and make sense of it later. Is this considered fast for a sorting algorithm?

Sorting like this is not ideal because I wanted to avoid trig, but I can't see any way that could feasibly not involve trig so i'll use this for now. Thanks heaps!

[Exüberance]

This sorting algorithm is basically quicksort, which is the fastest algorithm for sorting randomly ordered data. It's usually used for very large sets of data because it's efficiency is very clear then. It may not be the best for sorting very small amount of mostly orded data, however. This is how it works: http://en.wikipedia.org/wiki/Quicksort (This will make the source code make a LOT more sense :D)

Would it be possible to construct your function such that it finds the corner points in order so you don't have to sort it? I don't think it would be, but it's hard to say.

[mattk210]

well, the list isn't entirely random. Each object will have several points to consider, and these will be added to the array in order as points are scanned through, so they will often already be in order or reverse order. Also, the order objects is scanned is arbitrarily the order they exist in the level data, and in general level designers will create objects in order because it's more convenient, so this order might also exist in the angular sorting. I don't think there's any reliable order to the points though.

I now understand the quicksort, thanks. I can understand that it's very close to the upper limit on speed for my fairly random data, and it doesn't create enough of an impact on the processing required each step for me to worry about it further.

[scythe]

You don't need to use triginometry; you can just exploit the fact that a > b iff tan(a) > tan(b), assuming a and b are in the same quadrant. Just divide the points into quadrants (of the Cartesian plane) and sort them according to y / x.

(technically, you're using trig here, but you're not calculating the angle, which saves a good bit of time)

[mattk210]

thanks! that's really clever.
I thought I'd need to mess with divide-by-zero stuff, but flash conveniently has an "Infinity" value which is a pain everywhere else but actually useful here.