Tuesday 7 May 2013

The Funny Thing About Coding...



I've spent the last two days on my project. Being a rookie game developer, I get hung up on what are probably incredibly simple tasks to more experienced veterans. The following is the account of my first major issue with performance (only two days in!)

Besides the player, Wanderer is going to contain two other types of entities. Those you can interact with (enemies and "chests" for now.) and those you can't (just stationary obstacles like wall sections which will from here-in be referred to as "blocks"). Because everything is a 16x16 block, many aspects of larger maps can be scaled down and stored on smaller grids. For example, current map sizes are going to be approximately 3200x3200 pixels large (subject to change), the grid used to store blocks will only be 200x200 elements large.

My first big issue had to do with the way I'm storing this data. Each wall section is actually it's own entity with it's own sprite and position. Each of these entities was stored in a linked list. I wanted to store each item in a linked list because I didn't want to set an arbitrary maximum number of entities and linked list can be dynamically sized. The problem came from the fact that each block's position needs to be checked in order to draw it to the screen. This involved n semi-traversals of the linked list per step where n is the size of the linked list.

If you're a a little bit lost, this basically means that I'm storing the blocks in a never ending address book where each block has an address. The first block has the address 0, the second block has the address 1, the third block has the address 2 and so on until the last block. Unfortunately, each time I wanted to reach block 3 I also had to access block 0, 1, and 2. After accessing block 3, if I wanted to access block 4, I had to go back to the beginning and access block 0, 1, 2, and 3.

I was foolhardy. I figured "This is 2013, we have powerful computers! I can have 100 blocks in a linked list! So what if we have to traverse a linked list 100 times a step?" Well as it turned out, 100 times a step isn't actually so bad. In fact you can see what 100 blocks looks like at this point in time.



Not too shabby!

My hard cap of 59.whatever frames per second (FPS) isn't even phased by these puny blocks. However, each game space is supposed to be a 200 x 200 grid or 40,000 total spaces. What are the chances I'm only going to use 100 of those bad boys? Let's kick it up a notch to 3,600 blocks which is a little less than 10% of the available grid spaces.


Yikes!

Not the sort of FPS I was hoping for. The problem came from how many traversals the game was doing each time it rendered the scene and by extension how many times it was accessing each block (accessions?). I'm not a mathematician but I estimate that each step of the game loop, Wanderer was doing (give or take a few ) approximately around exactly 3600! accessions.

Uh oh.
In layman's terms, every time I wanted to draw the scene to the screen (approximately 60 times per second) the game needed to make 3600! comparisons to determine the locations of 3600 blocks.

This was not okay. I was stubborn however. I had spent nearly two days wrestling with pointers to get my current system to work, an area in which I am not yet an expert.

I began brainstorming solutions, from storing blocks in separate linked lists to simply accepting my fate and making The. Slowest. Game. Ever.

Fortunately, the solution came quickly. I began to reason: "If the maximum game space is 40,000 grid spaces, then why shouldn't I have a cap on the number of blocks in the game space at any one time?" From this stance I quickly surmised that an array of blocks would suit my purposes nicely.

Now, since arrays are statically sized (you give them a size which can not change) in order to get everything working exactly right I had to create a class called "block array" which has functions for adding blocks to the first unused element, getting the size of the used space, etc.

Now, if you're once again lost what I'm doing now is subbing out my never ending, inefficient address book for a far more efficient far more believable address book that, while containing a specified beginning and end, does not require me to access every address successively. If I want to access block 7, I do not have to run past blocks 1-6 first.

You can see how much better this works.


That's a far more pleasing sight...

...but I crave more!



MORE!


In conclusion, there are two lessons to be taken from this:

1. Screw flexibility for flexibility's sake, just do things the simple way the first time if you have no real reason otherwise.

2. As soon as days and days of frustration and tooth grinding have culminated in a functioning solution held together with (proverbial) duct tape, glue sticks and sheer power of will, you WILL think of a simpler, easier method. (Has this law been taken already? If not, I dub it "Bender's law". If so I didn't want it anyways.)

Hopefully I can get the collision detection and enemies up and running soon so that I can have something a little more impressive to excitedly show my parents.

4 comments:

  1. std::vector is like the ArrayList of C++.

    ReplyDelete
  2. Also resisting the urge to say first was really tough.

    ReplyDelete
  3. While std::vectors can be dynamically sized, it's also slower and I'm trying to be a little bit more efficient.

    ReplyDelete
  4. TL:DR Bender solves life's problems.

    ReplyDelete