Procedural level generation on the NES?

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Procedural level generation on the NES?

Post by FrankenGraphics »

I can't think of a single game from the commercial NES era that did this. It might be that its occurrence (in roguelikes) was pretty underground up until Diablo, which is post-nes. But i don't know of a single homebrew that does this either. Is there something that's technically difficult with having a, say, schmup, generate a level procedurally on the NES? Or is it just simply because it's generally hard to device procedural level generation that can maintain the players' interest for more than a couple of minutes (in other words, more of a design question rather than a technical one)?
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: Procedural level generation on the NES?

Post by Sumez »

I'm sure you can find quite a few NES games that did it, but it's really hard to think of any. :) It's probably a lot more common in games with more abstract concepts of "stages".

I'm pretty sure Elite has procedurally generated areas due to the massive scope of the game?
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Procedural level generation on the NES?

Post by tepples »

Procedural level generation tends to need more RAM than hardcoded levels, and RAM is one thing that the NES doesn't have much of. The exception is one-way scrolling like that of Super Mario Bros., where the procedural level generator could conceivably replace the level decompression code. But even in that case, balancing procedural levels to ensure even difficulty progression was not trivial.

One pre-NES example: River Raid for Atari 2600 is procedural with a fixed seed as a compression technique.
Pokun
Posts: 2675
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Re: Procedural level generation on the NES?

Post by Pokun »

Closest thing I could think of is those endless Megaman hacks. They are based on the endless mode of Megaman 9 and 10 where you play short stages in random order endlessly. Each stage is designed by hand but they are thrown at you randomly and endlessly.
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Procedural level generation on the NES?

Post by FrankenGraphics »

tepples wrote:RAM
Right! That would make a design that allowed for backtracking (ie diablo) extra hard to fit without cutting a lot of corners. A ratchet scroller like gradius or smb1 might be easier, and definitely something like Pokun described.

There's also the method used in the "hidden rooms" of Axiom verge where a subset of predefined structures (like in Metroid) are thrown at the screen based on a random seed. Or at least that's what it seems to be. Keeping such segments short enough might work.

Turning this into more of a hardware query:
For a hypothetical homebrew that needs to retain work RAM data (like a procedurally generated retrackable world/dungeon), even between sessions, FeRAM / FRAM seems like an option, though probably with the need of a proper 5v-3.3v converter.

Fujitsu FeRAM chips aren't that expensive at proper sizes.

https://www.semiconductorstore.com/page ... l_Interest

Would there be problems using such a chip?
lidnariq
Posts: 11430
Joined: Sun Apr 13, 2008 11:12 am

Re: Procedural level generation on the NES?

Post by lidnariq »

SPI and/or I2C memory is kind of annoying from the NES's point of view; either you need some external hardware to automatically handle the serial-to-and-fro-parallel conversion, or it's quite slow.

Flash might be preferable?
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Procedural level generation on the NES?

Post by FrankenGraphics »

So one would need to add in the cost of two shift registers, basically?
Flash might be preferable?
You might expect the flashROM to be worn down a lot quicker if it's constantly poked and prodded by procedural generation.
lidnariq
Posts: 11430
Joined: Sun Apr 13, 2008 11:12 am

Re: Procedural level generation on the NES?

Post by lidnariq »

Yeah, it's approximately a SIPO and a PISO shift register, but ideally you'd just stuff it in a CPLD or something to handle all the rest of the support.


For flash, reads are free, you can only write 0s, blocks can be converted from 0 to 1 only (large number of bits) at a time, and each block is limited to ~10k total erase cycles before the data won't be retained for the specified amount of time. (But it will still retain data after that: just for less than the specified amount of time)

For FeRAM all reads are also writes, and each cell has a finite (but huge, usually) number of total writes.


I would naively assume that a procedurally generated world wouldn't overwrite the same memory over and over? Because then you couldn't backtrack...
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Procedural level generation on the NES?

Post by FrankenGraphics »

I guess it depends a lot on the design of a game. If the world is highly manipulable (think sim city, minecraft, scorched earth, worms, etc, simulations in general and roguelike/simulation crossovers), you'd overwrite a persistent world.

For something that's an endless gauntlet, like a racer or schmup, you'd be constantly overwriting it, but wouldn't need persistence (or as much RAM), so non-volatile work ram isn't called for, really..

There are parallel interfaced FeRAM:s, though they seem to be in the 3-4 dollar range each rather than 1-2. I haven't done a thorough comparison, but here's an example:
https://www.semiconductorstore.com/cart ... duct=48940

edit: In contrast to FlashROM, it is also faster; much like conventional RAM.
(But it will still retain data after that: just for less than the specified amount of time)
Oh... this is a new piece of info for me. So it's not that it goes sour directly, but rather becomes volatile after some time of non-use once it has passed its durability?


===
A (debatably) good thing is that FeRAM can essentially replace both ROM and RAM on a single board, just as long as you're careful not to overwrite essential code and data.
lidnariq
Posts: 11430
Joined: Sun Apr 13, 2008 11:12 am

Re: Procedural level generation on the NES?

Post by lidnariq »

FrankenGraphics wrote:I guess it depends a lot on the design of a game. If the world is highly manipulable (think sim city, minecraft, scorched earth, worms, etc, simulations in general and roguelike/simulation crossovers), you'd overwrite a persistent world.
Oh, fair enough. Yeah, that's definitely a RAM / FeRAM kind of situation.
Oh... this is a new piece of info for me. So it's not that it goes sour directly, but rather becomes volatile after some time of non-use once it has passed its durability?
Yeah. Each time the block is erased (by intentionally causing the floating gates to leak), the floating gates become a little more leaky. The guaranteed durability just means that the floating gates are guaranteed to not become more leaky than however many femtocoloumbs per year after however many erasures.
A (debatably) good thing is that FeRAM can essentially replace both ROM and RAM on a single board, just as long as you're careful not to overwrite essential code and data.
That's roughly the same reason that Memblers used with GTROM... don't need to provide PRG RAM for saves if using flash.
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Procedural level generation on the NES?

Post by FrankenGraphics »

Ok, so here's an attempt compiling what FeRAM might be good for on a technical level:

-Speed: Close to conventional RAM speeds; overwrites in a single cycle*. Suitable for frequent and quick access.
-Durability/data retention: While there's an upper limit (typically 10^12 times per byte ), it goes many times beyond FlashROM and EEPROM.
-Interface: Comes as parallel, though serial seems to be cheaper in general. The parallel ones typically have a SRAM like interface built in.
-Price range: 1-5 dollars for reasonable sizes in the 64kB-512kB range
-Suitable as RAM? For most applications; it seems so yes.
-Suitable as ROM? yes No, if accessed frequently, as reads will cause wear just like rewrites.**
-Volatile? no.
-Battery requirement? no
-Unpowered data retention: typically estimated to last over 200 years below +35C, 95 years at +55C, or 10 years at a temperature of +85C.
-Power consumption: low; needs no "charge pump", and no constant current.
-technology: CMOS (warning: typically max 3.6v)
-availability: a few major companies like fujitsu and texas instruments manufacture FeRAM/FRAM; aswell as some relatively smaller companies.

Anything missing?

On a game/application design level:
-Good for any sort of world/data that is more or less manipulable, for example a level made of blocks the player can move, destroy and/or create
-Simulation-like parameters like "population happiness in this city block", "temperature", "minerals left" etc.
-Persistent enemy, npc, treasure statuses etc.
-Modifiable locations of ID:d items/objects
-Fog of war/field of exploration/field of view and other manipulable masks/maps
-any sort of complex save file
-generated, retrackable worlds/levels

*FeRAM doesn't need an erase cycle; nor separate read/write cycles. It operates by a rewrite cycle solely. This allows for very fast rates, especially with a Parallel interface. An SPI type FeRAM is a double bottle-neck, so avoid it.

**See tepples' subsequent post for details
Last edited by FrankenGraphics on Fri Nov 17, 2017 9:28 am, edited 4 times in total.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Procedural level generation on the NES?

Post by tepples »

FrankenGraphics wrote:
lidnariq wrote:For FeRAM all reads are also writes, and each cell has a finite (but huge, usually) number of total writes.
Ok, so here's an attempt compiling what FeRAM might be good for on a technical level:

[...]
-Durability/data retention: While there's an upper limit (typically 10^12 times per byte ), it goes many times beyond FlashROM and EEPROM.
[...]
-Suitable as ROM? yes
Because reads count as writes, I don't see how something with a limit of a trillion reads is "Suitable as ROM".

Assume for a moment that a game spends an average of 973,000 cycles per second in a wait for vblank or wait for sprite 0 loop, and the loop is 7 cycles long. This means each byte of this loop is accessed 139,000 times every second. With a limit of a trillion access per byte, that's 7.2 million seconds or 2000 hours of power on time until the FeRAM cells holding this loop are no longer warranted. It's even worse for an all-in-NMI design like that of Super Mario Bros., whose loop is only 3 bytes long.

Emulators would have to warn for too many reads from the same ROM location in one second, and games would have to copy tight loops into the 2K RAM or unroll them.
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Procedural level generation on the NES?

Post by FrankenGraphics »

Thanks, i'll revise the post. The waiting spinlock could be copied to and ran from internal/separate RAM, though? EDIT: I somehow missed you wrote that more or less in your last sentence.
User avatar
Alp
Posts: 223
Joined: Mon Oct 06, 2014 12:37 am

Re: Procedural level generation on the NES?

Post by Alp »

tepples wrote:Procedural level generation tends to need more RAM than hardcoded levels, and RAM is one thing that the NES doesn't have much of. The exception is one-way scrolling like that of Super Mario Bros., where the procedural level generator could conceivably replace the level decompression code. But even in that case, balancing procedural levels to ensure even difficulty progression was not trivial.

One pre-NES example: River Raid for Atari 2600 is procedural with a fixed seed as a compression technique.
Not necessarily, clever data formatting is always king.

Last year, I had prototyped a randomly generated Zelda 1 clone on the NES, and the dungeons only used 64 bytes of RAM, generated from a seed. The Overworlds were a slightly different case, using about double that, to accommodate the extra level of detail.

The project was shelved, simply because I ran out of design ideas for monsters! :P

Coincidentally, my Super Mario Bros. clone "Cotton & Candy" actually features procedural level generation as an easter egg. If you walk through the top of a fake wall in level 1-2, you'll unlock a secret stage on the Overworld named "Minus World" :wink:

My levels have full left/right scrolling though, none of that one-way scrolling crap.
User avatar
thefox
Posts: 3134
Joined: Mon Jan 03, 2005 10:36 am
Location: 🇫🇮
Contact:

Re: Procedural level generation on the NES?

Post by thefox »

This isn't exactly the kind of procedural generation that you're looking for (because it doesn't affect gameplay), but some time I happened to notice that Noah's Ark (E) uses randomization to generate some of its levels' visual content:
noahs-ark-ground.gif
noahs-ark-ground.gif (11.34 KiB) Viewed 10129 times
In the GIF is the nametable at the start of the level on two separate occasions. (I seem to recall this also affecting grass, but I couldn't reproduce that easily right now.)

SMB3 does something similar when generating the background layer, although that also doesn't affect gameplay in any way.
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi
Post Reply