*SOLVED* Stuck in recursion hell!

Newbie & Debugging Questions
#1

Hi All!

This one has been foxing me for a while now - I’m convinced I’m missing something obvious.

I’ve written a little ‘electric wiring’ game (not realistic, I should point out!) where you can drop down a ‘power generation’ node, and connect wires to it on a grid.

This is a good example of how it’s laid out:

The power generation node in the top-left corner of the grid can supply power for up to 6 cells distance. You can see that the green lines represent wires that are ‘on’, and the pink ones represent wires that are ‘off’ (sorry, you need mega-vision to see these at the moment).

To calculate the wires that get affected by this, I use the following code, seeding the function with the location of the power source first (0,0 - in my example image):



   // ~ ----- The bit that sets up the wire map and prepares it for being 'solved' ----- ~

   // global props
   private final int MAX_POWER_TRAVEL = 6;
   private int CURRENT_RECURSION_OPS = 0;

   // turn 'off' all wiring prior to solving the current power distribution
   turnOffAllWires();

   // solve the wiring map
   for (PowerSource p : powerSources)
   {
       CURRENT_RECURSION_OPS = 0;
       calcNextWireNode(p.x, p.y, 0);
       System.out.println("Calculated power source in " + CURRENT_RECURSION_OPS + " operations");
   }


   // ~ ----- Elsewhere in the class, this method provides the recursive means to solve the wiring map ----- ~

	private void calcNextWireNode(int x, int y, int depth)
	{
		// if we've hit our maximum recursion (distance) depth, finish here
		if (depth >= MAX_POWER_TRAVEL) return;
		
		// if we're not in bounds, finish here
		if (!tileInBounds(x, y)) return;
		
		// if this tile isn't a valid wire type, finish here
		if (wireMap[x][y] == WireType.NONE) return;
		
		// don't process this wire if it's already on
		if (isWireOn(wireMap[x][y])) return;
		
		// turn 'on' this wire
		wireMap[x][y] = onlineWireForType(wireMap[x][y]);
		
		// increase the depth
		depth++;
		
		CURRENT_RECURSION_OPS++;    // how many (global) recursion calls we've made to solve the wiring map
		
		// test the four spaces around this tile
		calcNextWireNode(x-1, y, depth);
		calcNextWireNode(x+1, y, depth);
		calcNextWireNode(x, y-1, depth);
		calcNextWireNode(x, y+1, depth);
	}

This code works nicely enough. Especially so since it doesn’t break or endlessly loop when the wiring is set up like this:

In the image above, there are loops - but in the recursion, a node checks to see if itself is ‘on’, and skips it.

However, when adding another power source to the network, it doesn’t distribute properly - it should exhibit the same spread amount as the original power source. This is what it looks like in its ‘broken’ state:

You can see that the second power source doesn’t spread for all 6 cells. It SHOULD look like this:

I know what’s happening here - the second lot of recursion to happen (the second power source) looks at the cells around it which are already ‘on’, thus killing the recursion.

How do I get around this pickle of an issue? I need something robust enough to work with (potentially) tens, if not hundreds of power sources. I know that recursion, done right, can be very powerful - but this ‘flood fill’ method I’ve adapted seems troublesome!

Any advice would be greatly appreciated.

Thanks guys n’ gals!

#2

Decouple ‘on’ state from ‘traced’ state.

Reset traced state prior to flood filling from each node.

#3

I’d suggest you move to using a queue and perform a breadth-first fill.

Tail recursion is just depth-first traversal where you use the program stack instead of explicitly using a stack object. This makes the code more succinct and maps nicely to recurrence relations, but doesn’t buy you much else.

For the breadth-first fill, start by putting all sources in the queue then just dequeue and process one by one as you are now.

Edit: you can do fancier stuff with non-tail recursion, but that doesn’t really apply here

#4

http://www.java-gaming.org/topics/stuck-in-recursion-hell/34162/msg/322076/view.html#msg322076

Cas :stuck_out_tongue:

#5

Cute.

#6

Hah, thanks! I was almost tempted to click on that link!

I solved this by taking the concept first suggested to me. I added a ‘current source’ counter, which increments with every power source that’s generated. Then, inside each Wire object I have a reference ID that’s initially set to -1 when the map calculation begins.

Every time the recursion ‘looks’ at a wire - if its reference ID doesn’t match the current source counter then it processes immediately. It then has its ID set to that very same source counter value.

If, however, a recursion looks at a wire whose reference ID is the same as the current source counter, it ignores it (since it’s already been looked-at, or ‘traced’, to use the nomenclature of the offered solution).

This has the benefit of being compatible with the original code (with some modifications) but also solves the problem about each power source not travelling the correct distance.

Thanks a bunch for your help, guys, it’s been invaluable!

#7

That was actually the solution I had in mind - but I wanted to keep it simple. Great that you figured it out too.

#8

Of course, and thank you!

For those that are interested, this is the code that solved the issue:


	private void calcNextWireNode(int x, int y, int depth)
	{
		// if we've hit our maximum recursion (distance) depth, finish here
		if (depth >= MAX_GENERATOR_TRAVEL) return;
		
		// if we're not in bounds, finish here
		if (!tileInBounds(x, y)) return;
		
		// if this tile isn't a valid wire type, finish here
		if (wireMap[x][y].type == WireType.NONE) return;
		
		// don't process this wire if it's already on
		if (wireMap[x][y].on) return;
		
		// don't process this if we're on the same generator ID
		if (wireMap[x][y].generatorID == CURRENT_GENERATOR) return;
		
		wireMap[x][y].generatorID = CURRENT_GENERATOR;
		
		// turn 'on' this wire if it's in range of the generator
		wireMap[x][y].type = onlineWireForType(wireMap[x][y].type);
		
		// increase the depth
		depth++;
		
		CURRENT_GENERATOR_OPS++;
		
		// test the four spaces around this tile
		calcNextWireNode(x-1, y, depth);
		calcNextWireNode(x+1, y, depth);
		calcNextWireNode(x, y-1, depth);
		calcNextWireNode(x, y+1, depth);
	}

Now that the wire map is made up of wire objects - I can start doing some cool things now, like having each wire store a power value which can be ‘boosted’ with other generators nearby, thereby allowing me to calculate a power ‘fall off’ value, rather than a simple cut off.

Thanks for everyone’s input! I’m glad this is no longer a sticking point!

#9

Line 12 and 13 shouldn’t be there, right? As that was the cause of the original problem.

Also, the ‘on’ field can be removed, as this can be implicitly determined with [icode]wireMap[x][y].generatorID != 0[/icode] if you clear the IDs each tick, like you clear the ‘on’ property currently.

Last but not least: it’s preferable to pass the generatorID as a parameter, removing the presumably static CURRENT_GENERATOR field.


public void turnOffAllWires() {
   for(...)
      wireMap[x][y].lastGenID = 0;
}

public boolean isWireOn(int x, int y) {
   return wireMap[x][y].lastGenID != 0;
}

public void tick() {
   this.turnOffAllWires();

   for(Generator gen: generators)
      this.calcNextWireNode(gen.x, gen.y, gen.reach, gen.id);

   for(...)
      if(wireMap[x][y].type != NONE)
         wireMap[x][y].type = isWireOn(x,y) ? ON : OFF;
   
}

@@ private void calcNextWireNode(int x, int y, int remaining, int genID)
   {
      // if we've hit our maximum recursion (distance) depth, finish here

@@      if (remaining == 0) return;
      
      // if we're not in bounds, finish here
      if (!tileInBounds(x, y)) return;
      
      // if this tile isn't a valid wire type, finish here
      if (wireMap[x][y].type == WireType.NONE) return;
      
      // don't process this if we're on the same generator ID
      if (wireMap[x][y].lastGenID == genID) return;      
      wireMap[x][y].lastGenID = genID;

      CURRENT_GENERATOR_OPS++;
      
      // test the four spaces around this tile
      calcNextWireNode(x-1, y, remaining-1, genID);
      calcNextWireNode(x+1, y, remaining-1, genID);
      calcNextWireNode(x, y-1, remaining-1, genID);
      calcNextWireNode(x, y+1, remaining-1, genID);
   }
#10

Thanks for your reply!

I’m guessing you were referring to this line of code:

This was in to handle cases where the wire-trace loops back over itself (if someone essentially draws a wire in a ‘box’ shape). However, with the new code that prevents a wire from being re-traced when its generator ID matches the current process ID this is now redundant - I didn’t spot it, so thanks for pointing that out!