Chunky Pixel Collision

[AMSDOS]

ervin wrote:

The version I was working on before I put Savage in contained 12 Miner Willy sprites, that were 64 pixels tall (that's 64 normal pixels, as opposed to the chunky pixels I'm creating).
They were moving around the screen at around 11-12 fps.
That didn't contain the final big optimisation I plan to make.

Having lots of large-ish sprites on the screen at once is looking possible. 

Well I guess it may depend on how much stuff you've got going in your game. The game I'm thinking of uses Colour Switching, Scrolling Backdrops and large-ish sprites which slows down a little bit when too much is on screen - some people on the scene has critised this and trash the game, but it doesn't bother me, I'm more bothered by the number of times I've completed it - and critics call it too difficult (I better not name the game otherwise I'll get branded!).

[arnoldemu]

The version I was working on before I put Savage in contained 12 Miner Willy sprites, that were 64 pixels tall (that's 64 normal pixels, as opposed to the chunky pixels I'm creating).
They were moving around the screen at around 11-12 fps.
That didn't contain the final big optimisation I plan to make.

Having lots of large-ish sprites on the screen at once is looking possible. 

If you have ram, you could consider a z buffer like approach, but based on the tile size you are using?
Or even a dirty buffer like idea?
Then draw front to back to avoid overdraw.
I'm not sure if that would be possible for what you want to do, or if that would be suitable.

[ervin]

The game I'm thinking of uses Colour Switching, Scrolling Backdrops and large-ish sprites which slows down a little bit when too much is on screen - some people on the scene has critised this and trash the game, but it doesn't bother me, I'm more bothered by the number of times I've completed it - and critics call it too difficult (I better not name the game otherwise I'll get branded!).

Do tell! Go on, which game is it?

[ervin]

If you have ram, you could consider a z buffer like approach, but based on the tile size you are using?
Or even a dirty buffer like idea?
Then draw front to back to avoid overdraw.
I'm not sure if that would be possible for what you want to do, or if that would be suitable.

A z-buffer approach... hmmm... is that where the "nearest" sprite is drawn first, and only the visible bits of the 2nd-nearest sprite are drawn, and so on and on?

As for the dirty buffer... is that when only changed parts of the screen are actually drawn?

[arnoldemu]

A z-buffer approach... hmmm... is that where the "nearest" sprite is drawn first, and only the visible bits of the 2nd-nearest sprite are drawn, and so on and on?

yes

As for the dirty buffer... is that when only changed parts of the screen are actually drawn?

Yes, but it could also be used to tag which cells you have drawn to your screen, so you can avoid drawing them again, so perhaps a simple z buffer, but yes, also for tagging which parts of the screen have changed.

If your going for dirty buffer you can group 8 consecutive cells together into a byte to get a better speedup.

[ervin]

If your going for dirty buffer you can group 8 consecutive cells together into a byte to get a better speedup.

That's a good idea.
Do you mean by setting up to 8 bits to represent 8 cells?

Thanks for your great suggestions, by the way!

[AMSDOS]

It's on this page, but it's not the Wombles! 

[ervin]

It's on this page, but it's not the Wombles! 

Is it Wizard Willy?
I remember that being quite impressive, despite the slowdown.

Oh! By the way, Savage is now moving at 5.9fps.
Woohoo for progress! Still a lot to do...

[AMSDOS]

ervin wrote:

Is it Wizard Willy?
I remember that being quite impressive, despite the slowdown.

Yep! And the sad thing about it is I've probably completed it Hundreds of times!    The game does slow down, but if you shoot the baddies, collect the eyes and other tokens and keep moving, the game is straightfoward, towards the end of Level 3 and in Level 4 the game gets tricky cause you need to do some perfect jump timing to get the eye and avoid the instant death laterns, but if you buildup your lives, you should just get away cause there's only around 4 of them. In the game itself there's hardly any sound fx, there's the zapping sound if you zapped the baddie and the sound of you dying, the badies don't generate any sound and there's no shooting sounds when you cast a spell and the game is only accompanied by a tune on the title screen. Given it's been made in 40k or so and no multiloads, I reckon is pretty good going! 

[ervin]

If I remember correctly it even had some pretty nice parallax scrolling.

... hang on, I'll just download it and try it ...

Ok, I'm back.
Yes indeed, very nice scrolling indeed.

Savage is now 6.25fps. Yippee!

[AMSDOS]

ervin wrote:

If I remember correctly it even had some pretty nice parallax scrolling.

... hang on, I'll just download it and try it ...

Ok, I'm back.
Yes indeed, very nice scrolling indeed.

WW has some very nice graphical elements in it and the scrolling as you say is very nice. The animated components in the background I think are colour switches from the palette. The Scrolling in WW seems to be quite complicated given there's foreground objects platforms which you interact with and the background. Even the ground stands out from the background, amazing!   

Savage is now 6.25fps. Yippee!

Sounds good!

[ervin]

Woohoo! Giant Savage is now moving around at approx 10-11 fps!
I'm very chuffed, I must say. 

I don't think I can squeeze any more performance out of the sprite data processing code.
It has been optimised to within an inch of its life, and I've (very carefully) used the shadow registers, the 8-bit index registers, even the I register, to avoid accessing memory locations directly.
I've rearranged code so that less stuff happens to registers each frame... I'm really quite proud of it.

Now it's time to implement a dirty-buffer type of idea, where only changes to the screen are actually rendered, so to speak. That should speed things up a whole lot more, with any luck!

[Gryzor]

Do you have a target? 10-11 is not too bad, but it depends on what else is going on on the screen...

[ervin]

Well, I'll push it as far as I can with a few more crazy optimisation ideas.
I'm hoping to get 20fps. Or at least 17.5 fps which is what Savage the game itself seems to run at (I made a video in Winape and counted the frames!)

But it'll be quite a challenge, as this is a full mode 0 screen, not a shrunken spectrum sized one.
Also, the sprites clip to all 4 screen edges nicely (it appears to work perfectly!), and they all have transparency as well, so there are quite a few overheads. Also, the sprites can be pretty much any size, memory permitting. It's pretty flexible, and I'm trying to do it without sacrificing performance.

I remain optimistic! 

[arnoldemu]

I remain optimistic! 

Yes. Good. Keep going.

Game development is like a rollercoaster.. there are times when the coding goes well, it fits into ram, and it's working fast (it was like this for me a few weeks ago on my current project), and then there are times where it all seems to go wrong, things take much longer to code (a week back for me), but then that passes and you get through it (now), finish it and release it (next year ).

In the end, if it doesn't work out fast enough, it may still be worth continuing to completion to get an idea of how the game goes together, how to package the final build, if it is a bit slow, scale back or modify your design to work with it.

I really hope it goes as fast as you want, I think it's an interesting idea to go for, and I think the way you are drawing the screen is also interesting and could open up a new route of ideas for cpc games.. where chunky is embraced as part of the game design.

Keep going and there are plenty of people who want to help, even in small ways, if you need it.

[ervin]

Thanks for the kind words!
I really appreciate all the help you've given me so far, and I'm sure everyone else around here would agree with that sentiment, for all the help you've offered over the years.

I do indeed remain optimistic, and I really believe that I can figure out how to do everything my game design requires.
There are a couple of things I don't know how to do yet (like using the extra 64k to store sprite data, and paging it in, and also scaling sprites), but I'll figure them out.

Indeed, I also really like the idea of chunky being used for design and performance reasons. If used correctly, it could lead to really fast games, I think.

Incidentally, don't get alarmed by "scaling sprites". It'll be done behind the scenes at level transition time, as opposed to being realtime. The idea is to have one copy of each sprite sitting in the extra 64k waiting to be called upon.
When one is needed, it will be read into normal ram, and different sizes of it will be created, ready for the next level. This should be a lot faster than disk access, and probably a lot more flexible too.

Personally, I can't wait to see the game that is running in my head, working on a cpc.
I wish I could see it on a real cpc, but WinAPE will have to do. 

Maybe when it is ready, someone with a real cpc can post a video of it to youtube...

[AMSDOS]

Yes it should work faster minus the hidden frames! 

Otherwise it sounds pretty good. 

[redbox]

That's really interesting about the speed of Savage in fps - I always wondered about that.  I don't know why but I am obsessed with 50hz and am only just getting my head around the fact that I can use 25fps and use two frames worth of code every time. 

Your project is fascinating to hear about and as arnoldemu said, it could open up new doors.  Keep up the good work and it sounds as if you are rapidly turning into quite a programmer 

[ervin]

That's really interesting about the speed of Savage in fps - I always wondered about that.  I don't know why but I am obsessed with 50hz and am only just getting my head around the fact that I can use 25fps and use two frames worth of code every time. 

Your project is fascinating to hear about and as arnoldemu said, it could open up new doors.  Keep up the good work and it sounds as if you are rapidly turning into quite a programmer 

Thanks man.

Yes, I hope this crazy chunky pixel idea inspires others to do something with the concept. Who knows what might pop up?

I've actually been a professional programmer for over 16 years, as a database programmer. Thrilling eh? 
Game dev is MUCH more interesting. The concepts of game dev are quite simple - it's the implementation that's the tricky bit, particularly in low-level z80! It's an awesome challenge that is very rewarding, and really enjoyable.

Having said that, I'm a bit of an optimisation fanatic with databases as well. 
That obsessive streak comes in handy when dealing with only 4Mhz (or whatever the cpc z80 actually runs at!)

[redbox]

Having said that, I'm a bit of an optimisation fanatic with databases as well. 

That's interesting - I recently asked someone to make a MySQL database run faster and their answer was "buy a better server"! 

[ervin]

Alrighty, update time!

I've spent the last fortnight completely rewriting the sprite processing code.
The algorithm was rewritten from scratch, and is now much more efficient, and faster as a result.
I don't see how (with my current knowledge) I can speed it up any further.

Of course, every time I think a routine is done, I think of some other crazy idea to try! 

Anyway, I've also implemented two ideas for speeding up the screen drawing, and they are working really well.
They were actually much easier to implement than the sprite processing code, but the results are far more dramatic.

The first is to only draw rows that had a sprite write in them in either the previous or current frame (the screen is drawn as 50 rows of chunky pixels, so there are 50 rows to draw or ignore).
This results in a VERY large speedup when the sprite (in this case giant Savage) moves partly off the screen.
In fact the speedup might be too much, as it would cause large framerate (and game-logic-timing) fluctuations in-game.
I don't really know what to do about this... although in the game I'm planning, it may not be a problem, as the largest sprites would only appear on-screen very briefly. Not sure yet...

The second optimisation is to only draw columns that have had a sprite write to them.
I currently process the screen as 8 columns (8 groups of 10 bytes for each pixel row).
I haven't figured out the optimal number of columns groups to be using yet, but I suspect 8 groups might be about right.
Having more groups means I'd need to do more stack pointer hijinx for each pixel row, and more SET/RES stuff. More overheads in other words.
Having less groups would be very difficult now, as I had to rewrite some parts of the screen-redraw code to accomodate these 2 optimisations. I had to let go of a couple of registers in the push/pop cycle.

These optimisations came from the ashes of the unfinished rewrite of my 3d-maze conversion, where I was researching the idea of only drawing "changed" parts of the screen. They have been significantly refined since then though.

Anyway, I'm very chuffed with the results.
Please download the updated version and have a play.
It's attached to the original post in this thread.
You'll notice that as Savage moves towards any of the 4 screen edges, he speeds up a lot (particularly as there is less of him displayed vertically). As mentioned above, this may be ok for my game design.

There's one more nutty optimisation idea I'm going to try... it may be a really silly idea, and fail miserably. Or it might be awesome. I don't know yet.

After that, it'll be time to write some code that shows what sort of game this will be. 

[jbaudrand]

I've just discover your amazing piece of code, very very impressive.   very smooth.  maybe you can slow it down when the number of pixel is   lower than a defined amount to maintain the same velocity?

[ervin]

I've just discover your amazing piece of code, very very impressive.   very smooth.  maybe you can slow it down when the number of pixel is   lower than a defined amount to maintain the same velocity?

Thanks - that's a good idea.
I might try it if the game is unplayable due to framerate fluctuations.

Incidentally, I've uploaded a new version to the first post in this thread.
It contains a new (very basic) front-end, which really just lists the controls.
You can now change Savage's movement speed, anywhere from 1 pixel to 10 pixel steps.

[EDIT]

I've exhausted my optimisation ideas now.
The final idea actually slowed Savage down. 
Oh well...

Luckily most sprites in the game will be smaller than giant savage, so the game should run pretty quickly. Even if there are any sprites as big as our friend, it's doubtful there'll be 2 on the screen at a time, in full view (i.e. unclipped).

Onto the next phase now!

[ervin]

Time for another little update.

I've taken Savage out, and put Miner Willy in.
The attached file simply has a chunky willy  on-screen.
He can be moved around with the arrow keys.

The purpose of this prototype is to show the new screen display routines.
I took out the routines that made Savage speed up so dramatically when he was partly (or mostly) off-screen.
I now have a cell-based system, where the program keeps track of which cells are written to.
I'm using a 50x8 array. 50 rows, with 8 columns.

As you move willy around, you'll see the area around him change colour, as the cells that need to be printed are drawn to screen memory. In the demo, once a cell has been written to, it will stay that colour. That's because I'm not drawing some other stuff over the top of it.

Only the cells that willy is "in" are actually printed each frame. This will (hopefully) allow my game to run quickly, and this technique should also have a more consistent framerate than my previous effort.

Move vertically, and the rows fill in smoothly. Move horizontally, and the columns fill in, in quite dramatic jumps.
Having more columns would take more memory, and there would be more overhead keeping track of it all in realtime.

Enjoy!

[redbox]

Hey Ervin, this is turning into a really thought provoking piece of code.

It's actually given me an idea for a demo effect that I'm working on now!

Will watch your optimisations with interest