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!