Where I am in my game development?

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.

Leave a Reply

Your email address will not be published. Required fields are marked *