As you probably know I decided to completely rewrite the Next graphics tool into something a lot more useful, well this has taken much longer than expected so I had to leave my z80 coding behind and get back to some c#. However, with that mostly out of the way I am ready to continue with my game development.
I have started building a new game engine in z80 and therefore I have had to look at this machine as a fresh platform starting with the 128 sprites.
Normally in other languages I write a linked list for accessing my sprites with used list and free list header pointers and this is no different, I am not going to give all my code away for this as I need to keep some stuff for me and my games, but I will go through some of the principles and give you some z80 snippets to point you in the right direction.
So, what is a linked list?
Linked lists come on a couple of varieties, a single linked list and a double linked list, me I implement a double linked list as that makes it easier to insert before, by simply traversing backwards one link. There is another variety called circular linked list, which just links the end to the start but that is no good for my purpose’s.
What is the benefit?
Ok say we had 128 sprites and we needed to find a free sprite, it would be quite easy to cycle through each sprite and check to see when one is used and return the index into the array, then multiply that index by the size of the sprite data and to get the address. Yes, I know 128 is not many sprites to check and it can be quite fast, but what happens when you want to draw, animate or even just move only the used sprites? Do you cycle through each one again checking to see if they need moving or drawing? Or would it be easier and faster to get the address of the next used sprite from this sprite? For me I think it may be quicker using a linked list so I only have to go through the used ones, or the free ones if I want a new one!
By having both free and used lists heads you can easily have the two lists within the same block of data and insert and remove from each list simply by changing the addresses of the next and previous links.
So my Object structure looks like this:-
struct object prevObject word 0 nextObject word 0 id byte 0 // this object id actionFunction word 0 // the objects current action function animaton word 0 // animation sequence animationFrame byte 0 // animation fame animationDelay byte 0 xPos word 0 // x position yPos word 0 // y position mirrorRotateBits byte 0 // bits 7-4 = Palette offset/colour index // bit 3 = X mirror // bit 2 = Y mirror // bit 1 = Rotate // bit 0 = MSB of X coordinate patternScaleBits byte 0 // bit 7 = H (1 = sprite uses 4-bit patterns) // bit 6 = N6 (0 = 1st 128 bytes of the pattern 2nd 128 bytes) // bit 5 = 1 if relative sprites are composite, // bits 4-3 = X scaling (00 = 1x, 01 = 2x, 10 = 4x, 11 = 8x) // bits 2-1 = Y scaling (00 = 1x, 01 = 2x, 10 = 4x, 11 = 8x) objectState byte 0 // states for the object such as turning, jumping, dying lastObjectState byte 0 // previous state of the object objectVariables byte 0 // Object Variables byte 0 // Object Variables ends // 16 bytes
As you can see my objects have prevObject and nextObject nodes, these are the addresses of the next sprite in the list. Therefore, it’s just a matter of linking all the objects together on the free list, which is done during game initialization, then during the game, if you want another object you simply remove it from the free list and add it to the used list. And to free a sprite you remove it from the used list and add it to the free list.
//-------------------------------------------------------------------------- // insert at the end of the list // in ix which list // in iy object to insert (new object) // // out iy object inserted // dirty hl,bc,ix,iy //-------------------------------------------------------------------------- insertObjectEnd: ld hl,(ix+listHead.lastObject) // get the last object ld (iy+object.prevObject),hl // tell this they have a new parent from the bottom of the list ld (iy+object.nextObject),0 // terminate their children ld (iy+object.nextObject+1),0 // terminate their children ld bc,iy // move registers ld (ix+listHead.lastObject),bc // tell the lists last object, it has a new child ld ix,hl // get the saved last object ld (ix+object.nextObject),bc // tell the object it has a new child ret
Removing and adding is just a matter of changing the addresses in the prevObject and nextObject nodes. The hard part is getting your head around the linking and remembering what registers you need to preserve, but thats assembler for you.
As I have said I am not going to give all my z80 code away however I will give you a cleaned-up version my C implementation from my game skyfight.io which is easy to read and maybe port if you want to.
#define MAX_LINKS 1024
struct link
{
connection * parent;
connection * child;
int id;
.... data
};
struct listHead
{
link * firstConnection;
link * lastConnection;
};
link links[MAX_LINKS];
listHead usedLinks;
listHead freeLinks;
//--------------------------------------------------------------
//
// linked list
//
//--------------------------------------------------------------
void initLinkList()
{
for (int p = 1; p < MAX_LINKS; p++)
{
links[p].child = &links[p + 1];
links[p].parent = &links[p - 1];
links[p].id = p;
}
//link[0].child = NULL;
links[0].parent = nullptr;
links[0].child = &links[1];
links[0].id = 0;
links[MAX_LINKS - 1].child = nullptr;
links[MAX_LINKS - 1].parent = &links[MAX_LINKS - 2];
links[MAX_LINKS - 1].id = MAX_LINKS - 1;
freeLinks.firstLink = &links[0];
freeLinks.lastLink = &links[MAX_LINKS - 1];
usedLinks.firstLink = nullptr;
usedLinks.lastLink = nullptr;
}
//--------------------------------------------------------------------------
//
// insert at the before this one
//
//--------------------------------------------------------------------------
void insertLinkBefore(linkHead * thisList, link * thisLink, link* newLink)
{
// hook the new link infront of link
newLink->parent = thisLink->parent;
newLink->child = thisLink;
// now if this was the first link in the list
if (thisLink->parent == nullptr)
{
// tell the first link pointer to go to the new link first
thisList->firstLink = newLink;
}
else
{
// Not the first so get where link was linked from
// and place the new link into that link next
thisLink->parent->child = newLink;
}
// and finally place the new link into this link
thisLink->parent = newLink;
}
//--------------------------------------------------------------------------
//
// insert at the after this one
//
//--------------------------------------------------------------------------
void insertLinkAfter(linkHead * thisList, link * thisLink, link* newLink)
{
// hook the new link infront of link
newLink->parent = thisLink;
newLink->child = thisLink->child;
// now if this was the first link in the list
if (thisLink->child == nullptr)
{
// tell the last link pointer to go to the new link first
thisList->lastLink = newLink;
}
else
{
// Not the last so get where link was linked from
// and place the new link into that link next link
thisLink->child->parent = newLink;
}
// and finally place the new link into this link
thisLink->child = newLink;
}
//--------------------------------------------------------------------------
//
// insert at the beginning of the list
//
//--------------------------------------------------------------------------
void insertLinkBeginning(linkHead * thisList, link* newLink)
{
// see if there is actually a list
if (thisList->firstLink == nullptr)
{
// there is not so make the new link the first on the list
thisList->firstLink = newLink;
// and only one on the list
thisList->lastLink = newLink;
newLink->parent = nullptr;
// and tell it were the first and last
newLink->child = nullptr;
}
else
{
// no must have link on the list so insert at the beginning of the list
insertLinkBefore(thisList, thisList->firstLink, newLink);
}
}
//--------------------------------------------------------------------------
//
// insert as the end link
//
//--------------------------------------------------------------------------
void insertLinkEnd(linkHead * thisList, link* newLink)
{
// hook the new link at the end of list
newLink->parent = thisList->lastLink;
newLink->child = nullptr;
thisList->lastLink->child = newLink;
thisList->lastLink = newLink;
}
//--------------------------------------------------------------------------
//
// add item at the end of the list
//
//--------------------------------------------------------------------------
void addLinkLast(linkHead * thisList, link* newLink)
{
// see if there is actually a list
if (thisList->firstLink == nullptr)
{ // there is not, so make the new link the first on the list
thisList->firstLink = newLink;
// and only one on the list
thisList->lastLink = newLink;
newLink->parent = nullptr;
// and tell it were the first and last
newLink->child = nullptr;
}
else
{
// no must have link on the list so insert at the beginning of the list
insertLinkEnd(thisList, newLink);
}
}
//--------------------------------------------------------------------------
//
// Remove from linked list
//
//--------------------------------------------------------------------------
void removeLink(linkHead * thisList, link* thisLink)
{
// if this was the first link on the list
if (thisLink->parent == nullptr)
{
// make the first link jump to the next
thisList->firstLink = thisLink->child;
}
else
{
// its not so get the one that was pointing to this one point to its child
// tell its parent to go directly to its child
thisLink->parent->child = thisLink->child;
}
// see if it was the last on the list
if (thisLink->child == nullptr)
{
// it was so make the this link parent the last on the list
// but see if this has a parent
if (thisLink->parent == nullptr)
{
thisList->firstLink = nullptr;
}
else
{
thisList->lastLink = thisLink->parent;
thisLink->parent->child = nullptr;
}
}
else
{
// tell its child that it has a new parent
thisLink->child->parent = thisLink->parent;
}
}
//--------------------------------------------------------------------------
//
// Remove from linked list and add to free list
//
//--------------------------------------------------------------------------
void deleteLink(link* thisLink)
{
removeLink(&usedLinks, thisLink);
addLinkLast(&freeLinks, thisLink);
}
//--------------------------------------------------------------------------
//
// Get a free link from the free list and add to the used list
//
//--------------------------------------------------------------------------
link* getFreeLink(link* otherLink, uInt8 Where)
{
if (freeLinks.firstLink != nullptr)
{
// take the next off the top;
link* newLink = freeLinks.firstLink;
// remove from the empty list
removeLink(&freeLinks, freeLinks.firstLink);
// and insert it to the used list
switch (Where)
{
case LIST_TOP:
insertLinkBeginning(&usedLinks, newLink);
break;
case LIST_END:
addLinkLast(&usedLinks, newLink);
break;
case BEFORE_LINK:
insertLinkBefore(&usedLinks, otherLink, newLink);
break;
case AFTER_LINK:
insertLinkAfter(&usedLinks, otherLink, newLink);
break;
}
return newLink;
}
return nullptr;
}
//--------------------------------------------------------------------------
//
// locate the link in the lits by its ID
//
//--------------------------------------------------------------------------
link* locateLink(Int16 thisIndex)
{
link* link = usedLinks.firstLink;
while (link != nullptr)
{
if (link->id == thisIndex)
{
return link;
}
link = link->child;
}
return nullptr;
}
Next time making the art for my game level using next graphics.
