Object-induced slow down

[sikthehedgehog]

I've noticed the game slows down rather quickly when there are enough objects on screen. I've decided to take a look at how it works and noticed that it's an one-way linked list, but the game tries to access the previous object quite often (resulting in it traversing a lot of the list for no reason). How much would it help to turn it into a double linked list? (so checking the previous object is just as fast as the next object)

Of course would be nice to still check on other stuff that would possibly cause this, but that one seems to be a rather obvious problem.

[andwn]

I think the main thing causing slowdown is the sprite engine but there isn't any way I know of to measure that. It just ran at 60 in those sections before some of the objects had sprites. Having to jump through a linked list every time I delete something from it probably isn't helping though.

[sikthehedgehog]

Now that you mention it, I look at that and... oh gosh yeah that looks like a horrible mess.

How I handle that in my games is I just redo the table every frame. The table is cleared, then every object gets to "draw" (add to the table) its own sprite, then at the end of the frame (when the next vblank starts) I copy it directly to VRAM. Here's my current sprite code (albeit in assembly): https://github.com/sikthehedgehog/dragon/blob/master/src-68k/video.68k#L303

I guess that doing this change would be quite the refactoring, since now objects would never have to keep track of any sprites, instead they'd just issue a draw command every frame. But it could certainly bring up a big speed up.

[andwn]

Well I didn't get any speedup from the two way linked list so the sprite engine is going to have to change. I thought increasing the sprite cache might be good enough but the sprite engine will actually reupload tiles that are already in VRAM so it's pointless. Steph said he was going to rewrite that part in the next version so I'll just wait until then. If it still lags I will have to write my own similar to your suggestion.

[sikthehedgehog]

Wait a second, it's reuploading tiles every frame? Huh, that may explain a lot then (with enough objects on screen it'll inevitably run out of bandwidth in vblank). Although I noticed some frames from animations sometimes will go completely blank until the next time the room is reloaded (as if they got erased), so I guess this isn't true for everything.

But not reuploading tiles that are already there is a good start. And I don't recall SGDK doing that automatically... How does the sprite engine actually work in this game?

[andwn]

I don't know if it reloads everything but more than it has to. http://gendev.spritesmind.net/forum/viewtopic.php?p=29047#p29047

The sprite.c just wraps around SGDK's sprite_eng.h. I used byte IDs instead of giving out pointers to be able to differentiate between "invisible" and "deleted", but this introduced the problem of forgetting to unset the sprite and modifying the wrong one. Actually I should just get rid of it. I knew very little about the way sprites worked on the Genesis when I first wrote it.

[sikthehedgehog]

Well, thanks for giving me more reasons for disliking how SGDK approaches things... (ーー；)

At that point it sounds like you may be better off doing things on your own. That isn't so hard (at least as far as sprites go) but it's certainly annoying. That said, is there enough room in VRAM to hold all the graphics you may need for a room? If not then you may indeed have to do the allocation approach anyway. But I think you may still be able to get away with it except maybe for large sprites (which tend to be one of a kind in a room anyway).

[andwn]

I would have barely been able to get started without it. Only real problem I have had was with sprites. There are still the low level sprite access functions so I'll build off those.

Ultimately there would be 3 types of sprites. Those that load with the room, those that load dynamically when an object appears, and big bosses like monster x and ballos. I'll figure something out.

[sikthehedgehog]

Just downloaded the 2016-06-30 snapshot, remind me to report back later. I had also taken a look at the previous snapshot though and didn't spot any slow down at least, but got stuck at the egg corridor due to bugs.

EDIT: no slowdown yet but won't call it closed until I get to the worst spots (the crashes from #5 are getting really annoying and I keep getting it right at the beginning of Grasstown x_x), but looking promising so far.

[andwn]

The part with the big jellyfish still lags and I have some ideas on what to do about it.

I know while I was working on making critters fly they started crashing the game but I thought I fixed it. I'll post the latest ROM but that's mostly "making sand zone possible (it's still broken as hell)" stuff. I didn't even test Grasstown since then. Going to have to start making different copies of saves so I don't have to keep playing through the whole game.

Won't be working on this for a while since I am away on vacation.

[sikthehedgehog]

I'll go check, though I suppose the crash bug is probably the most important. And yeah I pretty much can't get through Grasstown, it keeps crashing so I can't confirm the slow down stuff. It definitely already seems much better than it used to be though, Egg Corridor doesn't slow down at all.

Going to have to start making different copies of saves so I don't have to keep playing through the whole game.

Maybe time to have multiple slots? :P

EDIT: OK yeah the newest build fixes the crashes. And yeah, can confirm the jellyfish part still slows down. At least it's slowing down in the one part it's clogged with tons of objects (before it'd slow down even with just a handful of sprites on screen).

[andwn]

Woah wasn't expecting you to reply that fast. I really need to start testing more before I put out releases but they are there mostly so people don't have to compile it themself.

I hope you got a good laugh at the horrible state of the bat AI at least.

[sikthehedgehog]

Woah wasn't expecting you to reply that fast.

E-mail notifications!

I hope you got a good laugh at the horrible state of the bat AI at least.

They go straight to the ceiling. Yup XD (still better than being stuck there doing nothing)

Will keep updating bug reports as I play around if you don't mind. Feel free to tackle those when you have time.

[catskull]

This seems to be much better in the last release. I didn't experience any slowdown playing up till grasstown.

[andwhyisit]

I want to look at the bullet to npc collision code in ASM and see how it works. Of course my experience is only with z80, not m68k, and reading the docs on m68k makes my head explode, but I might get a better idea of how m68k works by reading what's already there.

So in order to know approximately what I am looking for... where in the source files is the bullet to npc collision checking found?

[andwn]

It's in C. This function is called by every npc with the shootable flag.

https://github.com/andwn/cave-story-md/blob/master/src/weapon.c#L769

The "extent box" in the bullets hold the absolute position on the map of the 4 sides, but in pixels. The idea was to avoid recalculating these numbers every time that function is called. It's generated in the player code after moving the bullet.

https://github.com/andwn/cave-story-md/blob/master/src/player.c#L495

The compiled assembly isn't bad apart from unneeded .l instructions because C wants to do everything with 32 bit integers, and lack of dbra (decrement and branch if nonzero) for looping. Inlining the function into entities_update() could also help somewhat. That function is already a monster as it is though.

[andwhyisit]

I was right the first time, m68k makes my brain melt.

Anyhow I might as well hijack this issue for general discourse.

Here's my attempt at the Doctor's defeat sequence:

(for some weird reason that is running at twice the speed it should in a browser)

54x32, 50fps, 21 frames.

[andwhyisit]

Actually scratch that, here's the 10 frame version:

[andwn]

Gotta remember to toss this in

[andwn]

I REALLY gotta remember to toss this in

[SkyTheLeafeon]

This one's old. You've got this, Andy.

[andwn]

Here's the remaining slowdown spots I noticed:

• Bottom of Labyrinth M
  • Minor, I spent a long time reducing the lag in this section around ~0.5 and think it's about as good as I'm going to get it
• End of Last Cave with all the presses
  • Minor but a bit annoying, have a couple ideas to try later
• Muscle Doctor with the bats
  • Pretty bad because the cages and Mimigas are also objects, there's just a whole lot going on here
  • One thing that's a bit obvious, the red energy dripping from him during the fight are full blown objects instead of effects, could convert them over to see if that speeds things up
• Hell B3 (Middle section with archers stacked vertically)
  • I've already done some things in here, like only spawning Butes when the active object count is below a certain threshold. Will have to look into other things
• Ballos final form
  • I can't really reduce the object count here. It just wouldn't be the same fight. Have to think of other ways
  • One thing I have done already was make it so the spikes on the floor are part of the map, not a row of like 50 objects

There's other places you can make the game lag if you try. Like ignore a bunch of enemies and let the mass of them follow you into tons of more enemies, but I don't plan on fixing these situations.

[crocket]

Are the slow spots fixed by now? Can I mitigate slowdown by setting CPU speed to 200% in Genesis GX Plus libretro core?