Author Topic: My CPCRetroDev 2017 entry  (Read 2076 times)

0 Members and 1 Guest are viewing this topic.

Offline ervin

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.068
  • Country: au
    • index.php?action=treasury
  • Liked: 718
My CPCRetroDev 2017 entry
« on: 09:30, 01 August 17 »
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)
« Last Edit: 10:37, 01 August 17 by ervin »
My entry for the CPCRetroDev 2017 Competition http://www.cpcwiki.eu/forum/programming/my-cpcretrodev-2017-entry/
FAST line drawing in CPCtelera http://www.cpcwiki.eu/forum/programming/drawing-lines-with-cpctelera-sdcc/
RUNCPC My entry for the CPCRetroDev 2015 Competition http://www.pouet.net/prod.php?which=66566

Offline Arnaud

  • Supporter
  • 464 Plus
  • *
  • Posts: 331
  • Country: fr
  • Liked: 234
Re: My CPCRetroDev 2017 entry
« Reply #1 on: 15:50, 01 August 17 »
Really interesting. Have you idea of how many is the speed improvement with your successive optimizations (20%, 30%) ?

Offline ervin

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.068
  • Country: au
    • index.php?action=treasury
  • Liked: 718
Re: My CPCRetroDev 2017 entry
« Reply #2 on: 17:44, 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)
« Last Edit: 17:50, 01 August 17 by ervin »
My entry for the CPCRetroDev 2017 Competition http://www.cpcwiki.eu/forum/programming/my-cpcretrodev-2017-entry/
FAST line drawing in CPCtelera http://www.cpcwiki.eu/forum/programming/drawing-lines-with-cpctelera-sdcc/
RUNCPC My entry for the CPCRetroDev 2015 Competition http://www.pouet.net/prod.php?which=66566

Offline ervin

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.068
  • Country: au
    • index.php?action=treasury
  • Liked: 718
Re: My CPCRetroDev 2017 entry
« Reply #3 on: 15:18, 02 August 17 »
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)
My entry for the CPCRetroDev 2017 Competition http://www.cpcwiki.eu/forum/programming/my-cpcretrodev-2017-entry/
FAST line drawing in CPCtelera http://www.cpcwiki.eu/forum/programming/drawing-lines-with-cpctelera-sdcc/
RUNCPC My entry for the CPCRetroDev 2015 Competition http://www.pouet.net/prod.php?which=66566

Offline arnoldemu

  • Supporter
  • 6128 Plus
  • *
  • Posts: 5.207
  • Country: gb
    • Unofficial Amstrad WWW Resource
  • Liked: 2033
Re: My CPCRetroDev 2017 entry
« Reply #4 on: 15:44, 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.

« Last Edit: 15:45, 02 August 17 by arnoldemu »
My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

Offline ervin

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.068
  • Country: au
    • index.php?action=treasury
  • Liked: 718
Re: My CPCRetroDev 2017 entry
« Reply #5 on: 16:10, 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.
My entry for the CPCRetroDev 2017 Competition http://www.cpcwiki.eu/forum/programming/my-cpcretrodev-2017-entry/
FAST line drawing in CPCtelera http://www.cpcwiki.eu/forum/programming/drawing-lines-with-cpctelera-sdcc/
RUNCPC My entry for the CPCRetroDev 2015 Competition http://www.pouet.net/prod.php?which=66566

Offline ervin

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.068
  • Country: au
    • index.php?action=treasury
  • Liked: 718
Re: My CPCRetroDev 2017 entry
« Reply #6 on: 16:43, 04 August 17 »
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.
« Last Edit: 16:49, 04 August 17 by ervin »
My entry for the CPCRetroDev 2017 Competition http://www.cpcwiki.eu/forum/programming/my-cpcretrodev-2017-entry/
FAST line drawing in CPCtelera http://www.cpcwiki.eu/forum/programming/drawing-lines-with-cpctelera-sdcc/
RUNCPC My entry for the CPCRetroDev 2015 Competition http://www.pouet.net/prod.php?which=66566

Offline ronaldo

  • Dev
  • 6128 Plus
  • *****
  • Posts: 544
  • Country: es
    • Fremos Blog
  • Liked: 696
Re: My CPCRetroDev 2017 entry
« Reply #7 on: 22: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

Offline ervin

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.068
  • Country: au
    • index.php?action=treasury
  • Liked: 718
Re: My CPCRetroDev 2017 entry
« Reply #8 on: 14:51, 05 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.
My entry for the CPCRetroDev 2017 Competition http://www.cpcwiki.eu/forum/programming/my-cpcretrodev-2017-entry/
FAST line drawing in CPCtelera http://www.cpcwiki.eu/forum/programming/drawing-lines-with-cpctelera-sdcc/
RUNCPC My entry for the CPCRetroDev 2015 Competition http://www.pouet.net/prod.php?which=66566

Offline ronaldo

  • Dev
  • 6128 Plus
  • *****
  • Posts: 544
  • Country: es
    • Fremos Blog
  • Liked: 696
Re: My CPCRetroDev 2017 entry
« Reply #9 on: 17:30, 05 August 17 »
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 :)