have you ever used recursion on the NES?

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems.

Moderator: Moderators

User avatar
gravelstudios
Posts: 89
Joined: Mon Mar 13, 2017 5:21 pm
Contact:

have you ever used recursion on the NES?

Post by gravelstudios » Mon Mar 04, 2019 6:53 am

Just curious. I was thinking about this. Are there really any problems in NES programming that would be solved better through recursion than some other means? I got really into SNES SimCity for a while and I read a post on another blog/forum once (I forget where) about how power propagates out from power plants. something like that might be a good use for it, but I don't know how the NES version does it. It feels like the NES stack isn't really big enough to do anything with recursion that a loop couldn't do with less overhead. So how about it? Have you used recursion on the NES?

User avatar
pubby
Posts: 558
Joined: Thu Mar 31, 2016 11:15 am

Re: have you ever used recursion on the NES?

Post by pubby » Mon Mar 04, 2019 7:03 am

Recursion is rare because of how awkward it is to store values in the stack and how awkward it is to have nested data structures.

I've used it a few times though. Last time I did was for a byte-pair decompression subroutine, which is an inherently recursive algorithm.

User avatar
rainwarrior
Posts: 8000
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: have you ever used recursion on the NES?

Post by rainwarrior » Mon Mar 04, 2019 7:10 am

Not very often.

I think I used one instance of recursion in Lizard, where you could stack blocks on top of each other. Moving the bottom block in a stack could shift blocks on top of it recursively. Source code here. Despite implementing this, though, I don't think I ever put more than two blocks in a room you could reach.

Visual demonstration. If you have the game (or its demo), you can enter the password 16472, then hold A + Select before pressing Up to enter the password door. That will take you to this test room.

User avatar
slembcke
Posts: 171
Joined: Fri Nov 24, 2017 2:40 pm
Location: Minnesota

Re: have you ever used recursion on the NES?

Post by slembcke » Mon Mar 04, 2019 8:24 am

I use recursion all the time (not on the NES), it's easy to make compact and reasonably efficient code that handles an unknown number of items. Non-tail recursive stuff is always going to be faster with an iterative version though, and knowing that the code won't have a stack overflow is nice to know. So far my NES games have always dealt with a known (and small) number of items, so I haven't even thought of making recursive versions of anything.

Not quite the same thing, but I do use tail recursion in my C code quite a bit for implementing things like game states.

Something like this:

Code: Select all

typedef struct GameState {};

// Code structure is similar to main_loop()
GameState game_loop(void);

GameState main_menu(void){
	ppu_off();
	// load scene data
	ppu_on();
	
	while(true){
		if(start button is pressed) return game_loop();
		
		// Draw stuff or handle other input
		
		wait_nmi();
	}
}
The assembly generated by this is nice and predictable. I've used similar constructs in my coroutine code.

User avatar
never-obsolete
Posts: 399
Joined: Wed Sep 07, 2005 9:55 am
Location: Phoenix, AZ
Contact:

Re: have you ever used recursion on the NES?

Post by never-obsolete » Mon Mar 04, 2019 12:08 pm

A* maybe...without looking at the code, I think I looped over a FIFO queue.

Building metatiles out of metatiles out of metatiles could be a candidate, but you usually have a fixed depth so not much to gain there.
. That's just like, your opinion, man .

User avatar
Bregalad
Posts: 8008
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland

Re: have you ever used recursion on the NES?

Post by Bregalad » Mon Mar 04, 2019 1:19 pm

To be honnest, no, there's no way I've ever used recursion on the NES. I've however have a subroutine call it's own end, but only once, not in a recursive fashion.

Basically it's jut an optimiation, when a "ACBC" pattern happens in code, instead of :

Code: Select all

   A
   jsr C
   B
   jmp C

It's :
   A
   jsr C
   B
C:
  <code>
  rts

User avatar
koitsu
Posts: 4218
Joined: Sun Sep 19, 2004 9:28 pm
Location: A world gone mad

Re: have you ever used recursion on the NES?

Post by koitsu » Mon Mar 04, 2019 1:30 pm

I'm not sure this is really a "NES thing" but moreso a general "have you ever used recursion on the 6502, and if so, to solve what thing?" question. But an excellent question BTW.

I remember using recursion in a couple ways in a IIGS demo I worked on, but I can't remember exactly for what. I just remember it being a lot easier to do/deal with than the alternate, in whatever circumstance it was.

I expect Garth on the forum might have some some good use-case examples of where recursion comes in handy.

nocash
Posts: 1318
Joined: Fri Feb 24, 2012 12:09 pm
Contact:

Re: have you ever used recursion on the NES?

Post by nocash » Mon Mar 04, 2019 8:26 pm

Hey, all. Please stop bragging about your own projects! It would be much more appropriate to talk about Magic Floor, that is my project, and its "compute number of possible moves" function would be actually faster with recursive calls (for each newly entered map cell), that could work fine on a Z80 with about 1K free RAM, but on a NES it would require using a separate 16bit memory pointer (instead of the 8bit stack pointer), and an Atari 2600 wouldn't have enough RAM for that purpose at all. Instead of recursive calls, the game is flagging map cells as "needed to be processed later", the drawback is that the later processing requires to search through all map cells to find out which ones were flagged that way.
Other than that, in PC code, I am using recursive calls maybe once in 2-3 years, for things like crawling sub directories inside of sub directories, when creating a filesystem tree. Or in compression functions.
Last edited by nocash on Mon Mar 04, 2019 8:35 pm, edited 1 time in total.

User avatar
rainwarrior
Posts: 8000
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: have you ever used recursion on the NES?

Post by rainwarrior » Mon Mar 04, 2019 8:32 pm

Implementing a flood fill for a drawing program I think of as the canonical case for recursion. For every point you need to branch out to its 4 neighbours. Kind of a perfect fit for the need.

It's also maybe a nice learning case study, because while it's extremely simple to implement as recursion, on a lot of platforms you'll probably crash the stack because of how many pixels are involved once your flood area is large enough. (Unfortunately might not give such a teaching experience on modern platforms with giant stacks.)

So... flood fill was also the thing that taught me how to build your own stack and do it without subroutine recursion. A good learning experience about how and why and when that's important to do as well.

tepples
Posts: 22278
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: have you ever used recursion on the NES?

Post by tepples » Mon Mar 04, 2019 10:07 pm

nocash wrote:Magic Floor [...] is flagging map cells as "needed to be processed later", the drawback is that the later processing requires to search through all map cells to find out which ones were flagged that way.
My Game Boy port of Magic Floor likewise marks cells as ready for evaluation and makes multiple passes until evaluation settles, as does indoor/outdoor testing in RHDE. In both, it's subjectively "fast enough".

Ultimately, what makes "ready for evaluation"-based flood fill algorithms slow is that they behave like bubble sort: they propagate reachability slowly in the direction opposite that of scanning the array. For example, scanning from top to bottom makes propagation up take longer. Filling to the left or right is iterative (and thus fast). When it marks cells in the previous and next rows as ready for evaluation, the cells in the next row are quickly taken care of during the same scan. These cells in the next row are analogous to "rabbits" in bubble sort. But cells in the previous row have to wait for the next scan, like "turtles" in bubble sort.

Two extensions to bubble sort address the problem of turtles. The first is to make evaluation passes in opposite directions each time, producing cocktail sort. Applying bidirectional scanning to flood fill is also straightforward. Another is to compare cells several spaces apart, as in comb sort. This doesn't extend so easily to flood fill in the typical 4-direction or 8-direction connectedness definitions.

Cocktail sort wouldn't help Magic Floor though. In my tests, bidirectional scanning doesn't appreciably reduce the number of passes when determining reachability in this case. I implemented bidirectional reachability search in the Python prototype of floor generation. It didn't have noticeable effect on number of passes needed to solve reachability on smaller floors (2x8, 4x4, 6x4), where most floors are solved in 4 or 5 passes. For larger floors (6x6 or 8x6), the solution reduced from 5-7 passes to 4-6. I assume the improvement is so modest because the game defines connectedness to allow 2-cell moves, which reduces turtles anyway by allowing "ready for evaluation" state to propagate up two rows in one pass.

Puyo Puyo determines matches by a connected region of at least four cells of the same color. After a line clear and explosion, Bombliss breaks the remaining mass of blocks into connected regions and applies gravity to those regions that have not yet landed. Both are on Famicom and Game Boy. Rampart (Konami) for Famicom and Rampart (Jaleco) for NES use 8-way connectivity for indoor/outdoor testing. Has anyone debugged into those to see whether they use recursion?

Oziphantom
Posts: 1074
Joined: Tue Feb 07, 2017 2:03 am

Re: have you ever used recursion on the NES?

Post by Oziphantom » Mon Mar 04, 2019 10:22 pm

the SNES's stack is no better then the NES ;)

Most things that are small enough to be used recursively are also small enough to convert so they don't use recursion. I think I've used it a few times though, its kind of painful to use though.

Garth
Posts: 206
Joined: Wed Nov 30, 2016 4:45 pm
Location: Southern California
Contact:

Re: have you ever used recursion on the NES?

Post by Garth » Mon Mar 04, 2019 10:37 pm

koitsu wrote:I'm not sure this is really a "NES thing" but moreso a general "have you ever used recursion on the 6502, and if so, to solve what thing?" question. But an excellent question BTW.

I remember using recursion in a couple ways in a IIGS demo I worked on, but I can't remember exactly for what. I just remember it being a lot easier to do/deal with than the alternate, in whatever circumstance it was.

I expect Garth on the forum might have some some good use-case examples of where recursion comes in handy.
I have hardly used it. Section 15 of my 6502 stacks treatise is about recursion though, at http://wilsonminesco.com/stacks/recurse.html . It naturally follows section 14 which is about local variables and environments.
http://WilsonMinesCo.com/ lots of 6502 resources

User avatar
Bregalad
Posts: 8008
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland

Re: have you ever used recursion on the NES?

Post by Bregalad » Tue Mar 05, 2019 12:53 am

Garth wrote: I have hardly used it. Section 15 of my 6502 stacks treatise is about recursion though, at http://wilsonminesco.com/stacks/recurse.html . It naturally follows section 14 which is about local variables and environments.
What is funny about recursion is that the examples to show how amazing this is are always awful. Usually the fibonacci series is used as an example but theres a zillion reasons this is awful :
  • Fibonnaci series has no practical uses, especially not in game development.
  • Fibonnaci series would be better implemented as a lookup table, at least up to ~50 numbers.
  • Even if you want to actually compute the Fibonacci series, recursion is less intuitive than loop
  • And if you manage to do it with recursion, it's actually exponentially slower as more numbers goes up, and will soon bloat your stack and processing power, as each additional number doubles the amount of calculations. This is not the case with a loop.
So this idea of using recursion to compute fibonacci series is a very good example what NOT to do.

Factorial is less an awful idea because the time spent is still linear. But still it's less intuitive than loop, and is better done with a lookup table. It's only application is in probabilities calculations which often aren't done on computers, especially not video games,

User avatar
Quietust
Posts: 1684
Joined: Sun Sep 19, 2004 10:59 pm
Contact:

Re: have you ever used recursion on the NES?

Post by Quietust » Tue Mar 05, 2019 4:57 am

nocash wrote:Hey, all. Please stop bragging about your own projects! It would be much more appropriate to talk about Magic Floor, that is my project, ...
I get the feeling you're trying to make a statement about something, but it's just a little bit too subtle...
Quietust, QMT Productions
P.S. If you don't get this note, let me know and I'll write you another.

User avatar
BillyWM
Posts: 9
Joined: Sat Dec 27, 2014 10:05 am
Location: Sacramento, CA
Contact:

Re: have you ever used recursion on the NES?

Post by BillyWM » Tue Mar 05, 2019 11:23 am

Some notes accompanying the leaked prototype and the efforts to make a commented disassembly claim it's done recursively:
MISC#9. The power generated by all power stations equals (COAL*700)+(NUCLEAR*2000) points. This power "distributed" between every single powerable tiles including the Powers station and electric wires. Every single powerable tile (all tiles of buildings, electric wires) consume 1 point. Due to optimization rather than bug the recursive algorithm can overpower some tiles inside the buildings or at intersection of wires up to 3 times. So the same amount of buildings may consume more or less power just because of placement and grouping of power wires. Average consumption for 3x3 building is 13, not 9. The original Micropolis core has exactly the same algorithm.
It's also possible to do power-propagation style rules iteratively across simulation ticks with a cellular automaton.

Post Reply