If you have suggestions for new features, post them to the forum, where developers and other players will voice their opinions on your idea. Only post them under Requested features if you have first started a forum thread, and definitely don't create a separate page unless it's under your user page.
The general idea
Currently there is one tile on every (x,y) on the map. Wherever things are stacked (tunnels, bridges), every stacked item is packed into that one tile. The new array will take a different approach. Instead of one tile for every (x,y) we can have multiple. Whenever things are stacked, we just store multiple tiles. Take a bridge for example. The original ground tile will store all the info about what is underneath the bridge and a second tile is created that stores info about the bridge and everything on it. In a way, we could have one tile for every (x,y,z) on the map. But since most tiles would be unused (underground or in the air), this would increase the memory usage by a large factor, while most of the tiles would remain unused. We instead store at least one tile for every (x,y), which contains information about the ground tile. Any additional tiles (both below and above the ground) are stored in a linked-list kind of manner.
Maybe we should always store the lowest tile, instead of the ground tile? ie, if you build a tile below the ground tile, the new tile will be in the map array and the ground tile will be linked to by the bottom tile. We should probably also store the tiles sorted?
Thinking of this, finding the tile above a tile would be trivial, but how about finding the tile below a given tile? You would need to iterate the entire linked list until you would find the given tile to see what is below. For this you need to store the (x,y) in every tile. Might it be more efficient to make the tiles a doubly linked list, so not only store the next tile in the stack, but also the tile below? Would we need to store the (x,y) in a tile for something else? Coming to think of it, we probably should. But still it will probably have quite some speed advantages to make the tiles doubly linked...
--Matthijs
A simple solution would be use a pointer to the next tile. This is the easiest to follow, but has one big disadvantage: it is generally 32, and in the future even 64 bits. There will never be that much tiles, so it will be sufficient to just store the index of the next tile, which is then used as an index into an array. This way, all the ground tiles can be statically allocated in an array. The non-ground tiles will be needed when people start building things. When a new tile is needed, we use one from a second array that has been allocated for this.
We have a few options here. The simplest options would be allocating and deleting every tile when needed (malloc/free) but that would be too much overhead. We could also statically allocate an array of tiles and use tiles from that array when we need new tiles (this is how the code below works, this is the _mapextra array). The main disadvantage of this is that there is a hard maximum. An alternative would be mallocing tiles in large blocks, or reallocing the array.
A different thing used here, is indirection from the tile to the info about it. Every tile stores two indices, LandscapeInfo and BuildInfo, which are indices into the LI and BI arrays, resp. These LandscapeInfo and BuildInfo structs store information about the tile, and about what is (built) on it. The reason that these are not just embedded into the MapInfo struct, is that a lot of tiles will have identical info, so we only have to store the info once, and tiles can share the info. This means that whenever the info of a tile changes, the indices will have to be changed to point to the correct info (which might be added to LI or BI if it isn't there yet).
We will need to keep a hashmap that will allow us to easily find a given info in the LI and BI arrays.
struct {
uint8 altitude:5;
uint8 cliff_height_of_northern_tile:3; //give that thing a sane name
} grid [MAPSIZEX+1][MAPSIZEY+1];
typedef struct MapInfo {
uint16 BuildInfo;
uint16 index;
uint8 generic_counter; //tick counter for a number of options
uint8 generic_status; //status byte
uint8 LandscapeInfo;
uint8 owner;
uint16 next; //points to next MapInfo of the same X,Y
};
typedef struct LandscapeInfo{
uint16 ref_count;
uint8 type; //for landscape info and building info
union {
struct {
uint8 type:4; //bareland grass, snow, desert rocks and stuff
uint8 hedge_SW:3;
uint8 hedge_SE:3;
uint8 amount:2; //amount of snow and desert.
//counter in main map info
} barren;
struct {
uint8 type:3;
uint8 part:4; //for the canal locks
} water;
struct {
uint8 type:4;
uint8 dir:2;
uint8 section:1; //End part or middle part, do we need this?
uint8 height:5;
} bridge;
struct {
/* ask blathijs for details */
/* this takes the tunnels or subground structures later on*/
// suggestion
uint8 height:5;
uint8 type:3; //8 different types of supports, depending on year-in-game
} support;
};
};
typedef struct BuildInfo {
uint8 ref_count;
uint8 type; //for landscape info and building info
union {
struct {
uint8 type;
//construction status in the main status byte
} industry;
struct {
uint16 part:7;
uint16 type:4;
uint16 track_type:3;
} station;
struct {
uint8 dir:1;
uint8 track_type:3;
} checkpoint;
struct {
uint8 dir:2;
uint8 track_type:3;
//what about hangars and ship depots here?
} depot;
struct {
uint8 transport:2;
uint8 dir:2;
uint8 track_type:2;
} tunnel;
struct {
uint8 dir:1;
} canal;
struct {
uint8 tracks:6;
uint8 track_type:2;
struct {
uint8 presentA:2;
uint8 presentB:2;
uint8 typeA:2;
uint8 typeB:2; //for the second signal in the tile
uint8 semaphoreA:1;
uint8 semaphoreB:1; //second signal in the tile
} signal;
} rail;
struct {
uint8 type:2;
uint8 snow_or_desert:1;
union {
struct {
uint8 pieces; //8 bits if we want to have diagonal stuff some day
} road;
struct {
uint8 road_owner;
uint8 dir:1; //we may need more bits if we have diagonal roads
uint8 track_type:2;
} crossing;
};
} road;
struct {
uint8 type;
struct {
uint8 pos:7;
uint8 moving:1;
uint8 dest:6;
} lift;
} town;
struct {
uint8 type;
uint8 ground:2; //what the fuck is in here?
uint8 count:2;
uint8 growth:3;
} trees;
struct {
uint8 type;
} field;
struct {
uint8 type:7;
uint8 part:4;
} unmovable;
};
} BuildInfo;
MapInfo _map[MAPSIZEX][MAPSIZEY];
MapInfo _extra[MAPSIZEX * 10];
LandscapeInfo LI[255];
BuildInfo BI[65536];
#include <stdio.h>
#define MAPSIZEX 1024
#define MAPSIZEY 1024
typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned long uint32;
typedef struct barren_t {
uint8 type:4; //Bare Land, grass, snow, desert, rocks and and
uint8 amount:2; //amount of snow
uint8 counter:2; //is this large enough? how often will it be incremented?
//put the hedge somewhere else maybe?
uint8 hedge_SW:3;
uint8 hedge_SE:3;
} barren_t;
typedef struct water_t {
//FIXME - compare to canal_t
uint8 type:3;
uint8 part:4; //for the canal locks
} water_t;
typedef struct bridge_t {
uint8 type:4; //type of the bridge, e.g. wooden, concrete, tubular
uint8 dir:2; //direction, we want to allow more than just two in the future
uint8 section:1; //is it a middle part, or a "endcap"? endcaps will not be needed for cliffs maybe
} bridge_t;
typedef struct support_t {
//Blathis needs to detail this
uint8 type:4; //different types of support, also depending on year
} support_t;
typedef struct industry_t {
uint8 type; //type of the industry
uint8 index;
uint8 built:1;
uint8 stage:2;
uint8 counter:3;
} industry_t;
typedef struct station_t {
uint16 index; //index of the station
uint16 part:7; //FIXME - dunno .. airport stuff maybe??
uint16 type:4; //FIXME - dunno this either, possibly type of vehicles served
uint16 track_type:3;
} station_t;
typedef struct checkpoint_t {
uint8 dir:1; //direction
uint8 type:1; //road or rail if we want road checkpoints later on
uint8 track_type:3; //rail, electric rail, monorail, trams, maglev ...
} checkpoint_t;
typedef struct depot_t {
uint8 dir:2; //direction
uint8 type:1; //road or rail?
uint8 track_type:3; //rail, maglev ....
} depot_t;
typedef struct tunnel_t { //This might end up in the support_t stuff one day
uint8 type:2; //road or rail
uint8 dir:2; //direction
uint8 track_type:3; // well .. you got the point
} tunnel_t;
typedef struct canal_t {
uint8 dir:1;
uint8 type:1; //canal or lock
uint8 part:3; //part of the lock
uint8 status; //if we want to have REAL locks sometime, we need
// astatus of the doors/lift
} canal_t;
typedef struct signal_t {
uint8 present:2; //what signals are found
uint8 type:3; //type of signals/presignals, maybe Advance later on
uint8 semaphore:1; //is it a semaphore?
uint8 status:2; //status of the signal
} signal_t;
typedef struct track_t {
uint8 tracks; //which tracks are present
uint8 track_type; //what type of track
signal_t signal[2]; //signals on the tile
} track_t;
typedef struct tram_t {
//void currently
} tram_t;
typedef struct road_t {
uint8 type:2; //type of the road (when is it used)?
uint8 pieces; //roads which are present in the tile
} road_t;
typedef struct crossing_t {
uint8 road_owner;
uint8 dir:1; //do we want to be more flexible in the future
uint8 track_type:3;
} crossing_t;
typedef struct lift_t {
uint8 pos:7; //position
uint8 moving:1; //is it moving?
uint8 dest:6; //where is it going to?
} lift_t;
typedef struct town_t {
uint8 type;
uint8 stage:2;
uint8 counter:3;
lift_t lift;
} town_t;
typedef struct trees_t {
uint8 type;
uint8 counter:4;
uint8 count:2;
uint8 growth:3;
} trees_t;
typedef struct fields_t {
uint8 type;
uint8 counter:5;
uint8 state:3; //do we need this stuff here
} fields_t;
typedef struct unmovable_t {
uint8 type;
uint8 part;
} unmovable_t;
typedef struct {
uint8 altitude_N; //NO BITPACKING
uint8 altitude_S; //NO BITPACKING
uint8 altitude_E; //NO BITPACKING
uint8 altitude_W; //NO BITPACKING
uint8 owner;
uint8 groundtype:4;
uint8 buildtype:4;
uint16 next;
union {
barren_t barren;
water_t water;
bridge_t bridge;
support_t support;
} ground;
union {
industry_t industry;
station_t station;
checkpoint_t checkpoint;
depot_t depot;
tunnel_t tunnel;
canal_t canal;
track_t track;
tram_t tram;
road_t road;
crossing_t crossing;
town_t town;
trees_t trees;
fields_t fields;
unmovable_t unmovable;
} build;
} Tile;
Tile _map[MAPSIZEX][MAPSIZEY];
int main ( void )
{
printf("Tile: %d\n",sizeof(_map[0][0]));
printf("|-- ground: %d\n",sizeof(_map[0][0].ground));
printf("|-- build: %d\n",sizeof(_map[0][0].build));
printf("-----------------------------------\n");
printf("Barren: %d\n",sizeof(barren_t));
printf("Water: %d\n",sizeof(water_t));
printf("Bridge: %d\n",sizeof(bridge_t));
printf("Support: %d\n",sizeof(support_t));
printf("-----------------------------------\n");
printf("Industry %d\n",sizeof(industry_t));
printf("Station %d\n",sizeof(station_t));
printf("Checkpoint %d\n",sizeof(checkpoint_t));
printf("Depot %d\n",sizeof(depot_t));
printf("Tunnel %d\n",sizeof(tunnel_t));
printf("Canal: %d\n",sizeof(canal_t));
printf("Tracks %d\n",sizeof(track_t));
printf("Trams %d\n",sizeof(tram_t));
printf("Road: %d\n",sizeof(road_t));
printf("Crossing: %d\n",sizeof(crossing_t));
printf("Town: %d\n",sizeof(town_t));
printf("Trees: %d\n",sizeof(trees_t));
printf("Fields: %d\n",sizeof(fields_t));
printf("Unmovable: %d\n",sizeof(unmovable_t));
return 0;
}