Question about linked object lists.

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Question about linked object lists.

Post by psycopathicteen »

Tokumaru introduced me to the concept of linked lists. It sounded like a good idea in theory, but it ended up being complicated for me to implement. Now I realized something I didn't initially think about.

Was I supposed to make a dummy object slot that is always "active" to start the list so that the first real object doesn't need special case to despawn?
User avatar
rainwarrior
Posts: 8731
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Question about linked object lists.

Post by rainwarrior »

The head or tail of a linked list is a special case for some operations. Creating an extra entry for the head or tail that is never removed is one way of dealing with that special case.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Question about linked object lists.

Post by tokumaru »

I had never thought about this, but are you talking about modifying the variable that points to the beginning of the list, which only happens when the first object is loaded/unloaded? Well, if you use arrays of structures for your object slots, you don't need to have a dummy slot taking up the same memory as an actual slot, you could have one extra entry only in the array that links to the next object.

I don't think that special-casing this is a big problem though... IIRC, I believe we agreed we needed a variable indicating the previous slot that was processed, so if this is verified to be invalid (e.g. >128, so you can use the N flag) when relinking, you know it's a special case and you have to modify the variable that points to the beginning of the list. It's just a bmi/bpl instruction, it's no big deal.

You have to consider that despawning the first object is something that will happen once every several seconds, if that, so there's very little to gain by optimizing the hell out of this. This is not the type of task you should be worrying about optimizing.
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Question about linked object lists.

Post by psycopathicteen »

More like I'm trying to untangle spagetti code.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Question about linked object lists.

Post by Oziphantom »

Another way is you keep a count/length of the list. And then you can do a
LDA len
BEQ _specialCase
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Question about linked object lists.

Post by tokumaru »

That's one LDA more than you need with the other solution, plus the INCs and DECs to change that variable.

You already have a flag (invalid slot index) indicating the end of the list, and you already load it when relinking the list. You really only need the one BMI or BPL to detect the special case.
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Question about linked object lists.

Post by psycopathicteen »

I was able to trick the engine into thinking the slot entry register was an object.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Question about linked object lists.

Post by tokumaru »

Here are the subroutines I'd use for adding and removing objects to/from linked lists:

Code: Select all

;X: index of the current item;
;FirstItem: index of the first item in the linked list;
AddItem:
	lda FirstItem ;get the index of the current first item
	sta NextItem, x ;have the new item point to it
	stx FirstItem ;make the current item the first one
	rts ;return

Code: Select all

;X: index of the current item;
;FirstItem: index of the first item in the linked list;
;PreviousItem: index of the previously processed item that WASN'T REMOVED from the list;
RemoveItem:
	lda NextItem, x ;get the index of the next item
	ldx PreviousItem ;get the index of the item that pointed to this one
	bmi :+ ;skip if this is the first item
	sta NextItem, x ;make the previous item point to the next item
	rts ;return
:	sta FirstItem ;make the next item the first
	rts ;return
If there are multiple linked lists (i.e. separate groups of objects), index register Y can be used to access a "FirstObjects" array, instead of the "FirstItem" variable.

I really don't mind that bmi handling the special case of the first item, as it just costs very little CPU time and the code is still pretty clear and easy to follow, but if "tricking the engine" and eliminating the special case doesn't have any drawbacks, then that's fine too.
Post Reply