Game Programming: A Power Grid!

Sir Carcass

So I'm messing around with coding this little game and I'm looking for some input on how to tackle this problem.

The game features a city made up of blocks arranged in a 25 by 25 block grid (using a 2d array of a CityBlock class). Each block currently has a hasWire and a hasPower boolean member. The city contains a power plant (at grid locations 4,6 and 4,7, if it matters). My intention is if the player gets it up and running (post apocalyptic setting), they can wire power to different parts of the city.

I'm basically trying to figure out a decent way to simulate electricity traveling out from those 2 blocks, along wires if present, to whatever blocks end up being wired back to the power plant. It would also need to handle if a wire was cut. I have an ugly system currently that will at least handle blocks becoming powered (but doesn't handle the removal of power) that I can use if nothing else works, but I'd like this to look fancy.

About the only thing I can think of is some sort of node system with 8 pointers per node and just starting at the plant and following the nodes, but I'm not sure if that's even feasible. I'm not sure how to handle multiple connections to a block using that, at least offhand.

Any ideas?

Delzhand

I think you're in the wrong forum, but this sounds like an issue that can be solved with recursion.

start at power plant
Get all neighboring tiles.
for each neighboring tile, if the tile hasWire, set its hasPower value and get it's neighbors
for each neighboring tile [...]

I can probably come up with better pseudocode once I'm off work

Sir Carcass

oh shit, i thought I was in H/A.

Can a mod move this please?

:oops:

MentalExercise

Delzhand wrote: »

I think you're in the wrong forum, but this sounds like an issue that can be solved with recursion.

start at power plant
Get all neighboring tiles.
for each neighboring tile, if the tile hasWire, set its hasPower value and get it's neighbors
for each neighboring tile [...]

I can probably come up with better pseudocode once I'm off work

That's what I was thinking. If the city is set up with a set array you shouldn't even need pointers, the neighboring blocks have knowable addressess in the array.

Your function should take as arguments the address of the block you start with, and then you can just calculate the addresses of the adjacent blocks. The left block has the same row, but column - 1, top left block has row-1 column-1, right block has the same row but column+1, etc.
You'd just need a check to make sure you don't run off your grid.

setPower( blockColumn, blockRow )
{
if block ( hasWire ) set hasPower( true )
if block hasPower setPower( leftBlock ) setPower( topLeftBlock ) setPower( topBlock ) etc.
}

Then whenever a wire gets moved, cut, changed, whatever, you just rerun your little setPower function/object.

Malgaras

Pretty much what was already said. The only thing I would mention is to make sure to include checks for already visited blocks or something so you don't wind up with a stack overflow if the lines loop. Actually, on second thought, you need that anyways.

bowen

Yeah recursion is probably the key to this.

Sir Carcass

gespo89 wrote: »

Pretty much what was already said. The only thing I would mention is to make sure to include checks for already visited blocks or something so you don't wind up with a stack overflow if the lines loop. Actually, on second thought, you need that anyways.

What would be the best way to do this? Another array?

Malgaras

Sir Carcass wrote: »

gespo89 wrote: »

Pretty much what was already said. The only thing I would mention is to make sure to include checks for already visited blocks or something so you don't wind up with a stack overflow if the lines loop. Actually, on second thought, you need that anyways.

What would be the best way to do this? Another array?

Give me a minute and I will write up some code for you. I keep doing dumb stuff.

Delzhand

I assumed the check would be performed every update cycle, in which case all tiles would be set to hasPower = false at the start of the update

Malgaras

Delzhand wrote: »

I assumed the check would be performed every update cycle, in which case all tiles would be set to hasPower = false at the start of the update

Yeah, hence my edit. I realized I was being dumb. My bad.

Malgaras

Here is some java that does what you are looking for. It should be obvious enough to port to whatever (unless it's an android game?). Probably not what you are using but it's what I write fastest.

For purposes of pointing out the obvious blocks[][] is your array of CityBlock.

public void startPower(){
	//turn off all power
	for(int x = 0; x < blocks.length; x++){
		for(int y = 0; y < blocks[0].length; y++){
			blocks[x][y].setPower(false);
		}
	}
	
	//reset our visited squares
	boolean[][] visited = new boolean[blocks.length][blocks[0].length];
	for(int x = 0; x < blocks.length; x++){
		for(int y = 0; y < blocks[0].length; y++){
			visited[x][y] = false;
		}
	}
	
	//call once for each square of your power plant
	power(4, 6, visited);
	power(4, 7, visited);
}

private void power (int x, int y, boolean[][] visited){
	//if we already visited this square or are off the grid, just move on
	if(visited[x][y] || x < 0 || x >= blocks.length || y < 0 || y >= blocks[0].length){
		return;
	} else {
		//make sure to set visited to true before doing any recursive calls
		visited[x][y] = true;
		
		//if the square has wire, power it and attempt to power every adjacent square
		if(blocks[x][y].hasWire()){
			blocks[x][y].setPower(true);
			
			//you mentioned 8 pointers so I assume this is what you want
			power(x - 1, y - 1, visited);
			power(x, y - 1, visited);
			power(x + 1, y - 1, visited);
			power(x - 1, y, visited);
			power(x + 1, y, visited);
			power(x - 1, y + 1, visited);
			power(x, y + 1, visited);
			power(x + 1, y + 1, visited);
		}
	}
}

Malgaras

Accidental double post, oops. Was taking a while to post and I'm impatient with the mouse.

Sir Carcass

I'm using C++, but that's close enough. I'll give it a try tomorrow and let you know how it works out. Thanks for everyone's help!

Sir Carcass

That doesn't work. It powers every block with a wire, regardless of whether it's connected to the power source.

But when I add this:

if(city.getBlockHasPower(x,y))

before the block where it does the adjacent squares, it seems to work like I want. Rudimentary testing showed it working, anyway.

Thanks for the help everyone. I'll leave this open for now in case I find a problem later, but so far so good.

bowen

Yeah you need to test which block you want to check, and then radiate from there.

Basically you pick a point, check adjacent ones, then check other adjacent blocks from those adjacent blocks and so on and so forth until you've computed everything (and not repeated). Once you hit a ("I'M POWERED") you can short circuit and assume true from there, so long as they're connected in some fashion.

Malgaras

Sir Carcass wrote: »

That doesn't work. It powers every block with a wire, regardless of whether it's connected to the power source.

But when I add this:

if(city.getBlockHasPower(x,y))

before the block where it does the adjacent squares, it seems to work like I want. Rudimentary testing showed it working, anyway.

Thanks for the help everyone. I'll leave this open for now in case I find a problem later, but so far so good.

Weird. That check should be redundant, as we only make the adjacent block calls if we are already said we are going to power the current block, and it has no way to bridge gaps in wire so it should only ever get to wire that you want powered. You are only calling it from the two blocks of your power plant and not every block right?

Anyways, glad you got it working. I'd love to see the code if you're willing to share, if for no reason other than my personal edification. Also, it occurs to me I forgot the less than checks for x and y when checking if we're off the grid, so make sure to include those yourself if you haven't.

bowen wrote: »

Yeah you need to test which block you want to check, and then radiate from there.

Basically you pick a point, check adjacent ones, then check other adjacent blocks from those adjacent blocks and so on and so forth until you've computed everything (and not repeated). Once you hit a ("I'M POWERED") you can short circuit and assume true from there, so long as they're connected in some fashion.

Well I would assume that the power plant would always be powered (correct me if I'm wrong here), and you never need to call it for any other blocks as the recursion should take care of everything.

Sir Carcass

gespo89 wrote: »

Well I would assume that the power plant would always be powered (correct me if I'm wrong here), and you never need to call it for any other blocks as the recursion should take care of everything.

Actually, it starts off non-powered and can later be turned on if the player is able to. Otherwise they have to rely on generators that can only power a single block and consume fuel.

Here is the code I ended up writing. Very similar to yours but with a few tweaks:

in my gameLoop:
	
	doPower();


and the functions:

void doPower()
{
	bool visited[25][25];

	//turn off power and reset visited
	for(int y=0;y<25;y++)
		for(int x=0;x<25;x++)
		{
			city.setBlockHasPower(x,y,false);
			visited[x][y] = false;
		}
		

	power(3,5,visited);
	power(3,6,visited);
}

void power(int x, int y, bool visited[25][25])
{
	if(visited[x][y] || x > 24 || x < 0 || y > 24 || y < 0)
		return;
	else
	{
		visited[x][y] = true;
		
		if(city.getBlockHasWire(x,y) && powerOn)
			city.setBlockHasPower(x,y,true);
			
		//get recursive, baby!
		if(city.getBlockHasPower(x,y))
		{
			power(x-1,y-1,visited);
			power(x,y-1,visited);
			power(x+1,y-1,visited);
			power(x-1,y,visited);
			power(x+1,y,visited);
			power(x-1,y+1,visited);
			power(x,y+1,visited);
			power(x+1,y+1,visited);	
		}
	}
}

Please excuse my old school formatting. I am a creature of habit.

Bethryn

For what it's worth, you're talking about node/tree/graph traversal.

You can read around it here:

http://en.wikipedia.org/wiki/Tree_traversal

Latest code looks fine for a breadth-first search, powerOn might need to be changed if you add more than one generator to a city.

Malgaras

Sir Carcass wrote: »

gespo89 wrote: »

Well I would assume that the power plant would always be powered (correct me if I'm wrong here), and you never need to call it for any other blocks as the recursion should take care of everything.

Actually, it starts off non-powered and can later be turned on if the player is able to. Otherwise they have to rely on generators that can only power a single block and consume fuel.

Ah, the code not working right makes a lot more sense then. I was thinking more along the lines of the power plant being good and the player having to run lines, which in retrospect doesn't make nearly as much sense. Glad it's working, and thanks for posting code. I always like seeing the final product on things like this. Helps me improve (and not use two loops when one will do apparently).