Well, you are basically looking for something like a path finding algorithm. In the case of adding 1 new building, A* sounds like a reasonable choice, but perhaps not the best way. However, when recomputing connectivity information for a large number of buildings, there are certainly better choices. When a building is destroyed, or perhaps loading a saved game, or scenario with pre-existing buildings, you probably want something more global in scope.
With A*, you're computing a shortest path between two points. What you actually want, is just plain connectivity (yes/no), and don't really care if it's the shortest path. You might also want to be able to do this for a bunch of buildings at once.
Consider the global case first. Say a game was loaded, or a scenario with existing buildings was needs to be initialized. What you can do is start at the Command Center, and expand out from there activating things along the way. The most natural way to think of this conceptually is with a Breadth First Search (BFS). Starting off, the command center is active. You check for neighbors of the active nodes (neighbors of the command center), and mark them as active too. Then you repeat with this new set of active nodes.
BFS
Or rather, to state this in a way with a nod toward efficiency, you proceed by processing one of the remaining exterior nodes. The command center will be an interior node once you've checked for all it's neighbors, and each neighbor you found will be a new exterior node. You don't need to process the command center again once you've marked it as interior (that is, once you've processed it's surrounding neighbors). You then check the list of exterior nodes that have recently been marked as active, remove one from that list, and try to find it's neighbors to be marked as active and placed on the exterior node list. (Make sure they aren't already marked as active, so you don't get stuck in an infinite loop adding the same nodes over and over again until you run out of memory). As you process each node, you move it from the exterior list to the interior list, and the algorithm terminates when there are no more exterior nodes to process. (You initialize the algorithm by placing the command center, or rather, all command centers, on the exterior list, and marking them as active). For this algorithm, you'd probably want to use a linked list to maintain the exterior list. The active flag can be placed in the unit data, and should be initialized to false before starting the algorithm. A next link could also be placed in the unit records for the linked list of exterior nodes, but usually this is maintained externally.
Of course, it need not be a breadth first search. I just figure that's the easiest way to think of it conceptually. You might also use a depth first search. This uses recursion and the stack instead of a linked list. Rather than expanding out in circles about the active points, you could expand out in lines as far as they'll go, and then backtrack looking for branch points. This is more like tree traversal. Depending on the structure of the graph, there will be different memory requirement tradeoffs between the two algorithms. If the graph has a high branching factor, but low depth along each branch, then the DFS will probably use less memory. If the graph has long paths with little branching, than the BFS might use less memory.
DFS
Initialize all nodes to inactive. For each command center, do the following. Mark the node as active, and for each neighbor, which isn't already active, recursively mark it as active and check all it's neighbors.
Now, that covers initialization, or reinitialization when a building is destroyed. How about when a new building is built?
In the same case, you build a unit, and check if any neighbors are active, and if so, the new building is active. If not, well, nothing left to do. This works fine as is for leaf buildings at the fringe of a colony, but what about a new connecting building that is reattaching a branch to the main colony trunk. In that case, you'll also have to activate any non-active buildings that it connects to. This can be done by using one of the above two algorithms, without first initializing all nodes as inactive, and starting with the new building as the starting point.
Pseudo-code:
(Assumes a few global arrays/objects exist, and ignores Sirbomber's comment about only activating with tubes)
void MarkAllInactive()
{
int i;
for (i = 0; i < numBuildings; i++)
{
building[i].active = false;
}
}
struct Point
{
int x;
int y;
Point(int x, int y) // Constructor
{
this->x = x;
this->y = y;
};
Point operator + (Point &other) // + operator
{
return Point(x + other.x, y + other.y)
};
};
Point direction[] = {
{ 0, -1 }, // Top
{-1, 0 }, // Left
{ 1, 0 }, // Right
{ 0, 1 }, // Bottom
// ... keep adding more if all 8 surrounding tiles are adjacent
};
const unsigned int NumDirections = sizeof(direction)/sizeof(*direction);
void ActivateBFS(int startBuildingIndex)
{
int i;
LinkedList<int> exteriorNodes;
exteriorNodes.Add(startBuildingIndex);
building[startBuildingIndex].active = true;
while (exteriorNodes.numNodes > 0)
{
currentBuildingIndex = exteriorNodes.RemoveHead();
for (i = 0; i < NumDirections; i++)
{
neighborBuildingIndex = map.Tile(building[startBuildingIndex].location + direction[i]).buildingIndex
// Make sure the index is valid here, perhaps by checking...
if (neighborBuildingIndex != -1) // Obviously -1 isn't a valid index
{
// Make sure the building hasn't already been marked as active
if (!building[neighborBuildingIndex].active)
{
building[neighborBuildingIndex].active = true;
exteriorNodes.Add(neighborBuildingIndex)
}
}
}
}
}
void ActivateDFS(int startBuildingIndex)
{
int i;
building[startBuildingIndex].active = true;
for (i = 0; i < NumDirections; i++)
{
// Assuming the map hold an array of building indexes, for simplicity
neighborBuildingIndex = map.Tile(building[startBuildingIndex].location + direction[i]).buildingIndex
// Make sure the index is valid here, perhaps by checking...
if (neighborBuildingIndex != -1) // Obviously -1 isn't a valid index
{
// Make sure the building hasn't already been marked as active
if (!building[neighborBuildingIndex].active)
{
ActiveDFS(neighborBuildingIndex)
}
}
}
}
// Call on load, or when a building is destroyed (BFS version)
void InitializeActiveBFS()
{
int i;
MarkAllInactive();
for (i = 0; i < numBuildings; i++)
{
if (building[i].type == CommandCenter)
{
ActivateBFS(i);
// Optionally, instead of the above call, we could "push" the CC onto the exterior list (mark as active and add), and use the loop from ActivateBFS
}
}
}
// Call on load, or when a building is destroyed (DFS version)
void InitializeActiveDFS()
{
int i;
MarkAllInactive();
for (i = 0; i < numBuildings; i++)
{
if (building[i].type == CommandCenter)
{
ActivateDFS(i);
}
}
}
void ActivateNewBuilding(int buildingIndex)
{
int i;
// Check for active neighbor
for (i = 0; i < NumDirections; i++)
{
neighborBuildingIndex = map.Tile(building[startBuildingIndex].location + direction[i]).buildingIndex
if (neighborBuildingIndex != -1)
{
if (building[neighborBuildingIndex].active)
{
// This building, and all connections are active
ActivateBFS/DFS(buildingIndex);
return; // No need to keep checking
}
}
}
}
1) Me making new graphics = me spending less time making the new graphics actually *do* something. New graphics will need to be made for distribution though. And I actually think the graphics were quite good for the time.
2) I remember reading that there was also had a hard codeed 4 tube iteration limit. The problem is I don't know how it was iterated. The problem I am worried about is if a connection is destroyed. Here is ascii art. (B is building, C command center, everything else is tube)
B--B--(rest of colony)
| |
B--C--(rest of colony)
Now say you get hit with a mass driver and you lost some buildings
B B--(rest of colony)
| |
B C--(rest of colony)
I'm not sure an effective way to check the two buildings on the left getting disconnected from the command center and the rest of the colony.
My other problem, at least for being tile based like this, is I can't find any gameplay justification for having tubes.
i tryed my best to get it running but just got some error msgs
server
Traceback (most recent call last):
File "./Server.py", line 177, in <module>
main()
File "./Server.py", line 165, in main
game = Game(eventManager)
File "$$$/openoutpost/Network.py", line 27, in __init__
self.loadStructures()
AttributeError: Game instance has no attribute 'loadStructures'
and the oupost .py
DirectStart: Starting the game.
Warning: DirectNotify: category 'Interval' already exists
Known pipe types:
glxGraphicsPipe
(all display modules loaded.)
Traceback (most recent call last):
File "./Outpost.py", line 47, in <module>
from UI import AIMenu, Picker, ContextMenu, UI
File "$$$/openoutpost/UI.py", line 10, in <module>
import Menu
ImportError: No module named Menu
hope thats not waste of your time and helps youu somehow ^^
//note this is from the old version not 0.2
Well bugger. I made a new install of windows in a virtual machine (you would think I would of thought of this sooner). The problem is in this bit of code
def launchSPServer(self):
#self.singlePlayer = True
if os.name == 'posix':
self.server = subprocess.Popen('python' +' ./Server.py', shell=True)
#self.server = subprocess.Popen('panda' +' ./Server.py', shell=True)
self.server = True
else:
self.server = subprocess.Popen('..\\python\\ppython.exe' +' Server.py')
self.server = True
import socket
x = True
serverSocket = socket.socket()
serverSocket.settimeout(0.25)
while x:
try:
#print 0
serverSocket.connect(('127.0.0.1', 1999))
x = False
#print 1
except socket.error:
pass
messenger.send('login')
print 'Server launched'
which launches the server, checks that it is listening and ready to go (the while loop) before the client attempts to log in. It works fine in linux. Under windows the server launches properly, but the port check constantly returns a socket error.
Would you like troubleshooting questions to go somewhere specific, or should it all stay in this thread?
I'm having trouble getting this to run on windowsXP SP3. I installed the patch but it didn't help.
When I use the start menu shortcut the openoutpost window will appear for a split second then vanish. Trying to run from the command prompt gives the following response (although I could swear I saw more text than this during the split second the window was up)
C:\openoutpost-Alpha.0\python>ppython.exe -E main.py
ppython.exe: can't open file 'main.py': [Errno 2] No such file or directory
When I try to execute main.py directly (I already have python on this computer) it gives the following error:
Traceback (most recent call last):
File "C:\openoutpost-Alpha.0\game\main.py", line 4, in <module>
import Outpost
File "C:\openoutpost-Alpha.0\game\Outpost.py", line 6, in <module>
from pandac.PandaModules import loadPrcFileData
ImportError: No module named pandac.PandaModules
Possible relevant info:
-I have python 2.6 installed on the computer already
-I may have once had panda3D installed here, but have since removed it.
Thanks, I think it might take a few weeks to wrap my head around why that worked, but anyway...
Here is the full error message that OO gives when executed:
DirectStart: Starting the game.
Known pipe types:
wglGraphicsPipe
(all display modules loaded.)
:display:wgldisplay(error): SetPixelFormat(57) failed after window create
:display(error): Window wouldn't open; abandoning window.
:ShowBase(warning): Unable to open 'onscreen' window.
Traceback (most recent call last):
File "main.py", line 4, in <module>
import Outpost
File "C:\openoutpost-Alpha.0\game\Outpost.py", line 24, in <module>
import direct.directbase.DirectStart
File "C:\openoutpost-Alpha.0\direct\directbase\DirectStart.py", line 4, in <mo
dule>
ShowBase.ShowBase()
File "C:\openoutpost-Alpha.0\direct\showbase\ShowBase.py", line 229, in __init
__
self.openDefaultWindow(startDirect = False, props=props)
File "C:\openoutpost-Alpha.0\direct\showbase\ShowBase.py", line 726, in openDe
faultWindow
raise StandardError, 'Could not open window.'
StandardError: Could not open window.
Also: couldn't this stuff be written to an error log, so people can just copy/paste it instead of having to run from the command line in order to catch the error message? Seems like it would make bug reporting easier.
=====non-troubleshooting conversation=====
-I'm glad you are keeping the tubes in the game, there needs to be some constraint to keep colonies from just being blobs of buildings all right next to each other. If you want to eliminate some of the tedium of them though, maybe allow them to be built in lines.
-You said you were using a heightmap, how does it translate into a grid? Does it literally represent each square as a different height like Sid Meirs Alpha Centauri/Sim City 2000/3000, or will the game retain the OP1/OP2/Civ style of each square having a particular type of terrain? (please tell me it's not the former, I always hated that system)
-Jessai mentioned power transmitters to cut down on tubes. I don't think power transmitters would be all that useful though; if you are going to build two power transmitter stations, why not just build a power plant in the far-off colony and get the added disaster resistance? In any case tubes would still be required for their air/water/waste/etc.
I think the solution is that far off colonies should just have their own separate infrastructure, rather than trying to tube across an entire continent.
Also, on the subject of tubes getting in the way of things, do you think it would be difficult to make the three connector tiles pass over each other? You would need to make a custom "road sloping under tube" tile, but the others fit together very well already.
(http://img192.imageshack.us/img192/8389/intersections.th.png) (http://img192.imageshack.us/my.php?image=intersections.png)
-Finally, a nitpick; when you changed levels in the video it looked like you were going down a very very long way. I feel like each underground level should only be one, maybe two tiles deeper than the last (see pic). I don't have any real-life underground cities to compare with, but going down so deep seems unrealistic.
(http://img30.imageshack.us/img30/463/ugdistance.th.png) (http://img30.imageshack.us/my.php?image=ugdistance.png)