Every good programming technique

[tokumaru]

I tried your suggestion of using a shared "previous" variable, but I ran into a problem. When there's two consecutive objects dying at once, the second object links the already dead first object to the next object, instead of linking the last active object to the next object.

I see what you mean. Well, you should only remember the previous active object. If the current object dies, don't update the variable. the only reason we need to know the previous object is because we may need to change its "next" field in case the current one dies, so as long as you keep a reference to the previous active object, its "next" field will be changed repeatedly as the objects after it, no matter how many, die.

I don't know what your doing, but I'm going to have the object handler detect blank slots, and do the link-list rearranging inside the object handler routine.

Sounds slow, considering it's doable without searching, but do whatever you feel comfortable with. I was just explaining why handling linked lists doesn't need to be so complicated as it sounds at first.

[Sik]

I don't know the exact structure you're using for composite objects, but assuming you do process them in the order specified by the list, simply saving each object's index in a variable (a single global variable, overwritten by each object) as they're processed will allow every object to know which the one immediately before it is.

This works when an object is deleting itself, it won't work when you're deleting another object instead.

Also a big advantage of using linked lists is that an object can belong to multiple lists. For example, you could have a global list with every object, and then individual lists for different groups (enemies, items, etc.) which can be useful when sorting objects for drawing or, more importantly, when an object wants to interact with others (scanning a single group is much cheaper than scanning everything). The latter really matters when you have a lot of objects.

Another advantage of using linked lists is that you never get to stumble upon empty slots when processing objects, and if you have to add an object, you can have a list of free slots where you outright grab whatever is the free slot available without any sort of looping. So yes, linked lists are noticeably more complex to handle, but if object performance is a serious issue, they can be worth the effort.

[tokumaru]

This works when an object is deleting itself, it won't work when you're deleting another object instead.

Only an object can delete itself in my engine, and I think this is a good thing, because objects may have a bit of cleaning up to do before dying, and it's not nice to let others clean up your mess. An object can request another one to delete itself, though.

Anyway, since this is a thread about programming techniques, I guess I'll show how I handle my linked lists. This is 6502 code though, since my console of choice is the NES, hopefully that won't be a problem. I also use some ca65 features, but those should be self-explanatory.

I use several linked lists to control my objects: one for the empty slots, and one for each group of active objects. When the level first starts, the groups are all empty, so the indices that indicate the start of each list are all invalid pointers:

Code: Select all

	;empty all groups
	lda #$ff
	.repeat Object::GROUP_COUNT, Group
	sta Object::FirstObjects+Group
	.endrepeat

The list of empty slots, on the other hand, is full, so this is how it's initialized:

Code: Select all

	;create a linked list of 24 empty object slots
	lda #$ff
	ldx #$17
:	sta Object::InstancesNext, x
	txa
	dex
	bpl :-
	sta Object::FirstEmptySlot

This just makes each slot point to the next (except the last slot, gets an invalid index to signal the end of the list), and makes the Object::FirstEmptySlot variable indicate the first slot. I do it backwards because it's slightly faster.

This function removes an empty slot from the list so you can use it:

Code: Select all

	;get the index of the second empty slot
	lda Object::InstancesNext, x

	;get the index of the first empty slot
	ldx Object::FirstEmptySlot
	bmi Return

	;make the second empty slot the first
	sta Object::FirstEmptySlot

Return:

	;slot index now in X
	rts

If there are no more free slots, $ff is returned. I should move the lda to the top though, so the state of the N flag after the ldx is preserved, and I can just check N to see whether X contains a valid slot index. EDIT: DONE!

Now this adds the slot specified in the X register to one of the groups:

Code: Select all

	;add the current object to a group of objects
	lda Object::FirstObjects+Group
	sta Object::InstancesNext, x
	stx Object::FirstObjects+Group
	rts

I made one function for each group to keep things fast, but you could just as well specify the group using the Y register and accomplish the task with a few more instructions.

Anyway, once the object dies, comes a slightly more complicated procedure, which is removing the slot specified in the X register from the group:

Code: Select all

	;remove the current object from a group of objects
	lda Object::InstancesNext, x
	ldy Object::Previous
	bmi :+
	sta Object::InstancesNext, y
	rts
:	sta Object::FirstObjects+Group
	rts

If there's no previous object (the current one is the first), the next one becomes the first. Otherwise, overwrite the previous object's "next" field. Again, the group index is hardcoded and I have one function for each group, but you can generalize it at the cost of making the code slightly more complex.

The last step is to return the slot specified in the X register to the list of free slots:

Code: Select all

	;make the first empty slot the second
	lda Object::FirstEmptySlot
	sta Object::InstancesNext, x

	;make this the first empty slot
	stx Object::FirstEmptySlot

	;return
	rts

As you can see, all the functions are fairly short and straightforward. I can only see advantages in managing slots using linked lists instead of searches, specially if you have many slots. Grouping objects is also great for performance, because you can limit the object interactions (collisions!) by checking only the groups that are relevant to each object.

[Sik]

Only an object can delete itself in my engine, and I think this is a good thing, because objects may have a bit of cleaning up to do before dying, and it's not nice to let others clean up your mess.

In practice it's likely the object won't be cleaning up itself though, but will call a subroutine from the object manager to do it, since the manager itself will need its own cleanup to remove the object (especially when the data for the object being destroyed is currently being used, you really don't want to wreck that state) - and at that point what you're saying becomes moot, because that subroutine can just call any cleanup code that may be needed by the object.

[tokumaru]

In practice it's likely the object won't be cleaning up itself though, but will call a subroutine from the object manager to do it

In most cases, yeah, but there are a few things that only the object itself can do. From the top of my head, I can name saving the state for a future reactivation of the object. IIRC, even the Sonic games on the Genesis dedicate, per object, only 1 byte of information that will persist throughout the entire level, and depending on the amount of state you need to back up when an object is deactivated, you might need to encode multiple aspects of the state to fit in a single byte, and that is unique to each object. Sure you could encode the information every frame and buffer the result in the object's slot, so the object manager could just copy it to the state table, but that'd be a waste of CPU time since most of the time the data would not be used.

In my engine, I only have 1 bit guaranteed for each object (alive/dead), and an extra chunk of memory that objects that need to remember more than that can use, and only the objects themselves know how many bytes they use and how that data is encoded.

[psycopathicteen]

I don't know what your doing, but I'm going to have the object handler detect blank slots, and do the link-list rearranging inside the object handler routine.

Sounds slow, considering it's doable without searching, but do whatever you feel comfortable with. I was just explaining why handling linked lists doesn't need to be so complicated as it sounds at first.

Wouldn't you still need to check afterwards if an object is dead or not so you know if you should save it's index or not?

[tokumaru]

Depends on how you do it. The way I do it, each object is responsible for saving its own index, it's not done automatically. The first thing every object does is check if it needs to destroy itself. If it doesn't, THEN it saves its index.

[Kannagi]

For good practice I would add:
For sprites it is wrong to manipulate their x and y position directly (otherwise it becomes difficult for the clipping), it is better function / macro that manages it.
Same for the joypad to variables that recover during the late VBlank.
A buffer for the tranfer in VBlank.
For palettes I transfers 2 times (1: pal BG , 2 : pal Sprite).

For positions I don't use fixed point, only for speed (you just have to put to zero only units).

After lots of things encoded before starting a game, animation, background, joypad ect.
There are 'good' and 'bad' practice too.

I don't use the chained lists, just a table with all my sprites for example:

Code: Select all

ldx #$00 ; Character 1
lda s_Character+_x,x
;code ect

ldx #$40 ; Character 2
lda s_Character+_x,x
;code ect

My structure is size of $40 (this is RPG)
But for other types of games can I think has cut $20
I put a 's_' to know the type of my variables.

Of course this is only my experience, habits are different for each one.

[psycopathicteen]

I figured why I had slowdown with the pumpkin-head boss exploding. I placed an elevator platform too close to the side of the bosses's scrolling range.

At least I got the linked list to work.

[Sik]

In most cases, yeah, but there are a few things that only the object itself can do. From the top of my head, I can name saving the state for a future reactivation of the object. IIRC, even the Sonic games on the Genesis dedicate, per object, only 1 byte of information that will persist throughout the entire level, and depending on the amount of state you need to back up when an object is deactivated, you might need to encode multiple aspects of the state to fit in a single byte, and that is unique to each object.

I don't see how an object-specific deinit function can't take care of that? This is stuff that would be currently stored in the object state, you don't need the object to be the one currently running for that.

But I guess this brings me up another point: don't treat each object through a single subroutine. Have dedicated init, run (logic) and draw subroutines (and possibly a deinit one, as the conversation brought up). Init/deinit are called when an object is created (to set up the initial state) or destroyed (to preserve any permanent state or destroy other objects). You also want logic and draw to be separate, first because the drawing order may be different than the execution order, and second because then this allows you to implement frameskip if needed (by running logic and skipping drawing).

[tokumaru]

don't treat each object through a single subroutine. Have dedicated init, run (logic) and draw subroutines (and possibly a deinit one, as the conversation brought up).

Yes, this is what I do. I never felt the need for a dedicated deinit routine though, since the object itself decides when to destroy itself, so it just runs the appropriate code right there on the spot.

You also want logic and draw to be separate, first because the drawing order may be different than the execution order, and second because then this allows you to implement frameskip if needed (by running logic and skipping drawing).

That's true. I tried to run away from that for a while, by updating and drawing in one go, but that introduced all sorts of limitations, so my current model does use separate routines.

[psycopathicteen]

I'm kind've disappointed that the linked list didn't give the performance boost I wanted it to. When I do CPU scanline tests, the bar is still scraping the bottom of the screen, meaning there's still some lag frames.

[Sik]

Maybe your problem is something else? Did you consider measuring each part of the program instead? E.g. how long it takes to draw all the objects?

[psycopathicteen]

It seems like my level object spawning code is taking 11 scanlines, and will increasingly take longer the more objects are in the level. I should figure out a way of bookmarking it.

[rainwarrior]

I'm kind've disappointed that the linked list didn't give the performance boost I wanted it to. When I do CPU scanline tests, the bar is still scraping the bottom of the screen, meaning there's still some lag frames.

Well, a linked list only saves the time spent testing empty slots for emptiness, which is usually pretty minor to begin with. Most likely the stuff you do when a slot ISN'T empty takes a lot more CPU time. The linked list is probably only going to pay off significantly if you have to iterate through the list many times per frame.

The worst case performance is probably going to be when all the slots are full, too. The linked list as an optimization isn't effective on this case, too, unless you're iterating partial lists many times per frame (and of course has the drawback of requiring memory to store all the links).

A linked list can be a great choice in many cases, but it's always situational. Going back to good programming techniques, if you want to find the effective thing to optimize, you need to profile your code to see what code takes the most time in a frame. e.g. If one subroutine is run 50 times in a single frame, that's a 50x performance multiplier on any optimization you do to it.