Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (806)
Games in Android Showcase (239)
games submitted by our members
Games in WIP (868)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  *SOLVED* Stuck in recursion hell!  (Read 9407 times)
0 Members and 1 Guest are viewing this topic.
Offline pixelprime

Junior Devvie


Medals: 3



« Posted 2014-08-27 20:33:02 »

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:

Click to Play


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):

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
   // ~ ----- 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:

Click to Play


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:

Click to Play


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

Click to Play


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!
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2014-08-27 20:44:25 »

Decouple 'on' state from 'traced' state.

Reset traced state prior to flood filling from each node.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline Jono
« Reply #2 - Posted 2014-08-28 07:36:36 »

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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

« JGO Spiffy Duke »


Medals: 1146
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #3 - Posted 2014-08-28 08:06:12 »

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


Cas Tongue

Offline Roquen

JGO Kernel


Medals: 518



« Reply #4 - Posted 2014-08-28 08:36:02 »

Cute.
Offline pixelprime

Junior Devvie


Medals: 3



« Reply #5 - Posted 2014-08-28 16:25:40 »

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!

Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2014-08-28 16:31:50 »

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline pixelprime

Junior Devvie


Medals: 3



« Reply #7 - Posted 2014-08-29 08:01:54 »

Of course, and thank you!

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

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
   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!
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2014-08-29 10:00:52 »

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
wireMap[x][y].generatorID != 0
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.


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
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);
   }

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline pixelprime

Junior Devvie


Medals: 3



« Reply #9 - Posted 2014-08-30 08:51:22 »

Thanks for your reply!

I'm guessing you were referring to this line of code:
Quote
// don't process this wire if it's already on
      if (wireMap
  • [y].on) return;
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!
Pages: [1]
  ignore  |  Print  
 
 

 
Riven (587 views)
2019-09-04 15:33:17

hadezbladez (5528 views)
2018-11-16 13:46:03

hadezbladez (2410 views)
2018-11-16 13:41:33

hadezbladez (5790 views)
2018-11-16 13:35:35

hadezbladez (1233 views)
2018-11-16 13:32:03

EgonOlsen (4669 views)
2018-06-10 19:43:48

EgonOlsen (5688 views)
2018-06-10 19:43:44

EgonOlsen (3205 views)
2018-06-10 19:43:20

DesertCoockie (4104 views)
2018-05-13 18:23:11

nelsongames (5125 views)
2018-04-24 18:15:36
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!