[tcaudilllg]

I intend for the purpose of this thread to be the discussion of game programming's evolution. The way I see it, games aren't really a far cry today from what they were only two decades ago. Although the graphics have changed, not much else has. I think this will become apparent as the history of the techniques is explored, game by game by game and year by year. It will be shown that each period is marked by the development of new algorithms, the development of which marks the transition from one period to the next. As such, each game can be reduced to its constituent algorithms, and the progression of their design explored.

What I intend to show is that games really haven't changed much since the days of Space Invaders, Rouge, and Donkey Kong. In fact, I would have to say that these three games are the genesis of everything that came after, and that today we are still mostly relying on these same fundamental techniques not only as the basis for our programmings of games, but also for our conceptualizations of their design. It will be shown that although there has been change (as there have been developments) these changes have all centered around the rethinking of Space Invaders, Rouge, and Donkey Kong.

I intend for this to be a long discussion, maybe a year or more.

[tcaudilllg]

I'll start with the forefather of games, Pong.

Pong was the first game to use realistic physics. It involves a four-boundary test algorithm by which it determines whether to bounce the ball or declare it out of bounds. It uses a planar movement algorithm for the ball, and a linear movement algorithm for the paddles. Although it might be surmised that each paddle has a boundary test for its side, it's more likely that it just has a simple test for the presence of the left and rightmost points of the ball in either paddle's vector. I surmise that the left, right, top, and bottom-most pixels alone of the ball are actually used for testing, although alternatively you could count pixels from the center of the ball and get away with testing only the ends of radius-length rays extending from the center. The most complex element was the use of accurate rebound vectors and velocity shifts of the ball -- although these apparently were not as complex as you might think.

It would appear that Pong itself was derived from Magnavox's table tennis game, which was everything Pong was without the physics.

[RampantCoyote]

Are you doing a history of game PROGRAMMING, or the games themselves?

A couple of books I'd recommend would be:

High Score!: The Illustrated History of Electronic Games, Second Edition

I love this book. Pretty detailed for covering such a huge field. It starts way back in the pre-pong era, with SpaceWar! and William Higinbotham's Tennis for Two - played on an oscilloscope in 1958. And it goes on through to (I think) the early-to-mid 2000's. While it doesn't cover every game ever, it does cover all of the major players, touches on the most influential games, and has LOTS of screenshots and cover illustrations. Did I mention I love this book?

Also:

Hackers: Heroes of the Computer Revolution

This is another of my Favorite Books Ever. It emphasizes the early era at MIT and the Tech Model Railroad Club (including their first experiments at Chess and - of course - the making of SpaceWar!), the early Apple and homebrew computer clubs, and a sizable section on the era of Sierra (AKA Sierra On-Line) when computer games started becoming a real business. It's really kind of an "inside story" type of thing - going into the culture and personalities of the people behind the curtain.
_________________
Tales of the Rampant Coyote - Old-School Game Developer talks Indie Games, RPGs, and the Games Biz

[tcaudilllg]

Space Invaders was predated by Space Wars. Space Wars was the first game to use variables to manage the game state. It was also, apparently, the first game. It used linear moving sprites (this from what I can gather, at least) and collision detection. Just a short hop, apparently, from Space Wars to Pong. (bouncing bullets? Lines instead of ships?)

It also used backgrounds, but apparently no masking because the ships were line graphics and hollow.

Space Invaders was an evolution of Space Wars. Instead of one enemy ship there were many, and collision detection was done with bounding boxes. (usually) The barriers used pixel-perfect detection. Enemies had AI which consisted of movement to the bottom of the screen and random firing of bullets towards the bottom. The game also featured animation, which was accomplished by reassigning sprite images at regular intervals. The death animation was triggered by a simple event system.

In essence, Space Invaders' AI was the union of the pong ball, the out-of-bounds boundary test, the enemy paddle, and Space War.

[RampantCoyote]

Actually, it's SpaceWar! with the exclamation point, officially, I think. Space Wars was an arcade game that came much later inspired by SpaceWar!

Computer Space was actually the first arcade game (predating Space Wars by about six years, I think). Nolan Bushnell was so inspired by playing SpaceWar! at the University of Utah that he tried to make a coin-op version. It didn't do so well. He eventually decided that it was just too complicated for its intended audience (who might have two or three beers in 'em) that he went simpler, and followed up with Pong. Obviously, Pong did phenomenally well, and for most people was THE game that ushered in the era of the arcade video game.

There was initially no backgrounds for SpaceWar! - there were only five objects in the most common releases of the game: Two ships, two missiles, and a star. Later versions included a "background" starfield.

As I understand, the Space War graphics were vector-based, not sprite based.

As a total aside: years later, in 2004, I wrote Void War, inspired by Space War and played in 3D. But that's got nothing to do with your history. I'm quite proud of it though. And I actually broke even on it, if you don't include the insane amount of time I devoted to it, and to writing the engine from scratch. My homage to SpaceWar!

As far as the "first videogame" (which is still subject to argument) was probably OXO in 1952, followed byTennis For Two, in 1958. Spacewar! didn't have its first release until 1962.
_________________
Tales of the Rampant Coyote - Old-School Game Developer talks Indie Games, RPGs, and the Games Biz

[tcaudilllg]

Pong was followed by Breakout, which was different than Pong in that it was vertically-oriented as opposed to horizontal, and used destructible barriers instead of enemy paddles. The algorithms used were fundamentally the same as Pong, however, including moving paddles, accelerating balls, out-of-bounds tests and rebounds, and angles of deflection. One important difference is that the barriers are composed of blocks which can be destroyed from any direction -- this points to clear use of bounding boxes, perhaps the first game to require such. The enemies in Space Invaders required only the use of lower bound tests for collision.

[tcaudilllg]

Asteroids, as we all know, pioneered vector collision detection. (or did it?) It used vector-based collisions and clipping. I remember reading about a clone made by Andre LaMothe in the first edition of his Teach Yourself Game Programming in 21 Days; he described it in very great detail, most of which I did not and still do not understand. Asteroids also used a random generator to create asteroids... and as such may have been the first game to randomly generate opponent characteristics.

It also appears to have randomly generated the positions of flying saucer enemies.

The asteroid splitting process appears to have involved several stages:

• The collision event was tested for the asteroid hit.
  
• If the test returned true, the asteroid was destroyed, and in its place several smaller asteroid sprites were created.
  

In Asteroids, the vector sprites doubled as the logical objects used by the game physics.

[tcaudilllg]

Galaxian used most of Space Invaders' algorithms. (minus the enemy advance to the bottom of the screen). Its major innovation was free moving enemies who could move about in arcs and try to crash directly into the player. The player collision tactics involved the use of a seeking algorithm which locked into the player position and moved towards it without adjustment. This algorithm was remarkably simple: it merely involved taking the player's position and scripting the enemy alien to go after it.

But to that effect, it was the first game to use scripted NPCs. This proto-script engine itself was apparently a state machine which had four states: formation, free, tracking, and dead. This in comparison to Space Invaders, which probably didn't use states at all.

I suppose it was Galaxian which necessitated the development of the modern NPC cycle as we know it today.

I just took some time out to play the game, and my, it is sophisticated! The game uses three graphics layers, one for the background (which creates the illusion of vertical scrolling by moving blinking stars from top to bottom), one for the sprites, and one for the stats. The explosion animations are complex and plainly scripted. Doing some checking but this may well have been the first game to use NPCs as we know them.

[Mattias Gustavsson]

[RampantCoyote]

You are welcome! I love the subject, as I pretty much started out in the golden age of Asteroids, Pac-Man, Space Invaders, Wizardry, Ultima, and the rest. I remember when Galaga was the big new thing. :)

Oh, I also strongly recommend (on the RPG side of things) Matt Barton's EXCELLENT three-part series at GamaSutra:

History of Computer Role-Playing Games, Part 1: The Early Years

History of Computer Role-Playing Games, Part 2: The Golden Age

The History of Computer Role-Playing Games, Part 3: The Platinum and Modern Ages

He also published a book on the subject that I need to strongly hint to my wife would make an excellent birthday present...

Dungeons and Desktops: The History of Computer Role-Playing Games

For what it's worth, germane (maybe) to this thread - he wrote several other articles about the "History of..." various important games and platforms in the industry...

GamaSutra Articles by Matt Barton

Okay, done. Sorry about hijacking your thread, there, LG. I'll stay out of it now...
_________________
Tales of the Rampant Coyote - Old-School Game Developer talks Indie Games, RPGs, and the Games Biz

[tcaudilllg]

No need. That's the purpose of the thread, to get a real sense of game design's history. I'm glad you posted those links, because I don't think I had seen them. It is so much more difficult to stay abreast of internet developments than print. How exactly do you stay on top of things, RC?

Edit: nevermind. I forgot about that thing called RSS. Never have yet got into it.

[RampantCoyote]

I do try and track a lot of feeds - but the rest comes from digging and networking.
_________________
Tales of the Rampant Coyote - Old-School Game Developer talks Indie Games, RPGs, and the Games Biz

[tcaudilllg]

I was going to review the early RPGs before moving into the 80s era. I can't seem to get hold of a video showing the early RPGs in action, so I don't really know what they did have and what they didn't. Apparently the gist was to recreate D&D on a mainframe... they seem to be kinda obsessed over that, and I get the impression that at least part of the CRPG industry is oriented around satisfying folks who would like to participate in a real D&D game but are too schizotypal to do so. I don't think that's what motivated the creator's of the original games though; no, I think it was a sense of the historic which led them to put all those hours in, coupled with a compensatory sense of boredom and the knowledge that this invention would alleviate it. (which does admittedly lead back to schizotypy).

But it does seem like they had dungeons, though you could only see one room at a time and there were no sprites, only static premade graphics. They definitely had item systems, and apparently, even shops and exp. They used level tables and item lists. Back then nobody had apparently thought of hashes (or they were simply too inefficient), and as such arrays were necessary for the item tables. Most likely the item name and the item's logical description were wholly disconnected; the game probably did nothing more than overwrite the current item's onscreen text with the new item's. The item names themselves were string constants (obviously) and the items points on a number line probably extending from 0-255 (the range of an unsigned char). Having read about the internals of console RPGs, this practice seems to have held up even to this day. There was absolutely no scripting -- every item was hard-coded and intentioned, probably with a fairly large switch statement. Each item went into a list of preallocated slots, each of which was most likely an element of an "item slots" array or inventory. All the variables which mattered to the player were shown onscreen and updated in real time using "bleeding edge" software design that required the programmer to be exceedingly careful with the length of item names, lest they accidentally overwrite another part of the display. The "interface matter" has become a wicked problem that plagues us still.

Rogue was apparently the first game to use moving symbols. I don't think I could ever really get into that game... something about using letters for enemies doesn't appeal to me. Neither did it to Richard Garriot, apparently, who designed the first graphical RPG, Akalabeth. The interface (for Akalabeth) was text based... not into that. What is worth mentioning is how either of these games managed their graphics, particularly given that Zelda is, if not a direct descendent of Rogue (the missing link appears to be either Dragon Slayer or Hydlide), certainly an improvement upon the original algorithm.

In Rogue, there is no collision detection, only potential and determinants for its exercise. Adjacent characters can act against each other. The game also apparently used a vision cone, although I'm not sure if that was a later innovation or an original feature. Enemies moved only when the player moved, and when they became adjacent to the player could attack the next time the player took their turn. This functionality was accomplished with a simple adjacency test, testing whether the player's coordinates were +1 or -1 for the enemy's. Then game is not real time and as such, does not use a game loop. An input loop is used which tests for each possible key press, and depending on if the player performs a "time advancing" action runs through each of the enemies on the board and allows them to act depending on their proximity to the player. If they are next to the player, they attack. If they are away from the player, then they may attack if they have line of sight with the player and a missile weapon (or long-range spell), or else move in the player's direction. I can't tell if they have line of sight or not.

Rogue was the first game to permit interaction with game objects, and the first game to offer a simulated world for the player to interact in. It used the first tile map, which was represented by a two dimensional matrix of numbers. When the player tried to move their character, the attempted location was calculated and looked up in the 2-D array matrix. The number at that position was then passed to a switch statement which could evaluate it and perform the associated tasks. This might mean inhibiting the player's movement, in the case of one of the wall characters, or inserting an item represented by the tile in the character's inventory. (and subsequently replacing the item symbol with a floor symbol). The player's (adjacent) combat is accomplished by checking the location of every enemy for its presence on the point next to the player in the direction of the strike. If there is an enemy on that square, the relevant calculations are made and damage dealt (or not). In the case of a ranged attack, the adjacent attack algorithm is repeated for each point in the direction of the attack until an enemy is found to be on the square, or the point is found to be a wall.

The inventory system is uncomplicated: there is a hard-coded slot for every item type, and an associated variable for the quantity of that item possessed. When equipping an item as a weapon or armor, the number for the item selected is checked against a list of numbers whose associated items can be equipped in that spot. If it's on the list, it's a go. If not, it's a fail.

If I'm wrong about anything, please point it out.

[tcaudilllg]

From Rogue, RPGs went in two directions, the Rogue-clone route and the arcade-Rogue fusion route. The fusion route was made possible by faster processors, which enabled the invention of the game loop as an advancement over the input wait loop. The fusion paradigm allowed enemies to move independently of the player (this was impractical on early machines due to the lack of speed). This was the invention of the action RPG. The Rogue-clone route remained in force, although the basic algorithm (compute the enemy's moves after the player decides theirs) is still used in tactical RPGs, particularly Shining Force and Tactics Ogre. There were three major innovations in that vein, the overworld map, the party system, and the use of multiple action turns. The overworld map appears to have been invented by Richard Garriot for use in Akalabeth. It is complicated in that it is a completely different mode of play from the tactical map used by Rogue. The tactical map, in particular, has to be eliminated entirely -- it effectively hands over control to a completely different loop. However, the loop is similar: it allows player movement and the ability to trigger events that end the loop. The entire system has the following structure:

• A loop with two conditions, "town" and "overworld".
  
• When the town condition is true, enter the tactics loop.
  
• Load tactical map and actors (player characters and NPCs)
  
• When the player exits the town,
  - unset the town condition
  - set the overworld conditon
  - destroy the tactical map and all actors
  - exit the tactics loop
  
• With the overworld condition set, enter the overworld loop.
  
• Load overworld map
  
• When the player moves onto a space with a town,
  - unset the overworld condition
  - set the town condition
  - exit the overworld loop
  

Ultima I does not use a true overworld map at all, but instead uses a massive tactical map. Interesting that the Japanese made more use of Garriot's idea than Garriot himself.

[tcaudilllg]

Akalabeth used an overworld system and a tactical exploration system. Like Rogue, the tactical system used a random dungeon generator. The tactical system was innovative, though, in that it used a 3D first-person display.

The 3D dungeon system is nothing but the Rogue engine with a 3D mask. The logic is completely Rogue; however the presentation of the game world is different. The player's "perspective" is generated by first creating rules by which to find the player's "looking" direction. After assessing the direction, the first two rows of three points in that direction are used to select from a list of pre-generated images to show the player.