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?
Question about linked object lists.
Moderator: Moderators
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
- rainwarrior
- Posts: 8731
- Joined: Sun Jan 22, 2012 12:03 pm
- Location: Canada
- Contact:
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.
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.
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.
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: Question about linked object lists.
More like I'm trying to untangle spagetti code.
-
- Posts: 1565
- Joined: Tue Feb 07, 2017 2:03 am
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
LDA len
BEQ _specialCase
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.
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.
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: Question about linked object lists.
I was able to trick the engine into thinking the slot entry register was an object.
Re: Question about linked object lists.
Here are the subroutines I'd use for adding and removing objects to/from linked lists:
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.
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
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.