The first time that I saw the game, was on my brother's computer. He had created the computer himself, based on a Zilog Z80A CPU with 4MHz and 4kbyte RAM. Everything was home made - graphics electronics design, etching the boards, a hex keyboard for his machine code boot software, and a high level language and all the software on top of it. However, the computer had the boot software and the high level language in an EPROM (requires UV light to be erased), and there was no other persistent storage, so all programs that you wanted to use, had to be programmed before using it.
It was back in 1981, and I was allowed to use his computer for gaming, and I knew how to use the hex keyboard to instruct the boot software to start up the high level language, so that was great. I just had to program the snake game every time I wanted to play it, so I got quite good at it. And each time I programmed it, I made it a bit different, of course.
Enough about the background, here is the data structure of a snake game:
type TItem=(spEmpty, spFood, spPoison, spWall, spSnakeHead, spUp, spDown, spLeft, spRight); var arr:array[0..79,0..24] of TItem; TailX,TailY,HeadX,HeadY:integer; SnakeLength,LengthToAdd:integer;
This is how you add food or poison, avoiding snake positions, wall etc.:
procedure AddItem (item:TItem);
var
x,y:integer;
begin
// It can be argued that this loop does not
// always end within finite time, but who cares?
repeat
x:=random(80);
y:=random(25);
until arr[x,y]=spEmpty;
arr[x,y]:=item;
end;Then you need this one:
procedure MoveCoor (var x,y:integer;dir:TItem);
begin
case dir of
spUp:dec (y);
spDown:inc (y);
spLeft:dec (x);
spRight:inc (x);
end;
end;So when you want to move the snake's head, you do this:
arr[HeadX,HeadY]:=MoveDirection; MoveCoor (HeadX,HeadY,MoveDirection); found:=arr[HeadX,HeadY]; arr[HeadX,HeadY]:=spSnakeHead; if found<>spEmpty then begin if found=spFood then LengthToAdd:=SnakeLength*0.5 // Alternatively just set LengthToAdd:=1 else (* End game, we ran into something that is not healthy *); end;
Increasing the length is simple, just keep a counter of how much longer the snake needs to become, and every time you are about to move the tail, either decrement that counter, or when it is zero, actually move the tail. This is how to move the tail:
if LengthToAdd=0 then begin dir:=arr[TailX,TailY]; arr[TailX,TailY]:=spEmpty; MoveCoor (TailX,TailY,dir); end else begin dec (LengthToAdd); inc (SnakeLength); end;
As you can see, a snake game is seriously simple, uses almost no CPU, is very short in source code and uses very little RAM. There is not a single object in all this, because OOP wasn't invented back then.
Could this be done more easily today using modern programming? I haven't found a better method, yet. If we should describe the old method with modern terminology, what would that description look like? The snake must be some kind of object, but it's data is stored in an array that represents the screen. However, the screen array doesn't just show the presence of the snake, but also the direction to go in order to find the next element of the snake. So, basically, according to modern criteria, this code is unstructured, messy, non-scalable, non-maintainable etc. However, in my opinion, as long as the code is easy to read, it is maintainable, and if it scales within required boundaries, it's scalable. It would be easy to encapsulate the "Snake game engine" into an API, hiding the implementation details, so I definitely still consider this to be great code.
15 comments:
Awesome :)
Well... I think we could create 2 objects (talking about java).
An object called 'items', holding its type (food, poison, wall) and its cartesian coordinates.
Another object called 'scenario' with an array of 'items' objects inside it. And an object called 'snake' holding the current x/y position of head, tail and the length of the snake... But I guess it would use more RAM and CPU...
Well... It is a thing to try =D
I'll try to code it!
See yah.
Just because you have a small amount of code for a very small and trivial task does not mean that the practices that you used for this trivial example should in any way apply to a more complex example.
I can stick two pieces of paper together quite well with bubble gum, does not mean I would build a house with it.
What if you wanted other animals aside from snakes? What if you wanted 20 different kinds of food, each with different properties and visual representation? What if the snake could grow in 15 different directions? What if the board should grow in a strange manner? etc. etc.
If you had coded your program using objects, these extensions would be (relatively) easy to do. With your linked list they are very difficult.
What you are showing here is the classic trade off of OO programming. Usually slower, and more complex, but more extensible and maintainable.
Lars, nice case!
In order to answer you question it is important to define the meaning of "doing things more easily" and "better method".
If "more easy" mean "with less RAM and less CPU" OOP often is not the best way of doing things. I think to some core parts in embedded systems written in assembler because of resources constraints.
Very specific tasks are often best solved with very specific code, this can be also without OOP.
If "better method" mean "scalable in an unpredictable way", like David said OOP allows to extend functionalities in a relatively simple way.
Finally, OOP is a way to build great software, this doesn't mean that cannot exists great software written in other ways, like your snake game.
Agile programming involves that rewriting can be better than modifying. When the code is this short and easy, the amount of time used to prepare it for hypothetical, possible, eventual, future modifications, later, is huge, compared to the time lost in a rewrite :-)
Also, you need to discount future work with an interest rate.
Odds are that this simple piece of code is actually easier to maintain and will scale better in many ways than the vast majority of OO versions that would be made of this code...
There is an explicit complexity and maintainance cost to every instruction in code, regardless of intended code clarity. This is something alas too often forgotten.
I was born in '68 and learned to program in the non-OO age myself. I still care about things like memory usage and code efficiency.
In the case of your Snake example there are still 'implicit objects'. These are the cells, the grid and the snake (with head and tail positions and length as properties, but not the body shape).
The reason this code and these data structures are (relatively) efficient is that the grid is quite small, has a fixed rectangular shape and there can only be one element per cell. Also the snake movement is always 1 grid cell at a time. Those restrictions were largely imposed by the character based graphics of the hardware of the 'early days'.
Now let's suppose we change just one thing, we make the grid as large as 10000 by 10000. Is the data structure still efficient now? No, storing the snake body, plants and other objects in lists will now use a lot less memory!
And, as David already mentioned, a better OO approach will also make it much simpler to change and add other game features.
@Victor: One of the things that I really find strange, is that the modern versions of the Snake games still use the grid structure, where the snake is 1 grid cell wide and can only turn at grid cells.
I'm not sure if this is done in order to simplify programming or because it makes the game more entertaining.
However, as long as the rules for snake movement and size is unchanged, the amount of data in the app is proportional to the grid size, because the snake can occupy most of the screen. This makes the 2-dimensional array more memory efficient than a list solution, even at 10000 x 10000 grid size.
The movement rules of the early snake games were imposed by the character based graphics, but also by the available input apparatus, i.e. the cursor keys or the digital 4-way joystick. The Nokia has the same input device restriction. And an attractive part of the course grid is that it makes it possible to line up the snake exactly to its own body.
So I guess I agree, the attraction of the game is in its simplicity, adding more movement options would not make it more fun to play.
As for the memory usage, that could still be limited by storing the snake body in a sort of run-length-encoded format, with a direction and length per segment. This would save a lot, as players tend to make each segment as long as possible. But for simple computing devices (is the current phone still in this category?) dynamic memory allocation is a bad thing, using a fixed size structure is better.
And yes, I agree, storing the snake body in the grid does come with the benefit of extremely simple 'hit testing'.
Of course, many other early computer games, like Zombies, used a grid - 2D array both as 'game world' and game objects positions data structure. Just like many pre-digital board games, like chess.
I wouldn't like to program Asteroids in this fashion though ;-)
Victor, memory usage would of course be most optimized by merely storing the player actions and the time at which they occurred (everything being deterministic). This however, like a linked list or your RLEs, transforms the problem from a constant time O(1) algorithm per step to an O(n) algorithm, n being either the length of the snake (or the number of segments, both can be considered roughly linearly proportional, so it doesn't change anything in the Big O scheme). If you're not careful in your implementation, you could even end up with O(n2) or worse.
Interestingly enough, this would mean that at some point, you would likely need to introduce some fairly intricate algorithms to handle a snake moving in a 10000x10000 environment f.i., as merely cheking all segments (whether compressed or in raw lists) would become too expensive to guarantee a high enough frame rate.
On the other hand, the grid method in a 10000x10000 environment still uses a measly amount of memory (by today's standards, or compared to what your video card would be using to render the snake ith today's graphics), and the grid would scale without issues to accomadate multiplayer. List approaches would hit their performance wall much sooner in a multiplayer (tron-like) case for instance.
i think the snake game is and always was a good way to show functional programming versus linear. you can't go straight from linear/goto style to OO, you have to understand functions first. once you get it functional, the point at which objects become more useful than straight functions is when you need to reuse code through an inheritance hierarchy. the simplest possible snake game doesn't need those properties, but add just about any amount of complexity and you soon find them invaluable...
if you look for examples long enough, you find everything is unnecessary. here, though, i think you've found the exception that proves the rule.
Given a non-vector display I would use pixels to keep track of the snake trails.
The only part that moves is the head of the snake, so you simply store coordinates, and test whether a pixel is at x,y to do intersections.
Like most games this would really lend itself to the Model-View-Controller pattern.
In the 1980's version, the array is the model, screen character memory is the view and the controller knows about keypresses.
In the 2010 version, the model might be a list of CSG solid models to do collision detection against, the view could be an openGL display, and the controller could be an Ipod touchscreen or a Wii remote.
The beauty of a clean OOP design is that the 1980's version could have evolved into the 2010 version in a step-wise fashion without the structure of the game changing much (if at all).
OOP doesn't inherently make code smaller/faster only more adaptable.
Are you sure OOP hadn't been invented by '81?
@Wyatt: OOP and other fancy words in IT are often just words that describe stuff that many people already did before it got a name. I definitely did OOP before I heard about objects, and we called it worm games, not snake games. But OOP didn't get mainstream traction until Borland made it popular in their Turbo Pascal series, I think it was Turbo Pascal 5.x or something like that.
Post a Comment