News:

Printed Amstrad Addict magazine announced, check it out here!

Main Menu
avatar_ervin

My CPCRetroDev 2017 entry

Started by ervin, 07:30, 01 August 17

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

ervin

Hi folks.

(Sorry about this long opening post; I'm very excited about this project, and want to talk about it!)  :P

I wasn't sure if I wanted to enter this year's CPCRetroDev competition, but in the end I thought I'd have a go.
I'm going to create a full-screen (not overscan) side-scrolling platformer, with an adaptive tile-based engine.
I'm using the wonderful cpctelera.

Due to concerns about running out of memory, I won't be using a double-buffer, which means I can't use hardware scrolling (well, not with my current level of knowledge anyway).

Now of course, this leads to a bit of a problem with screen tearing.
A couple of months ago I spent some time working on a tile engine, but the tearing became very annoying, so I scrapped that project.

This one is being written with a different perspective.
I thought I'd try to print the tiles to the screen in vertical bars, but that was slow, and suffered from bad tearing during vertical movement anyway.

Then one day while walking home from work I thought about storing the addresses of changed cells in a table, and going through that to print the tiles. So all tiles are processed and checked for changes from the previous screen refresh, and only differences are stored in the table. This did indeed reduce tearing quite significantly, but was even slower.

Then I remembered something arnoldemu mentioned a long time ago in an old forum thread... only check the parts of the screen that have changed. I thought about this for a while, and realised I could take the size of an object into account, and use those dimensions to determine the area(s) where tile differences will be checked.

So if the only thing being printed to the screen is an object consisting of 10x10 tiles, I only need to check that 10x10 area for tile differences from the previous screen refresh.

This turned out to be a bit harder to implement than I had anticipated, but I got it working, and was shocked at the speed difference!
The amount of looping was reduced so significantly, that the program became a lot faster, even in unoptimised form!
(I also had to allow for one extra row or column of checking for differences when scrolling, to prevent an object leaving bits of itself behind).

I then put in 9 objects, arranged in a 3x3 grid, and of course the program slowed down A LOT, so it was time to start optimising!
Converting the SDCC loops to z80 made a huge difference, but it was still rather slow, especially the loop that filled in the table of changed cells.

Then during dinner at a friend's house a few nights ago I had an idea... what if I change the location of the stackPointer, to point to a block of memory that will be treated as a table? That night I worked on it for almost 3 hours. It seemed like such a simple idea, but was very difficult to implement. But after much hair-pulling and teeth-gnashing, I had it working, and it made a big difference!

I then optimised the other loops, and it suddenly ran at a playable speed, even with 9 large objects on the screen!
The tricky thing now will be to create levels that run at a nice, consistent speed. If there aren't enough things on the screen, it will be too fast, and too many things on the screen will make it too slow.

The game itself will hopefully be easier than my entry from 2015, and it will have an ending (it won't be an endless runner).
If you're interested in how the engine runs, have a look at the first attachment. Use the arrow keys to scroll the screen.
8)

Arnaud

Really interesting. Have you idea of how many is the speed improvement with your successive optimizations (20%, 30%) ?

ervin

#2
Quote from: Arnaud on 13:50, 01 August 17
Really interesting. Have you idea of how many is the speed improvement with your successive optimizations (20%, 30%) ?

Hmmm, that's quite difficult to answer, as I didn't keep all records of speed improvements.
(I wish I had!)

But running through the previous versions of the program gives these me these approximate improvements:
(Note that these are *approximate* improvements, recorded with my phone's stopwatch app!)

v1: slow.
v2: didn't record %, but the improvement was *huge* (implemented arnoldemu's idea of only checking the parts of the screen that have objects drawn to them). This caused the biggest improvement of any optimisation.
v3: 35% faster (the routine that loops over the list of memory addresses, and the tiles to change them to, was converted to z80 from C).
v4: 5% faster (better use of pointers in C routine that populate the front "buffer" (not double-buffering related), and the routine that determines which parts of the screen to check for differences. These are the 2 tightest loops in the engine - but were still in C).
v5: 7% faster (the 2 tighest loops had their loops changed from incrementing the counters, to decrementing them to 0).
v6: 20% faster (the 1st of the 2 tightest loops was converted to z80 and optimised).
v7: 20% faster (the 2nd of the 2 tightest loops was converted to z80 and optimised).
v8: 30% faster (implemented stack usage to read/write table of changed addresses and tile references, and performed final smaller optimisations.)

Unfortunately I don't have the source code for the very first version I wrote 2 weeks ago, which was all in C and looped through all 40x25 cells on the screen looking for tile differences. But I can confidently say that the current version is several-hundred percent faster than that version was.
8)

ervin

Hmmm... oh dear...

I put 100 objects into the game "world", and things slowed to a crawl.
It's because each object is being checked for whether or not it needs to be ignored/clipped/displayed.

I played around with all the IF blocks, and improved speed a little, but it's still too slow.
Then after wondering what on earth to do, Minecraft (of all things!) provided the answer...

I'll split the game world into "zones" ("chunks" in Minecraft lingo).
What I'm thinking of doing is having zones that are exactly one screen wide (i.e. 40 character cells).
So if a level is 10 screens long, there will be 10 zones.

Then, when the player is in zone 0, only objects in zone 0 and zone 1 need to be checked,
If the player is in zone 3, only objects in zone 2, 3 and 4 need checking.

The question is... how do I implement the zones?
I have 2 ideas.

1) Assign a zone number to every object, and simply check each object's zone as I loop through the level's objects. This will be faster than what I have now (as the zone check will be the 1st IF block), but might still struggle with larger levels.
2) Create zone tables. i.e. each zone table will contain a list of the objects it contains. This will be a bit more complex than (1), and will impose some limits, but will likely be faster.

Has anyone tried this sort of thing before?
Maybe I'll try both ideas and see which works better.
8)

arnoldemu

#4
Quote from: ervin on 13:18, 02 August 17
The question is... how do I implement the zones?
I have 2 ideas.

1) Assign a zone number to every object, and simply check each object's zone as I loop through the level's objects. This will be faster than what I have now (as the zone check will be the 1st IF block), but might still struggle with larger levels.
2) Create zone tables. i.e. each zone table will contain a list of the objects it contains. This will be a bit more complex than (1), and will impose some limits, but will likely be faster.

Has anyone tried this sort of thing before?
Maybe I'll try both ideas and see which works better.
8)
2 should be faster.

In some cases you may have part of two or more zones on screen.

If you're moving left/right and things don't move past each other, then you could have a sorted list and your position, then you can update your position, check the next thing left/right etc.

I guess if your scrolling through a level, if it's sorted like this, then you can say that if you move, check x things on either side of your position.
Then enable any new things that would be activated, disable anything that should no longer be active. Each object then has a zone of maximum movement.

I'm only guessing on how your level is setup, so this may or may not work well.

And, instead of checking things left/right one by one, you could use your zones and activate all in that zone.

Also, I would tick things like enemies at a slower rate, in terms of making their decisions, than other logic.

My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

ervin

Quote from: arnoldemu on 13:44, 02 August 17
2 should be faster.

In some cases you may have part of two or more zones on screen.

If you're moving left/right and things don't move past each other, then you could have a sorted list and your position, then you can update your position, check the next thing left/right etc.

I guess if your scrolling through a level, if it's sorted like this, then you can say that if you move, check x things on either side of your position.
Then enable any new things that would be activated, disable anything that should no longer be active. Each object then has a zone of maximum movement.

I'm only guessing on how your level is setup, so this may or may not work well.

And, instead of checking things left/right one by one, you could use your zones and activate all in that zone.

Also, I would tick things like enemies at a slower rate, in terms of making their decisions, than other logic.

That's tremendous advice.
You've given me some good ideas; thanks.

ervin

#6
Alrighty, I've had a go at speeding up the engine when there are lots of objects in the level.

My little test level has 189 objects in it.
Without zones, it took 2 minutes 4 seconds to scroll from left to right.

I then assigned a zone to every object, effectively splitting the level into 21 zones, each containing 9 objects.
(Each zone is the same width as the screen; 40 character cells).
The first check made against every object was whether or not it is in a "visible" zone.
That brought the scroll-through down to 1 minute 36 seconds.

The next part was far more difficult... creating a table of zones.
The table contains 21 entries.
Each of those 21 entries points to a different zoneData table.
Each zoneData table, in this case, contains 9 records.
Only the objects in "visible" zones are considered, so the engine is doing much less work now.

I'm still having some trouble with C structures, and pointers, so this bit gave me a bit of a headache.
Anyway, once I got it working, the scroll-through came down to 1 minute 4 seconds.
Much better!

And it certainly scrolls at a "playable" speed now.
8)

Next, I'll try some basic conversion of the C object checks to z80.

ronaldo

@ervin: I would personally not use static zones for visible/not visible objects. Instead, I would use an ordered list of objects, along with 2 indexes to mark the left-most object and the right-most one that are visible now. Then, if your screen moves to the left or to the right, you only have to check the object besides the left-most or the right-most for inclusion/exclusion from the visible zone.

Then you can safely iterate from the left-most to the right-most object in the ordered list, and you will be checking only those inside the screen.

You can extend this technique in different ways depending on the movement of your objects, or your scroll, and get some optimizations. Moreover, you can also use that list as a collision-detection hint: you will be able to check for collisions only with nearby objects within a given range, automatically excluding others because of their distance, without any additional check.

Good luck with your game. It looks promising :). And, of course, do not forget to throughly read the rules first, and take advantage from them! :D

ervin

Quote from: ronaldo on 20:18, 04 August 17
@ervin: I would personally not use static zones for visible/not visible objects. Instead, I would use an ordered list of objects, along with 2 indexes to mark the left-most object and the right-most one that are visible now. Then, if your screen moves to the left or to the right, you only have to check the object besides the left-most or the right-most for inclusion/exclusion from the visible zone.

Then you can safely iterate from the left-most to the right-most object in the ordered list, and you will be checking only those inside the screen.

You can extend this technique in different ways depending on the movement of your objects, or your scroll, and get some optimizations. Moreover, you can also use that list as a collision-detection hint: you will be able to check for collisions only with nearby objects within a given range, automatically excluding others because of their distance, without any additional check.

Good luck with your game. It looks promising :) . And, of course, do not forget to throughly read the rules first, and take advantage from them! :D

Thanks @ronaldo.
That's really great advice.

Also, I'm not 100% sure about something in the rules.
It says, "Developers are free to publish screenshots, images, videos, teasers or previews of the game along its development. These promotional actions will NOT make the game be considered as previosly published."

Does that mean I *can* upload development builds of the game engine?
(I certainly won't upload things that resemble the final game at all, but I just want to be sure of what I can/cannot do).

Thanks.

ronaldo

Well, you have already uploaded a version of the game engine. As far as I understand, the game engine is not the game. However, just make sure you do not upload any development version of the game, as the previous rule to the one you quoted clearly sais:

Quote from: CPCRetroDev Rules
A game will be considered as previously published in these cases:
• An executable version of the game or a development version of the game has been made publicly available.

When in doubt, just do not upload any executable. You will always be fine with some screenshots and preview videos :)

ervin

Thanks @ronaldo.
I won't upload any more executables, as I don't want to put my entry in jeopardy.
8)

AMSDOS

Quote from: ervin on 02:34, 06 August 17
Thanks @ronaldo.
I won't upload any more executables, as I don't want to put my entry in jeopardy.
8)


Is it breaking the rules (sorry rulez!), if you were to PM @ronaldo?
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

ronaldo

As far as I know, there is no rule preventing people to communicate with me, or sending me PMs 😉

AMSDOS

Quote from: ronaldo on 07:12, 06 August 17
As far as I know, there is no rule preventing people to communicate with me, or sending me PMs 😉


Sorry I didn't make my post clear, I was asking in relation to sending code through as a PM for help.
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

ronaldo

Equally, nothing prevents people from sending me code or help requests :). I'm not part of the jury, just organizer of the contest. It'd be different if I had to judge your game, but that's not the case ;).

ervin

#15
Hi everyone.

Alrighty, I've made some great progress on the engine.
(Wow, I really need to get on with the actual "game" part of the project!)

With various optimisations and algorithm changes, I've managed to speed things up by around 15%.
It's running really well now.

A few nights ago I had a bit of a bug that was driving me nuts.
Objects that joined other objects, or partially overlapped other objects, would sometimes leave parts of themselves incorrectly on the screen.
This caused a great deal of anxiety, because I really didn't feel like rewriting large parts of the engine if my base algorithm was wrong.

However, I must have had some very active dreams, because I woke up the next morning with what I thought might be a solution!
I implemented that solution, and lo and behold, it worked!

The gist of it was because I was calling some functions in the wrong order.  :doh:
(Well, it's a bit more complicated than that, but still a pretty good idea of what went wrong).
It was actually a pretty silly mistake, and I'm so glad it's in the past now!

Now that the engine is nice and fast, and objects can overlap correctly without visual corruption, I'll have a go at implementing some simple parallax scrolling.
8)

ervin

#16
Well, that took a bit longer than expected!
(And was a lot harder than I thought it would be).

I've figured out how to do parallax scrolling in my engine.
(I still need to incorporate it into the main routine though).

Luckily the offsets needed to make the parallax work can slot nicely into the optimised object-analysis code that I finished work on a few days ago. I didn't think it would slot in the way it does, and indeed it's not the angle that I was approaching the problem from initially. Realising *how* to make it slot in was the AHA! moment I needed to arrive at.

It would have been so much easier to work with unoptimised easy-to-read code, but that's a lesson I'll take forward into my next project.  :doh:

Hopefully I'll have time in the next day or two to incorporate the parallax logic, and then the level design can finally begin!
(No doubt I'll trip over the character controls though!)

SRS

>It would have been so much easier to work with unoptimised easy-to-read code, but that's a lesson I'll take forward into my next project.  :doh:

Ah well, I learned that the hard way in my first payed project, too. First get it ALL to work, and then start to optimize. And only the time consuming critical parts, not all and everything :)

(It was fixed price, so ... )

ervin

Quote from: SRS on 20:19, 14 August 17
>It would have been so much easier to work with unoptimised easy-to-read code, but that's a lesson I'll take forward into my next project.  :doh:

Ah well, I learned that the hard way in my first payed project, too. First get it ALL to work, and then start to optimize. And only the time consuming critical parts, not all and everything :)

(It was fixed price, so ... )


Indeed, I know that premature optimisation is pretty much always a bad idea, but making tile-printing loops run faster is so tempting...  :laugh:

ervin

#19
I wasted a few very frustrating hours last night on a very strange problem with running out of memory.
Except I am absolutely nowhere near the memory limit!

If you know a bit about how SDCC organises variables and code at compilation time, please have a look at this thread:
http://www.cpcwiki.eu/forum/programming/(sdcc)-weird-memory-problem/

ervin

#20
I think I have dealt with the problem now.
In any case, it seems to be working correctly.

In other news, parallax scrolling is in, and working!
Now I'll try to improve the parallax scrolling, by using pre-shifted tiles for the background layer.

ervin

#21
Hooray!
I've figured out how to implement pre-shifted tiles!

I was rather fortunate because the concept of pre-shifted tiles works fine with the engine as it is.
The only thing I had to do was tell the program which tileset to point to when drawing the scene.

It basically works like this:
When the screen scrolls, I have a variable called tileSet flicking between 0 and 1.
When it is 0, tile set 0 is selected, and when it is 1, I use tile set 1.

Here's how things are looking now (presented with terrible placeholder graphics)!


ervin

A simple block has been added for my main character.
It has been defined the same way as any other object in the game, so it has slotted right into the game engine without any modifications to the tile routines!
8)

I'm going to have a go at drawing something in pixels soon, but I don't think this will be a particularly good looking game!
Ah well.

Regardless, the block is in, and has been connected to the scrolling appropriately, including handling the block's position at the far left or right of the level.
Next up, I'll try putting in some really bad animation frames.
I don't know how I'll implement animation yet, but I think I may have a little idea...

Arnaud

Quote from: ervin on 16:00, 15 August 17
Hooray!
I've figured out how to implement pre-shifted tiles!

I was rather fortunate because the concept of pre-shifted tiles works fine with the engine as it is.
The only thing I had to do was tell the program which tileset to point to when drawing the scene.

It basically works like this:
When the screen scrolls, I have a variable called tileSet flicking between 0 and 1.
When it is 0, tile set 0 is selected, and when it is 1, I use tile set 1.

Here's how things are looking now (presented with terrible placeholder graphics)!



Is real time animation ?

ervin


Powered by SMFPacks Menu Editor Mod