Friday, May 4, 2007

More Tweaking

Right, in my previous blog I didn't go in depth about collision detection and left it for later, here I'll talk about it more and fill you in about what I've been doing. Previously I had explained that I threaded the collision detection, to be more accurate I only threaded the collision checking and not the rest of it that dealt with organizing game objects into their cells. Because more than one thread (The main thread and the collision check thread) was accessing the same lists I had to try and achieve some sort of synchronization, I don't want the engine to add an object to a collision list in the middle of a check and have it be missed or removed before it can be used or checked. Java's approach to this type of synchronization is were you nominate which object you want to use and that object becomes locked to all other threads until it has finished doing what its doing. This is a good method of keeping things organized but it can cause deadlocks, wereby if threadA needs to access an object ThreadB has a lock on, whilst ThreadB needs to access an object ThreadA has locked you end up in a pretty bad situation. I'm not sure if its possible to get out of a deadlock but by the looks of things its not. It took me sometime to get the code actually going, I was using a great book title "Java Threads 3rd Ed" to help me with some source and the ideas being threading and proper techniques. When I did eventually get the code working, for some reason when ever a collision occurred it would fire off 4-5 times (in this example I was getting about 10 asteroids appearing on the screen instead of 2) I believe this is because the game is only operating at around 60 frames per second compared to the collision checker which is probably running at triple that. I was also getting some deadlocking on occasions and the game was freezing completely. I'll have to keep at it, maybe I have the synchronization setup wrong.

Whilst coding the new collision system I decided to optimize the way the engine split objects up into cells and stored them in lists. After looking over Pete's code I discovered he was using ArrayLists to store each object, and then was using a very high iteration looping algorithm designed to retrieve objects that were needed for collision checks. The method "getObjects" is passed in a list of game objects and then its supposed to pick out any matching objects from the cells list, in theory this works but in practice it was horribly slow, Pete had used the "ArrayList.contains(Object)" method, which when looked into deeper just runs through a for loop checking for the passed in object and returns true if it has been found. Now if this method is looping through all of the objects in the input list (could potentially be in the hundreds) and then looping through all the objects in the cell list for each object in the input list it equates to A LOT of loops! e.g. 100 Objects X 10 Objects in Cell list X 9 Cell Lists = 9000 checks every time the engine needs to check for a collision. That is a lot of checks, to optimize this I looked at how the cell list operates and its general purpose. It's designed only to store objects contained in each cell but because objects have the potential to move out of their current cell the cell list is constantly being updated and objects are being moved from one list to another. The first data structure that popped into my head was a LinkedList, it is famous for its fast in and out processing and is just as fast at iterating through its contents as any other type of data structure (besides a binary tree) so remembering my old data structure techniques I converted the Cell class into a linked list that used a "cellNode" to store its data and references to the next node. After implementing this I immediately discovered a massive performance increase, which is exactly what I was looking for, previously with Pete's design I wasn't to happy to discover that if you placed more than 500-1000 objects on the screen it would start to chug and lose frames even on my PC which has enough power to run Neverwinter Nights 2 on full graphics at 1600x1050 resolution without losing a frame (A pretty good feat if you ask me) whilst our little game that is only 2D and uses basic primitives is chugging and grinding to a halt.

Another change I made was to the engine and the engine loader. Currently when you start a game a Loader is initialized and is setup to load all of the games textures into memory and build any display lists (currently not setup) for objects, when it has finished doing these things it then starts a new game/engine. But the problem with that is that it will make it harder down the track when we begin to have more and more games, and the need for a dynamic way of starting/loading games becomes necessary, I guess the main problem is, how do I tell the loader what game to load without having to change the code and recompile every time? This is why I decided to change the way it works. I want the engine/game to be started and then the engine starts its own loader, this in theory will actually allow developers to utilize this time frame to load any custom textures they need for their game, and this also solves the problem I described above because now it doesn't matter what game is started, they will all start a loader and load the game specific textures and display lists.

One thing thats been annoying me lately is the fact that all the objects related to a game (e.g. City, Turret, Missile - relate to Missile Command) are placed alongside the game class, inside a package specifically for that game. E.g. "". Whilst we have another package called "retrowars.modules.premade" which was actually designed to be the correct place to put all of these objects so that way other developers can use them for other things besides just that game. A lot of the functionality built into these objects is pretty generic and should be able to be used across all games. So I moved them all into the premade package and reorganised the game files to reside in just the "games" package, so we can have a list of more than one game. Netbeans did all the refactoring (changing of the code) for me.

Thats about it for today, their is probably a bunch of other little things I neglected to mention but its pretty difficult to keep track of everything you do whilst coding. I'm sorry but no pictures today.

No comments: