Archive for the ‘games’ Category

Scrolling game edge tile list

Friday, February 12th, 2016

Suppose you're writing a scrolling game for very limited hardware. You have a frame buffer which is larger than the visible screen, but smaller than the entire level. So when the screen scrolls upwards (for example) you may need to plot a new set of tiles into the frame buffer just above the current screen position, so that the correct image will be displayed when the top of the visible screen overlaps the space where those tiles are plotted.

Now suppose that the hardware is so limited that there is not enough CPU time to plot an entire row of tiles each time you pass a tile boundary - perhaps you can get 60fps normally, but every time you pass a tile boundary you drop a frame or two while the new row of tiles is drawn into the frame buffer.

To avoid this glitch, instead of drawing all tiles at once, we can just draw one or two each frame. Suppose there are N tiles horizontally across the screen, and it takes M frames to scroll upwards by the span of 1 tile. Then we can draw N/M tiles each frame, and by the time the top of the screen gets to the bottom of a particular row of tiles, all of those tiles have been drawn.

Now we need to keep track of which tiles have been drawn and which haven't. The obvious way to do this would be to just have an array of bits, 1 for "tile has been drawn" and 0 for "tile needs to be drawn". Now, each frame when we draw a tile we can iterate through the array to find the first tile that hasn't been drawn and draw that one.

But what if there are rather a lot of tiles? Iterating through all those slots to find a "needs to be drawn" one could take a while, especially if all the undrawn slots are all the way over to the right. So we've turned a O(N) operation (N being the number of tiles drawn) into a O(N2) operation. Oh, and did I forget to mention that this is a 2D scrolling game? So we'll have a similiar list for each side of the screen, and each time we pass a tile boundary going vertically, we'll have to shift the left and right lists one tile.

How can we get rid of this quadratic behavior? Well, I think a data structure that should work well is a linked list. If we put the information about one tile slot in each node of the list, that makes it O(1) to shift the whole list one tile forwards or back for lateral scrolling, but doesn't fix the O(N2) search behavior. However, notice that we only need to store 1 bit of information about each tile slot. So what we can do is apply a run-length-encoding transformation to the list. Each node stores a pair of numbers - the length of a run of drawn tiles and the lengh of a run of undrawn tiles immediately following it.

Now all the operations we need are O(1). For the "top of screen" list, scrolling left or right by one tile just involves adding a slot to one end of the list and removing one from another. Finding the next tile to be drawn just involves looking at the first element of the list. We need two more operations: throwing away the entire list and replacing it with an "all drawn" list (for scrolling downwards) and throwing away the entire list (hopefully a single "all drawn" entry) and replacing it with a "none drawn" list (for scrolling downwards). Throwing away a list with potentially many entries sounds like it could potentially be an O(N) operation, but as it's a linked list we can move all the nodes to a "free nodes" list just by modifying the ends.

As always where performance is concerned, be sure to actually benchmark this before using it - depending on the hardware and the number of tiles in question, all that pointer chasing and cleverness may actually be slower than the naive bit array method. This is especially true if you're not in a hard-real-time situation, and the average case behavior matters more than the worst case behavior. Constant time algorithms have a definite appeal from an the aesthetics pespective, though.

Preventing cheating in online games

Saturday, August 20th, 2011

In computer security, there is a general rule which says that you should never trust anything sent to your server by client software running on a user's machine. No matter how many cryptographic checks and anti-tampering mechanisms you put into your code, you can never be sure that it's not running on an emulated machine over which the user has complete control, and any bits could be changed at any time to give the server an answer it accepts.

This a problem for online gaming, though, as cheaters can give themselves all sorts of capabilities that the game designer did not plan for. This (apparently - I am not much of a gamer) reduces the enjoyment of non-cheating players.

However, games do have one advantage here - they generally push the hardware to (something approximating) its limits, which means that running the entire game under emulation may not be possible.

So, what games can do is have the server transmit a small piece of code to the client which runs in the same process as the game, performs various checks and sends the results to the server so it can determine if the user is cheating or not. The Cisco Secure Desktop VPN software apparently uses this technique (which is how I came to think about it). I have heard this small piece of code referred to as a "trojan" in this context, although this terminology seems misleading because this particular kind of trojan doesn't run without the users knowledge and consent, and is only malicious in the sense that it doesn't trust the user (the same sort of maliciousness as DRM, which is not quite as bad as illegal malware).

The trojan for an online game could send things which are very computationally intensive to compute (such as the results of the GPU's rendering of the game). Because the server can keep track of time, doing these computations in anything less than real time would not suffice. To avoid too much load on the server, the computations would have to be things that are easier to verify correct than to compute in the first place (otherwise the server farm would need to have a gaming-class computer for every player, just to verify the results). And to avoid too much load on the client, it should be something that the game was going to compute anyway. I'm not quite sure how to reconcile these two requirements, but I think it should be possible.

The system should be tuned such that the fastest generally available computer would not be powerful enough to emulate the slowest computer that would be allowed to run the game. Depending on the pace of progress of computer technology and the lifespan of the game, it might eventually be necessary to change these requirements and force the users of the slowest computers to upgrade their hardware if they want to continue playing the game. While this would be frustrating for these players, I don't have a problem with it as long as there is a contract between the players and the game company that both agree to and are bound by - it would be part of the cost of playing without cheaters. Though I would hope that independent servers without these restrictions would also be available if there is demand for them.

Special relativity game

Friday, August 19th, 2011

I think it would be awesome if somebody made a 3D, first person computer game where the speed of light was significantly slower (perhaps 30mph as in the Mr Tompkins books) and did relativistically correct rendering so that you could see the geometric distortions and Doppler shifts as you walked around. It might be necessary to map the visible spectrum onto the full electromagnetic spectrum in order continue to be able to continue to see everything (albeit with reddish or bluish hues) when you're moving quickly.

It would have to be a single player game because (in the absence of time travel) there is no way to simulate the time dilation that would occur between players moving around at different speeds.

It appears that I'm not the first person to have this idea, though the game mentioned there (Relativity) doesn't seem to be quite what I'm looking for.

I do realize that it might be quite difficult to do this with current graphics engines, but I'm sure it could be done in real time, perhaps with the aid of suitable vertex and pixel shaders for the geometric/chromatic distortions respectively.

Politics simulator

Friday, August 6th, 2010

I've occasionally thought it would be fun to have a computer game where you start out with some land, some people and some natural resources, and your job is to found a country and run it. You get to write your constitution, set up laws and so on and see how things unfold. You might also play the part of a politician once the country is set up. You might get voted out, which changes the set of powers you have (and makes the main next objective "get back into power"). Maybe there are other countries on the "virtual planet" - you can invade them, embargo them, make treaties with them etc. They have their own objectives. You get problems thrown at you (war, dissent, natural disaster and so on) and have to make changes to your policies to try to keep everybody happy.

Given the similarities between writing laws and writing code, I suspect this might devolve into a "programming game" style activity (albeit with a rather more political type of geekiness). I also suspect that there are so many aspects of human activity that would need to be simulated that making it realistic would be an overwhelmingly large task. But of course it doesn't need to be perfectly realistic to be fun - it may be fun enough with just easy-to-implement large-scale economic features.

Tet4 is a game of luck

Saturday, October 3rd, 2009

I used to think it might be possible to come up with some kind of general algorithm for playing Tet4 indefinitely, but I now suspect that no matter how tall the pit is and how many pieces you can look ahead, there are always sequences of pieces that will guarantee a loss - in particular, I don't think there is any way to place the sequence SSZ without adding a row every 6 pieces. This means that ultimately, Tet4 is a game of luck. However, most sequences that occur in practice do seem to be solvable - many years ago I wrote a program to play Tet4 automatically, and it seems to be able to play indefinitely. So in practice speed and accuracy are more important than luck for winning the game.

Side note: On the most recent occasion that I tried to figure this out, I attempted to resurrect my old Tet4-auto-player program (not trivial, since it's a graphical DOS program and hence doesn't work on Vista) and modify it to see if it could solve the SSZ repeated sequence. Once I'd got it running, I was amused to see that it was already set up to solve the SSZ repeated sequence - I'd done the exact same thing before and forgotten all about it!

Talking of Tet4, it's had a couple of updates since I last mentioned it here. The original version has had a bug fix so that playback of games in which the curtain reaches the bottom works properly. Also, a second version has been added, which is exactly the same but with no undo (and which is therefore less forgiving). This may be one of very few occasions on which the second version of a piece of software is identical to the first version apart from the removal of a significant feature.

When I first wrote the Javascript version of Tet4, I took the opportunity to change the keys from the DOS version a bit, to make them more logical and faster (so that if there were 5 or fewer possible positions for a piece, either hand could be used, for example). This meant that I kept making mistakes because (although I hadn't played Tet4 for years) my muscle memory was still trained with the old keys. Hence I added the undo feature. But in making the game more forgiving, I changed its nature significantly.

There's two ways I could have added undo to Tet4. One way is to undo the random number generator one step when undoing. The other is not to. Undoing the random number generator essentially gives you unlimited lookahead capability. To look ahead n pieces, drop those n pieces (anywhere) and then undo n times. I didn't want to grant that power, so I wrote it in such a way that dropping n pieces and undoing them changes the random number generator state. However, this gives an even stronger ability - now you can essentially choose which piece comes next by dropping and undoing until you get the piece you want. I think this makes the game too easy (at least until it gets really fast), hence the new version.

Game browser

Friday, July 24th, 2009

I was thinking some more about convergence of game engines recently, and started wondering what a cross between a web browser and a game engine would look like.

I think the real value in this would be lowering the barrier to entry for 3D game creation, much as the appearance of HTML and web browsers made it easy for anyone to create rich documents and publish them to the world.

The first thing we need is a very high level way of specifying simple 3D environments. I think the best interface for such a task ever conceived is that of the holodeck in Star Trek: The Next Generation. Captain Picard walks into the holodeck, which initially is an empty room. he says "Computer, create me a table" and a generic table appears. Next he says "make it pine, 2 inches taller, rotate it 45 degrees clockwise and move it 6 feet to the left". Iterating in this way, he converges on the design he had in mind. Seeing the intermediate results immediately allows him to determine what's "most wrong" and therefore needs fixing first, and may also provide inspiration in the event that he doesn't really know what he wants just yet.

The difficult thing about this interface is that one needs to have a big database of objects to start with - tables, trees, bees, books and so on. Once also needs a big database of textures, a big database of transformations and so on. In fact, there are all sorts of databases which would come in handy - animations, AI routines, material properties, object behaviours. The obvious "Web 2.0" way to populate these databases is to encourage people to publish the things they create for their own games in such a form that they can be used by other people for their games. I don't think the software should necessarily go out of its way to forbid people from making content that can only be used in their own game, but making the default be "this is free to use" would probably help a lot.

If you're creating a website today you can easily find lots of free backgrounds, buttons, menus, applets and so that have been created by the community. With the right encouragement, a similar community could form around creating game things. Put a search engine on top of this community's effort so that when you search for "chair" you get a gallery of models to choose from and you're well on your way to the holodeck interface.

To create compelling games, one needs more than just a decorated 3D space to wonder around in - there need to be challenges, there needs to be something at stake. The web model breaks down a bit here - since you can get from anywhere to anywhere else just by typing in the appropriate URL, what's to stop players from just transporting themselves to the holy grail room?

I think that any non-trivial game would generally involve writing some code (possibly in an ECMAScript-ish sort of language). That code would need to have certain powers over the player, including associating information with them (like "has the player been through this obstacle yet?") and the ability to move the player (which could be done by moving a portal through the space that the player's avatar is occupying) to send them back to the beginning if they haven't completed a required obstacle or if they are "killed" by the minotaur. In computer games, death is of course never permanent, so can be effectively emulated by teleportation.

Another web principle that I think this software should embody is decentralization. Someone who wants to create a website has many options for hosting it (depending on their needs), one of which is to run their own web server. A major problem with a system like Second Life is that there is a central server, which is a single point of failure and a monopoly of sorts over the game universe. Virtual "land" is not not free in second life, it leased from the central authority. And if that central authority decides to raise their prices, censor content they find objectionable or has a server failure, there is nothing that the users can do about it. I suspect that this is a limiting factor in SL's growth.

If no-one "owns" this universe, who decides how it "fits together" (more concretely, what's to stop everyone saying "our site is directly north of Yahoo!"). I think in this scheme one has to give up having a single Hausdorff space and instead have many worlds connected by portals. The owner of a space decides what portals go in it, how large those portals are, what their positions and orientations are, how they move and where you end up when you go through them. Portals are not necessarily bi-directional - on going through one, one cannot necessarily get back to where one was just by retracing one's steps. They are more like links on a website than the portals in Portal. Mutual portals could be constructed though, if two gamemasters cooperate with each other to do so.

Ideally a portal should be rendered in such a way that you see what's on the other side - this just means that that "world" would also be loaded by the client software and rendered from the correct perspective (though should not be able to affect the player).

I think it would be great fun to wander around and explore different game worlds this way. It might be confusing sometimes, but if a place is too confusing people probably won't create many portals to it, so the system would be self-governing to some extent.

The system I've described could run with a standard HTTP server to implement a wide variety of single-player games. But where the internet really comes into its own is real-time interaction with other people - (massively) multiplayer games. Here, things become more complicated because the movements and actions of each player need to be sent to all the other players, and conflicts need to be resolved (who actually got to that loot first?) These problems have all been solved in real-life multiplayer games - one just needs a server which does some of this "real time" stuff as well as serving the content.

While games would be probably be the initial "killer application" for this, I'm sure all sorts of other interest applications would emerge.

Shortly after I originally wrote this, Google announced their O3D API which seems like it has at least some of the same aims, though at the moment I think it's really just an in-browser 3D API rather than a 3D version of the web. However, it'll be interesting to see what it evolves into.

Game engines will converge

Saturday, October 25th, 2008

At the moment, just about every computer game published has its own code for rendering graphics, simulating physics and so on. Sometimes this code is at least partially reused from game to game (e.g. Source), but each game still comes with its own tuned and updated version of it.

I think at some point the games industry will reach the point where game engines are independent of the games themselves. In other words, there will be a common "language" that game designers will use to specify how the game will work and to store assets (graphics, models, sound, music etc.) and there will be multiple client programs that can interpret this data and be used to actually play the game. Some engines will naturally be more advanced than others - these may be able to give extra realism to games not specifically written to take advantage of it. And games written for later engines may be able to run on earlier ones with some features switched off.

Many classes of software have evolved this way. For example, in the 80s and early 90s there were many different ways of having rich documents and many such documents came with their own proprietary readers. Nowadays everybody just uses HTML and the documents are almost always independent of the browsers. As far as 2D games are concerned, this convergence is already happening to some extent with flash.

3D games have always pushed hardware to its limits, so the overhead of having a game engine not tuned for a particular game has always been unacceptable. But as computer power increases, this overhead vanishes. Also, game engines are becoming more difficult to write (since there is so much technology involved in making realistic real-time images) so there are economies of scale in having a common engine. Finally, I think people will increasingly expect games to be multi-platform, which is most easily done if games are written in a portable way.

If game design does go this way, I think it will be a positive thing for the games industry - it will mean that more of the resources of the game can be devoted to art, music and story-telling. This may in turn open up whole new audiences for games.

What makes a game addictive?

Wednesday, September 24th, 2008

I have an unfortunate habit of getting addicted to computer games - this is one reason why I don't play them as much as I used to, and why when I do now play games, I usually pick one with a definite ending so that there's a natural place to stop.

But occasionally I do slip into excess playing of Tet4, Freecell or Spider Solitaire. I think what makes these games particularly addictive is that restarting them is a move which seems to bring you closer to winning. In all these games, the state of the game starts out as quite simple and the moves are obvious, but as you play things get more complexified and constrained until either you lose or (if possible) winning becomes inevitable. Restarting decomplexifies so when you lose your brain (which is still thinking in terms of the game) naturally reaches for the "restart" key.

Tet4 implemented in JavaScript

Tuesday, September 23rd, 2008

If you want to just skip to the game, the link is here.

Many years ago, I decided to write a Tetris game, just to see if I could. I succeeded, but the play area was very wide. So I added controls to make it adjustable. I figured the minimum sensible width was 4 (otherwise not all orientations of all pieces can be used). Playing Tetris on a board of width 4 (or Tet4 for short), I discovered, is very different to normal Tetris. Things change much more quickly, every piece has a profound effect on the state of the board and the normal Tetris strategies don't apply because it's impossible to play without leaving some gaps.

After playing for a while, I discovered that Tet4 was even more addictive than normal Tetris, and that it was much easier to get to the state of mental concentration known as "the zone" - where the entire rest of the world seems to melt away and there is nothing left except you and the falling blocks. When you notice this (and can do so without leaving the zone), it becomes almost an "out of body" experience - your conscious mind almost seems to observe from outside as your unconscious mind plays the game as if on some kind of automatic pilot.

Once I experienced this, I wanted to intensify it. I realized that a gradual increase in speed is intrinsic to the zone experience (otherwise it's just repetitive). But at a particular speed, the limiting factor becomes how fast your fingers can move to maneuvre the piece into place - this can take as many as 4 or 5 keystrokes with the normal Tetris controls. I realized that Tet4 only had at most 10 possible combinations of orientation and position for each block. Most people have 10 fingers so let's just assign one combination to each of 10 keys and have a finger corresponding to each key. This is the control mechanism that Tet4 uses, and it worked exactly as I had hoped.

This version is a rewritten version in JavaScript (because I wanted to learn the language, and because by making it run in a web browser more people would be able to play it). I've tested it on IE7, FireFox 3 and Chrome and it seems to work fine but there may be bugs with other browsers. Let me know if you find any. I've made some fairly substantial changes with this rewrite, which makes this a rather unusual and minimalist version of the game:

  • A display which shows the position and orientation for each key (on my original version I learned the combinations by trial and error). This display is really just to reduce the game's learning curve a bit - to truly get into the zone you'll need to commit all the combinations to muscle memory.
  • In my original version, the 10 keys just set the position and orientation of the tetroid - you had to press the spacebar (or wait for gravity) to drop the piece to the bottom and get the next piece. This meant a decrease in zone at the point where it gets too fast to use the space bar and you switch from 11-key mode to 10-key mode. In this version, the 10 keys drop the piece as well, so you always press 1 key per piece.
  • In my original version, the game ends rather suddenly when your tower gets so high that there isn't time to think before your active tetroid locks. In this version, there is a "curtain" which falls behind the playfield, and you always have until it gets all the way to the bottom before your tetroid drops. This means that the amount of time you have isn't dependent on the height of your tower. Also, the piece doesn't enter the playfield until it is dropped, so you can take care even with the endgame (you lose when you drop a piece and it would protrude from the top of the screen).
  • The single key control mechanism is rather unforgiving of misdrops, so I added an undo feature - at any time you can press Q to undo the last drop. This helps in learning the keys, but for getting the best scores it is best avoided as your score is also undone but the time speedup is not. This also doesn't allow you to "look into the future" (further than you can anyway with the next piece indicator) - a new tetroid is chosen at random for the new next piece whenever a piece is placed.
  • I added a persistant, global high score table which includes a facility for replaying the top 10 games.
  • I modified the colours and key to position correspondances to better take advantage of the symmetries. This puts me at a bit of a disadvantage (since I'm used to the original keys) but should be easier to learn.

One other thing I'd like to do in the future is make an ActionScript/Flash version so that it can be embedded into other pages. I started this but it turns out that without the official Adobe development kit, Flash is really hard to learn.

Cheating in online games

Friday, September 12th, 2008

Many modern online games go to great lengths to try to prevent players from cheating - some of them quite invasive. I hope that in the future our computer systems are architected to make it trivial to subvert such malware, but where does that leave players of on-line games who want to avoid playing against cheaters?

Well, I hope that in the future, online games are designed in such a way that cheating is impossible - that is, no information sent to a player's computer that would allow them to gain an unfair advantage and no information received from a player's computer is trusted to be untampered-with. In such a game, a player would be allowed to use whatever client software they like, and would be encouraged to use client software that gives them the best odds. Serious golf players pick the clubs that give them the best advantage, tennis players pick the best tennis rackets and so on - why should on-line gaming be any different?

One implication of this is that the best games will be Turing tests of a sort - a game of aiming accurately and reacting quickly won't be much of a challenge since the computer can do those things better than human players. Tasks that humans can do well but computers are poor at will need to be integral to the game.

That's not to say that games of aiming accurately and reacting quickly won't exist, but if they are played online they will be played between people who each other and trust each other not to cheat, not between strangers.