Advice for data structure: boxes inside a "hull"

Question

I'm making a (2D) spaceship game, and I haven't been able to figure out an efficient way of saving spaceship data.

I have a "hull" (boundaries), in which all of the systems/rooms go. Rooms are contiguous, some systems are as well. I want to efficiently save the hull and room data for both easy manipulation of them (adding/subtracting space between rooms, extending and/or damaging the hull, etc.) and easily saving them in a (preferably) human-readable format.

What I see so far is two options:

• saving everything "by-pixel" in a 2D array of objects that hold what "pixel" this part of the room is (tedious and can easily cause errors, though easiest to implement), or
• saving via a tree-like data structure, representable as XML (holds to most of my requirements, but I can't figure out how to implement it well - a "box model" approach doesn't get me too far into rooms that aren't rectangular).

If it makes any difference, I'm using (will be using) C# and Blend/WPF. If there's a component that can magically allow manipulation of children and serialize it, then I think that would be acceptable as well.

This is my first question on this site, so please mention if I did something incorrectly. Thanks for your time. :)

Answer 1

Considering that you probably have a number of things that would make the system of rooms more complex:

• Your rooms/systems might have properties, room Name, type of room, subtyping while adding properties, e.g. a ComputerRoom might have NumberOfCPUCores as a property, while this would not apply to a normal room. % Damage, where the damage is, etc.
• The overlap rules might be more complex, e.g. you might later add something that could overlap or span multiple rooms.

Simple size/shape and position could be represented using a bitmap style storage model, however it would not allow for more complex structures easily, without accompanying data.

I would consider using Data Contract serialization, this enables a wide range of methods to store and send your data, including but not limited to storing as XML, binary (more efficient, but not human readable), sending over network using WCF, etc. It allows to scale to pretty much infinitely complex models.

An example of a simple model and XML serialization below. (Everthing is rectangular here).

The definition of the hull, rooms, etc:

[DataContract]
class Hull
{
    public int Width { get; set; }
    public int Height { get; set; }

    [DataMember]
    public List<Component> Components { get; set; } 

    //read only properties will be ignored
    public int SurfaceArea { get { return Width*Height; }}

    //some properties can be excluded from serialization:
    [IgnoreDataMember]
    public int NotStoredInXml { get; set; }

    public Hull()
    {
        this.Components = new List<Component>();
    }

}

[DataContract]
[KnownType(typeof(Room))]
[KnownType(typeof(ComputerRoom))]
[KnownType(typeof(System))]
abstract class Component
{
    [DataMember]
    int Width { get; set; }
    [DataMember]
    int Height { get; set; }
    [DataMember]
    int X { get; set; }
    [DataMember]
    int Y { get; set; }
}

[DataContract] class Room : Component { }
[DataContract] class System : Component { }
[DataContract] class ComputerRoom : Room
{
    [DataMember]
    public int NumberOfCPUCores { get; set; }
}

Saving and loading data:

var hull = new Hull();
hull.Components.Add(new ComputerRoom { NumberOfCPUCores = 3 });
hull.Components.Add(new System());
hull.Components.Add(new Room());

var serializer = new DataContractSerializer(typeof (Hull));
using (var stream = File.Open("test.xml", FileMode.Create))
{
    serializer.WriteObject(stream, hull);
}

Hull newHull;
using (var stream = File.OpenRead("test.xml"))
{
    newHull = serializer.ReadObject(stream) as Hull;
}

Console.WriteLine(newHull.Components.Count); //3

The resulting XML:

<Hull xmlns="http://schemas.datacontract.org/2004/07/ConsoleApplication22" 
      xmlns:i="http://www.w3.org/2001/XMLSchema-instance">
  <Components>
    <Component i:type="ComputerRoom">
        <Height>0</Height>
        <Width>0</Width>
        <X>0</X>
        <Y>0</Y>
        <NumberOfCPUCores>3</NumberOfCPUCores>
    </Component>
    <Component i:type="System">
        <Height>0</Height>
        <Width>0</Width>
        <X>0</X>
        <Y>0</Y>
    </Component>
    <Component i:type="Room">
        <Height>0</Height>
        <Width>0</Width>
        <X>0</X>
        <Y>0</Y>
        </Component>
    </Components>
</Hull>

Update

If you want to support arbitrary shapes, you can look at the Path syntax in WPF and the Geometry Class