Well, I didn't quite get my weekend goal. I actually played some games this weekend, and losing hours into Smugglers V didn't help me achieve my own programming goals. Speaking of that, it's a fun little game. Reminds me a lot of Space Rangers, only there's less to do on-planet (very Sid Meier's Pirates-style on-planet stuff), and the way that combat is handled is very different. Combat is done in a 1-on-1 style separate combat system, with turn-based, action-point-oriented, ability-driven mechanics. Frankly, it plays a lot like a card game, where your abilities are cards that you play on the table. It's fun. Very sandbox-y, and should play very well in small bites, which is something I have come to enormously appreciate in a game.
Anyway, I didn't quite reach my goal. I do have the ability to select tiles from the tileset working, and when you select a tile, it becomes your cursor on the tile map, where eventually you'll place it and it'll be rendered. I spent some time struggling with an odd problem. wx, for fairly understandable reasons, has their own string objects, but they encourage programmers to use std::string or std::wstring in their own stuff that interacts with wx. As a result, I spend several places converting wxStrings to std::strings. This mostly works just fine. Unfortunately, when retrieving data from a custom dialog (and dialogs in general, but custom dialogs -- wx::TextCtrls -- seem to have this problem worse than standard dialogs), I can't seem to get a good std::string back out of it. I can get the wxString just fine; it outputs the expected data. But when I use wxString::ToStdString() to convert it to a std::string, I end up getting an empty string back. I finally had to do an incredibly stupid workaround: I called the std::string constructor on wxString::mb_str(). I suspect that it might have to do with the transient scope of the converted String, but I'll have to do some more testing with it to see if I can fix the problem. If so, it's really just a matter of needing to clone or copy the string instead of trying to use its reference. Guess I'm learning that the copy constructor isn't always such a terrible thing. :P
For reference, I'm going to use the word "StageMap" for the representation of the game's playable area (i.e. "map," "level," "stage," "floor," or "zone"). That helps me differentiate it from any other word "level" or "map" (like the datastructure).
So the other problem I'm trying to tackle is getting a good grip on the data structure I need to store the stagemap data in. I spent a lot of time trying to decide if I was looking at the situation, and deciding the various pros and cons of different data structures. The problem is really sort of two-fold. I need to have an abstract version of the stagemap stored, which can easily be saved independently of the tilesets contained in the stagemap. I also need to have a renderable version of the stagemap, where the tiles are stored in sfml::VertexArrays. Traditionally, the abstract form of a game grid is a two-dimensional array. However, unlike a chess board, my stagemaps might be different sizes, and I really want to make it dynamic -- you don't have to know how big the stagemap is going to be when you initially create it; it'll grow to fit what you draw. That means it's really more like a two-dimenional vector; or a vector of vectors. (I don't know how practical that is, and I might have to make a vector of vectors class that can do all the work of keeping the vectors unified sizes for each dimension (all x vectors are the same length, all y vectors are of the same length); we'll see). If the stagemap only grows in the positive directions, that's not that bad; we're just pushing abstract tiles onto the ends of each vector. But it won't just be growing along the axes, sometimes I'll be placing tiles near the 0-position of an axis, and then I need to shift all of the vector contents down that axis, effectively "growing" the low-index part of the gridspace. In just the abstract datastructure, that's also not terrible, even if those operations are fairly slow.
I've been trying to decide if that's the right method, or if I'd be better off storing the abstract representation in something like a linked list, where I'm only storing the actual placed tiles instead of storing a whole bunch of empty space. I'll need to do some math to figure out how bad storing everything, including empty space, in these big crazy vectors is going to be. In the vector representation, the position of the tile is pure metadata. I know by the indices of the vectors where the tile exists in space. So all I have to store is two integers (more or less) -- the std::map keys of the tile set and the tile within that tileset (I use std::hash() on the names of the tileset and the tile to build the std::map key values, which produces std::size_t type values). For this thought experiment, we'll place a 10x10 room in a 15x15 gridspace, and use 4-byte ints as the std::size_t values. The room will require 10 * 10 * 4 * 2 = 800 bytes. However we don't just care about the room, we also have to store all the empty squares around the room. As a result, we're actually storing 15 * 15 * 4 * 2 = 1800 bytes. Our storage requirements scale linearly with the gridmap size, not the stagemap size. Due to the vector growth formula, this will actually end up being something more akin to growing exponentially with the stagemap size.
If I use a linked list (or similar) representation, I'm only storing the actual placed tiles, which dramatically decreases the virtual space being stored. However, I have to separately store metadata like the gridspace area (so that I can grow it when appropriate), and each of the abstract tiles has to know its x,y coordinates, which is another two integers, bringing us up to a total of 4 integers. For our 15x15 space, we only store the 10x10 room: 10 * 10 * 4 * 4 = 1600 bytes. That's a modest savings of 200 bytes. It's maybe that's worth while, because that value scales linearly with the size of the stagemap itself, not the grid; it doesn't care how big the grid is.
For fun, let's use something bigger. Say 1000 x 1000 gridspace, with 75% of the tiles contained in that gridspace actually having useful tile data in them (the rest is space around the stagemap, or "holes" in the stagemap between rooms and the like). The vector representation requires the full gridspace to be stored: 1000 * 1000 * 4 * 2 = 8000000; about 8 Megabytes (how "about" that is depends on how pedantic you are concerning metric prefixes). The linked list representation is 1000 * 1000 * 0.75 * 4 * 4 = 12000000, or about 12 Megabytes. Wow, those two extra ints made a big difference.
The VertexArray department is not without its problems, which are pretty much shared with the linked-list version of the abstract stagemap. The VertexArrays store exact position data on the placed vertices, and so moving things around is not as easy as just applying a transform to an sfml::Sprite. When I insert to the front of an abstract stagemap vector, I'll have to iterate through all the vertexes in all the VertexArrays and move all of them appropriately. I get to pick between the easy relocatability of Sprites (I could seriously just make them children of a Transformable object, and then transform that object to move all of them around; it'd be pretty easy), or the much more efficient drawing capability of the VertexArray approach (only one draw() call per VertexArray; remember theres one VertexArray per tileset, so on some/many stagemaps, that's a single draw() call to render all the tiles). Considering that the average stagemap will probably be hundreds or thousands of tiles (a 10x10 room is 100 tiles alone), efficiency in draw calls is an optimization I need. So iteration over the tileset is the way it's going to have to work. I guess the lesson to take from this is "don't grow the map up or to the left if you can help it."
But the similarities between the VertexArray and the linked-list version of the abstract stagemap gives me pause: maybe I don't need an abstract version at all. I'm already storing location data for each tile quad in the VertexArray, each VertexArray already knows its tileset, and I can theoretically back-calculate the tile from the (u,v) coordinates of the first vertex in the quad. That means I should be able to reasonably serialize the VertexArray to create a composite tileset containing only the tiles used from each component tileset (I know that I want the finalized, "game-ready" stagemap to only contain a single tileset for performance reasons). I'm already going to have to iterate over the VertexArray to move the quad coordinates around when I change the gridspace's size. While another datastructure might be convenient, I don't think it's necessary. The real problem then is replacing tiles. With a separate data structure, you just look the tile up in it (which is at worst O(n) and at best constant time), then you know which VertexArray contains the original tile quad (which can be removed). Without that separate data structure, we'll need to walk every VertexArray and look for the existing tile to replace. Here's the kicker: without a separate datastructure (which can know if that gridspace it represents is empty) every tile placed is treated like it's replacing a tile. That means checking every single quad in every single VertexArray for an overlap. That's going to get slow in a hurry. In order to address that, I'd be back to a list or a std::set, which would at least have to know the location and the tileset (and then we could search the tileset for the tile); so I'm back to eating up a bunch of memory.
Sorry for rambling on you all there; I was thinking through the problem out loud, and frankly, this was a big help, even if I'm still trying to sort the problems out and decide what's going to be best. I'll have a lot of time for thinking this week, but not much time for writing code: I'm on a trip for work for a big chunk of the week. Hopefully I can at least figure out how I want to tackle this.