Data Structure Time Trials [AS3]

As many developers do when they write their own Linked List and Binary Tree Classes, I have run some time trials. And I share it with you. But there are things you should know before clicking on the Cabin link:

1. The test takes 52 seconds to run on my old-school Dell 2350 Computer. It might be quicker on yours, but the point here is you will not see anything on the screen for a while.

2. During a time trial avoid moving or clicking the mouse. This takes time away from the test as the operating system has to service your mouse clicks or moves.

3. During a time trial don’t have anything else running except your browser.

4. If any of the TextFields have an asterisk in them, instead of an integer, then that section of the time trial failed.

5. http://www.swfcabin.com/open/1258576820

I called the time trial “Mond Time Trial II” in case you want to search for it on swfCabin. I have tested this time trial in FireFox and Flash Player 9.

I’ve seen you talking about linked lists and binary trees a lot recently, what are you intending to do with them?

My current game was slowing down, so I needed to make a move on the data structures I was using in the game. But I didn’t know enough to know which data structure would be best suited to my needs. So I investigated both types of intermediate level structures.

And the experience writing the Classes helps me understand recursion. It was sort of a self-inflicted homework assignment.

What exactly were you doing that slowed the game down?

http://swfcabin.com/open/1255066100 This is from GOTW9. When sandbags land they must be touching another sandbag, if not the bag gets removed in 6 seconds. However, what if there are 325 sandbags already out on the playing field…How could I determine if a newly landed sandbag was in contact with another bag? Collision detection between the newly arrived bag and 325 previously landed bags. That means traversing an array with 325 bags in it.

I wasn’t making 325 hitTestObject calls. I had a compound if statement culling out bags prior to a hitTestObject call, but still it got so bad that bags obviously in contact with another bag were getting removed from the game before the contact property (Boolean) had time to get set properly.

Collision detection between the newly arrived bag and 325 previously landed bags. That means traversing an array with 325 bags in it.

That seems pretty insignificant. If you’re not doing anything fancy, that’s only a little over a thousand comparisons, which should be fine to do in the routine which actually places the sandbag.

Since you are traversing through all the sandbags for the collision detection, it is O(n) for all of your data structures. I’d say just focus on what will be most efficient at adding and removing items, such as a linked list.

Array kicked your tree’s ass in everything except searching, which made sense to me. In remove/reinsert, Array was almost 6x faster. Searching was the only thing the binary tree on against the Array and it was only 1.5x faster. And about 2x faster in Search & Remove.

BTW:
http://lab.polygonal.de/ds/

The problem with the time trial is that it measures remove and reinsert at the same time, which you won’t be doing. When you remove an item in the array you will have to modify the array to remove the gap. This will make it very slow.

How about a simple vector? I hear they are quite a bit faster than arrays(Possibly up to 3x)..

I’ve never seen anyone use Vectors before. They’re one of those things that everyone knows is better to use, but then never does. I use them where I can, but I’ve never really had an occasion where Array has been too slow so I don’t know how helpful they really are.

Since you are traversing through all the sandbags for the collision detection, it is O(n) for all of your data structures.

Indeed. It would be much better to use the binary tree, sort it by (say) horizontal position, and then you’ve cut it down to O(log n) when testing for collisions.

The problem with data structure time trials isn’t that hitTesting every object in an array against every other object in the array means iterating through the array 10,000 times, its calling hitTest ten thousand times. So you want a data structure that cuts down on search time so you can narrow down which sandbags should be hitTesting each other.

Originally posted by Jabor:

Since you are traversing through all the sandbags for the collision detection, it is O(n) for all of your data structures.

Indeed. It would be much better to use the binary tree, sort it by (say) horizontal position, and then you’ve cut it down to O(log n) when testing for collisions.

Wouldn’t that only work if collision detection means having exactly the same horizontal position? Two sandbags could be in contact without having exactly the same x value

Wouldn’t that only work if collision detection means having exactly the same horizontal position? Two sandbags could be in contact without having exactly the same x value

It doesn’t matter.

If we know that Sandbag X is to the left of the sandbag of interest, then we can eliminate the entire tree to the left of Sandbag X.

Similarly, if we find some Sandbag Y that is to the right of the sandbag of interest, we can eliminate the entire tree to the right of that.

You’re cutting your hittests down to a very small fraction of the entire tree.

Hi ya’ll, thanks for all the advice. I considered the BTree for this application, but “What am I searching for?”
Once the recently landed sandbag is inserted into the tree, I need all the bags within a certain range of it.
The tree is great for finding something, but once found what data do I want returned
…all the Nodes that satisfy:

testValue > thisNode.myValue – rangeOffset AND testValue < thisNode.myValue + rangeOffset

( Assuming, as Jabor suggested, the tree was sorted by x ).

I tried to write a search algorithm to do this, but the best I could do was to return all the bags < testValue
or all the bags > testValue. I couldn’t figure out how to combine the two.

public function SearchLT(testValue:*, aNode:BTreeNode):int  //returns through retArray all nodes < the testValue
{			
	if (testValue < aNode.myValue)
	{
	        if (aNode.leftRef) SearchLT(testValue, aNode.leftRef);
	}
	else //testValue >= aNode.myValue
	{
	        if (aNode.leftRef) PushAllTraverse(aNode.leftRef);
		if (aNode.rightRef) SearchLT(testValue, aNode.rightRef);
 	}
	
	if ((aNode.myValue < testValue) && aNode.parentRef) retArray.push(aNode); 
	
	return retArray.length;
} //end of function SearchLT
	
public function SearchGT(testValue:*, aNode:BTreeNode):int  //returns through retArray all nodes > the testValue
{			
	if (testValue > aNode.myValue)
	{
		if (aNode.rightRef) SearchGT(testValue, aNode.rightRef);
	}
	else //testValue <= aNode.myValue
	{
		if (aNode.rightRef) PushAllTraverse(aNode.rightRef);
		if (aNode.leftRef) SearchGT(testValue, aNode.leftRef);
 	}
	
	if ((aNode.myValue > testValue) && aNode.parentRef) retArray.push(aNode); 
	
	return retArray.length;
} //end of function SearchGT

I might possibly just nose around in the Nodes close to the recently inserted bag, checking each Node’s
sorting value (sandbag.x) until the values go beyond the rangeOffset. I’m not quite sure how to do
that either. And then I would still need to check y values, as andrew pointed out.

Here’s the code for the collision detection. I use a standard four points test to take advantage of
hitTestPoint’s pixel perfect capability. I don’t see any opportunities to “take the fat” out of the code,
it seems lean and tight. But I welcome any comments…

public function LandedMove(landedSandBags:Array, theDamFace:Sprite, leftBags:Array, rightBags:Array):void
{
	var i:int = 0;
	var adjustedCoeffX:Number = 0.0;
	var adjustedCoeffY:Number = 0.0;
	var pt1, pt2, pt3, pt4:Point;
	
	if (contact) return;
													
	if (alpha < 0.1)			// || (y < 0.0) || (y > 553.0) || (x < 0.0) || (x > 700.0))
	{
		Remove();
		++numOfBagsRemoved;
		landedSandBags.splice(landedSandBags.indexOf(this), 1);
		return;
	}
	
	if (damFace)
	{
		if (++damCounter > 9)
		{
			damFace = theDamFace.hitTestPoint(x, y, true);
			y += Number(damCounter - 10) * 0.3;
			if (rot) rotation += 5.0; else rotation -= 5.0;
		}
	}
	
	adjustedCoeffX = 20.80865 * scaleX;	//check for contact with another sandbag
	adjustedCoeffY = 20.80865 * scaleY;
	
	pt1 = new Point(x + (adjustedCoeffX * Math.cos((rotation - 35.23) * 0.0174533)),
					y + (adjustedCoeffY * Math.sin((rotation - 35.23) * 0.0174533)));
	
	pt2 = new Point(x + (adjustedCoeffX * Math.cos((rotation + 35.23) * 0.0174533)),
					y + (adjustedCoeffY * Math.sin((rotation + 35.23) * 0.0174533)));
	
	pt3 = new Point(x + (adjustedCoeffX * Math.cos((rotation - 144.77) * 0.0174533)),
					y + (adjustedCoeffY * Math.sin((rotation - 144.77) * 0.0174533)));
	
	pt4 = new Point(x + (adjustedCoeffX * Math.cos((rotation + 144.77) * 0.0174533)),
					y + (adjustedCoeffY * Math.sin((rotation + 144.77) * 0.0174533)));
				
	for (i = landedSandBags.length - 1; i >= 0; i--)
		if ((Math.abs(x - landedSandBags[i].x) < 21.0) &&
			(Math.abs(y - landedSandBags[i].y) < 20.0) &&
			(landedSandBags[i] != this))
		{
			if ((x == landedSandBags[i].x) && (y == landedSandBags[i].y))
			{
				alpha = 0.0;
				return;
			}
			if (landedSandBags[i].hitTestPoint(pt1.x, pt1.y, true))
			{
				landedSandBags[i].contact = true;
				contact = true;
				return;
			}
			if (landedSandBags[i].hitTestPoint(pt2.x, pt2.y, true))
			{
				landedSandBags[i].contact = true;
				contact = true;
				return;
			}
			if (landedSandBags[i].hitTestPoint(pt3.x, pt3.y, true))
			{
				landedSandBags[i].contact = true;
				contact = true;
				return;
			}
			if (landedSandBags[i].hitTestPoint(pt4.x, pt4.y, true))
			{
				landedSandBags[i].contact = true;
				contact = true;
				return;
			}
		}
			
	if (getTimer() - timeLaunched > 5000.0) alpha -= 0.07;
} //end of function LandedMove

Here’s a quick search algorithm (psuedocode)

function TreeSearch(Node n, int lower, int upper) {
	List l = new list();
	if(lower <= n.value <= upper)
		l.add(n);
	if(lower <= n.value)
		l.add(TreeSearch(n.left, lower, upper));
	if(n.value <= upper)
		l.add(TreeSearch(n.right, lower, upper));
	return l;
}

You’d call it like follows (assuming a uniform bag width):

TreeSearch(Tree.head, bag.x - bag.width, bag.x + bag.width);

followed by checking the y values of the stuff in the returned list.

But that is a full in-order traversal of the tree isn’t it? ( As my time trial shows the BTree is
less-than-desirable on traversals ) Or is it, I’m still looking at it.

EDIT:yes, the bags are the same size after they have been scaled down for the 3d effect. But they rotate
while in flight, so it is a little bit more than just bag.x – bag.width, but I get your point.

But that is a full in-order traversal of the tree isn’t it?

Look at the code again. You don’t traverse a subtree if the entirety of it is going to be outside your desired range.

Getting late, I’m an east coaster (USA). So from wherever I (speaking as the sandbag) have been inserted, go left, pushing everything I find into list, until I am outside of the rangeOffset or I encounter NULL.
Then go right, doing the same. That’s the way I thought of it, but could never figure out the code to do it.

Thanks ofr the help. I’ll Bump this thread tomorrow.

EDIT:But the recursion requires a trigger to start the avalanche back through the recursive calls. That trigger is usually NULL…….

to that add a second trigger (aNode.myValue < aNode.myValue – rangeOffset)…. and then a third trigger (aNode.myValue > aNode.myValue + rangeOffset).

I think that was where I had probs with this code and was convinced it couldn’t be done with recursion. And on top of that, the return value had to survive the avalanche! :)

Getting late, I’m an east coaster (USA). So from wherever I (speaking as the sandbag) have been inserted, go left, pushing everything I find into list, until I am outside of the rangeOffset or I encounter NULL. Then go right, doing the same. That’s the way I thought of it, but could never figure out the code to do it.

I’m not sure this is the best way to handle it :/

Firstly, you ignore everything above you (which you could very well be touching).
Secondly, if it turns out you’re not touching anything, you have to do an insert/rebalance followed by a delete/rebalance – which takes time.

Unless your game design requires the player be able to drop two directly on top of each other and have them remain (despite being separate from everything else), you’re better off not putting duds in the tree at all – first walk (the relevant subset of) the tree to determine whether they’re touching, and only add them to the tree if they are.

But I couldn’t do that! One sandbag ( I call them “orphans” ) all by its lonesome must remain for 6 seconds to give the player time to drop another sandbag close enough for contact. So its not a dud until the alpha hits < 0.1; It must be in the landedSandBagsBTree.

I’m not shunning those above me….lol….I am using the BTree to instantly cull many bags from consideration in a few comparisons ( maybe hundreds of bags ). At the end of this search, I expect to have all sandbags within the rangeOffset but only in the .x property. How many can that be?…35 maybe (in the worst case scenario)…all with varying values of y. The time I saved using the BTree should give me plenty of time to traverse the retArray.

If an incoming bag lands exactly on top of a previously landed sandbag ( .x and .y must be == ) the incoming bag is removed. If it lands exactly on an orphan, both bags are removed. Had to do that or the player would just sit there hurling bags in the same spot, never adjusting the launcher.

EDIT:oh I see your point, yes….two bags off by themselves will stay in the game. All it takes is contact.

EDIT: EDIT: you mean above me in the tree….that’s why I needed a parent linked BTree. Each Node points back at what’s pointing at them.

6 seconds: easy. store unconnected bags in an array (trivial to check for hits due to the array’s size) and if a new bag hits one of those, add them both to the tree.

I’m not sure this is the best way to handle it :/

Firstly, you ignore everything above you (which you could very well be touching).


OK, then start the OffSetSearch from a Node other than the bag that was just inserted. Perform a Search for sandbagJustInserted.x – offSet ( or the closest Node <= ). Start from there, and I think I can get all bags within +/- offSet.

Secondly, if it turns out you’re not touching anything, you have to do an insert/rebalance followed by a delete/rebalance – which takes time.

That point I am still thinking about…the rebalance is unavoidable(normal maintenance overhead)….since removeNode is so time consuming, maybe I will not remove anything. I don’t like processing NULLS, but it might work.

Thanxs Draco, I think that is what Jabor meant. Essentially, setup a “pipeline” of sorts.