Moved

Posted: December 23, 2010 in Programming

I’ve moved to http://www.fracturedcode.com


A while ago, maybe a few months, I made a small racing style game 3d engine for the js1k competition. Unfortunately there was a submission error after I submitted it and I didn’t get a chance to resubmit. too bad, because I tested it in 5 different browsers to make sure it would pass everything… anyway I thought I would share my code for anyone interested.

The engine is programmed in JavaScript so it can simply run inside of a standard web browser. It isn’t a regular 3d-engine, it’s actually pseudo-3d. It takes a 2d map and copies pixels from the map in a 3d-like manner, then translating those pixels onto the screen. I believe this is called a mode7 engine, originally used on the super Nintendo for Mario Kart games. It is a quick and efficient way of rendering from a 2d-map to the screen.  Below is a screenshot of the program in action.

This was renderered off a 2d map shown below, can you guess where the viewer is and in what direction they are looking?

Below is the code I used for the entire demonstration, for fun I am also putting in the code I submitted for the js1k competition as well. Basically it is just the same code, but compressed into 1024 bytes or 1kb.

This can be done by using tricks such as;

  • Placing all code on one line – new lines take up space.
  • Renaming functions to smaller names – such a R instead of Redraw
  • Placing re-usable/re-used identifiers into variables – such as m=Math; so we can reference the Math path with just an m.
  • Using g=’#ccc’; instead of g=’grey’ – we can save one character

There are many other tricks to reduce code length size but here is the code already:

function G(){

 C.fillStyle=g;
 C.fillRect(0,0,w,h);
 r=C.getImageData(0,0,w,h);
 C.fillStyle='#0b0';
 C.strokeStyle='#000';
 C.lineWidth=14;
 C.moveTo(f,u); 
 C.quadraticCurveTo(u,u,u,f);
 C.quadraticCurveTo(u,320,f,320);
 C.quadraticCurveTo(h,320,h,f);
 C.quadraticCurveTo(h,u,f,u);
 C.fill();
 C.stroke();
 C.font="16px Calibri"; 
 C.fillStyle='red'; 
 C.fillText("JS1K",200,85);
 I=C.getImageData(0,0,w,h);

}

function s(u,v){return x+(u-x)*m.cos(d)-(v-y)*m.sin(d)}

function t(u,v){return y+(u-x)*m.sin(d)+(v-y)*m.cos(d)}

function R(){
x=s(x,y-3);
y=t(x,y-3);

for(v=f;v<h;v++){
for(u=0;u<w;u++){

 e=(v-f)/f;
 a=f-f*e;

 i=x-a/2+a*u/w;
 j=y-a+a*e;

 o=parseInt(t(i,j));
 p=parseInt(s(i,j));

 nn=4*((v*w)+u);
 if(o<0||p<0||o>h||p>w){r.data[nn]=r.data[nn+1]=r.data[nn+2]=204;r.data[nn+3]=255;}else{
 n=4*((o*w)+p);
 r.data[nn]=I.data[n];
 r.data[nn+1]=I.data[n+1];
 r.data[nn+2]=I.data[n+2];
 r.data[nn+3]=255;

 }

 }
}
C.putImageData(r,0,0);
}

D=document;
D.addEventListener('keyup',function(e){k=e.keyCode;if(k==65){d-=.1}if(k==68){d+=.1}R()},true);
C=D.getElementById("myCanvas").getContext("2d");
m=Math;u=80;g='#ccc';
w=600;h=400;f=h/2;
x=150;y=85;d=1.5;r=0;
setInterval('R()',90);
G();
 

You may notice that I have used putImageData(); to write pixel data to the screen. This was faster than any other method I was experimenting in, in terms of messing around with one canvas and drawing to another on a pixel-by-pixel basis.

And here is the 1024 bytes long code for the engine.

function s(u,v){return x+(u-x)*m.cos(d)-(v-y)*m.sin(d)}
function t(u,v){return y+(u-x)*m.sin(d)+(v-y)*m.cos(d)}
function R(){x=s(x,y-3);y=t(x,y-3);for(v=f;v<h;v++){for(u=0;u<w;u++){e=(v-f)/f;a=f-f*e;i=x-a/2+a*u/w;j=y-a+a*e;o=parseInt(t(i,j));p=parseInt(s(i,j));z=4*((v*w)+u);if(o<0||p<0||o>=h||p>w){for(n=0;n<3;n++){r.data[z+n]=204*e+204*(1-e)}}else{for(n=0;n<3;n++){r.data[z+n]=I.data[4*((o*w)+p)+n]*e+204*(1-e)}}}}C.putImageData(r,0,0);}
D=document;D.addEventListener('keyup',function(e){k=e.keyCode;if(k==65){d-=.1}if(k==68){d+=.1}R()},true);
C=D.getElementById("myCanvas").getContext("2d");m=Math;g='#ccc';w=600;h=400;f=h/2;x=150;y=85;d=1.5;u=80;
C.fillStyle=g;C.fillRect(0,0,w,h);r=C.getImageData(0,0,w,h);C.fillStyle='#0b0';C.lineWidth=14;C.moveTo(f,u);C.quadraticCurveTo(u,u,u,f);C.quadraticCurveTo(u,320,f,320);C.quadraticCurveTo(h,320,h,f);C.quadraticCurveTo(h,u,f,u);C.fill();C.stroke();C.font="16px Calibri";C.fillStyle='red';C.fillText("JS1K",200,85);I=C.getImageData(0,0,w,h);
setInterval('R()',1);

More 2 come, when I get around to revising/editing and adding to this post!


So I’ve been doing some reading since my last post to try and find out how the Gameforge OGame programmers have been so successful at creating this online game that is seemingly real-time, reliable and playable by thousands. The discussions going on at http://webgamedev.wordpress.com were definitely helpful but confirmed my suspicions that there is no magic bullet.

Below I have come up with a list of basic requirements I expect if I were to duplicate or create an OGame style browser game.

Requirements:

  • Update every second
  • Update 5000+ players
  • Keep all statistics updated (more or less)
  • Inbuilt redundancy for simple server or script failures
  • Efficient scripting and resource usage

Methods:

From what I’ve read from comments and posts there are a few ways of going about updating players details and statistics;

  • Cron Jobs Every minute or hour (updating information over that hour) – this is a tick and does not suit our requirements for time or resources/players
  • Trickle updates Where a few minor updates are run every now and then that a player views something – used in combination with other techniques
  • OnView() Where we update all details concerning a player on viewing of their details by them or an outside element  – after all does a falling tree make a sound if no one hears it?
  • MySQL Events This allows for second-timed events but is too unresponsive for this to be suited to multiple user generated actions around the same time
  • PHP Session We could keep one or two open PHP scripts to deal with things on the fly in realtime – but this is difficult for resource loading with actions

They can also be mixed together in various ways and with various databases.

Simply put;

  • A scheduler can be problematic when the server drops out or inevitably goes offline.
  • A scheduler can impact server performance where actions are centered around a certain time.
  • OnView only needs to be updated when a player views something.
  • OnView does not need to update details when nothing is viewed.
  • OnView can distribute resource load through random player login and view times.
  • OnView keeps information stored in the database.
  • OnView is far more complicated and consequential than scheduling.
  • A realtime PHP session is liable to failure and hard to make redundant.
  • A realtime PHP session is good for a few players on an appropriately designed system with a tick gameplay.
  • A realtime PHP session must use some sort of queue of action serving mechanism.
  • MySQL events are tricky and problematic when the server drops out or inevitably goes offline.
  • MySQL events consume the maximal amount of server resources.
  • MySQL events are conceptually easy.

What I’ve decided on – OnView of course.

Yes it is complicated but if you understand your program architecture well enough, cover your bases and test well then your going to reap the reward of this interesting method for updating player and game details and actions.

OnView will update the result of any action or series of actions on a player only when that player views themselves. Or when another player views their actions on that player or that players details. Essentially, If an action occurs that is between 2 players while they are offline and they don’t log in again then the actions will never be processed by the server because they don’t need to be.

For the more gritty working details how about an example or two;

I attack – Say I launch my fleet and log off. Now I am not viewing anything. What I have done is sent some information to the game server saying I want this and that ship to go to this place and do something. So those details of my action are recorded into the games database. Now, the action (lets say I attacked someone) has occurred and I have not logged in yet. All the while the other player is not logged in either during this time. Still, nothing happens and all the server has done is to log my attack details into the server database. Now I come online. I view my details and OnView is triggered, the server finds the details of my attack and then submits them to an attack calculator along with the victims details. The results are outputted and my message box is updated as well as that of the other player. My previously entered details on my attack are now purged from the database as the action had been completed. If it had not – and I logged in to check on my attack then quite simply I would just get a view screen showing what details I have entered in for the attack (destination, time to land, etc..).

I attack, my friend attacks too – So what if I attack then my friend or another person attacks the same guy. Poor guy. Well the system put in place should handle this. The scenario here is that both the other attacker is offline and our victim, as well both attacks need to be processed because I have just triggered OnView after logging in after the attack should have taken place. The server will need to somehow fetch both attack details. It will process the first attack (the attack with the earlier landing time and then process the later one. I will then get a message as well as the other players. The difficult part here is deciding how the onView trigger will be able to retrieve the two attacks – how does it know?

How does it know? Quite simply it depends on your database, If I am going to trigger all onView details on a player called ‘Bob’ then his attack action or any other action will be stored in the database along with his name ‘Bob’. We need to efficiently search through and retrieve the actions by Bob on his target,retrieve them and then check for any actions on that target by any one else. Why? because we are now looking at the victims details, we need to update them don’t we? This can of course initiate a chain of action retrievals on accounts where people have not logged in for a while, however based on a network, socially oriented game structure it wont take too long before one player causes an OnView update on another.

But what if there is a third party? In Ogame a fleet can be destroyed by another armada and it leaves a debris field out in space. Anyone can view any galaxy and see the debris fields out there. Never-the-less our method does not become unstuck – as you could imagine an OnView of that galaxy will check to see if that planet has a debris field (after all it is part of the players details.. kind of). I know that sounds like it could become potentially a problem where the server keeps checking for un-initiated actions on each galaxy view but I’ll have to think about that and if I find a better way then I’ll let you know.

There is a lot more we could discuss on this topic but I have answered some of my own questions about how browser games work in real-time and how they are processed. I have not talked about databases much but of course they are integral and important to how the game runs. Maybe I’ll talk further about this and more on another upcoming post. For now, if you have any questions just ask away and don’t be afraid to give feedback!


Ogame Ship

I have been playing OGame for quite some time now (many months), but have only really wondered how it all works very recently.

I’ve played other games, Utopia, Earth2025.. I quite like being able to play a game, albeit text-based, in my browser. Actually, come to think of it the text-based aspect does appeal to me as long as there are some good graphics and a clean interface. OGame has many online tools for it, wikis and other pages, indeed a very popular online and free game.

But I was wondering how it all worked! Sure we can augment our HTML pages with Javascript and AJAX, php and a few SQL databases on the backend, but the best I could do with that at the moment is a turn based system. What about real-time? OGame is completely real time and updated every second, it’s not like we can have so many php sessions running and updating attacks and fleets every second can we? …or CAN we? (With php, every user (computer) has their own php session running on ther server, this is so the same script can be run by multiple users.)

I don’t know, but I would like to find out because I would imagine multiple sessions are easy to manage/program although very resource consuming. We couldn’t run a session script for every player because that could mean 5000+ sessions on a single server. Also, a queue based system (where each action is put in a queue based on the time it completes) would be more efficient but would need to be updated every second and for a lot of different attacks or fleet actions again. How OGame?! I will find out, or at least endevour to!


In my first post about calculating covariance matrices quickly I explained how to apply the ideas presented in a paper by Fatih Porikli, Oncel Tuzel. I showed a basic 2nd year university method for calculating cells based on reusing previous calculations (where the answer was stored in another cell).

I mentioned that the code can further be sped up by removing the if’s. I’ve done that and want to show the results.

Here is the old code;

P covariance code after

But you’ll see that after xd and yd are above 1 the ifs become quite useless and waste time. A good way to further increase speed is just to expand the code, so I removed them.

Here is the new code;

code enhanced

You’ll see that for the very first cell we seed the value, and then calculate the top and left columns. From then on, no more if!

And finally the average timings in MATLAB on an i5-750, win7;

Timings;

Before

P (Time ms.): 0.012948
Q (Time ms.): 0.081901

After

P (Time ms.): 0.0094849 (136% faster)
Q (Time ms.): 0.073851 (111% faster)


I just recently created a small MATLAB program to calculate a  covariance matrix from a multi-dimensional input ‘image’. I need the matrix as part of my program to verify palmprints which is for my final year thesis. This article needs to be written because there simply does not seem to be much out there on this, and it can greatly improve the time taken to calculate multiple matrices from the input set.

Precalculation does take some time compared to a MATLAB function like cov but we justify this precalc time if we need to extract many different matrices (as windows) from the input image.

I use the paper ‘FAST CONSTRUCTION OF COVARIANCE MATRICES FOR ARBITRARY SIZE IMAGE WINDOWS’ by Fatih Porikli, Oncel Tuzel. I assume you have read this paper, and may be having implementation troubles.

A naive implementation of this (as I was initially guilty of, and I have seen some others guilty of too!) will lead you to have a precalulation image that is extremely slow and has an exponential O.

For example the naive code may look like this (for calculating P);

P covariance code before

And after adapting a simple programming technique of using pre-calculated values to determine other values;

P covariance code after

Notice we have reduced the complexity and now have only 4 operations per cell We could further speed this up by removing the if’s and calculating the top and side rows seperately in their own loop.

To explain:

P is the summation of values from our input image F. Essentially we are starting at (1,1) and moving right and down, and for any pixel it is the summed values of all the pixels left and above it (in a square). What we have done is we have added the current cell’s value to the cell above and left of it, because the cell above it contains the summed values of all the cells to the left and above of that one we have instantly summed all those values. We do this with both the left and above cell but then we get an overlap (hence the subtraction). We subtract the cell(s) that are counted twice in the previous addition and we are left with our final summation of all the cells to the left and above of our target cell. Neat huh.

For a better idea, let me give you a picture. Grey represents the current cell, yellow the cells being summed, orange the cells overlapped.