Best way to manage sprites

Ask anything your want about Megadrive/Genesis programming.

Moderator: BigEvilCorporation

Post Reply
Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Best way to manage sprites

Post by Sik » Fri Nov 10, 2017 11:35 pm

Splitting from viewtopic.php?f=2&t=2739#p32653 because I don't want to pollute that thread.
Miquel wrote:
Fri Nov 10, 2017 2:17 pm
About the "Reset/Clear" function:
As you do with a typical 3D game where you resend all the meshes (triangles) every frame to the render engine, I think is convenient to reset the sprite list every frame not as an optional behaviour in your custom code but as an embedded working idea for most situations. Are there exceptions? Of course! but for the complexity of a MD game is necessary this approach as a basis.
1) It's an API for the sprite manager, so it gets a subroutine because that's how APIs work (I'm not going to inline that into an unrelated portion of code and ruin organization when it's a non-issue)
2) I actually managed to get bitten once by not making clear optional (tip: don't ever do a fade in function that halts the game unless you explicitly make it not clear the sprite table)
Miquel wrote:
Fri Nov 10, 2017 2:17 pm
About the "AddSprite" function, but first a little about the 68K philosophy:
The idea behind the implementation of the 68000 itself is that ideally a function/routine uses all free 15 registers and when it needs more register another function is called. Was designed this way because an experienced programmer uses around 10 local variables in a complex function. Probably right now you are thinking that not all functions should be complex in a program, if so: don't forget about inlining/macros/defines and it's virtues.

This is how the cpu is optimized at it's maximum, you use all 15 registers for your current task, you need to call for another task, you push almost all registers, push the parameters, do the call to subroutine, do the task, pop back all the register,... and so on.
So calling to a subroutine is a heavy task!
I normally arrange things into "major" and "minor" subroutines. The former are the big chunks of program logic and use up all registers, the latter are meant to be helpers within an algorithm and are only expected to scratch a few (since the remainder registers would be still in use by the algorithm that invoked them).

Also I don't know how pushing registers all the time is faster, memory accesses are slow. Better to reserve a few registers to scratch for minor subroutines. Heck, even the 68000 C ABI reserves a few for this reason.
Miquel wrote:
Fri Nov 10, 2017 2:17 pm
About the "AddSprite":
In the same way in other environments, while going for real, you don't do a "PutPixel" or a "PutTriangle" because the continuing calling/returning will completely kill the cpu, the same happens on the 68K when trying to use a "AddSprite".
The reason you don't build complex primitives on top of PutPixel is because often you can optimize away all the checks by doing clipping first (and I haven't found a way to get rid of the checks AddSprite does, as in a metasprite you still want to get rid of the sprites outside the boundaries, and you always want to check against the sprite limit to prevent a crash).

The reason you don't do PutTriangle but instead whole models (and in practice not even that, you just build a huge list to be sent all at once) is because the CPU-GPU bus and starting a draw call is a massive bottleneck. Remember OpenGL used to literally work the PutTriangle way at some point - because early on that didn't matter.

And that isn't any different here, in fact: ClearSprite starts the list, AddSprite builds the list, UpdateSprite submits it.
Sik is pronounced as "seek", not as "sick".

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Best way to manage sprites

Post by Miquel » Tue Nov 14, 2017 3:21 pm

Sik wrote:
Fri Nov 10, 2017 11:35 pm
1) It's an API for the sprite manager [...]
What api are you talking about? SGDK perhaps? but we were talking about code in asm, what has to do that with SGDK which is in C?

I will reply the rest when I understand what are you referring to...

EDIT:
Sik wrote:
Fri Nov 10, 2017 11:35 pm
Heck, even the 68000 C ABI reserves a few for this reason.
Nothing concludes by "68000 C ABI" on google. I suppose you are relating to the default call convention used by GCC on a 68K, is this right?
HELP. Spanish TVs are brain washing people to be hostile to me.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Best way to manage sprites

Post by Sik » Tue Nov 14, 2017 5:10 pm

Miquel wrote:
Tue Nov 14, 2017 3:21 pm
Sik wrote:
Fri Nov 10, 2017 11:35 pm
1) It's an API for the sprite manager [...]
What api are you talking about? SGDK perhaps? but we were talking about code in asm, what has to do that with SGDK which is in C?
I was referring to one's own APIs ( '-')

Different parts of the program can be grouped into "subsystems" with their own APIs that are used as building bricks by other parts of the program (e.g. the Clear/Add/UpdateSprites subroutines used for manipulating the sprite table in our case). Keeps things organized and makes it easier to modify individual parts without risk of breaking everything else as their internals are isolated (they don't care how it works, just what you have to give them). No need to work around it unless you're having a severe performance problem (and you can prove it), and that will be at the expense of maintenance.
Miquel wrote:
Tue Nov 14, 2017 3:21 pm
EDIT:
Sik wrote:
Fri Nov 10, 2017 11:35 pm
Heck, even the 68000 C ABI reserves a few for this reason.
Nothing concludes by "68000 C ABI" on google. I suppose you are relating to the default call convention used by GCC on a 68K, is this right?
It's like literally the only one it supports on 68000, I think? =/ (could be wrong, but either way, yeah that one)
Sik is pronounced as "seek", not as "sick".

Chilly Willy
Very interested
Posts: 2984
Joined: Fri Aug 17, 2007 9:33 pm

Re: Best way to manage sprites

Post by Chilly Willy » Tue Nov 14, 2017 6:13 pm

There are still some oooooooold compilers for the 68000 on for DOS/Windows, Amiga, and Atari ST. If you don't want a compiler that will need an emulator (or a 20-something year-old machine) to run, go with gcc. :lol:

As for the gcc 680x0 ABI, all parameters are pushed as longs on the stack, preceded by the return address. So when you first enter a function, the stack is arranged like this:

0(sp) return address
4(sp) leftmost arg
8(sp) next arg going right
etc

d0 is the return value (d0-d1 for 64 bits values)
d0-d1/a0-a1 scratch
d2-d7/a2-a6 must be saved by the function if used

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Best way to manage sprites

Post by Miquel » Tue Nov 14, 2017 6:45 pm

Sik wrote:
Tue Nov 14, 2017 5:10 pm
It's like literally the only one it supports on 68000, I think? =/ (could be wrong, but either way, yeah that one)
Must be another one to support exceptions, but yeah it's pretty much the only usable.
Sik wrote:
Fri Nov 10, 2017 11:35 pm
2) I actually managed to get bitten once by not making clear optional (tip: don't ever do a fade in function that halts the game unless you explicitly make it not clear the sprite table)
Do not allow a function EVER to halt the global game loop function! Seems the easy way but complicates everything in the long run. In the non-halt way you can do the fade, do I don't think the result would be the desired one.
Sik wrote:
Fri Nov 10, 2017 11:35 pm
I normally arrange things into "major" and "minor" subroutines. The former are the big chunks of program logic and use up all registers, the latter are meant to be helpers within an algorithm and are only expected to scratch a few (since the remainder registers would be still in use by the algorithm that invoked them).
I like the idea, a way to reduce code, and avoid repeated code. Nice! But notice that there are more options: you can do it thought macros, which uses more code but are faster and don't force you to use predetermined registers.
Sik wrote:
Fri Nov 10, 2017 11:35 pm
Also I don't know how pushing registers all the time is faster, memory accesses are slow. Better to reserve a few registers to scratch for minor subroutines. Heck, even the 68000 C ABI reserves a few for this reason.
GCC uses d0,d1,a0,a1 to store temporal results (something like the typical "tmp", "aux", "swap" variables in C) something that you will always need in asm, never to store values with actual meaning (except when GCC concludes that their value will never been overwritten in theirs useful life). That's why you don't need to save theirs values, their values are temporal in nature.

I don't understand what do you mean understand by "pushing registers all the time" but there is no way you are going to develop a game without using ram, what the heck, the code itself is retrieved thought memory access. By reserving registers for future usage you are only degrading cpu performance.


(What is really the point):
Anyway, in all this discussion you haven't touch my main objection: In an actual game you are not going to use AddSprite but in a single place.
HELP. Spanish TVs are brain washing people to be hostile to me.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Best way to manage sprites

Post by Sik » Wed Nov 15, 2017 11:12 am

Miquel wrote:
Tue Nov 14, 2017 6:45 pm
Sik wrote:
Fri Nov 10, 2017 11:35 pm
2) I actually managed to get bitten once by not making clear optional (tip: don't ever do a fade in function that halts the game unless you explicitly make it not clear the sprite table)
Do not allow a function EVER to halt the global game loop function! Seems the easy way but complicates everything in the long run. In the non-halt way you can do the fade, do I don't think the result would be the desired one.
For fading in it's not much of a problem (just let the game logic run as usual), for fading out it's a bigger issue since you can't just quit the current game loop (to move to the next one), you have to start the fading, then wait for it, and then make sure to cope with anything that could happen during that period that could potentially change the outcome when actually quitting (rare, but eventually bound to happen). Would rather have the game paused during fading even if it isn't as pretty. Heck, Sonic games get away with it :v

If you mean to keep the state of the system updated then yeah, that's another story. I actually wrap around all the hardware stuff that needs to update every frame into a NextFrame subroutine (as well as vsync) just for that purpose. And yes, fading would use that too =P
Miquel wrote:
Tue Nov 14, 2017 6:45 pm
I like the idea, a way to reduce code, and avoid repeated code. Nice! But notice that there are more options: you can do it thought macros, which uses more code but are faster and don't force you to use predetermined registers.
And that's how you end with code that's hundreds of KB. And don't tell me space is cheap, you'll run into the 4MB limit very quickly if you're careless (I've seen this happen regularly).

Also I swear, you seem to think that if even half a cycle is wasted it's the end of the world. Even when the game is running just fine at 60FPS without the CPU being pushed hard ( ゚-゚) Don't go overoptimizing like that until you know it's a problem.
Miquel wrote:
Tue Nov 14, 2017 6:45 pm
GCC uses d0,d1,a0,a1 to store temporal results (something like the typical "tmp", "aux", "swap" variables in C) something that you will always need in asm, never to store values with actual meaning (except when GCC concludes that their value will never been overwritten in theirs useful life). That's why you don't need to save theirs values, their values are temporal in nature.

I don't understand what do you mean understand by "pushing registers all the time" but there is no way you are going to develop a game without using ram, what the heck, the code itself is retrieved thought memory access. By reserving registers for future usage you are only degrading cpu performance.
And what do you think those minor subroutines spend their register usage on? They just do a minor task for which you can actually get away with a few registers and nothing else (and only touch RAM when that's literally part of their task). And even when they do need more registers: if you don't save the registers in the callee then the caller will have to do it - and without guarantees of what the subroutine may trash, the caller will have to save everything unless you want to risk some piece of code breaking like hell the moment you touch a different piece of code.

And yes, macros also need to state which registers they can trash or you end up in the exact same situation, the only difference is that they're inlined instead of having a BSR/RTS pair to go. So that made your suggestion above pretty useless in practice.
Miquel wrote:
Tue Nov 14, 2017 6:45 pm
(What is really the point):
Anyway, in all this discussion you haven't touch my main objection: In an actual game you are not going to use AddSprite but in a single place.
Because every time I say something you ignore it and say that it's bad anyway -_-

Also since you want an example of some other way it may be used: a surprisingly common case for calling AddSprite directly is that often the UI needs to build up sprites on the fly rather than using pre-made mappings. And also in many cases it's just drawing things like cursors or the like which are just a single sprite.

And for even further screwery: I've done some silly demo with vertical split screen, and part of this involves clipping sprites properly to each half of the screen. However including explicit code for that everywhere would be cumbersome, so what I did was turn AddSprite into a wrapper that actually calls the correct subroutine to do the clipping, which then later jump into common code to insert the sprite into the table (as a bonus, this means that now absolutely everything can be clipped the same way in that game when I want):
https://youtu.be/bnGv9pVvTvY

And yes, in theory you could inline that. Heck, you don't even need subroutines at all in a game technically. Doesn't mean it's a good idea.


Honestly what ticks me off the most is that (in the other thread) you literally said that you can't make a "proper" game in any way other than what you suggested. Even though I've been doing it this way since even before Project MD, yet nobody questions any of those projects.
Sik is pronounced as "seek", not as "sick".

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Best way to manage sprites

Post by Miquel » Tue Nov 21, 2017 12:24 am

Sik wrote:
Wed Nov 15, 2017 11:12 am
For fading in it's not much of a problem (just let the game logic run as usual), for fading out it's a bigger issue since you can't just quit the current game loop (to move to the next one), you have to start the fading, then wait for it, and then make sure to cope with anything that could happen during that period that could potentially change the outcome when actually quitting (rare, but eventually bound to happen). Would rather have the game paused during fading even if it isn't as pretty. Heck, Sonic games get away with it :v

If you mean to keep the state of the system updated then yeah, that's another story. I actually wrap around all the hardware stuff that needs to update every frame into a NextFrame subroutine (as well as vsync) just for that purpose. And yes, fading would use that too =P
I mean that something like next code is extremely terrible in the long run. Which is what I thought you mean by halting the game. At least is done by a great number of people at the communities like spritemind.

Code: Select all

void main()
{
	for(;;)
	{
		ReadInput(); // For example...
		[...]
		if( input & START )
		{
			// Pause game
			waitAFewVBlanks();
			while( !(input & START) ) ; // Do nothing and block the game until button start is pressed
		}
		[...]
		UpdateScroll(); // For example
		WaitVBlank();
	}
}
Sik wrote:
Wed Nov 15, 2017 11:12 am
And yes, macros also need to state which registers they can trash or you end up in the exact same situation, the only difference is that they're inlined instead of having a BSR/RTS pair to go. So that made your suggestion above pretty useless in practice.
Can't you pass arguments to macros? I haven't program in asm with MD yet.
Sik wrote:
Wed Nov 15, 2017 11:12 am
Honestly what ticks me off the most is that (in the other thread) you literally said that you can't make a "proper" game in any way other than what you suggested. Even though I've been doing it this way since even before Project MD, yet nobody questions any of those projects.
Where I have said this?
Sik wrote:
Wed Nov 15, 2017 11:12 am
Also since you want an example of some other way it may be used: a surprisingly common case for calling AddSprite directly is that often the UI needs to build up sprites on the fly rather than using pre-made mappings. And also in many cases it's just drawing things like cursors or the like which are just a single sprite.

And for even further screwery: I've done some silly demo with vertical split screen, and part of this involves clipping sprites properly to each half of the screen. However including explicit code for that everywhere would be cumbersome, so what I did was turn AddSprite into a wrapper that actually calls the correct subroutine to do the clipping, which then later jump into common code to insert the sprite into the table (as a bonus, this means that now absolutely everything can be clipped the same way in that game when I want):
https://youtu.be/bnGv9pVvTvY
Agree, if the HUD is made with sprites, AddSprite could be usefull there.


What I meant from the start is that this is a terrible design in every considerable way:

Code: Select all

class Actor
{
	int x, y;
	[...]
};

Actor actors[ 80 ];

void AddSprite( x, y, ... )
{
	[...]
}

void main()
{
	for(;;)
	{
		for each actor
		{
			actor.move();
			actor.paint();
		}
		waitVBlank();
	}
}

void ConcreteActor::Paint() // for EVERY FRIEND/FOE/ITEM
{
	AddSprite(...);
	AddSprite(...);
	AddSprite(...);
	for(...)
	{
		if(...)
			AddSprite(...);
		else
			AddSprite(...);
	}
	if(...)
		AddSprite(...);
}
Instead I propouse this one for reasons already stated:

Code: Select all

HardwareSpriteList g_hsl[ 80 ];
int g_spriteCount;

CustomSpriteList csl[] =
{
	// Modify data here
	// or better optain it from a txt file/editor where the animator can play with it
};

void PaintActor( Actor* actor, CustomSpriteList *csl, int count, uint options ) // Only once!
{
	for( int i = 0; i < count; i++ )
	{
		g_hsl[ spriteCount ].x = csl->x + actor->x - scrollX;
		[...]
		g_spriteCount++;
	}
}
HELP. Spanish TVs are brain washing people to be hostile to me.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Best way to manage sprites

Post by Sik » Wed Nov 22, 2017 5:51 am

Miquel wrote:
Tue Nov 21, 2017 12:24 am
Sik wrote:
Wed Nov 15, 2017 11:12 am
And yes, macros also need to state which registers they can trash or you end up in the exact same situation, the only difference is that they're inlined instead of having a BSR/RTS pair to go. So that made your suggestion above pretty useless in practice.
Can't you pass arguments to macros? I haven't program in asm with MD yet.
Well yeah, you can pass registers as arguments to macros.

That's not the problem though. If you don't explicitly define what registers can be trashed, then whenever the routine changes and if needs another register to trash you risk the code calling it already is using said register and now you have to change code all over to accomodate for it. Maybe you also broke an assumption too and some routine is now short on regisers and something needs to be pushed to RAM to make up for it. This situation is always there regardless of whether it's a subroutine or a macro.

The only time a macro helps is if the overhead of jumping into a subroutine is proportionally significant enough that inlining brings a big performance boost. If the code is doing quite a bunch of things or isn't called often you're probably better off just leaving it as a subroutine as the gain would be minimal and instead you wasted ROM space (and possibly polluted the namespace with new labels, which may be even more problematic).
Miquel wrote:
Tue Nov 21, 2017 12:24 am
Sik wrote:
Wed Nov 15, 2017 11:12 am
Honestly what ticks me off the most is that (in the other thread) you literally said that you can't make a "proper" game in any way other than what you suggested. Even though I've been doing it this way since even before Project MD, yet nobody questions any of those projects.
Where I have said this?
viewtopic.php?f=2&t=2739#p32651
"AddSprite sounds convenient for starters toying with the machine, but not for an actual game setup."
Miquel wrote:
Tue Nov 21, 2017 12:24 am
Agree, if the HUD is made with sprites, AddSprite could be usefull there.

What I meant from the start is that this is a terrible design in every considerable way:
«snip»

Instead I propouse this one for reasons already stated:
«snip»
That's a problem with the actor manager, not the sprite code.

Incidentally, you probably want to isolate the multisprite stuff from the actor code, so it can be reused elsewhere the same way AddSprite can (otherwise you're forced to use actors everywhere), otherwise you end up in the same pitfall you're complaining about. Not like actor code doesn't have to worry about other stuff either (like checking from where to fetch the graphics, or taking care about animating them).
Sik is pronounced as "seek", not as "sick".

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Best way to manage sprites

Post by Miquel » Wed Nov 22, 2017 7:39 pm

Can you give an example where you put an sprite on screen and isn't dealt by an Actor?

For example I am thinking that someone could be carried by the idea of not using an Actor for the HUD, but anyway you have to build a (sort of) object and all it's code associated, in the other hand you can make Actor's objects enough abstract to support HUDs. For example could be as simple as:

Code: Select all

typedef void (*FNCustomPaint)( Actor* );

struct Actor
{
	bool bUsingCustomCode;
	union
	{
		FNCustomPaint pfnCustomPaint;
		CustomSpriteList* csl;
	};
};

void PaintActor( Actor* actor, uint options )
{
	if( actor->bUsingCustomCode )
	{
		actor->pfnCustomPaint( actor );
	}
	else
	{
		for( int i = 0; i < count; i++ )
		{
			[...]
		}
	}
}
(Do I'm using a kind of C++ pseudocode, I'm always have MD programing in mind, therefore the union)

The same applies for other effects like rain and sparks. I don't mean you have to use Actors for that work, but you could easily. Is there any especial reason for not using Actors in some instances?
HELP. Spanish TVs are brain washing people to be hostile to me.

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Best way to manage sprites

Post by Miquel » Thu Aug 16, 2018 11:51 am

Just wanted to add that I have found using minimal and very specialized scripts is a better option to using structures. It's a similar idea but much more modifyable, for example you can include sounds to it. No need of pointer or indexes and you can always add more data without any negative consecuence.
The trick is to make it very efficient, but that's another matter.
HELP. Spanish TVs are brain washing people to be hostile to me.

Post Reply