Researchers Find Mystery Hidden In Early 80's Atari Game (bbc.com) 169
wired_parrot shares a report from the BBC: 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. An early maze-navigating game, Entombed intrigued the researchers for how early programmers solved the problem of drawing a solvable maze that is drawn procedurally. But they got more than they bargained for: they found a mystery bit of code they couldn't explain (Link to full paper). The fundamental logic that determines how the maze is drawn is locked in a table of possible values written in the games code. However, it seems the logic behind the table has been lost forever.
Lost forever (Score:2)
However, it seems the logic behind the table has been lost forever
The game was made all the way back in 1982, so by now the developer has been dead and gone for decades and we can't possibly ever, like, just ask him.
Re: Lost forever (Score:5, Informative)
According to TFA they asked but got no response.
People who were involved in the production of the game shared that the programmer was hardly sober, and came up with the maze algorithm while whacked on booze.
Itâ(TM)s likely he doesnâ(TM)t know anyway. That would be another level of archeology there...
Re: Lost forever (Score:5, Insightful)
Re: Lost forever (Score:4, Interesting)
I don't remember code I wrote 10 minutes ago. How the hell is this guy going to remember code he wrote in 1982?
Well I have printouts, and the assembly code was commented. [Not the game in question].
The printout was necessary for debugging bug reports back in the day.
Re: Lost forever (Score:5, Interesting)
I remember code I wrote in 1982.
I was recently contacted by some emulator writers who said the sound in one of my games didn't work on their emulator and I knew right away what the problem was (a thing with interrupt mode 2 on the Z80 and their assumptions about what bits would be on the data bus).
Re: (Score:2)
Pretty cool! What games did you write? I am assuming Spectrum games?
Re: (Score:3)
I worked at Gremlin Graphics from 1983-1989, pretty much all their Z80 games in that era would have had some of my code in them, even if it was just the music player.
Re: (Score:2)
But did you tell them.......?
Re: Lost forever (Score:5, Funny)
I still remember "Dark Mode" for C64...
Poke 53280,0
Poke 53281,0
Re: (Score:2)
My god, I did not even think that other might have even thought about recalling such a Poke
thank you for the laughter
Re: Lost forever (Score:4, Informative)
You forgot Poke 646, 1
Unless you are a mutant and like cyan on black.
Re: Lost forever (Score:4, Interesting)
I still remember the instructions I had to toggle into the switches of my PDP-8/E to get it boot from the RK05 hard disk!
Address Data Function
0030 6743 DLAG - Disk Load and Go (reads to current address initialized at 0 and post-increment)
0031 5031 JMP 0030 - Endless loop (gets overwritten by data from disk and when it overwrites 0030, it gets replaced by a JMP 0000
so it goes back and executes the bootloader now sitting at 0000-0030. That then proceeds to load and execute the 2nd stage bootloader.
That shit is from 1972! :P
Re: (Score:3)
Hmm. The RK05 was too easy; it had 1-cycle DMA, initialized for bootstrapping. For the even earlier DF32 (a 32k(x12) hard disk), which had 3-cycle DMA, so it relied upon memory locations 7750 and 7751 to hold DMA current state, the bootstrap sequence was:
7750 + ADDR LOAD
6603 + DEP (DF32 read, and DF32 negative read count, big enough to be later overwritten by boot code)
7577 + DEP (elaborate OPR that decodes as a NOP on PDP-8/I; DF32 starting address of transfer, pre-incremented before use)
5352 + DEP (JMP 7
Re: Lost forever (Score:5, Interesting)
I remember code I wrote in 1982.
Agreed. And I have a hard time accepting that they didn't ask Sidley about a bug partially because of "the unreliability of memory regarding long-past technical minutia". IMO, that's the very thing coders, at least good ones, WILL remember. Every detail of it. In fact, everything else is what will be forgotten and the ONLY thing that will be remembered are those technical bits that were actually interesting to solve.
Re: (Score:2)
Forgive me for this comment :
6x9=42
I hope you are laughing as deeply and as joyfully.
Re: (Score:2)
Re: (Score:2)
101010
Ahhh crap, onepoint beat me to it.
- Yo Grark
Re: (Score:2)
I remember code I wrote in 1982.
Agreed. And I have a hard time accepting that they didn't ask Sidley about a bug partially because of "the unreliability of memory regarding long-past technical minutia". IMO, that's the very thing coders, at least good ones, WILL remember. Every detail of it. In fact, everything else is what will be forgotten and the ONLY thing that will be remembered are those technical bits that were actually interesting to solve.
I got the impression they didn't ask him out of respect. They allude to the possibility that he didn't even know about it, considering it would have been easy to fix. Seems like he was intoxicated on the fond memories of being a bad ass early programmer. "Hey how about that bug we found" may have turned an enthusiatic interview participant into a cagey one.
Re: (Score:3)
I remember code I wrote in 1982.
I was recently contacted by some emulator writers who said the sound in one of my games didn't work on their emulator and I knew right away what the problem was (a thing with interrupt mode 2 on the Z80 and their assumptions about what bits would be on the data bus).
I doubt you are joking, but rather I would predict that this was the solution of a particularly memorable problem you encountered. Now I'm wondering if you remember the problem more than the solution?
It was a quirk of the Z80. Their emulator was a port of a Sinclair Spectrum emulator. When an interrupt arrives at a Z80 in mode 2 the lower 8 bits on the data bus can select an interrupt vector. On a Sinclair Spectrum it happens to always be 0x20, so that's where their emulator was looking for the interrupt vector. On other computers it can be other values (including completely random data, in which case your interrupt routine has to be placed at an address where hi/lo bytes are the same, eg. 0x1010, and y
Re: Lost forever (Score:4, Interesting)
Well I have printouts
Print outs wouldn't help in this case. The programmer solved a algebraic problem on paper and placed the solutions into a table. The program consulted the table for building the levels, this saved the console from having to perform the calculations since a human had already solved all the permutations of the equation that were going to be used for the game. The question being asked is how did the programmer solve for those equations? What logic was being used to solve them? Of which, we'd need to see those sheets of paper he wrote down the solution on.
Re: (Score:2)
Being the output posted in a table. Why wouldn’t they fudge the results to give the desired output.
Re: (Score:3)
That's basically what's being explained in the paper. There is reference to a PRNG maze generator that was researched but it seems the implementation in this game is buggy and it seems intentional but they don't know why.
Re: (Score:2)
That's basically what's being explained in the paper. There is reference to a PRNG maze generator that was researched but it seems the implementation in this game is buggy and it seems intentional but they don't know why.
PRNG pseudo-random number generator , that produced values that were used by the maze generator.
Re: (Score:2)
Well I have printouts
Print outs wouldn't help in this case. The programmer solved a algebraic problem on paper and placed the solutions into a table.
You left off "and the assembly code was commented." I would have described the algebraic problem in the comments.
Re: Lost forever (Score:4, Interesting)
That's sad, I re-wrote graphic routines back in the day to make the games I bought faster,
and I think my favorite coding past time was the AD&D manual that I made for my c-64. it
needed 4 floppy disks, it was HUGE!!!
If that Table design was something that the coder gave himself a pat of the back, I bet he
can even find which note book he wrote in big letters SOLUTION. buy that man a drink and
ask for stories if he is still alive, I bet the code will come back.
And I kinda recall all the gosub's and goto's and optimization I had to do, just to speed the
machine to walking pace. you could do a lot with 42K of space, 64K ram but the overhead was
graphic's and some other stuff... can't recall to give you an accurate answer.
When I tell modern code jockeys that I paid more for my compiler ($1300) than for the brand
new c-64 ( $895 ), I get laughs, then it's even funnier when I tell them it had a dongle.
I really did like some of those c-64 games.
Re: (Score:3)
To be fair you can still very easily pay far more for the development environment you wish to use than for the hardware on which you're going to run it.
Re: (Score:2)
Well I got to ask, being that you ( like me ) have been around for awhile and survived the lies
we have seen ( amazing that we have not blown the world up yet too ).
If you were 52, and had zero code skill set's, where would you start start today as a code jock.
I would not mind getting back into using my head, but I don't even know where the first step
is.
Re: (Score:3)
erm. This may sound silly but start with computer games.
Something like the ones by Zachtronics, which give you a very structured and objective oriented introduction to many programming concepts while also entertaining you.
Should you find they entice you to dig further then the current favourites du jour that are easily accessible are things like Python or (dare I say) Javascript. The real trick is finding a problem to solve; unfocused learning isn't really going to get you very far.
Re: (Score:2)
The porn was pretty sweet for the time too.
Re: (Score:2)
Porn was different, it was Ascii art LOL
and big boob's were 5 out of 7 times natural
Re: (Score:2)
The guy was also asked the day after he wrote it. Didn't remember then either. I've definitely argued for an extended period that code I wrote more than a year ago was written by somebody else.
Re: (Score:2)
I do the same thing, I go back and look at some of my code and i'm like "who the hell wrote this?"
Re: (Score:2)
That would be another level of archeology there...
https://www.youtube.com/watch?... [youtube.com]
Re: (Score:2)
it's just a "if I do it this way it works and with this table it works".
why don't they uh, find out how it works and could the table be anything else and the rest of the code to still work to produce a maze..
Or inspiration from paper maze / mosaic pattern (Score:4, Interesting)
it's just a "if I do it this way it works and with this table it works".
That's a possibility: it had randomly sprung into the mind of a stoner programmer while high, which got fine tuned until it works.
(It's possible, there's a very rough pattern if you eyeball the table printout in the PDF, 1 and 0 output seem more or less grouped, basically splitting the 32 entry in group, with 1 when there aren't many in the lookup key and 0 vice-versa, but a little bit more scrambled to seem random and calls to random generator every now and then).
The "post-processing" step mentioned in the PDF certainly seems like fine tuning added later upon the base algorithm.
Another possibility, is that the algorithm author found some paper labyrinth he liked, or drew an nice one on graph paper (or even a funny pattern in the mosaic tile of a bathroom inspired him. Given that the author is reportedly a stoner and given the overall patterns in the PDF's test runs of the generation algorithm, it could be that one too).
Then the author vague looked a a couple of subset of the labyrinth here and there to come up with the table. If the author looked at least at 3~4 similar subsets per pattern, he could also built a lookup table:
- Whenever top and left looks like this and that in the "nice example" there's a wall next: put 1 in the table
- Whenever top and left look like that different pattern in the "nice example" there's a hole: put 0 in the table
- Other top and left pattern that doesn't seem to be followed by anything in particular : put a "call the random generator" in the table.
Bingo a nice table is built.
Re: (Score:3)
Take the table, and resort it by columns c d and e (this idea also sort of works looking at "a b c", but it's more intuitive with "c d e", which I bet is the way the programmer originally conceived of it). It really seems to be mostly 8 groups. If you diagram out all 8 scenarios of what sits in those, its actually a fairly intuitive algorithm that minimizes open rooms (and the reverse...huge blocks o
The algorithm appears not to be logical (Score:4, Informative)
First off I'll note that there were eneless maze generators well before 1977. I wrote one myself for generating meters long mazes on line printers using less than 1K of memory and it was guaranteed to be solvable, have a unique path and be random, no matter how long the page went on. So I can tell you definitively it's possible to do this by only storing information about the last line and the present line.
Now this maze generator does not produce mazes that are solvable! Both examples shown lack a path from top to bottom. You have to break a new wall.
Of course one might want that as a feature of the game to require wall busting. But if one were going to do that then I suspect you'd want the algorithm to generate mazes for which any impass could be overcome by breaking one wall. That is if you reach a dead end then breaking a single wall tile should always connect to an open space on the otherside. Otherwise you coul;d get to a situation where you are always drilling through walls.
Looking at the table I can see by construction that this algorithm can create dead ends that require more than one all break to escape.
Thus I don't see any logic to this algorithm. I think it's goal was simply to avoid overly dense mazes with a fast algorithm. The matrix tends to favor giving an escape path to the right whenever the path up is blocked. So it will favor making longer runs over impenetrable chess boards. but nothing assures the maze is solvable or requires only one break to get out of a dead end.
Almost: 2 rules generate matrix (Score:2)
1. If not A=B=1 then: (i.e. not the left hand edge)
1. if there are two instances of touching 00 or touching 11 then:
output random
Re: (Score:3, Funny)
Re:Lost forever (Score:5, Informative)
and we can't possibly ever, like, just ask him.
Did you look at the article or paper? They asked one of the developers and he hadn't been able to figure it out...
During their research, Aycock and Copplestone were able to interview one of the people involved in the gameâ(TM)s production, Steve Sidley.
He too remembered being confused by the table at the time. âoeI couldnâ(TM)t unscramble it,â he told the researchers. And he claimed it had been the work of a programmer who developed it while not entirely sober: âoeHe told me it came upon him when he was drunk and whacked out of his brain.â Aycock tried to contact the programmer in question but got no response.
Maybe no-one ever really understood the logic of the algorithm. But there it is, in a 1982 Atari game, posing a seemingly unanswerable question.
Re: (Score:2)
One of the developers is not the developer in question. You fail.
Re:Lost forever (Score:4, Informative)
This highlight from the paper is particularly telling:
The basic maze generating routine had been partially written by a stoner
who had left. I contacted him to try and understand what the maze generating
algorithm did. He told me it came upon him when he was drunk and whacked
out of his brain, he coded it up in assembly overnight before he passed out, but
now could not for the life of him remember how the algorithm worked
Re:Lost forever (Score:5, Funny)
The basic maze generating routine had been partially written by a stoner
who had left. I contacted him to try and understand what the maze generating
algorithm did. He told me it came upon him when he was drunk and whacked
out of his brain, he coded it up in assembly overnight before he passed out, but
now could not for the life of him remember how the algorithm worked
Ah yes. I assume this was what happened when designing memory allocation in Chrome.
Re: (Score:2)
Ah yes. I assume this was what happened when designing memory allocation in Chrome.
Oh that's an easy problem that even 1st semester programmers can solve -- just keep calling malloc().
Re: (Score:2)
The basic maze generating routine had been partially written by a stoner
who had left. I contacted him to try and understand what the maze generating
algorithm did. He told me it came upon him when he was drunk and whacked
out of his brain, he coded it up in assembly overnight before he passed out, but
now could not for the life of him remember how the algorithm worked
Ah yes. I assume this was what happened when designing memory allocation in Chrome.
And everyone of the 5 auto-generated IPC layers every single function call has to pass though. No one dares touch any of them, as no one even knows why they are there.
Re: (Score:2)
Re: (Score:3)
I have had some of my best ideas in my most indescribable states. I've built some really nice things and left them in the garage to surprise future me on my next visit. My buddy's grandad suggested that with anything you wanted to be good at, you needed to practice drunk as well to demonstrate true mastery. I'm not the wreck I once was, but I haven't had any great ideas lately, either...
Re: (Score:2)
This happens to be very true for lot's of people who enjoy tinkering.
and the heydays of advertising happen to be the same way, Martini lunches.
I might add, Humphrey Bogart, who is my personal hero is also a
happy drunk that understood when to work and when to play.
Re: (Score:2)
Re: (Score:2)
I have had some of my best ideas in my most indescribable states. I've built some really nice things and left them in the garage to surprise future me on my next visit. My buddy's grandad suggested that with anything you wanted to be good at, you needed to practice drunk as well to demonstrate true mastery. I'm not the wreck I once was, but I haven't had any great ideas lately, either...
This reminds me of my brother in law telling me about the mystery gifts he would sometimes get from Amazon. I was curious as I use Amazon a lot yet had never been sent a mystery gift.
He went on to explain that he would get black out drunk and place orders on Amazon, when the package would arrive it was always a surprise opening the box.
Re: (Score:2)
Then the solution is simple [youtu.be]. Get the man drunk and stoned again and ask him how he solved the problem. I read about this technique in the journal "Maxim" under the title "E = MC Hammered."
Re: (Score:2)
I write absolute crud for code when not sober. I have a hard time believing that an intricate algorithm was created and implemented bug-free during an all-night bender.
It's more believable that the idea for the algorithm came to him while under the influence of something or another, and then was implemented during some following days of sobriety. In the intervening years, additional abuse to the brain in the form of self-medication has rendered the details forgotten. Complex code when drunk and high and
Re: (Score:3)
Oh yeah, let's ask a dead developer a question. Genius.
Re: (Score:2)
However, it seems the logic behind the table has been lost forever
The game was made all the way back in 1982, so by now the developer has been dead and gone for decades and we can't possibly ever, like, just ask him.
Well maybe if the alcoholism persisted but in general 1982 game developers are probably in their 50s these day. Mostly alive and well.
Re: (Score:2)
No 60's I'm 52 and was in high school back then, to get a job at one of the big firms, you "had to have" that college degree, making it at least 1986 grad on the very low end ( 56 years of age )
And back then, you had some boss that was some fucking idiot, would not let you code and be like "Pinball Wizard"
Something which makes me very proud of my observation of modern day youth and risk takers who focus on being the very best in the skill set of whatever code they program. I love how you all fight for the c
Maybe in his head (Score:5, Insightful)
I canâ(TM)t see any reference to the size of the table but I sounds a bit to me like something you could do buy drawing some examples on paper, build the solution table from that and then make some test code to try out many iterations.
But it is a great example of the tricks you had to use one the old machines. I can imagine it is an lost art these days with everything make used game engines.
32 entry: could be reference based too (Score:5, Interesting)
I can {'} t see any reference to the size of the table
From the PDF: 32 entries.
Generating a new wall depend on the two wall on the left and the three walls above. That gives 5 binary (wall / hole) inputs.
The table outputs either "wall", "hole" or "go call the random number generator".
but I sounds a bit to me like something you could do buy drawing some examples on paper, build the solution table from that and then make some test code to try out many iterations.
Yup my hypothesis to. The guy could certainly have found a reference labyrinth he like, draw one himself on grid paper, or found a fascinating pattern on a ceramic tile wall in the bathroom (he was supposedly a stoner, after all).
Look up several places to find 5-bits patterns, tally what usually happens, try it and see the result.
Also, the fact that there's a post-processing step mentioned in the PDF speaks in favor of later iterations improvements.
Re:Maybe in his head (Score:4, Insightful)
Remember the very first rule in The Elements of Programming Style [1978]:
You had to be clever to get things done back in the day when your computer might only have 32k of memory, but it was all too easy for cleverness to become an end in itself.
Re: (Score:3)
clever != too clever
Unfortunately sometimes the way to determine the two is to compare the results and long-term maintainability of the code. Other times it's a bit more obvious, like if a programmer exploits a known bug in hardware to achieve a result, a bug that may be removed by a manufacturer on subsequent products or whole revisions.
Mystery ? (Score:5, Informative)
Re:Mystery ? (Score:4, Interesting)
That was my thought. In addition they mention that if you change some of the values the maze generation algorithm does not work very well. So the rather obvious conclusion is that the table was generated through a process of trial and error and when the developer hit on something that worked it was set in stone.
Re:Mystery ? (Score:5, Interesting)
If the table allows you procedurally to create a random maze, using severely constrained storage and computing power, with only a single correct solution, this is a difficult problem, certainly if the maze is of arbitrary size. All the algorithms I am aware of are computationally intensive when generating large mazes. Based on a cursory glance at the paper, they seem to be saying that Entombed facilitates an algorithm (albeit only for a two-dimensional maze) that avoids the need for backtracking behaviour. This could be of significant theoretical interest.
Re: (Score:2)
Mazes in Entombed require the player to blow up wall cells every once in a while. So it's not quite as sophisticated as Eller's algorithm, which creates a perfect maze by partitioning columns of the infinitely tall maze into connected sets, but it's suitable for the gameplay concept the developers wanted to do.
Re: (Score:2)
A question was raised, the wrong person was asked, and now you have your 800 words by deadline. Thus is normal capitalism, inventing a non story for a paycheck.
Re: (Score:3)
Looking at the table in the paper, it's fairly simple in concept - lots of empty space in those areas - stick a wall in. Lots of walls, stick a space in. In the middle it's trial and error (look at generated mazes, can you solve it? No - more white space, Yes - is it too easy? More walls, and then for interest you have some random choices to make the mazes more natural, and special collectables to destroy or build walls in your path (because the algorithm isn't perfect, and the game needs something to make it more than just a maze solver). I can see a stoned developer in the zone knocking that out in a couple of hours before crashing out.
Three hours. When they get up to flip the Black Sabbath LP they will get distracted by something.
Ob XKCD (Score:5, Insightful)
Re: (Score:2)
Business: Drools Rule Engine.
Re: (Score:3)
Heh. A friend of mine was asked to solve a path routing problem at work, to create some software to make the routes the drivers followed better. After some study he realized it was a rehash of the Seven Bridges of Koenigsberg [wikipedia.org] and he had to justify to them why he as a simple computer programmer wasn't going to be solving that one for them.
Re: (Score:2)
How is that different than the Travelling salesman problem [wikipedia.org]? Surprisingly I've never seen the Seven Bridges scenario.
visit all the cities vs visit all routes inbetween (Score:3)
Really? This is rather well-known. The Travelling Salesman requires that you hit all the vertices (destinations). The Seven Bridges problem requires that you traverse all the edges (the routes between the destinations).
Intrigued researchers (Score:5, Interesting)
"intrigued the researchers for how early programmers solved the problem of drawing a solvable maze that is drawn procedurally."
These days most younger coders seem to be intrigued about how to write code that doesn't require a dozen different frameworks, half of system memory and 99% CPU just to write Hello World.
Someone wrote Chess in 1K (yes ONE K) for the ZX81 back in the 80s. Granted it wasn't a complete version but it played a basic game.
Re:Intrigued researchers (Score:5, Insightful)
"intrigued the researchers for how early programmers solved the problem of drawing a solvable maze that is drawn procedurally."
These days most younger coders seem to be intrigued about how to write code that doesn't require a dozen different frameworks, half of system memory and 99% CPU just to write Hello World.
Someone wrote Chess in 1K (yes ONE K) for the ZX81 back in the 80s. Granted it wasn't a complete version but it played a basic game.
a) Not every 1980s "programmer" was capable of coding chess in 1k. Many 1980s programmers insisted in trying to use bloated high level languages like C (idiots).
b) Today's demo scene has regular competitions for small code and they code things that most 1980s programmers couldn't (today's kids have the entire Internet for reference, back then things like data compression were only mythical, third-hand rumors).
c) There's tons of web sites about retro-programming on Atari VCSs, etc. (arguably the smallest, tightest, gaming platform ever). I know people who are actively coding games for the C64.
d) The fact that you're reading an "archeology" article today shows that some people still care.
Re: (Score:2)
Sure, I'm not denying that there are some expert younger coders around. But in general I find today that the majority of them are a bit lost without all the helper libraries and frameworks that do stuff they should be able to do themselves.
The difference between now and back then is the bar is much lower now to be able to get into programming. Back then if you couldn't figure out how to write certain algorithms , eg various sorting types, linked lists etc then you'd have never got in the door and you'd have
Re: (Score:3)
I feel like the bar was *lower* in the 1980s, not higher.
We got an Apple ][ in 1982 and by 1984 I was writing programs that mixed Applesoft and 6502 assembler, all with just the Apple manuals, a 6502 assembly book, an "Inside Applesoft" kind of book that basically let you use Applesoft like an API by detailing it's machine language interfaces, and some kind of book about inside Apple DOS that gave you similar access to DOS subroutines.
I could focus on the technical without fucking around about input and out
Re: (Score:3)
It's one of the reason Arduino programming is so popular.
Re:Intrigued researchers (Score:5, Funny)
If you think event driven programming is harder than writing 6502 assembler then you're a very strange person.
Re: (Score:2)
It kind of depended on what you were doing. At a certain level of functionality/complexity, sure 6502 assembler written by hand as hex opcodes is hard, using a reasonable assembler made it easier, with easier being relative to how sophisticated the assembler was in terms of using mnemonics and labels.
Plus, there's the idea that on the Apple ][ there was a pretty low upper limit as to how complex your program was going to be. I found it possible to write hybrid programs, with assembler used for some kinds
Re: (Score:2)
once you know the 6502,
then I believe you have the right to carry a towel and a shirt numbered 6*9=42
something might be harder in life, but a towel, a cup of coffee and a good sandwich might just solve most issues.
It's just different (Score:2)
great (Score:2)
an up goes the price of another old game.
I knew someone who developed a similar algorithm (Score:5, Interesting)
For a dungeon type game. I forget many of the specifics, but we all used to play an online dungeon game called Milieu. The code for it was considered a big deal and everyone seemed to want to code up a similar game.
Supposedly a big pain was creating dungeon maps with variation but without having to generate the map and store it for each level, but have each new dungeon game have a unique map.
This guy Don Sidoroff came up with some kind of semi-random map generator that could take some kind of seed value and generate the same map for a level based on the seed. The seeds for each level were saved with the game, and the seeds for a particular game were more randomly (or less pseudo-randomly) generated, so that the odds of any game having a level identical to some other game were basically non-existent over any normal level of play.
It's probably considered a not interesting problem in today's computing environment, but it seemed like a big deal then to have a procedurally generated map that could easily be generated on the fly without having to dedicate a lot of memory to holding the map.
Re: (Score:2)
Some of the biggest arguments at that time 1980-1985 were in random number generation and the maze was a good test bed as any.
let me explain. The human mind is amazing at discovering patterns, in groups it's even more prevalent in finding solutions, and a great maze that had little to no pattern was an advantage to the game designer. I don't know if it happens in modern day gaming but I do recall when I was with friends someone would say " stay to the left, I think there is a door on the next step" and sure
Re: (Score:2)
Now they call it "rogue-like"
Wow (Score:2)
Re: (Score:2)
FYI - Interview with one of the developers (Score:5, Informative)
this reminds me of (Score:2)
A story about a black jack game written in the late 70's. The powers that be wanted it to be a little easier to win. The original coder quit and they asked his replacement to 'fix' it. After a while he discovered the code as one of its steps used a bug in the CPU to advance the code. He told them he couldn't fix it and they were not surprised.
Re:this reminds me of (Score:5, Informative)
https://en.wikipedia.org/wiki/... [wikipedia.org]
Obvious pun (Score:2)
Funky Town (Score:2)
Mel ~ The Story Of A Real Programmer (Score:3)
Real Programmers write in FORTRAN. Maybe they do now, in this decadent era of Lite beer, hand calculators, and ``user-friendly'' software but back in the Good Old Days, when the term ``software'' sounded funny and Real Computers were made out of drums and vacuum tubes, Real Programmers wrote in machine code. Not FORTRAN. Not RATFOR. Not, even, assembly language. Machine Code. Raw, unadorned, inscrutable hexadecimal numbers. Directly.
https://www.cs.utah.edu/~elb/f... [utah.edu]
Obligatory post.
Dung Bettles (Score:2)
Tl;dr version of the article (Score:3)
The game has you run "down" through a maze that scrolls upward, the maze is symmetrical consisting of rows of 16 blocks that can be either wall or free (and walls to both sides). The algorithm is tasked to provide the next bottom row consisting of 8 bits of information (mirrored to make 16).
For each block in the (left half of) new row the decision to make it free or wall is based on the two blocks left of it and the three blocks directly and diagonally above. These 5 bits point to the lookup table which decides if the block is free, wall, or decided by a random generator (for the first and last bock there are slight modifications introducing additional randomness).
The algorithm did not work perfectly, in the game "wall breakers" could be collected to open dead ends.
Two accounts (gained from interviews) about the origin of the maze algorithm are given:
Paul Allen Newell:
"Duncan and I went out for a beer and ended up coming up with this “problem” of wondering whether one could generate an endless maze that always had a solution’ and that ‘We worked out the algorithm and [...] I spent a weekend coding something up."
Steve Sidley (the programmer tasked with writing the game based on the algorithm):
"The basic maze generating routine had been partially written by a stoner who had left. I contacted him to try and understand what the maze generating algorithm did. He told me it came upon him when he was drunk and whacked out of his brain, he coded it up in assembly overnight before he passed out, but now could not for the life of him remember how the algorithm worked."
If CS researchers can't follow the algorithm... (Score:2)
It's a cellular automaton (Score:2)
The researchers understand how to execute the algorithm on generic hardware. However, the algorithm is largely driven by a one-dimensional cellular automaton, and they don't understand the principles underlying the construction of the CA's rule that cause it to generate a maze with under a certain fraction of walls needing to be blown up using explosives.
Reminds me of how Slashdot used to be (Score:2)
This article and the ensuing comments remind me of when I used to really enjoy lurking on Slashdot many years ago. We have some nerdy thing (an old, seldom referenced computer game), a problem, and some interesting thoughts on how the problem might be solved. There's even people discussing how they ran into similar problems on similar hardware and how they tackled them (or failed to tackle them). It would be nice to see more articles like this.
Re:comments (Score:5, Funny)
; tired of working on it. these values seem good
Re: (Score:2)
You assume that comments were even possible in these environments.
Re: (Score:2)
Re: (Score:2)