Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1382195 Posts in 66019 Topics- by 58435 Members - Latest Member: ahomewki

September 19, 2020, 02:29:28 PM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsCommunityDevLogsLeilani's Island
Pages: 1 ... 59 60 [61] 62
Print
Author Topic: Leilani's Island  (Read 238107 times)
Suttebun
Level 1
*


Howdy Neighbor †


View Profile
« Reply #1200 on: July 28, 2020, 11:07:10 AM »

Quote from: mindless
easy fix
nothing is broken, your fixed point is JobLeonard's opinion

edit:
Quote from: mindless
I’m just trying to help out, but not if it causes issues
stop stop, don't do that.. It's good to muddle! It's how we learn.

My response was to put out there that your comment was leaning towards what you liked.
« Last Edit: July 29, 2020, 08:03:49 AM by Suttebun » Logged

mindless
Level 0
**


View Profile
« Reply #1201 on: July 28, 2020, 11:22:59 AM »

Quote from: mindless
easy fix
nothing is broken, your fixed point is JobLeonard's opinion
Can’t tell if you are actually bothered or not, so I just deleted my post. The response was to JobLeonard, so the term made sense based off that opinion. I’m just trying to help out, but not if it causes issues. I’m anxiously waiting to play this game Smiley
Logged
Ishi
Pixelhead
Level 10
******


coffee&coding


View Profile WWW
« Reply #1202 on: July 29, 2020, 08:24:35 AM »

I didn't see the deleted post, but doesn't sound like it was worth deleting! Smiley I welcome discussion about feedback on the game. When people point out these kind of small details, it often gets me to think about a small aspect of the game that I may have overlooked. There are tons of tweaks and polish that are only in the game because someone else has pointed it out to me. Similarly, seeing discussion about a point can show me other ways of looking at it that I hadn't considered.

In this case, I'd noticed before posting that it was a bit weird for the drill bot to stick into the spiky column even though it's rotating. I meant to mention it in the post, but forgot. It's one of those small things that I'm happy to ignore, and indeed it may be preferable for it to behave mechanically the same as a normal solid wall even if it's a little strange visually.
Logged

Suttebun
Level 1
*


Howdy Neighbor †


View Profile
« Reply #1203 on: July 29, 2020, 08:49:15 AM »

Sorry @Mindless Droop
Logged

mindless
Level 0
**


View Profile
« Reply #1204 on: July 29, 2020, 12:38:04 PM »

I just suggested that when the drill enemy gets stuck in a rotating spike block, that block could possibly stop rotating (just pause the animation?) until the enemy breaks, then resume. It might be easy to do if you already have implemented code to pause object animations.
Logged
Ishi
Pixelhead
Level 10
******


coffee&coding


View Profile WWW
« Reply #1205 on: July 29, 2020, 05:45:34 PM »

I just suggested that when the drill enemy gets stuck in a rotating spike block, that block could possibly stop rotating (just pause the animation?) until the enemy breaks, then resume. It might be easy to do if you already have implemented code to pause object animations.

Ah, I didn't even think of approaching it by pausing the rotating spikes without adjusting the behaviour of the drill bot. Currently the spike tower has no knowledge that the drill bot has hit it and become stuck - so some communication between them would have to be added. But this seems like it would be the best solution if I do decide to fix it. Thanks!
Logged

Prinsessa
Level 10
*****


Ava Skoog


View Profile WWW
« Reply #1206 on: July 31, 2020, 02:14:38 AM »

I think mindless's suggestion works too, but the way it is now also makes sense to me, as if the spiky part keeps spinning and the spikes keeps hitting the enemy. xp
Logged

Ishi
Pixelhead
Level 10
******


coffee&coding


View Profile WWW
« Reply #1207 on: August 02, 2020, 02:07:47 PM »

Fire Leaf cave level

I finished the first blockout of a level where players can first try out the Fire Leaf powerup. The level also features the totem enemies.



The general idea is that the player is encouraged to become a fireball and smash through the blocks to get through the level quickly. Otherwise they must get past the totems which tend to get in the way.

You can see in the screenshot that I've also added a variety of totem that has a spiky head - these ones must be attacked by destroying the individual sections rather than bouncing on the head. It also gives me the option of making totems with no weak point (e.g. if the whole thing is covered in spikes).

I'm also trying out some simple lighting effects! I think I'm quite easily influenced by the games I'm currently playing. I played an hour of Donkey Kong Country and next thing I knew was thinking about this lighting effect. Grin I like how they made the effort to give each level in DKC some kind of visual difference, whether it's through lighting, weather effects or colour palette changes. I've also tried to do the same, but I felt that this particular level was quite dull.

Before lighting...


...after lighting.


The level is tinted blue using the existing colour-tint system I already have in the game.

The light shafts are simply a new tileset with some white shapes in, which are hand-placed in the level. I have control over the colour tint and opacity of this layer of tiles, which are additive-blended over the top.



I think this works pretty well to give the level its own atmosphere and visual identity, without feeling light a high-tech visual effect that would be out of place in this game.
Logged

Suttebun
Level 1
*


Howdy Neighbor †


View Profile
« Reply #1208 on: August 02, 2020, 02:24:52 PM »

My suggestion, upwards floating feather particles and gentle humming music.. But only sparingly.
Logged

JobLeonard
Level 10
*****



View Profile
« Reply #1209 on: August 03, 2020, 02:22:15 AM »

Spiky totem!

Logged
Ishi
Pixelhead
Level 10
******


coffee&coding


View Profile WWW
« Reply #1210 on: August 07, 2020, 06:23:09 PM »

Glowing Eyes

On Wednesday I took part in #IndieDevHour on twitter. The hashtag is a weekly thing but I haven't joined in for a long time as it's at a weird time of day for me. I was thinking of getting into a routine where I take an hour out of my work day to do a bit of development and post about it on twitter, and this is my first go.

I wanted a small task to do over the hour so chose a little cosmetic effect. I want the robot's eyes to glow in the dark (or more accurately, I want them to not be affected by the colour tint that's applied to the rest of the level).



On the left is how the robot used to look, and the middle is the new, glowing eye. The effect is very subtle, but I do like that the white highlight on the eye remains bright as it doesn't get dimmed by the blue colour tint on the rest of the level.

On the right I've edited the level to have a much darker colour tint to show the effect off better.



The effect is achieved by making a duplicate version of the sprite animation that's only the eye, and layering it on top, but without the colour tint.

The main thing I put time into during the hour was setting up an easy way for me to do this via the sprite XML data, as shown in the image above. It uses the concept of Composite Sprites that I previously added to the sprite system. Sprites can be comprised of multiple layers/pieces without the gameplay code being aware of it. So the new part is the <CompositeLayer> xml tag which is a shortcut for loading a second set of sprites and layering it directly on top of the original.

This is basically feature creep, but it feels ok since it was an hour of work I wouldn't have normally done on the game! I now have to go through all of the robot sprites in the game and make their eyes glow - which I think I'll do as part of future #IndieDevHours. I would also like to make some other things glow, for example the firey elements of Fire Leilani's idle animations.

Speaking of glowing fire...

Glowing Fire Leilani

I realised that the colour tint I applied to the Fire Leaf Cave level (see previous post) could actually have a gameplay benefit. Fire Leilani's gimmick is that she can charge up heat and eventually turn into a fireball, and it's this ability that the level teaches by requiring Leilani to become a fireball to break certain blocks.

Leilani's heat level is displayed by her glowing brighter. The realisation I had was that the level's lighting could actually make this effect more prominent, making it easier to notice for new players learning to use the mechanic.



I made the lighting a little bluer than before to ensure the glow stands out prominently.

Controllers

Finally I went on quite a development tangent today and ended up working on the input system a little. I happened to look at the changelog for recent SDL2 versions and noticed that the latest version added the ability to query what type of controller is being used - Xbox 360, Xbox One, PS3, PS4 or Switch Pro Controller. I couldn't resist taking the opportunity to display correct button icons for these devices.

I don't think I've talked about controller support much - there was a brief mention in 2016 - so I'll give a brief overview of what the game supports.

Controller support overview

The game uses SDL2 for all of its input handling. SDL provides two ways to access controllers - either as Joysticks (using the SDL_Joystick* functions) or as Game Controllers (using the SDL_GameController* functions).

Joysticks provide basic access to the buttons, axes and other inputs on a generic device with an unknown layout. Game Controllers are a wrapper around Joysticks that allows it to be treated as an Xbox 360 pad. Game Controller support is implemented for a wide variety of devices which I think is based on a huge crowd-sourced database of the IDs of devices and the appropriate mappings to the physical layout of an Xbox pad (so the A button is always the lower of the four face buttons, regardless of the label on the button itself).

Leilani's Island supports... both systems! If SDL supports treating a device as a Game Controller, then it will use that system. For devices for which that isn't supported, it'll be treated as a basic Joystick with a bad button layout that the player will need to configure themselves.

Steam can also get involved in these systems. I haven't messed around with it for a long time but I believe Steam's Big Picture mode allows any controller to be set up as an Xbox controller. When the game is running, Steam does some sort of emulation of an Xbox controller and feeds the real device's inputs through to it. In this case, SDL will treat the emulated device as a Game Controller.

Here's the in-game controls screen when an Xbox 360 controller is being used.



Controller icons

Now, as I mentioned before, there's a new feature that allows me to query the type of controller. The type of controller doesn't affect the way the Game Controller works in SDL - the bottom most face button is still SDL_CONTROLLER_BUTTON_A, following the Xbox pad layout. However, if I know that the controller is a PlayStation controller, than I can display that A button using the Cross icon.

Xbox One:


Switch Pro Controller:


PlayStation 3: (I don't own one of these controllers so I just put in a hack to display the PS3 buttons on all controllers for testing purposes...)


PlayStation 4 controllers are technically supported too, again I don't have one of those to test with. For now they display the same buttons as the PS3 controller. I will need to change the icons for the Start and Select buttons - the PS4 controller doesn't have these - but I'm not sure how SDL maps these to the Options button or Trackpad.

Unknown type:

This is an iBuffalo SNES-style gamepad. SDL supports it as a Game Controller with the correct layout, but reports it as an unknown device type, so I just fall back to displaying the Xbox buttons. It's a bit confusing because the yellow B button on the controller is displayed as a green A button on-screen. However, I think it's only sensible to support the controller types that SDL inherently recognises. I could put together my own list of SNES-style controllers (using the joystick GUIDs to detect what type of joystick is connected) but this doesn't seem practical to maintain.

Non-Game Controller:

This is an SLS USB SEGA Saturn pad. SDL doesn't treat it as a Game Controller, either because no one has created a mapping for it, or because the mapping wouldn't be suitable (since it has 6 face buttons rather than 4). The game falls back to treating it as a basic joystick. In this image I've already manually rebound the controls to some suitable buttons.

Controller + Keyboard Combo, Active Device system

One final thing, and the reason I was originally looking at the input system today. I made the input binding system a little more flexible by allowing keyboard inputs to be bound even when a controller is the active device.



This is mainly there as an accessibility feature. If someone out there is relying on using a controller in one hand while pressing the space bar with their foot, then I want the game to support that! I haven't gone as far as supporting bindings across multiple controllers at the same time, because that introduces impracticalities that begin to worsen the game overall.

The game has a single 'active device' at any one time. This can either be a controller (whether a Joystick or Game Controller), or it can be the keyboard.

  • If the keyboard is the active device, only keyboard keys can be bound to each input.
  • If a controller is the active device, then buttons on that controller can be bound to each input, and so can keyboard keys.

The active device is initially selected by pressing a button/key to advance through the title screen, and after that point can be swapped by pressing buttons/keys on a non-active device. Having bindings spread across multiple controllers would make this process awkward, as I wouldn't know which of the connected controllers I should be listening to! So that's why I only allow bindings on a single controller at a time.

Having only a single active device also makes controller disconnection easier to handle. If the active controller disconnected, I pause everything with a 'controller disconnected' popup on the screen - I'm aiming for the real console game experience! At this point the player can reconnect their controller if they like, or press a button on any other device to make it the active one. I don't bother detecting keyboard disconnection though...

Thanks for reading Coffee
Logged

diegzumillo
Level 10
*****


This avatar is so old I still have a some hair


View Profile WWW
« Reply #1211 on: August 07, 2020, 07:58:03 PM »

As always your attention to detail is mesmerizing!

I don't think I tried the indiedevhour thing yet. I never remember it exists.
Logged

Prinsessa
Level 10
*****


Ava Skoog


View Profile WWW
« Reply #1212 on: August 10, 2020, 05:04:54 AM »

What diegzumillo said!! Love all these little touches. This game overall just seems to incredibly polished. And the devlog is fun to read too! Kiss

And thanks for telling us about the new SDL 2 feature, I need to look into that too.
Logged

Ishi
Pixelhead
Level 10
******


coffee&coding


View Profile WWW
« Reply #1213 on: August 14, 2020, 01:02:59 PM »

This week I've been mostly focused on various aspects of my data building process. But I'll start with the work I did during Indie Dev Hour:

Indie Dev Hour - More Glowing Eyes

This was once again a very productive hour. Something about having a time limit in which to work really focuses me!

I continued what I started last week, adding the glow layer to the robots' sprites to make their eyes glow. This is a manual process of making copies of each image and deleting all of the non-glowing parts of the image. I was able to get through nearly all of the sprites, except for a couple of variations of one of the enemies, and I stuck them all in a more-dimly-lit-than-usual room to show it off:



How To Play Screen - Adding Videos

My main focus this week was to start adding some more How To Play videos into the game. I previously wrote a post detailing the process of compressing the videos by splitting them up into small tiles. Since then I also implemented a first pass of the How To Play screen itself, which I don't seem to have shown off yet. Here's a video showing the screen including the new videos I've added this week:





Build Tool optimisation

I didn't plan on working on my data building process this week; however these videos were really starting to stretch my build tool to its limits. Let's go over the work that the tool has to do:

1) Load the 788 individual cels that comprise the six videos. Each cel is 128x80 in size.
2) Decompose them into 8x8 square pieces - this turns into (788 * 160) 126,080 pieces.
3) Do a first pass to combine neighbouring duplicate cels together. For example, if the first 6 frames of a video have no movement in them - just Leilani standing still - it'll compress them into a single frame. This process leaves 617 frames made of 98,720 pieces.
4) Detect duplicate pieces throughout all videos. All 98,720 pieces are compared with each other to check if they contain the same pixels, and one is marked as a duplicate of the other. This leaves 8,365 non-duplicate pieces.
5) Pack the 8,365 pieces into a 1024x512 image.
6) Save the image.
7) Save the sprite XML data that specifies which pieces are used for each cel.

Some of these steps were horrendously slow!

3) 0:26
4) 2:34
5) 1:03
7) 1:00

I was able to speed them up with some code optimisations. It was essentially all down to the existing code being written without much thought about the speed of it. It's tempting to say it was 'lazy' code - but I think that encourages bad attitude. It's perfectly fine to write slow code that does its job, and to only think about improving it later if you need to! It's only the large amount of data being processed here that made the optimisations worthwhile.

The optimisations for each step are as follows:

3) Combining neighbouring duplicate cels - 0:26
In this step, the source textures for the two neighbouring cel are compared to see if they're identical. This is done by going through each pixel of a texture and combining the values of the pixels into a single hash value. The hash values of both images are compared - if they're identical then we know* that the textures are identical, and the cels can be combined.

(*Side note: If you don't know what a hash value is, it's a small value that represents a much larger and more complex set of data. In this case, the R, G, B and A values of each of the 10,240 pixels in the image are combined together into a single 32-bit integer. This is really useful for quickly comparing large data sets for equality - you can calculate the hash value of many data sets just once, and then simply check if the hash values of two of the data sets are equal. However, when I say "we know that the textures are identical", this isn't strictly true, as it's possible for two different textures to produce the same hash value. This is unlikely enough that I don't bother to handle it.)

My code for generating the hash values of images was very slow. At the time I wrote it, the only function I had for calculating a hash value took a string as its input. To calculate the hash value of the texture, I put all of the RGBA values of each pixel into a long string, and then calculated the hash value of the string. This process of building a string was slow and unnecessary. If the RGBA values of each pixel need 12 characters, the whole texture needs 122,880 characters or 120 KB. That's a long string.

Instead I added functions for calculating a combined hash value from the individual integer R, G, B and A values with no strings involved. This reduced step 3 from 0:26 to less than 1 second.

4) Detect duplicate pieces - 2:34

Firstly, this was already sped up slightly by the previous optimisation, as the individual pieces of the images are also compared using hash values generated by the same code.

The main culprit of the slow down was some bad usage of containers. The 98,720 pieces are stored in a contiguous array (std::vector in c++). Contiguous means they are stored in a single uninterrupted block of memory. This is actually a good thing, as it makes it quicker to iterate through all of the pieces in order, as when accessing one entry in the array the CPU will tend to cache what's nearby in memory and be able to access the next entry very quickly. However, when I found a duplicate sprite, I was immediately removing it from the array. If the 10th piece is a duplicate, and is removed, then the 98,710 pieces that follow it all have to be moved back one space in the array to maintain its contiguous nature. Since about 90,000 of the pieces ended up being removed, one by one, you can see that this causes a lot of unnecessary work to move everything around in memory.

The solution was, instead of removing each duplicate piece from the array immediately, just mark it as a duplicate by setting a boolean flag on it. Then, after finding all duplicates, I do a single pass of moving all of the non-duplicate pieces down to the front of the array, and then trimming off all of the unneeded pieces from the end of the array. This reduced step 4 from 2:34 to around 6 seconds.

5) Packing pieces - 1:03

The packing process is a generic algorithm that takes a given set of rectangles, and the size of the space in which they all need to fit*, and decides the location of every rectangle. So it's not specifically designed for packing images, but that's what I'm using it for here.

(*Side note: I determine the target size of the texture by adding up the area of all of the pieces. In this case the code decides that all the pieces should fit into a 1024x512 area. In the event that they didn't fit - due to awkwardly shaped pieces that meant there was wasted space - it would try again with a 1024x1024 texture, but usually the pieces fit on the first try.)

During the packing process, there's a function CollidesWithPacked that's called very often. A rectangle is passed into the function, and it tests if this rectangle overlaps with any of the already-packed rectangles. This function was very inefficient - it simply looped over every packed rectangle and tested for the overlap. It's easy to see how the time adds up here. By the time we're packing the 8,001st rectangle, for every position that we consider packing it into, we have to check against the 8,000 rectangles that were already packed.

A simple optimisation here was to be smarter about how CollidesWithPacked searches for possible collisions. The whole packing space is now divided into evenly sized buckets - both across and down the space. After we finish packing a rectangle, we add it into all of the buckets it overlaps with. Then, when testing for collisions, we also check which buckets the input rectangle overlaps with. We know that only those packed rectangles that are in the overlapped buckets could possibly collide with the input rectangle.



This is a bit like a quad tree, but I don't have any quad tree code so just kept it simple! This reduced step 5 from 1:03 to less than 1 second.

7) Saving out sprite XML data - 1:00

Finally, yet another case of inefficiently searching for information. While saving out the XML data for a packed sprite, a function FindSpritePiece is called very often which looks up the data of a packed sprite so that data can be written to the XML. You can probably predict where this is going - FindSpritePiece was doing a straightforward loop through every known sprite piece until it found the relevant one. The removal of duplicates didn't help here - it's looping through 126,080 pieces.

The solution was to build a look-up table. In c++ I used a std::map to do this, but I think it might be called a Dictionary in some languages. I generated a hash value for each piece based on the information that was being used to look it up. Each piece is then stored in the look-up table using the hash value as the key. When FindSpritePiece is called later, a hash value is generated from the provided information. This can then be used to near-instantly look up the piece that's stored using that same hash value in the look-up table. This speeds up step 7 from 1:00 to less than 1 second.

Phew!

That was a lot of information - hopefully it provides some insight on how it's easy to really destroy the speed of a piece of code if you're not careful (or put another way, how a little care and attention can really speed up a piece of code later!). These optimisations don't actually directly affect the final game, but will avoid me occasionally having to wait around for long periods of time when I occasionally have to build the data. The problem would have only gotten worse as I continued to add more How To Play videos. As it currently stands, thanks to the optimisations the data for the entire game can be built in around 1:09 - very satisfying.

It'd be rude to write all this and not show the result - here are the How To Play videos in packed form.



Sprite XML Data condensation

I'm not done with this devlog yet though! I made another optimisation to the build process, but not one of speed.

This is the pre-build-process XML data that defines one of the How To Play videos - "Jump".

Code:
<Strip name="Jump"
filename="Jump%04i.png"
filePerCel="true"
cels="113"
length60="2"
/>
   
The total file that defines all six videos is around 1 KB in size.

After the build process, this XML data is much less simple. Each cel of each video (788 in total) has to be individually specified, as well as the source and position of each of the 160 pieces within each cel. Let's look at the "Jump" video again:

Code:
<CompositeStrip name="Jump" spriteSheet="PackedVideo.spritesheet" initialBackwardsCel="112">
<Cel length60="16">
<Piece sourceSprite="0" offsetx="-60" offsety="-36" />
<Piece sourceSprite="0" offsetx="-52" offsety="-36" />
<Piece sourceSprite="0" offsetx="-44" offsety="-36" />
<Piece sourceSprite="0" offsetx="-36" offsety="-36" />
<Piece sourceSprite="0" offsetx="-28" offsety="-36" />
... and 145 other pieces
</Cel>
... and 112 other cels
</CompositeStrip>
      
The file is now 99971 lines long, a hefty 6.33 MB. I didn't do any tests to see if this was particularly slow to load - but nevertheless I wasn't happy with leaving the data at that size.

I created a new data format to use for cels with many pieces. The overall file format is still XML - but data is simply condensed into a single XML tag rather than being defined by separate XML tags.

Code:
<CompositeStrip name="Jump" spriteSheet="PackedVideo.spritesheet" initialBackwardsCel="112">
<Cel length60="16">
<CondensedPieceData pieceCount="160">
p0x-60y-36p0x-52y-36p0x-44y-36p0x-36y-36p0x-28y-36p0x-20y-36p0x-12y-36p0x-4y-36p0x4y-36p0x12y-36p0x20y-36p0x28y-36p0x36y-36p0x44y-36p0x52y-36p0x60y-36p0x-60y-28p0x-52y-28p0x-44y-28p0x-36y-28p0x-28y-28p0x-20y-28p0x-12y-28p0x-4y-28p0x4y-28p0x12y-28p0x20y-28p0x28y-28p0x36y-28p0x44y-28p0x52y-28p0x60y-28p0x-60y-20p0x-52y-20p0x-44y-20p0x-36y-20p0x-28y-20p0x-20y-20p0x-12y-20p0x-4y-20p0x4y-20p0x12y-20p1x20y-18p1x28y-18p1x36y-18p1x44y-18p1x52y-18p1x60y-18p0x-60y-12p0x-52y-12p0x-44y-12p0x-36y-12p0x-28y-12p0x-20y-12p0x-12y-12p0x-4y-12p0x4y-12p3x14y-12p2x20y-12p2x28y-12p2x36y-12p2x44y-12p2x52y-12p2x60y-12p0x-60y-4p0x-52y-4p0x-44y-4p0x-36y-4p0x-28y-4p0x-20y-4p0x-12y-4p0x-4y-4p0x4y-4p3x14y-4p2x20y-4p2x28y-4p2x36y-4p2x44y-4p2x52y-4p2x60y-4p4x-58y6p5x-52y5p6x-44y6p0x-36y4p0x-28y4p0x-20y4p0x-12y4p0x-4y4p0x4y4p3x14y4p2x20y4p2x28y4p2x36y4p2x44y4p2x52y4p2x60y4p7x-58y11p8x-52y12p9x-45y12p0x-36y12p0x-28y12p0x-20y12p0x-12y12p0x-4y12p0x4y12p3x14y12p2x20y12p2x28y12p2x36y12p2x44y12p2x52y12p2x60y12p0x-60y20p10x-52y20p11x-44y20p0x-36y20p0x-28y20p0x-20y20p0x-12y20p0x-4y20p0x4y20p3x14y20p2x20y20p2x28y20p2x36y20p2x44y20p2x52y20p2x60y20p1x-60y30p12x-52y28p13x-44y28p1x-36y30p1x-28y30p1x-20y30p1x-12y30p1x-4y30p1x4y30p14x12y28p2x20y28p2x28y28p2x36y28p2x44y28p2x52y28p2x60y28p2x-60y36p2x-52y36p2x-44y36p2x-36y36p2x-28y36p2x-20y36p2x-12y36p2x-4y36p2x4y36p2x12y36p2x20y36p2x28y36p2x36y36p2x44y36p2x52y36p2x60y36
</CondensedPieceData>
</Cel>
... and 112 other cels
</CompositeStrip>

While still a lot of data, the file size was reduced to 944 KB which seems more reasonable.

Duplicate Sprite detection bug

Will this devlog never end? We're nearly there. This final thing brings us full circle back to the glowing eye sprites I mentioned at the start. While working on all of this sprite packing stuff, I looked at the packed sprites for the laser enemy and noticed that some of the sprites that should have been recognised as duplicates, weren't.



Specifically, it's the sprites that I had manually separated out into different layers - the glowing parts, and the hands - where the identical sprites aren't always being recognised as duplicates.

As mentioned earlier in this post, duplicate sprites are detected by generating a hash value of each of the RGBA values of each pixel of the sprite, and comparing it with the hash value of the other sprite. I realised that the error here is that there's invisible RGB data even in the pixels that have an Alpha value of 0, leftover from when the sprites were last edited. It's really easy to overlook this as to a human's eye the fully transparent pixels are identical. So a simple fix - to treat any pixel with an Alpha value of 0 as completely black - worked!



Thanks for reading! Coffee
Logged

Tobers
Level 0
***



View Profile WWW
« Reply #1214 on: August 15, 2020, 02:35:03 AM »

Oh my good lord the animations are so good! She's so appealing!
Logged

Oh god make it stop.
Prinsessa
Level 10
*****


Ava Skoog


View Profile WWW
« Reply #1215 on: August 16, 2020, 01:17:28 AM »

Wow! Kiss
Logged

Ishi
Pixelhead
Level 10
******


coffee&coding


View Profile WWW
« Reply #1216 on: August 16, 2020, 12:48:18 PM »

Devlog follow-up: Further optimisations and fixes

Throughout the weekend I added more How-to-Play videos, and there are now 3,608 frames of video being put through this build process (compared to 788 when I wrote the last post).

Video glitches

Occasionally, video frames would glitch out like this during playback.



The pieces of the video are being linked up to the wrong image. I narrowed the issue down to this bit of code:

7) Saving out sprite XML data - 1:00

Finally, yet another case of inefficiently searching for information. While saving out the XML data for a packed sprite, a function FindSpritePiece is called very often which looks up the data of a packed sprite so that data can be written to the XML. You can probably predict where this is going - FindSpritePiece was doing a straightforward loop through every known sprite piece until it found the relevant one. The removal of duplicates didn't help here - it's looping through 126,080 pieces.

The solution was to build a look-up table. In c++ I used a std::map to do this, but I think it might be called a Dictionary in some languages. I generated a hash value for each piece based on the information that was being used to look it up. Each piece is then stored in the look-up table using the hash value as the key. When FindSpritePiece is called later, a hash value is generated from the provided information. This can then be used to near-instantly look up the piece that's stored using that same hash value in the look-up table. This speeds up step 7 from 1:00 to less than 1 second.

There's a lot of information going into this lookup table, and it turns out that the hash values being used were clashing with each other occasionally. This meant the animation data was saved out with some pieces of the animation cels pointing to the wrong bit of image data.

Fortunately there's an easy solution: use a std::multimap instead of std::map. This allows multiple sprite pieces to be stored in the map under the same hash value. When looking up the sprite piece in the hash map, the hash value is calculated. If there are multiple sprite pieces stored for that hash value, I loop through them and check their details to see which one is the correct one I'm looking for.

Duplicate piece detection was slow again

The solution was, instead of removing each duplicate piece from the array immediately, just mark it as a duplicate by setting a boolean flag on it. Then, after finding all duplicates, I do a single pass of moving all of the non-duplicate pieces down to the front of the array, and then trimming off all of the unneeded pieces from the end of the array. This reduced step 4 from 2:34 to around 6 seconds.

This optimisation of improving how the containers were used had worked well before, allowing the 98,720 pieces to be checked for duplicates in 6 seconds. However, after adding so many videos to the system, it was now having to check 470,560 pieces, and getting slower and slower. Finding the duplicates in this many pieces took around 1:20.

It was time to look at the algorithm itself. Here's some pseudocode for it. Note that the hash values for each sprite piece have already been calculated, so doing the duplication check is a simple case of comparing the two numbers.

Code:
for every sprite piece (A) from 0 to sprite piece count
    if it's not known to be a duplicate
        for every sprite piece (B) from (A + 1) to sprite piece count
            if it's not known to be a duplicate, and if it's the same as sprite piece A, then mark sprite piece B as a duplicate
        end
    end
end

This loops through every possible pair of pieces and does the duplication check. For small numbers of pieces this works well. But for 470,560 pieces, this blows up to ridiculous proportions. I believe the number of pairs that need to be checked in the worst case is 110,713,121,520. In practise it's not as bad as this because once we've found duplicates they are excluded from future loops. However, it's still very slow.

I had an idea for an optimisation that worked much better than I expected.

Code:
sort the sprite pieces by the image hash value

for every sprite piece (A) from 0 to sprite piece count
    if A > 0 and the hash value is the same as the previous sprite piece (A - 1)
        mark sprite piece A as a duplicate
    end
end

The success of this optimisation hinged on how quickly I'd be able to sort the sprite pieces. Once the pieces are sorted by their hash value, then any pieces with the same hash value will naturally be right next to each other, and I only need to loop through them all a single time to find the duplicates.

Simply using std::sort to sort the array provided fantastic results, reducing this process from 1:20 down to about 1 second!

Further XML data size reduction

This is the pre-build-process XML data that defines one of the How To Play videos - "Jump".

Code:
<Strip name="Jump"
filename="Jump%04i.png"
filePerCel="true"
cels="113"
length60="2"
/>
   
The total file that defines all six videos is around 1 KB in size.

After the build process, this XML data is much less simple. Each cel of each video (788 in total) has to be individually specified, as well as the source and position of each of the 160 pieces within each cel. Let's look at the "Jump" video again:

Code:
<CompositeStrip name="Jump" spriteSheet="PackedVideo.spritesheet" initialBackwardsCel="112">
<Cel length60="16">
<Piece sourceSprite="0" offsetx="-60" offsety="-36" />
<Piece sourceSprite="0" offsetx="-52" offsety="-36" />
<Piece sourceSprite="0" offsetx="-44" offsety="-36" />
<Piece sourceSprite="0" offsetx="-36" offsety="-36" />
<Piece sourceSprite="0" offsetx="-28" offsety="-36" />
... and 145 other pieces
</Cel>
... and 112 other cels
</CompositeStrip>
      
The file is now 99971 lines long, a hefty 6.33 MB. I didn't do any tests to see if this was particularly slow to load - but nevertheless I wasn't happy with leaving the data at that size.

I created a new data format to use for cels with many pieces. The overall file format is still XML - but data is simply condensed into a single XML tag rather than being defined by separate XML tags.

Code:
<CompositeStrip name="Jump" spriteSheet="PackedVideo.spritesheet" initialBackwardsCel="112">
<Cel length60="16">
<CondensedPieceData pieceCount="160">
p0x-60y-36p0x-52y-36p0x-44y-36p0x-36y-36p0x-28y-36p0x-20y-36p0x-12y-36p0x-4y-36p0x4y-36p0x12y-36p0x20y-36p0x28y-36p0x36y-36p0x44y-36p0x52y-36p0x60y-36p0x-60y-28p0x-52y-28p0x-44y-28p0x-36y-28p0x-28y-28p0x-20y-28p0x-12y-28p0x-4y-28p0x4y-28p0x12y-28p0x20y-28p0x28y-28p0x36y-28p0x44y-28p0x52y-28p0x60y-28p0x-60y-20p0x-52y-20p0x-44y-20p0x-36y-20p0x-28y-20p0x-20y-20p0x-12y-20p0x-4y-20p0x4y-20p0x12y-20p1x20y-18p1x28y-18p1x36y-18p1x44y-18p1x52y-18p1x60y-18p0x-60y-12p0x-52y-12p0x-44y-12p0x-36y-12p0x-28y-12p0x-20y-12p0x-12y-12p0x-4y-12p0x4y-12p3x14y-12p2x20y-12p2x28y-12p2x36y-12p2x44y-12p2x52y-12p2x60y-12p0x-60y-4p0x-52y-4p0x-44y-4p0x-36y-4p0x-28y-4p0x-20y-4p0x-12y-4p0x-4y-4p0x4y-4p3x14y-4p2x20y-4p2x28y-4p2x36y-4p2x44y-4p2x52y-4p2x60y-4p4x-58y6p5x-52y5p6x-44y6p0x-36y4p0x-28y4p0x-20y4p0x-12y4p0x-4y4p0x4y4p3x14y4p2x20y4p2x28y4p2x36y4p2x44y4p2x52y4p2x60y4p7x-58y11p8x-52y12p9x-45y12p0x-36y12p0x-28y12p0x-20y12p0x-12y12p0x-4y12p0x4y12p3x14y12p2x20y12p2x28y12p2x36y12p2x44y12p2x52y12p2x60y12p0x-60y20p10x-52y20p11x-44y20p0x-36y20p0x-28y20p0x-20y20p0x-12y20p0x-4y20p0x4y20p3x14y20p2x20y20p2x28y20p2x36y20p2x44y20p2x52y20p2x60y20p1x-60y30p12x-52y28p13x-44y28p1x-36y30p1x-28y30p1x-20y30p1x-12y30p1x-4y30p1x4y30p14x12y28p2x20y28p2x28y28p2x36y28p2x44y28p2x52y28p2x60y28p2x-60y36p2x-52y36p2x-44y36p2x-36y36p2x-28y36p2x-20y36p2x-12y36p2x-4y36p2x4y36p2x12y36p2x20y36p2x28y36p2x36y36p2x44y36p2x52y36p2x60y36
</CondensedPieceData>
</Cel>
... and 112 other cels
</CompositeStrip>

While still a lot of data, the file size was reduced to 944 KB which seems more reasonable.

The size of this file had ballooned back up to nearly 5 MB thanks to all the additional video frames I'd added. I condensed the data a bit further by providing a set of default values for the pieces of each cel. Let's say the first piece of each cel is almost always at a position of x=-60,y=-36, then it's wasteful to specify this for every single cel of the animation.

Code:
<CompositeStrip name="Jump" spriteSheet="PackedVideo.spritesheet" initialBackwardsCel="112">
<CelPieceDefaults>
<CondensedPieceData pieceCount="160">p0x-60y-36p0x-52y-36p0x-44y-36p0x-36y-36p0x-28y-36p0x-20y-36p0x-12y-36p0x-4y-36p0x4y-36p0x12y-36p0x20y-36p0x28y-36p0x36y-36p0x44y-36p0x52y-36p0x60y-36p0x-60y-28p0x-52y-28p0x-44y-28p0x-36y-28p0x-28y-28p0x-20y-28p0x-12y-28p0x-4y-28p0x4y-28p0x12y-28p0x20y-28p0x28y-28p0x36y-28p0x44y-28p0x52y-28p0x60y-28p0x-60y-20p0x-52y-20p0x-44y-20p0x-36y-20p0x-28y-20p0x-20y-20p0x-12y-20p0x-4y-20p0x4y-20p0x12y-20p1x20y-18p1x28y-18p1x36y-18p1x44y-18p1x52y-18p1x60y-18p0x-60y-12p0x-52y-12p0x-44y-12p0x-36y-12p0x-28y-12p0x-20y-12p0x-12y-12p0x-4y-12p0x4y-12p3906x14y-12p2x20y-12p2x28y-12p2x36y-12p2x44y-12p2x52y-12p2x60y-12p0x-60y-4p0x-52y-4p0x-44y-4p0x-36y-4p0x-28y-4p0x-20y-4p0x-12y-4p0x-4y-4p0x4y-4p3906x14y-4p2x20y-4p2x28y-4p2x36y-4p2x44y-4p2x52y-4p2x60y-4p0x-60y4p0x-52y4p0x-44y4p0x-36y4p0x-28y4p0x-20y4p0x-12y4p0x-4y4p0x4y4p3906x14y4p2x20y4p2x28y4p2x36y4p2x44y4p2x52y4p2x60y4p0x-60y12p0x-52y12p0x-44y12p0x-36y12p0x-28y12p0x-20y12p0x-12y12p0x-4y12p0x4y12p3906x14y12p2x20y12p2x28y12p2x36y12p2x44y12p2x52y12p2x60y12p0x-60y20p0x-52y20p0x-44y20p0x-36y20p0x-28y20p0x-20y20p0x-12y20p0x-4y20p0x4y20p3906x14y20p2x20y20p2x28y20p2x36y20p2x44y20p2x52y20p2x60y20p1x-60y30p1x-52y28p1x-44y30p1x-36y30p1x-28y30p1x-20y30p1x-12y30p1x-4y30p1x4y30p4200x12y28p2x20y28p2x28y28p2x36y28p2x44y28p2x52y28p2x60y28p2x-60y36p2x-52y36p2x-44y36p2x-36y36p2x-28y36p2x-20y36p2x-12y36p2x-4y36p2x4y36p2x12y36p2x20y36p2x28y36p2x36y36p2x44y36p2x52y36p2x60y36</CondensedPieceData>
</CelPieceDefaults>
<Cel length60="16">
<CondensedPieceData pieceCount="160">ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppps263x-58y6ps283y5ps3973y6pppppppppppppps3998x-58y11ps4001ps574x-45ppppppppppppppps4039ps4060ppppppppppppppps4093ps4139y28ppppppppppppppppppppppppppppp</CondensedPieceData>
</Cel>
<Cel length60="2">
<CondensedPieceData pieceCount="160">pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppps3923y-3ps3935x-46pppppppppppppps2213x-58y3ps3961ps3974x-45ppppppppppppppps4002ps4015x-46ppppppppppppppps4040ps4061x-46ppppppppppppppps4094ps4140y28ppppppppppppppppppppppppppppp</CondensedPieceData>
</Cel>
<Cel length60="2">
<CondensedPieceData pieceCount="160">ppppppppppppppppppppppppppppppppppppppppppppppppppps356x-46y-10pppppppppppppps3777x-58y-3ps3887ps3891pppppppppppppps3949x-58y3ps3924ps3937x-45pppppppppppppps2213x-58y11ps3991ps3995x-45ppppppppppppppps4032ps4034x-45ppppppppppppppps4095ps4141ppppppppppppppps1901pppppppppppppp</CondensedPieceData>
</Cel>
... and 110 other cels
</CompositeStrip>

You can see that the CelPieceDefaults tag provides the most common values. The following Cel tags then only provide values that are different from those defaults. So a 'p' on its own is a piece that uses the defaults. 'ps4095' is a piece that uses the default position, but uses sprite 4095 from the sprite sheet.

This reduces the file size back to a sensible 1.26 MB. The most obvious further optimisation would be condensing the long strings of default pieces - e.g. 'ppppppps4095pppppppppp' could be written as 'P6ps4095P10', where a capital 'P' is followed by the number of default pieces that occur in a row.

V-Syncing

The final optimisation is more of a silly oversight. My build tool is built on the same engine as the game itself. It's kind of a bodge - the engine is designed for making games, not tools, so the build tool has a small openGL game window as well as a console output.



The build tool runs a single process for each of the game window's updates - e.g. packing one set of sprites, calculating kerning and packing one font, or stripping comments from one XML file. To be honest I'd totally forgotten that this was the way the tool worked until today! I realised that this links the speed at which the tool can run to the framerate of the game window, and I also realised that v-sync was enabled, meaning at most 60 processes could be done per second! For very quick things like stripping comments from an XML file, this limitation was slowing things down.

Turning off v-sync for the build tool's game window was a really nice free speed up for the whole thing. Running the build tool on all of the game's data now takes 46 seconds, helped by this optimisation and the huge speed up in finding duplicate sprites mentioned earlier.

Next time

I don't know what I'll be working on this week, but I'll aim to get something more gameplay-oriented in the devlog. Smiley
Logged

JobLeonard
Level 10
*****



View Profile
« Reply #1217 on: August 16, 2020, 03:33:23 PM »

Ishi, I don't know if it's legal to be this good at being a developer
Logged
Prinsessa
Level 10
*****


Ava Skoog


View Profile WWW
« Reply #1218 on: August 16, 2020, 11:24:23 PM »

It's reassuring to see other devs also having to spend some time on tooling and not just constant direct progress on the game itself. Cheesy The little graphical window in the tool is a funny quirk. Good job on all the optimisation!
Logged

Ishi
Pixelhead
Level 10
******


coffee&coding


View Profile WWW
« Reply #1219 on: August 17, 2020, 12:32:12 PM »

It's reassuring to see other devs also having to spend some time on tooling and not just constant direct progress on the game itself. Cheesy The little graphical window in the tool is a funny quirk. Good job on all the optimisation!

I think it can feel unproductive to spend too much time on these things, but ultimately is still making progress towards the finished game! I think the hard part is that it may not seem worth doing polish/optimisations/etc to tools that are likely to only be used by yourself. But I think having faster or easier-to-use tools is invaluable in reducing friction when working on the game. You're more likely to be motivated to polish and tweak the game itself if the tools you use to do so are themselves more polished!

Ishi, I don't know if it's legal to be this good at being a developer

Embarrassed Now I just need to also become a good producer and get this thing finished someday Grin
Logged

Pages: 1 ... 59 60 [61] 62
Print
Jump to:  

Theme orange-lt created by panic