next »

[Alistair Aitcheson]

Hey all,

I'm working on a remake of Dam Busters for the Action 52 Owns project. You can have a go at it how it is here: Dam Busters (WIP)

I'm having trouble with Z-Ordering on the objects at the moment. You'll probably notice some bits where the Z-Ordering goes wrong in the demo, which I think I've tidied up. But as I've tried to expand and improve on the Z-Ordering system, more and more problems have come up and the code's getting more and more complicated and error-prone.

I can't be the first person who's tried to make a pseudo-3D game in Flash, and so I can't be the first person who's had to deal with this. Does anyone know of a good system for doing this? My current approach is way too complicated.

I'll describe my current approach below in case that's any help. You don't need to read it though, but it might shed a little light on my problem!

At the moment I have arrays of objects of each kind (blocks, moving objects (player, bullets, debris), and shadows). Each of these objects is inherited from a ZOrder object which has all the data it needs to arrange the objects properly. I have another array of all of these objects. Every loop I do a bubble-sort on this array by their position in the y-axis and z-axis, and every time I switch elements I perform swapChildren() on them as well. When an object is removed I have to remove it from all of these lists, and perform a removeChild() on it.

At the moment there's so many lists to deal with and it's incredibly unweildy. I want to keep arrays of my different object types so that I can check bullets against blocks to see if they collide, without having to factor in shadows and other objects too.

I've had to fix a lot of mistakes in my code such as it attempting to move children that have already been removed. I still have objects that aren't deleted properly, which seems to have a knock-on effect on the Z-Ordering (normally it means next time I want to remove something from the Z-Order array the wrong object gets removed).

Today I noticed that whenever I add an object (such as a particle or bullet) it gets stuck at the end of the array and the bubble-sort takes ages to get it to its correct position. This made the game pause for a while if I added lots of particles at once. I fixed this by adding functions to add an element into the middle of an array, then using addChildAt() to put the object in the right place in the list of children. But this ended up digging up plenty more errors, and there was so much fiddling and bug checking.

I think it mostly works now, but I'm not sure. As you can see it's way more complicated than I think it should be!

In short, there must be an easier way! Does anyone have any advice or know of any resources that could help?

Many thanks!

[Johan Peitz]

Sounds to me that the problem is two fold:
1) Your drawing code is entangled with your gameplay code.
2) You are afraid that the sorting algorithm is slow.

When it comes to your coding style, read up on the Model View Controller pattern. I personally don't use this to the full extent when working with Flash, but it should get you the idea.

As for the sorting, as long as you don't have bazillions of objects to sort AND the objects don't change their positions very much, bubble/insertion sort is the fastest. Most sort algorithms fall back on this one for their basic case. This means that unless your array order isn't too jumbled, you can just run sort on it and it should run at O(n) - which isn't that bad.

All in all, the slowness and weird behaviour of your current code is highly likely due to bad code design. Which obviously has led to that you don't really know what is going on in it once it runs.

[Tycho Brahe]

I mostly agree with johnp, but I have a couple of other points to make/things to say:

Sorting-wise bubblesort is a relatively slow sorting algorithm, even though it is often pimped out as one of the best. A better alternative might be quicksort or insertion sort. Insertion sort would be especially good as I get the feeling that your lists don't change drastically from frame to frame, so it would run relatively quickly.

You can also iterate through your lists when you create objects so as to have them in the correct place from the off. This could impact performance however if you create a large number of objects in one frame (eg a shotgun blast, or gibs from an explosion) so you could consider having a buffer to store all the "new" elements in, with only one iteration needed to insert all the objects.

I also agree that you should try to disentangle your z-ordering code from your entity management code. Having all entities inherit from a single "z-order" class may work, but it may be more adaptable later on to simply have a "z-order" object as a member of any entity classes. I may be wrong about this however, its more a matter of personal choice (I think).

I've noticed also that slowdowns mostly seem to occur when you have a large number of bullets on the screen as well, so it could be your bullet management code which is a fault here. You could consider simply having a set of float/integer/boolean arrays for the bullets to just record things like position, direction and status instead of having an array of bullet objects/entities (which is how I'm assuming you're doing it). This could be better performance wise.

hope this helps!

[Jonathan Whiting]

As an extra hint on sorting:

In actionscript (AS3 anyway, maybe AS2 as well but I don't know) Arrays have a myArray.sort(sortHint) function.  I believe it uses quicksort internally, but, importantly it's really pretty quick, and saves you fighting with sort code manually.  I've certainly used it for every-frame object sorting before with no noticeable impact.

[Draknek]

I don't think having lots of lists is necessarily a problem, as long as you've thought about how and where you're going to access/modify those lists. E.g. having an add() and a remove() method which decide which lists to edit rather than manually adding items to each relevant list.

I think the approach you've gone with makes as much sense as anything: insert new objects at the correct index and use bubble sort for frame-to-frame consistency. If you're having problems with this being unwieldy then you probably need to refactor it.

My solution would probably be to do it in a bitmap-based engine like FlashPunk or Flixel where you render objects in the traditional manner (blitting to a screen buffer). Then you know that after sorting your objects you can just iterate over them and be sure they'll be rendered in the right order. Of course, that would involve rewriting your game so isn't massively helpful to you right now.

[bart_the_13th]

Judging your game engine, I'll say go with multilayered background, like in some old console RPGs.
Or, you can just check if the player collide with background tiles, then swap it when necessary.
Or, instead of sorting everything, you just sort the visible walls, put all ground tile in background.

[bateleur]

At the moment there's so many lists to deal with and it's incredibly unweildy. I want to keep arrays of my different object types so that I can check bullets against blocks to see if they collide, without having to factor in shadows and other objects too.

I think the simplest fix to deal with your immediate problems (and hopefully avoid rewriting the entire thing) is to have each object on multiple lists.

Keep your lists of blocks, bullets, shadows and so on separate from one another, but don't sort them. Then have a single list of all renderable objects and sort just that one list based on depth. This should make your depth issues really straightforward to debug, because all you're dealing with is a single, sorted list. (And obviously you use the shorter, type-specific lists for stuff like collisions.)

[Tycho Brahe]

I think the approach you've gone with makes as much sense as anything: insert new objects at the correct index and use bubble sort for frame-to-frame consistency. If you're having problems with this being unwieldy then you probably need to refactor it.

I dont think I can stress this enough: don't use bubble sort. It's slow and horrible. Don't use it.

[grapefrukt]

another trick is to not z-sort on every frame, the bullets can likely make do with every third frame or something like that. that's a 300% speed improvement nearly for free!

[Jonathan Whiting]

another trick is to not z-sort on every frame, the bullets can likely make do with every third frame or something like that. that's a 300% speed improvement nearly for free!

Unfortunately it's not that simple.

If the sorting truly is the speed limiting element (and I'm of the opinion that if done efficiently it oughtn't be) then doing it every 3rd or whatever frame will improve net frame rate.  It will however introduce a stutter, as every 3rd frame takes longer to render.  This is frequently more unsightly than a steady but low frame rate.

A better solution along the lines of reducing computation if using bubble sort might be to only sort partially each frame (abort the bubble sort after x iterations).  I will emphasis again though if the sort speed is problematic it rather implies that the problem isn't as simple as it sounds.  Sorts should generally be quick operations as long as the lists involved aren't absolutely huge.

[st33d]

Any sorting algorithm you write in Flash is unlikely to be faster than the native sorting methods Array.sort and Vector.sort.

I've benchtested them and they are fast enough to make me believe that the sort is not being executed with actionscript but with compiled code. Much like BitmapData.copyPixels.

Any y based depthsort on MovieClips (or similarly with objects bearing a "y" property) can be quickly done like so:

Code:

package com.nitrome.util.clips {
	
	/* Depth sort all items in "clip" */
	public function depthSort(clip:DisplayObjectContainer, sort_on:String = "y"):void{
		var depthArray:Array = new Array();
		for(var i:int = 0; i < clip.numChildren; i++){
			depthArray.push(clip.getChildAt(i));
		}
		depthArray.sortOn(sort_on, Array.NUMERIC);
		i = depthArray.length;
		while(i--){
			if (clip.getChildIndex(depthArray[i]) != i) {
				clip.setChildIndex(depthArray[i], i);
			}
		}
	}

}

And you should definitely move all rendering code to one place, away from the engine code.

I've made this move recently and you end up with full control over the rendering. It's a lot easier to manage as well because you've got it all in one place. Game entities can have rendering methods, but just call them from your central rendering method.

Another note on depth sorting: Always sort at the y position of the feet of the object. If something is in front, it is because its feet are in front.

[Martin 2BAM]

I think AS3 arrays are quick sort because if the array is already ordered it takes O(n), and that's pretty fast, even for a thousand objects.

But if it changes drastically from one frame to the other it might introduce stutter. But it's not noticeable at all, even for 1000 objects.

So... not the best solution if you change your z constantly.

[Alistair Aitcheson]

Thanks for the help so far everyone. This is really really good advice!  

I'm personally of the opinion that the bubble sort algorithm isn't really the problem, although I do like the idea of aborting after x iterations. I noticed that when I told objects where to be inserted at first, rather than adding them to the end, there was no pause when I generated a large number of particles, unless that number was very large.

In the current version there's some enemies firing bullets. When you shoot the enemies they explode with 40 particles. When the particles were being added to the end of the list there was a long pause, but when they're added in an appropriate position it's fine. The main problem is that in doing this the code has become clumsy and mistake-prone. My current feelings are that the bubble-sort is fine as long as I add new objects in a sensible way.

I will have a look at alternative sorting algorithms and see what advantages they offer. I currently tend to have about 80 objects in the list at a time, although I expect in the finished game I'll expect to have many more if there's a lot of bullets and debris flying around. Is that a good number for a bubble sort?

I think seperating the game-objects from the Z-ordered images is a great idea. At the moment, each object contains a MovieClip object for its animation/image. Perhaps the images need to be stored seperately as a list in the game manager class, and each object points to (or sends commands to) the image representing it.

It also does need to be refactored significantly, and that will probably make things easier too. I will also have a look at the bullet code and check that there's nothing slowing things down.

At the moment I have the following lists: collidable objects, platform blocks, and shadows, for all active objects of each type. For each of these is a "to add" list, which moves them to their active list, and also adds them to the "Z-Order List". There's a lot of awkward and copied code here for the three different lists. The Z-Order list is the only list that is sorted, and when I perform a swap on the Z-Order list I also swap the objects Children list in the same way.

Perhaps I need to, instead of having an add() function and a remove() function for each object type, just have one add() function and one remove() function. Add() could decide which list to add an object into by its type, and remove() would remove objects from any lists they appear in.

A lot of great ideas here, and they're all very helpful. Many many thanks for all your suggestions, and let me know if you think of anything else.

[Tycho Brahe]

I'd be interested to see the performance of different sorting algorithms in flash. I've seen an application which compares different sorting algorithms in java, by sorting lists (identically sized, with identical random contents) with each algorithm and then graphing the result over a number of lists, with each list larger than the last. It would be interesting to see something similar in flash (I'm looking at you st33d)

[st33d]

I've recently done a minigame which has z-sorted effects pissing all over the place, and I'm sorting it using the method I listed. No slow down, 30 fps export.

I just put all the clips in one clip and run that function. No slow down. No fannying around with special sorts or trying to slot things into the array in the right place. Honest.

[oranda]

Hey all,

I'm working on a remake of Dam Busters for the Action 52 Owns project. You can have a go at it how it is here: Dam Busters (WIP)

I'm having trouble with Z-Ordering on the objects at the moment. You'll probably notice some bits where the Z-Ordering goes wrong in the demo, which I think I've tidied up. But as I've tried to expand and improve on the Z-Ordering system, more and more problems have come up and the code's getting more and more complicated and error-prone.

I can't be the first person who's tried to make a pseudo-3D game in Flash, and so I can't be the first person who's had to deal with this. Does anyone know of a good system for doing this? My current approach is way too complicated.

I'll describe my current approach below in case that's any help. You don't need to read it though, but it might shed a little light on my problem!

At the moment I have arrays of objects of each kind (blocks, moving objects (player, bullets, debris), and shadows). Each of these objects is inherited from a ZOrder object which has all the data it needs to arrange the objects properly. I have another array of all of these objects. Every loop I do a bubble-sort on this array by their position in the y-axis and z-axis, and every time I switch elements I perform swapChildren() on them as well. When an object is removed I have to remove it from all of these lists, and perform a removeChild() on it.

At the moment there's so many lists to deal with and it's incredibly unweildy. I want to keep arrays of my different object types so that I can check bullets against blocks to see if they collide, without having to factor in shadows and other objects too.

I've had to fix a lot of mistakes in my code such as it attempting to move children that have already been removed. I still have objects that aren't deleted properly, which seems to have a knock-on effect on the Z-Ordering (normally it means next time I want to remove something from the Z-Order array the wrong object gets removed).

Today I noticed that whenever I add an object (such as a particle or bullet) it gets stuck at the end of the array and the bubble-sort takes ages to get it to its correct position. This made the game pause for a while if I added lots of particles at once. I fixed this by adding functions to add an element into the middle of an array, then using addChildAt() to put the object in the right place in the list of children. But this ended up digging up plenty more errors, and there was so much fiddling and bug checking.

I think it mostly works now, but I'm not sure. As you can see it's way more complicated than I think it should be!

In short, there must be an easier way! Does anyone have any advice or know of any resources that could help?

Many thanks!

Probably the fastest (and easiest) way to do this is to make the array you render from temporary. Don't even worry about maintaining it between calls. Basic pseudocode would look like this:

// clear your temporary render list here. Just wipe it clean
temp_list.empty()

// now add everything from the object lists. There is probably a function to do it for you in a single call like this
temp_list.add(shadow_list)
temp_list.add(bullet_list)
temp_list.add(obstacle_list)
temp_list.add(player)

// sort it
temp_list.sort() // do this with whatever built in sort algorithm flash gives you. It WILL be faster than anything you can do in ActionScript, and it doesn't require a single line of code.

// and render your nicely sorted list
render_stuff(temp_list)

I know this may run counter to instinct, after all, how can rebuilding the render array every frame be fast?, but if you were to benchmark it, I think you'd be surprised at how fast it runs. If I had to guess I'd say it would probably be faster than your current system. All of the array copying and sorting will be happening with highly optimized code by some very smart people at Adobe, written in a lower level language than ActionScript.

[zez]

Code:

private function heightSort(a_thing:generic class you use for all your sprites, b_thing:same class.):Number
		{
			if(a_thing.y > b_thing.y ) {
			return 1;
			} else if(a_thing.drag.y < b_thing.y) {
			return -1;
			} else {
			return 0;
			}
		}

For the sort code works, and pretty friggin fast. Just run it from update. (so arrayofsprites.sort(heightSort))
Its (basically, save the fact that objects aren't reporting there actual Y coordinate but the y coordinate I want to test against to handle stuff like jumping) what Im using in ninja assault. I also recommend adding as little stuff as possible to the sorted array (for example, I add characters and enemy sprites, but not particle's, projectiles or the environment. In your case, you probably need to add the environment, as you actually want the option of running behind things to make mazes and such.)

I think, on a totally unrelated note, the most likely cause of your problem is either the garbage collector in flash (It gets called... kind of every once in awhile when it feels like it, and works on some stuff but not really very much of it, and makes everything hickup pretty hard when it gets called) or, your problem is that NOTHING is being properly garbage collected. You also need to properly remove references from an array (making objectx = null WILL get rid of objectx, however if arrayy looked like this [objectq, a donkey, objectx] it will now look like this [objectq, a donkey, null] as apposed to just cutting the null reference, and when you go to sort things, you probably will get as far in the sort algorithm as null, and then all your code will break well it trys to find the coordinate of a null object.

The ideal solution for this, believe it or not, is to never kill anything.
You basically want to set things somewhere out of the way (like at (-100,-100) or something), or make them invisible, then stop calling update on them, till you need that object back at which point you re-use the previous object, if there is one, and if there isnt make a new one. This basically requires you to have an array of objects (I recommend having an array of objects of a specific type) and a flag to say weather or not they are dead, so you can figure out if you have to make a new one or just reuse and old one. This will also help you avoid having to height sort a million objects, as you will never create a million objects.

Final bit of advice. For and while loops are comparable in speed, depending on what you are doing. I recommend for loops for looping (ack, tongue twister) through arrays, mostly because you dont have to set whatever variable to 0 then start the loop

Code:

i = 0;
while(i < array.length)
{
do something to array[i];
i++
}
vs
for{int:i = 0; i < array.length; i++)
{
do something to array[i];
}
basically.

HOWEVER, for each is slower then a retarded geriatric. Dont use it in a game, as temptingly simple as it would be.

[BadgerManufactureInc]

For simple objects such as particles that only require you to know their x, y and frame, have you considered just storing their positions in arrays.. you could argue that objects are overkill.

When I do use objects I use arrays of capped object pools.  My on-screen objects are pushed or spliced into another structure, an onscreen array.  The advantage is that you never have to instantiate an object in real time, and you never have to add or remove children, only push or splice.

In terms of ordering, I'm using pure blitting, so as long as I draw things in the right order I don't even need to add anything to the stage apart from my canvas.

My tutorial at 8bitrocket shows this system working.

[zez]

Badger makes a couple solid points, and I should probably mention that my sorting method assumed you where blitting, although it would still work as the order to add things to the screen, just a great deal slower.

[Theotherguy]

Why the hell are you sorting things? Obviously the fastest way is to maintain a sorted list as you insert objects, rather than pre-inserting them and THEN sorting. You also shouldn't maintain a list of objects with drawing data embedded! That's just silly. You should have a temporary list of objects to render that gets cleared every frame. This will be much, much, faster, and much easier to understand!


Here's some pseudocode:
1. Do all of your game logic.
2. Create an empty render list.
3. For each entity
   a. Insert entity into list at right Z order.
4. For each entity in the render list from back to front.
   a. render entity
5. Clear (or delete) the render list.
6. Goto 1

This has O(3N) runtime, wheras ANY sorting method will have at best O(N*log(N)) runtime.

Also, you should just push the index of the object onto the list, rather than the object itself, provided your list of objects does not change during the render phase (and it should not).

EDIT:
I am dumb. Do not do this.