Jump to content
 Share

_Rocket_

Learning to Optimize: When a Problem Needs Optimizing

Recommended Posts

Introduction

So, allow me to introduce you to a problem. Because as a programmer, your job is that of a problem solver. You will be spending a ton of time fixing bugs and working out kinks in your code, and in the workplace you might even be fixing other people's code. A good problem solver is someone who can fix these problems quickly but efficiently. Because in the end, all the libraries you have access to are just tools in a toolbox that you can utilize to do problem solving.

 

Improving your skills as a problem solver isn't something that you can truly practice. It's moreso something that comes from experience of making your own projects. The harder the project, the more problems you'll encounter, leading to more experience you'll gain.

 

Before The Problem

This problem actually comes from something I had to deal with as I was developing my game. And I am going to use this problem to help you gain some insight into the mindset you can inherit to fix your own optimization issues. Don't worry, because this is heavily boiled down for ease of digestion. In my actual code for the game, fixing the problem required pointers and pairs and vectors and an entirely separate function, etc. Something I couldn't possibly teach you in this forum post alone without making it incredibly long. So I'll show you a very watered down version of the problem I faced and had to fix using my own problem solving skills alone.

 

Basically, there is a block in the game that acts as a switch. When touched, it switches a bunch of different blocks into their opposite state. Again, for the sake of watering this down, true means you can stand on the platforms, false means you can't.

 

When the player touched one of these switch blocks, the game would then analyze the entire map to find pixels that have the switchable platform color. It worked like this:

 

Green was the switch block.

Magenta was the "true" platform.

Dark magenta was the "false" platform.

 

When a green block is touched, the game would analyze each pixel and find any pixels that have the colors of either magenta or dark magenta. If it found any, it would switch that block color to the opposite color.

 

Why is This a Problem?

When you are making something like a video game, if your game is going to lag, make it consistent and make it happen when it makes perfect sense. (Like a checkpoint being touched, a loading point being reached, etc.) However, when lag spikes are sudden and inconsistent, players of your game will NOT be happy. I was faced with this problem when during my playtesting I noticed a very big issue.

 

Map sizes are not always the same. Map sizes could range from 800x600, up to 1500x1200. This... This is a problem. Think about it, the larger the image is, the more pixels that need to be analyzed.

 

When analyzing a pixel, the game engine will return the exact pixel color. The thing is, it actually returns a class. Every time the method x.getPixel(); is called, it returns an sf::Color object. Even if a map is 600x600, that means the game will need to analyze 360,000 pixels! Which means it will return the sf::Color class well over a quarter of a million times every frame. On a map that is 1200x1200... That's 1200 squared. That's... 1,440,000 pixels... Per. Frame.

 

There's a very clear problem here. Because as you could imagine, if the map was any larger than 1000x800, the game would have lag frames. In a precision platformer, lag frames are dangerous and infuriating. Especially when the lag frames last for 20 frames just because the map is 1500x1200. So, how can we fix this? Well, before I continue, let me show you a watered down version of the code I originally had.

 

class Green : public ObjectEntity

{

  //Yata yata

 

public:

  void process() override

  {

    for(//for loop for x)

      for(//for y)

       {

         if(color == map.getPixel(x,y)) doThings();

       }

  }

    

}

 

The logic is simple. There's a for loop that covers all the x coordinates.

for(unsigned int x=0;x < m.getXsize();x++)

 

Then there's a nested for loop that runs through all the y coordinates.

 

Now, how do we optimize this?

 

To make it easier on you, I'm going to tell you about what you could use to fix this problem. I will give you a few hints.

 

When you die, everything is re-loaded before you respawn.

Blocks never move.

 

Now, let me tell you the tool you would use to fix this problem.

 

The Tool: Vectors

Let me educate you on what a vector is in C++. A vector is in the standard library, aka the std:: part. If you know what an array is, well prepare to be amazed by the new and improved dynamic array. A vector is a dynamic array. What that means is, the elements in the array can be added and removed at any given time... Dynamically.

 

The two methods you need to use here are these two here:

 

push_back();

clear();

 

Push back is a method that adds an element to the top of the array. Clear is a method that clears the entire array.

 

Vectors are a template class. This means you initialize them using angle brackets. You do this to tell the compiler what datatype the vector is going to store. This is very flexible. You can even store vectors within vectors to make a multi-dimensional array. Like this:

 

std::vector<std:: vector<unsigned int>> vecTOR();

 

So, you know your tools and you have your hints. Try to figure out how to fix this problem. And seriously, give it a shot. If you get stumped don't worry. Still try, you'll never learn if you don't make mistakes.

 

 

 

Okay, either you figured it out and feel pretty proud, or you're stumped. Either way, let me explain.

 

 

The Solution

Let me break this down.

 

One way to be efficient in problem solving is analyzing what you already know, and what you are currently trying to accomplish. If you are paying attention, you would know that the game is analyzing every coordinate in the map and getting it's pixel color. It then checks this pixel color to find out if it matches the platform color.

 

Still nothing? Pay close attention to "coordinates". Remember the hint about how "blocks never move".

 

Still nothing?

 

Don't worry, this is why I made this forum post. You'll learn through time and experience.

 

The solution is to analyze every pixel once to store all the coordinate locations where the platform blocks are located. That way, the for loops can loop through the arrays of coordinates instead of cycling through the entire map.

 

Firstly, remember. When you die/load in the map for the first time, you can still analyze the entire map during that loading period. That way, the lag frames do not matter. During that loading period, you can dynamically add pixel coordinates that share the correct color. Once the loading is complete and the gameplay begins as normal, once you come in contact with a green block, instead of cycling through 10 million pixels and constantly having to preform boolean expressions using classes, you just have to loop through your vector, take the coordinates saved, and use the coordinates to access the specific pixel that has the platform blocks and preform the process normally.

 

So this way, instead of doing 10 million instructions, you do at the very most 50,000 if you have a HUGE map. But most of the time, you should barely even crack 500 elements to cycle through.

 

This is FAR from the actual way the code looks in the game. The code in my game is far more complex and complicated. So I'll just provide my solution to the code I've written for this example.

 

class Green : bla bla

{

  struct Ye

  {

    unsigned int x;

    unsigned int y;

    Ye(unsigned int x, unsigned int y)

      :x(x),y(y)

     {}

   }

 

std::vector<Ye> pixelCoords();

 

public

 

  methodWew()

  {

    for(Ye e:pixelCoords)

    {

      if(color == m.getPixel(e.x,e.y) doThing();

    }

  }

}

  

 

Wew bois. We did some big brain hours right there. Anyways, the logic here is, I made a struct that can hold the x and y coordinates. The vector stores all the coordinates that get loaded in during load time when the entire map gets analyzed for pixels with magenta or dark magenta. Now, each frame the game will check that vector and use those coordinates to get the pixel colors, check if they match a specific color, and do the things they need to do.

 

 

Hopefully this opened your eye to the concepts of problem solving to optimize performance.

 

Thanks for reading!

 

 


I write programs and stuff.

 

If you need to contact me, here is my discord tag: Dustin#6688

 

I am a busy person. So responses may be delayed.

1840045955_Thicco(1).thumb.png.87c04f05633286f3b45b381b4acc4602.png

 

Share this post


Link to post
Share on other sites


Please note that the code showcased here is purely for visual representation. In all reality there would be enough compiler errors to feed an army if you tried to write code in this way lol


I write programs and stuff.

 

If you need to contact me, here is my discord tag: Dustin#6688

 

I am a busy person. So responses may be delayed.

1840045955_Thicco(1).thumb.png.87c04f05633286f3b45b381b4acc4602.png

 

Share this post


Link to post
Share on other sites


Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


×
×
  • Create New...