It is currently Wed Jul 18, 2018 9:30 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 8 posts ] 
Author Message
PostPosted: Sun May 13, 2018 3:39 am 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2712
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?


Top
 Profile  
 
PostPosted: Sun May 13, 2018 10:45 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6402
Location: Canada
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.


Top
 Profile  
 
PostPosted: Sun May 13, 2018 10:52 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10597
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
PostPosted: Sun May 13, 2018 12:13 pm 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2712
More like I'm trying to untangle spagetti code.


Top
 Profile  
 
PostPosted: Mon May 14, 2018 4:33 am 
Offline

Joined: Tue Feb 07, 2017 2:03 am
Posts: 477
Another way is you keep a count/length of the list. And then you can do a
LDA len
BEQ _specialCase


Top
 Profile  
 
PostPosted: Mon May 14, 2018 8:38 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10597
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
PostPosted: Mon May 14, 2018 7:20 pm 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2712
I was able to trick the engine into thinking the slot entry register was an object.


Top
 Profile  
 
PostPosted: Mon May 14, 2018 8:59 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10597
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: tepples and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group