Simcity style management

I have an idea of a short, quick game I want to make, but it involves a bit of 'SimCity' style management. Here's a simplified idea of what I want:

What I have is a 2d grid map; one or more squares are set as 'generators' and produce power, others are 'buildings' and have to be connected to another powered structure such as another building, or a generator to receive power.

Now, I can get a simple 'powering up' to work, but it's not perfect since if you shut the generator down, the buildings don't power down properly. I'm doing this by checking the buildings next to the current one and if one of them is powered, then the current building also gets powered. Of course, this doesn't work when you turn off the generator because two or more buildings will 'recharge' themselves. I've tried several variations on the basic theory, and none of them seem to work properly.

I hope this makes sense, if not I'll post a simple example. There has to be a simple way of doing this, I can't see using a complex pathfinding routine for every single building as that would really slow everything down and over complicate things.

Any thoughts? Ta. :)

Use a simpler pathfinder like breadth/depth first or Dijkstra and have a 'powered' field to your building type. Each time a generator is created run the algo and add 1 to the powered field. Each time it is down decrease the powered field. Not sure how many nodes you have but shouldn't take long. You could always show an electrical arc anim on the generator while you're doing it.

Unless I'm mis-understanding the problem (never played SimCity, myself), I don't see why you can't just use types/linked lists.

Have a generator type and a building type. The generator type should contain a linked list of all buildings it's powering, either directly, or in-directly.

The building type should contain a field identifying the generator it's being powered by, if any.

When you power-down a generator, go through the linked list and power-down all buildings.

When you create a new building next to a powered one, find which generator that building is being powered by and add the new building to it's linked list.

In SimCity, multiple power plants supply power to the same grid. The problem relates to the tile map of buildings and power lines. Removing a tile might shut off the power to a whole suburb, or there might be piles of redundancy in place.

Because of the myriad of different paths electricity can take through your buildings and power lines, I think some sort of "pathfinding" is the only way to properly solve this problem.

This hypothesis is supported by the fact that even the newer versions (e.g. 4) of SimCity take a few moments to decide that a building has lost or gained power, suggesting that there is pathfinding going on, spread out over the course of many frames to avoid slowdown.

My suggested approach would be to send out "pulses" of power from your generators - a very similar approach to your original strategy. All your buildings would have a "most recently powered" field, and if the power is more than two pulses old, the building is unpowered. Only one pulse would go out at a time. Every frame, you'd spend a certain amount of time extending the pulses to adjacent buildings.

I'll do up a quick and dirty demo to show you what I mean.

Const MAP_HEIGHT = 20, MAP_WIDTH = 27
Const TILE_HEIGHT = 30, TILE_WIDTH = 30

Type tile
	Field building_class$
	Field got_power_pulse
	Field powered
End Type

Dim map.tile(MAP_WIDTH-1, MAP_HEIGHT-1)

game_init()
While Not KeyHit(1)
	game_update()
	game_render()
	Flip
Wend
End

Function game_init()
	Graphics 800, 600, 32, 0
	SetBuffer BackBuffer()
	
	For y = 0 To MAP_HEIGHT-1
		For x = 0 To MAP_WIDTH-1
			map(x,y) = New tile
			Read t
			Select t
				Case 1
					map(x,y)\building_class = "house"
				Case 2
					map(x,y)\building_class = "powerplant"
			End Select
		Next
	Next
End Function

Function game_update()
	mx = Floor(MouseX() / TILE_WIDTH)
	my = Floor(MouseY() / TILE_HEIGHT)

	If MouseDown(1) Then map(mx,my)\building_class = "house"
	If MouseDown(2) Then map(mx,my)\building_class = ""
	If MouseDown(3) Then map(mx,my)\building_class = "powerplant"

	power_update()
End Function

Function power_update()
	Local pulse_propagations = 0
	; propagate the pulse through adjacent tiles
	For y = 0 To MAP_HEIGHT-1
		For x = 0 To MAP_WIDTH-1
			If map(x,y)\got_power_pulse=False Then
				; powerplants automatically get pulses
				If map(x,y)\building_class = "powerplant" Then
					map(x,y)\got_power_pulse = True
					pulse_propagations = pulse_propagations + 1
				EndIf
				; other structures get pulses if an adjacent tile got one
				If map(x,y)\building_class = "house" Then
					Local get_pulse = False
					If Not get_pulse Then get_pulse = check_tile_for_pulse(x-1,y)
					If Not get_pulse Then get_pulse = check_tile_for_pulse(x+1,y)
					If Not get_pulse Then get_pulse = check_tile_for_pulse(x,y-1)
					If Not get_pulse Then get_pulse = check_tile_for_pulse(x,y+1)
					If get_pulse Then
						map(x,y)\got_power_pulse = True
						;map(x,y)\powered = True
						pulse_propagations = pulse_propagations + 1
					EndIf
				EndIf
			EndIf
		Next
	Next
	
	; when the pulse is finished...
	If pulse_propagations = 0 Then
		For y = 0 To MAP_HEIGHT-1
			For x = 0 To MAP_WIDTH-1
				; tiles that got the pulse are powered, others are unpowered
				map(x,y)\powered = map(x,y)\got_power_pulse
				; and reset the field for the next pulse
				map(x,y)\got_power_pulse = False
			Next
		Next
	EndIf
End Function

Function check_tile_for_pulse(x, y)
	If x < 0            Then Return False
	If x > MAP_WIDTH-1  Then Return False
	If y < 0            Then Return False
	If y > MAP_HEIGHT-1 Then Return False
	Return map(x,y)\got_power_pulse
End Function

Function game_render()
	Cls
	For y = 0 To MAP_HEIGHT-1
		For x = 0 To MAP_WIDTH-1
			Select map(x,y)\building_class
				Case ""
					Color(0, 0, 0)
				Case "powerplant"
					Color(255, 255, 0)
				Case "house"
					If map(x,y)\powered Then
						If map(x,y)\got_power_pulse Then
							Color(32, 32, 255)
						Else
							Color(0, 0, 223)
						EndIf
					Else
						If map(x,y)\got_power_pulse Then
							Color(32, 32, 127)
						Else
							Color(0, 0, 95)
						EndIf
					EndIf
			End Select

			Rect(x * TILE_WIDTH, y * TILE_HEIGHT, TILE_WIDTH-1, TILE_HEIGHT-1, True)
		Next
	Next
End Function

Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,1,1,0,2,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,1,1,0,1,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,1,1,1,1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,1,1,1,1,1,1,0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,1,1,1,1,1,0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,1,1,1,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

Left mouse button: add a house/powerline/whatever (blue)
Middle mouse button: add a powerplant (yellow)
Right mouse button: clear the tile

A simple optimization would be to have the pulse propagation occur from (MAP_WIDTH,MAP_HEIGHT) to (0,0) every other time, instead of only the other way. Because I'm only going down and right from the top-left corner, pulses take a lot longer to propagate up and left.

Here's an example Data set that illustrates the "problem".

Data 1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,2
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0
Data 0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1
Data 1,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0
Data 0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1
Data 1,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0
Data 0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1
Data 0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1

Oh, and I guess the other two directions (NE and SW) would be a good idea too, as this would be slow even with the fix suggested above:

Data 1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1
Data 0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1
Data 0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1
Data 1,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1
Data 0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1
Data 1,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1
Data 0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1
Data 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0
Data 1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,2
Data 1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1

Hope this helps you, have fun!

That's fantastic thanks! I'll have a mess around with this and see what I can do. Something I didn't mention in my original post was that each object had 'power stored' variable, and that filled up as time went by. This is going to be important in what I am doing so I'll try to incorperate it into the code you gave above.

Thanks again!

Sweet - got it working. :)
I wasn't far off really! Thanks for giving me the nudge in the right direction though, got the old brain cells cooperating again.

I uploaded the original program I made with Octothorpes modifications to it; you can find it here.

I'm going to modify this even further; perhaps making each power station have an effective range and/or a total power output, etc.

instead of updating the power every frame, why don't you reset all of the tiles to unpowered whenever something is destroyed, then recalculate using whatever method you used before.

Because that's theoretically slow. Finding out which tiles are connected via a whole bunch of adjacent tiles could take a while and cause the game to "hiccup" whenever you needed to recalculate everything all at once.