Atari in the News - Cool BBC Article!

[hizzy]

Sorry if this was already posted, but here is a cool story about some scientists studying the game Entombed. 

 

Here is an excerpt:

 

You and your team of archaeologists have fallen into the ‘catacombs of the zombies’.” A miserable situation, to be sure. But this was the chilling trial that faced players of Entombed, an Atari 2600 game, according to the instruction manual.

The catacombs were an unforgiving place. A downward-scrolling, two-dimensional maze that players had to navigate expertly in order to evade the “clammy, deadly grip” of their zombie foes. An archaeologist’s nightmare.

Released in 1982, Entombed was far from a best-seller and today it’s largely forgotten. But recently, a computer scientist and a digital archaeologist decided to pull apart the game’s source code to investigate how it was made.

 

There was always something intriguing about Entombed, recalls John Aycock at the University of Calgary, in Alberta, Canada. And because it had fallen into obscurity, it hadn’t been pulled apart and analysed in depth before – one the main reasons Aycock and his co-author Tara Copplestone at the University of York, UK, were drawn to Entombed as a subject to study over the other 500 games made for the Atari 2600 console.

 

 

Link to the full article:

 

http://www.bbc.com/future/story/20190919-the-maze-puzzle-hidden-within-an-early-video-game

Edited September 23, 2019 by hizzy

[Big Player]

That is an interesting article.  The big part is that these two researchers are baffled by the logic behind Entombed's maze generating algorithm.

 

Have any of the homebrew authors or anyone else who disassembles 2600 games taken a look at Entombed's code?  If so, is it doing anything special when it generates the maze?

 

 

[Scotterpop]

I also saw that article and it’s a fascinating read. I clicked on that article the moment I saw the image of that woody VCS! It really does make you respect the ingenuity of those early game programmers having to work within the confines of such primitive hardware. 

[hizzy]

I would love to see Andrew Davies or Thomas Jentzsch chime in. I'm sure the programmers on the forums would be able to "crack" this mystery!

[Jstick]

From the article, it would seem that this is more of a general algorithm problem then one of programming or VCS peculiarities.  Basically trying to extract a logical mathematical pattern from a fixed data table.

[+Andrew Davie]

Heh... "and intoxicant-fueled design"

[+Andrew Davie]

11 hours ago, hizzy said:

I would love to see Andrew Davies or Thomas Jentzsch chime in. I'm sure the programmers on the forums would be able to "crack" this mystery!

 

Well, I was having a think about it.  Think about generating a maze "as you go... left to right, top to bottom".  Basically what you'd like to have is some context about the current position. Do you make it black, or white?  So the algorithm has info about 5 surrounding squares. Those two to the immediate left on the current line, and the three above the current position. From those you form a 5-bit index into the "magical mystery table".  That table gives you the next white/black (or random).  Now consider if your index was zero - that is, NO walls anywhere. You definitely don't want to generate another blank because that's all the maze would be - blank. So I predict that entry 0 is a 1.  Likewise for entry 31 - it will be blank because you don't want a completely solid maze.  Now the rest of it is basically "instructions" on what to do in certain situations. When there are clear blocky corners, you'd want to put in a blank. When there are clear blanky bits, perhaps you'd want to put in a solid. I suspect this is just sort of trial-and-error hardwired, with 1's and 0's put in for situations where you need to make a deifinite decision - and where it really doesn't matter - then put in a random block/blank.  I may be missing something but I don't think it's much more than what I have described.  Basically a sort of state machine that "responds" to particular patterns by generating a block, a blank, or a random block/blank.  The programmer would have fine-tuned it by generating mazes and where the result became too "blanky" then he would adjust one of those 0's to a 1. And vice-versa. And you'd try to have as many randoms in there as you could fit and still generate good mazes. By analysing the generated maze and looking at those 5 context squares around any position, you could decide if the table entry was doing the right thing or not, and adjust it. With not too many iterations, you'd have the result used in the cartridge. That's my take on it.

 

[Thomas Jentzsch]

Interesting challenge.

 

But are the mazes really that good? There are quite a lot of dead ends which you cannot avoid.

[+Andrew Davie]

59 minutes ago, Thomas Jentzsch said:

Interesting challenge.

 

But are the mazes really that good? There are quite a lot of dead ends which you cannot avoid.

 

Apparently you place a "bridge" that bridges the wall to an open passage when you have a dead end.

 

[Thomas Jentzsch]

After briefly looking into the code, I am not 100% sure that they did understand it correctly.

 

However, the code is really not easy to understand, so I could be wrong too.

Edited September 25, 2019 by Thomas Jentzsch

[+Psionic]

Emtombed was developed by Western Technologies.  Steve Sidley programmed the game but the finished product apparently used a simplified version of a more complex maze algorithm that had been developed by Paul Allen Newell (programmer of Towering Inferno).  Newell had assistance from Duncan Muirhead, a fellow WT programmer and math grad student from UCLA who I'm told spoke with a thick Scottish accent, smoked like a chimney, and would code in long marathon sessions before disappearing for days at a time.  Muirhead wasn't around WT very long (most employees weren't) and seems to have left to pursue an interest in sailing vessels.  He'd probably be the one to talk to but he may be difficult to get a hold of.

Relevant reading for those interested...

http://www.ataricompendium.com/archives/interviews/paul_allen_newell/interview_paul_allen_newell.html

https://prism.ucalgary.ca/bitstream/handle/1880/51724/2016-1090-09.pdf

[DanBoris]

This sort of reminds me of the algorithm the Telengard uses to generate it's maze. It uses a algorithm based on your current location in the maze and three hard coded constants. They must have had to hand tune those constants until they got acceptable mazes. You can read the details here:

 

http://atarihq.com/danb/Telengard.shtml

[Tensor]

On 9/25/2019 at 7:51 AM, Thomas Jentzsch said:

After briefly looking into the code, I am not 100% sure that they did understand it correctly.

 

However, the code is really not easy to understand, so I could be wrong too.

Where did you find the code? I'd love to look through it.

[gtoal]

It's no great secret - was written about here some time ago: http://www.digitpress.com/library/interviews/interview_paul_allen_newell.html

 

 

G

 

[gtoal]

On 9/24/2019 at 8:49 PM, Andrew Davie said:

 

Well, I was having a think about it.  Think about generating a maze "as you go... left to right, top to bottom".

Pretty sure one of the schoolkids on Scratch has posted an algorithm like that.  It'll be in this collection of maze generators:

 

  https://scratch.mit.edu/studios/403013/

 

Look for "Ellers algorithm" http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm

 

Here's another one... http://people.cs.ksu.edu/~ashley78/wiki.ashleycoleman.me/index.php/Sidewinder_Maze.html

 

(there are others that work similarly, can't remember the names right now.  You can read about maze algorithms in general at https://www.astrolog.org/labyrnth/algrithm.htm )

 

Just keep scrolling down, the page refreshes with more when you hit the bottom. 

(All those Scratch programs have source available, just select it and click "See inside")

Edited September 29, 2019 by gtoal
added link

[Thomas Jentzsch]

19 minutes ago, Tensor said:

Where did you find the code? I'd love to look through it.

I simply used Stella's savedis command.

[gtoal]

27 minutes ago, Tensor said:

Where did you find the code? I'd love to look through it.

https://arxiv.org/ftp/arxiv/papers/1811/1811.02035.pdf

 

also a rewrite in C is linked to at 

 

[ChildOfCv]

It also reminds me of how Battletech:  Crescent Hawk's Inception generated its terrain.  It begins with a grid about 1/256 the size of the total map, then uses a generated table of random numbers to fill in inbetween terrain values, and finally uses a fixed table of terrain tiles to generate each 8x8 square (which itself is doubled each direction, and also modified for elevation).  This allows it to procedurally generate any part of the terrain as you move over it, though in their case they want to create the same overall map.  You'll notice those common patterns in the final product, but the overall terrain does have a more naturally-evolved feel.

[Mr SQL]

I just had a chance to read the article with the maze generation algorithm explained as Drunken Monkey Programming Kung-Fu ...

 

 

Modern computer scientist often posture and stike a pose like Madonna when they don't understand, inviting non-programmers to play a game of Emperors new clothes because they understand even less:

Anybody can be a programmer today writing kiddy script to call libraries like the computer scientist in the article identifying drunken monkey kung-fu coding as the transcendential path to amazing code. 

 

Researcher should stop vogueing long enough to turn down the pomposity and take a retro programming course; many are available online on AtariAge. Ian Bogost, a professor at Georgetown and the author of Racing the Beam has an excellent study curriculum that could bring the scientist up to speed if they have the potential.

 

Not everybody does and that's why there are only a few of us today writing low level drivers, kernels and database cores professionally.