nesdev.com
http://forums.nesdev.com/

Question about linked object lists.
http://forums.nesdev.com/viewtopic.php?f=2&t=17353
Page 1 of 1

Author:  psycopathicteen [ Sun May 13, 2018 3:39 am ]
Post subject:  Question about linked object lists.

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?

Author:  rainwarrior [ Sun May 13, 2018 10:45 am ]
Post subject:  Re: Question about linked object lists.

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.

Author:  tokumaru [ Sun May 13, 2018 10:52 am ]
Post subject:  Re: Question about linked object lists.

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.

Author:  psycopathicteen [ Sun May 13, 2018 12:13 pm ]
Post subject:  Re: Question about linked object lists.

More like I'm trying to untangle spagetti code.

Author:  Oziphantom [ Mon May 14, 2018 4:33 am ]
Post subject:  Re: Question about linked object lists.

Another way is you keep a count/length of the list. And then you can do a
LDA len
BEQ _specialCase

Author:  tokumaru [ Mon May 14, 2018 8:38 am ]
Post subject:  Re: Question about linked object lists.

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.

Author:  psycopathicteen [ Mon May 14, 2018 7:20 pm ]
Post subject:  Re: Question about linked object lists.

I was able to trick the engine into thinking the slot entry register was an object.

Author:  tokumaru [ Mon May 14, 2018 8:59 pm ]
Post subject:  Re: Question about linked object lists.

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

Code:
;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:
;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.

Page 1 of 1 All times are UTC - 7 hours
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/