2d Tile Engine, Scrolling, with Dynamic Terrain/Tile/Zone Generation

Hey all. The code I've made for this project is massive, convoluted and horrifying. Of course I'll share it on request! =-D Basically this:

2D Tile Based Screen - fine.
Scrolling 2D Tile Based Screen - fine.
The problems start with the dynamically generated zones part:

Exerpt from world.h:

Code:

---


struct TileT
{
    int ID;
    int Type;
} Tile;

typedef std::vector<TileT> Row;
typedef std::vector<Row> Zone;
typedef std::map<std::string, Zone> AreaMap;

---

I construct a zone 'tag' based on the camera's World Coordinates (These could be anything (unsigned int, will switch to unsigned long if needed) so negative values are fine. Initially, if I delete all the maps in the /maps/ directory - the game takes the coordinates 0,0 to start.

example of a zone function:

Code:

---

std::string CoordsToZoneTag(mrt::Coords2i Coords, int AreaID = 1)
{
    // Generates and returns a string holding the zone tag
    // of the zone file containing the coordinates provided.
    int x = Coords.x;
    int y = Coords.y;

    char SignX = x > 0 ? 'P' : 'N';
    char SignY = y > 0 ? 'P' : 'N';

    int ax = abs(Coords.x);
    int ay = abs(Coords.y);

    std::stringstream zn;

    zn << SignX << (ax < 100 ? "0" : "") << (ax < 10 ? "0" : "") << ax;
    zn << SignY << (ay < 100 ? "0" : "") << (ay < 10 ? "0" : "") << ay;
    zn << "A"  << (AreaID  < 100 ? "0" : "") << (AreaID  < 10 ? "0" : "") << AreaID;

    return zn.str();;
}

---

It figures the tags for the 4 zones which may be on screen in part or in whole.
These will be like N001N001A001 for a screen 1 zone to the north and the west from the origin... moving on.

So then it checks the /maps/ directory for the 4 tags (after they've been changed to file paths). If it doesn't find one of them, it takes a moment to generate it with the default zero value for TileID and Type (so, basically like 001:000 would be a grass tile that's passable (ie: Not a wall, or river or w/e)

I don't think it's important, but here's the functions that generate the file, for example...

writing a zone file...

Code:

---

bool CreateZone(int zx, int zy)
{
    // Create a zone based on it's ZoneCoords.
    const std::string ZoneFileName = GenZonePath(zx, zy);

    std::ofstream outfile;
    outfile.open(ZoneFileName.c_str());
    if (!outfile) {
        std::cout << "World::CreatZone: Couldn't open zone file for creation!";
        return false;
    }
    outfile << "# ZoneFile Version 0.5" << std::endl;
    outfile << "# Area Label \"" << std::string(ZoneFileName).substr(5, 11) << "\"." << std::endl;
    outfile << "# System generated zone file: " << ZoneFileName << "\t\t(" << zx << ", " << zy << ")" << std::endl;

    // Text Files must be written left to right
    for (int y = 0; y < TILE_ROWS_Y_H; ++y)
    {
        for(int x = 0; x < TILE_COLS_X_W; ++x)
        {
            // Write the ID for tile (1,0) and Walkable Type (000)
            outfile << "001" << ":" << "000";
            if (x < TILE_COLS_X_W - 1) outfile << ": ";
        }
        outfile << std::endl;
    }
    outfile.close();
    return true;
}

---

Anyhow, in the actual processing of the movement, I move the character and if he gets too far from the camera's position, it scrolls to him, setting up a jerky kind of following. World fine for my early stage of developement.

The problem is efficiently reading the four zone object's from memory, and rending them in a timely fashion. My problem, I THINK is how I get the zones in and out of memory.

In the beginning, when the engine first loads, it will scour the maps/ directory and load ALL the *.zon files into typedef std::map<std::string, Zone> AreaMap and then during the games main loop, it will derive the 4 needed zone 'tags' from the area, and find them in the map - retrieve the zone object they are associated with and render it.

My best effort so far rending one screen with no dynamic shennannigans, was that I could render the screen nearly 300 times a second. After the dynamic hub bub was added and believe me, it was hacked in.... I'm so undisciplined. Anyhow, the fps dropped to 3 or 4, and it was horrid.

I'm re-writing now from scratch and will hopefully do better this time. The idea is that any individual tile can be modified in memory at any time, (any tile currently displayed, you don't want to edit tiles you can't see) and then with a push of F2, the entire AREA structure in memory is run through, tags are read from the zone files, or the Area map itself, zones that have changed since last load are saved again, over-writing the *.zon file, etc.

I've got all the pieces, but it's a mess.

My problem I think comes from the World Class loading it's zones into the Area Map, which I think works fine. But then maintaining a 'drawable' structre. A structure telling us what zones need to be draw in the current loop.

The angle I am working at the moment is a table of Zone Pointers, like this:
struct ZoneTableT

Code:

---

{
    ZoneTableT() : NW(nullptr), NE(nullptr), SW(nullptr), SE(nullptr)  {};
    Zone *NW;
    Zone *NE;
    Zone *SW;
    Zone *SE;

} ZoneTable;

---

In theory, this allowed me to move from a Map to a simple vector of zones - it's tanked horribly however with segfaults galore.

Code like this is not helping:

Code:

---

void UpdateZoneTable(Area& area, ZoneTableT& ZT, int x, int y)
{
    // Update the pointer of the ZoneTable
    // with reguard to the "World" vector of Zones.
    // Also known as the 'Area'
    int ax = x - 512;
    int ay = y - 384;
    int zx = ax / 1024;
    int zy = ay / 768;
    if (ax < 0) --zx;
    if (ay < 0) --zy;

    // ZoneCoords
    int NWzx = zx; int NWzy = zy;  int NEzx = zx+1; int NEzy = zy;
    int SWzx = zx; int SWzy = zy+1; int SEzx = zx+1; int SEzy = zy+1;

    Coords2i NW(NWzx, NWzy);
    Coords2i NE(NEzx, NEzy);
    Coords2i SW(SWzx, SWzy);
    Coords2i SE(SEzx, SEzy);

    Coords2i CurrZC;

    Area::iterator iter;
    for (iter = area.begin(); iter != area.end(); ++iter)
    {
        CurrZC = iter->ZoneCoord;
        if (CurrZC == NW)
            ZT.NW = &(*iter);
        if (CurrZC == NE)
            ZT.NE = &(*iter);
        if (CurrZC == SW)
            ZT.SW = &(*iter);
        if (CurrZC == SE)
            ZT.SE = &(*iter);
    }
}

---

Anyhow. Lemme re-view this post...
...
Yeah, I've lost my mind. If anyone has some stories of how they handled dynamically generated content - particularly as it applies to a 2D scrolling environment - please share.

- M

^_^

I love tile games.

Anyway, I think your problem is less the generation and more the way you are storing and referencing zones/areas/screen for display.

There is no way I'm going to look through a repository that is "massive, convoluted and horrifying". I don't anyone here will do more than offer small suggestions.

That said, if you can explain your strategy better without all the crazy and unfortunately styled code you may get better results.

Also, you may want to look into circular buffers (implemented with a simple matrix) for your display lists.

Soma

Thank you for the advice! I am also excited about tile games, and also believe the problem is the representation and access of the zones once in memory. Small suggestions like yours are all I ask for. This forum, along with Alex Allains mailing list and google, are pretty much my main resources. I specifically am wondering if anyone has advice on dynamically generated terrain (generated at runtime as needed) scrolled in 2 dimentions.

Example:
The camera is top-down, and centered over coordinates x(500), y(500) pixels.
The View is one full screen, 1024, by 768 pixels.

The camera's view's upper left coordinate would be x(-12), y(116). Which is the x coordinate minus half of the screen width, and the y coordinate minus half of the screen height.
In this situation, you'd need 4 "zones" rendered (at least partially)

The zone with an upper left coordinate of 0,0 - we'll call that NE.
Also, NW with an upper left coordinate at -1024, 0 -
Then SW and SE with upper left coords at -1024, 768
and 0, 768, respectively.

At least a piece of each of these four 'zones' must be rendered to compose the veiwable screen.

Now assume, the two southern zones had previously never been needed - and did not exist. They'd have to be created, initialized to some reasonable terrrain and later saved. But the creation and initialization would have to be on the fly during run time.

Well, there you have it. If anyone has strategies that may be applicable, I'm just happy to have some input.

I'm well into my re-write now and hope to get back with encouraging results. :)

My NEW coordinate class:

Code:

---

#ifndef COORD_H_INCLUDED
#define COORD_H_INCLUDED

//
// Copyright © 2000-2012 Matthew Tober
//
// Permission to use, copy, modify, distribute and sell this software and its
// documentation for any purpose is hereby granted without fee, provided that
// the above copyright notice appears in all copies and that both that copyright
// notice and this permission notice appear in supporting documentation.
// Matthew Tober makes no representations about the suitability of this software
// for any purpose. It is provided "as is" without express or implied warranty.
//

class Coord
{
    public:
    Coord() : x(0), y(0) {}
    Coord(int _x, int _y) : x(_x), y(_y) {}

    int x, y;

    friend bool operator==(Coord &lhs, Coord &rhs);
    friend bool operator!=(Coord &lhs, Coord &rhs);
    friend bool operator< (Coord &lhs, Coord &rhs);
    friend bool operator> (Coord &lhs, Coord &rhs);
    friend bool operator<=(Coord &lhs, Coord &rhs);
    friend bool operator>=(Coord &lhs, Coord &rhs);
};

bool operator== (Coord &lhs, Coord &rhs)
{
    return (lhs.x == rhs.x && lhs.y == rhs.y);
};

bool operator!= (Coord &lhs, Coord &rhs)
{
    return (lhs.x != rhs.x || lhs.y != rhs.y);
};

bool operator< (Coord &lhs, Coord &rhs)
{
    if (lhs.x < rhs.x) return true;
    if ((lhs.x == rhs.x) && (lhs.y < rhs.y)) return true;
    return false;
};

bool operator> (Coord &lhs, Coord &rhs)
{
    if (lhs.x > rhs.x) return true;
    if ((lhs.x == rhs.x) && (lhs.y > rhs.y)) return true;
    return false;
};

bool operator<= (Coord &lhs, Coord &rhs)
{
    if (lhs.x < rhs.x) return true;
    if ((lhs.x == rhs.x) && (lhs.y < rhs.y)) return true;
    if (lhs.x == rhs.x && lhs.y == rhs.y) return true;
    return false;
};

bool operator>= (Coord &lhs, Coord &rhs)
{
    if (lhs.x > rhs.x) return true;
    if ((lhs.x == rhs.x) && (lhs.y > rhs.y)) return true;
    if (lhs.x == rhs.x && lhs.y == rhs.y) return true;
    return false;
};

#endif // COORD_H_INCLUDED

---

O_o

Okay, let me setup a counter universe. To explain the changes would be painful, but to explain the alternative is trivial. You can decide for yourself what changes need to be made.

Pixel Screen Resolution: 768*1024
Tile Metrics: 32*32
Tile (Area) Resolution: 24*32
Zone Metrics: Dynamic*Dynamic

For fixed zone transitions (NES "The Legend of Zelda"): The fetch algorithm must be ready to load a 24*32 tile area on demand without undue delay.

For smooth (continuous) transitions (SNES "A Link to the Past"): The fetch algorithm must be ready to load either a 24*1 strip or a 1*32 strip on demand without undue delay.

To support either of these approaches loading from persistent storage must be as fast as possible. We can prefetch extra zones based on information calculated at run-time. (For example, we might fetch a quarter of a zone per full walk cycle keeping a buffer of four zones in any given direction at any given time.) We can bake zones into a format more suitable for dynamic loading. (Parsing strings and lots of operating system calls to persistent storage per frame is a performance bottleneck so we bake those easily digestible formats into fixed sized binary blocks.) We can reduce the overhead of any fetch operation by making it an iterative algorithm. (Calling one very expensive function every 60 frames cripples transition performance so we will call one very cheap function every frame.)

For the sake of simplicity, I will assume all of the above.

To support above mechanism a single fetch interface must be capable of selecting between buffered state and loading from persistent storage. Buffered state can be kept in a data structure simple enough that it can be used directly by drawing routines. Loading from persistent storage requires careful use of the operating system storage primitives, a secondary buffer, and iterative translation between the secondary buffer and the primary buffer useable for drawing. We can't use an expensive operating system storage primitive every frame so we amortize the cost of reading over multiple frames. (We instead use those primitives every several frames relying on our two buffer system and iterative algorithm to conditional process a new block every frame.) Finally, we can calculate the loading time versus drawing time as compared with walk distance to have a reasonable guess at the data we need to fetch from persistent storage.

To support dynamic generation of content for areas that have never yet existed we use a similar approach. Instead of attempting to build an area all at once during a transition frame we move to an iterative approach. As the player moves down we examine future terrain. If the terrain exists we load it with the above mechanism. If the terrain doesn't exist we create as many columns or rows as we need as derived from walk cycle duration versus walk distance to provide a new row for display when that terrain is required. (For example, if the walk cycle is 16 frames and moves down 1 tile we need to generate 1 new row of 32 tiles in 16 frames or two tiles per frame.)

With those components in place we can get either transition type without undue delay.

For fixed transitions we buffer as many tiles as necessary during other loading times (such as the player loading a save state) to provide as many frames for work as we need to fetch (newly created or loaded from persistent storage) a new area for display. So, for example, we buffer a 4*4 area of 24*32 tiles of the starting zone on game start and as the player moves more in a given direction we feed that information to our fetch algorithm; the fetch algorithm examines walk cycle and distance and determines that at speed the player will cross the buffer line for the fixed transition in 48 walk cycles or 768 frames; buffering is then a trivial function of conditionally fetching 4 tiles every tile of movement beyond the adjusted fetch point which is updated for "back and forth" travel.

For smooth transitions we use almost the same approach. The most significant difference is how buffer distance and fetching is calculated. If the walk cycle, for example, moves 4 pixels in 4 frames that warrants loading only one tile fetch for buffering every 4 frames of movement beyond the adjusted fetch point keeping the buffer full forever.

Soma

=D Thank you so much for your time Phantomotap - I'm getting there.

Well, I don't have a good fetch from "persistent storage/load to memory - save to persistent storage/unload from memory" algorithm yet. But I read your post and reworked some things in a more "proof of concept" format. (I got rid of my 192 tile terrain sprite sheet and fabricated a simple 4 block sheet for example) Here is what I have so far:

I use only the SFML library, and C++11 settings on GCC so my vector<vector>> syntax is nice. Nothing way out in left field here:

NOTE: I grant permission for the user of this forum to use this code in any way shape or form serving educational purposes.

NOTE: If you compile this, tap 'minus' a few times to zoom out, then use WASD to move around a bit. You'll notice my 'culling' algorithm has a bug that culls properly on the North, east and South sides - but that the western edge culls in large 'chunks' 32 tiles wide. This bug is stalling my progress towards more of your idea's being implemented - but I've been over the math for 2 hours and can't find it.

main.cpp

Code:

---

#include <SFML/Graphics.hpp>
#include <iostream>
#include <vector>
#include "coord.h"
#include "zone.h"
#include "area.h"

using namespace std;
using namespace sf;

int main()
{
    // Create the main window
    sf::RenderWindow App(sf::VideoMode(1024, 768), "2D Tile Engine");

    // Load a sprite to represent the camera
    Image CamImage(32, 32, Color(255, 0, 0, 128));
    Sprite Cam(CamImage);


    // Build the Terrain Sprites
    Image BlackImage(32, 32, Color(0, 0, 0));
    Sprite Black(BlackImage);
    Image GreenImage(32, 32, Color(0, 255, 0));
    Sprite Green(GreenImage);
    Image BlueImage(32, 32, Color(0, 0, 255));
    Sprite Blue(BlueImage);
    Image BrownImage(32, 32, Color(150, 75, 0));
    Sprite Brown(BrownImage);

    // Build the Terrain Vector
    vector<Sprite> Terrain;
    Terrain.push_back(Black);
    Terrain.push_back(Green);
    Terrain.push_back(Blue);
    Terrain.push_back(Brown);

    // Build Start Area
    Area MyArea;

    for (int i = -4; i < 4; ++i)
    {
        for (int j = -4; j < 4; ++j)
        {
            Zone TempZone;
            TempZone.Create(Coord(i, j));
            MyArea.Zones.push_back(TempZone);
        }
    }

    // Key Array
    vector<bool> KeyArray(512, false);

    // The view
    Coord CamPos(512, 384);
    Vector2f Center(512, 384);
    Vector2f HalfSize(512, 384);
    View MyView(Center, HalfSize);
    App.SetView(MyView);
    float Speed(500.0);

    // Start the game loop
    while (App.IsOpened())
    {
        // Process events
        sf::Event Event;
        while (App.GetEvent(Event))
        {
            // Close window : exit
            if (Event.Type == sf::Event::Closed) App.Close();
            if (Event.Type == sf::Event::KeyPressed) KeyArray[Event.Key.Code] = true;
            if (Event.Type == sf::Event::KeyReleased) KeyArray[Event.Key.Code] = false;
        }

        float Offset = Speed * App.GetFrameTime();

        if (KeyArray[sf::Key::Escape]) App.Close();
        if (KeyArray[sf::Key::W]) CamPos.y -= Offset;
        if (KeyArray[sf::Key::S]) CamPos.y += Offset;
        if (KeyArray[sf::Key::A]) CamPos.x -= Offset;
        if (KeyArray[sf::Key::D]) CamPos.x += Offset;
        if (KeyArray[sf::Key::Add]) MyView.Zoom(1.101f);
        if (KeyArray[sf::Key::Subtract]) MyView.Zoom(0.899f);

        // Clear screen
        App.Clear();

        // DRAW
        MyView.SetCenter(CamPos.x, CamPos.y);
        Cam.SetPosition(CamPos.x, CamPos.y);

        MyArea.Draw(App, CamPos, Terrain);
        App.Draw(Cam);

        // Update the window
        App.Display();
    }
    return EXIT_SUCCESS;
}

---

area.h

Code:

---

#ifndef AREA_H_INCLUDED
#define AREA_H_INCLUDED

//
// Copyright © 2000-2012
// Matthew Tober
//
// Permission to use, copy, modify, distribute and sell this software and its documentation for any
// purpose is hereby granted without fee, provided that the above copyright notice appears in all
// copies and that both that copyright notice and this permission notice appear in supporting
// documentation. Matthew Tober makes no representations about the suitability of this software for
// any purpose. It is provided "as is" without express or implied warranty.
//

#include <SFML/Graphics.hpp>
#include <iostream>
#include "zone.h"

class Area
{
    public:
        Area() : ID(0), Zones(0) {};
        int ID;
        std::vector<Zone> Zones;
        void Draw(sf::RenderWindow &Screen, Coord Cam, std::vector<sf::Sprite>& Terrain);
};

void Area::Draw(sf::RenderWindow &Screen, Coord Cam, std::vector<sf::Sprite>& Terrain)
{
    static float infotimer = 0.0;
    static bool info = false;

    using namespace std;

    infotimer += Screen.GetFrameTime();
    if (infotimer > 1.0)
    {
        info = true;
        infotimer = 0.0;
    }


    sf::Sprite TempSprite;
    std::vector<Zone>::iterator iter = Zones.begin();
    for (iter = Zones.begin(); iter != Zones.end(); ++iter)
    {
        // For each Zone:
        for (int y = 0; y < TileRowsY; ++y)
        {
            for (int x = 0; x < TileColsX; ++x)
            {
                //counter++;
                float fx = (iter->ZonePos.x * 1024.0) + (iter->Data[y][x].Pos.x * 32.0);
                float fy = (iter->ZonePos.y *  768.0) + (iter->Data[y][x].Pos.y * 32.0);
                if (info)
                {
                    cout << "Fx,y: " << fx    << ", " << fy;
                    cout << "Cam : " << Cam.x << ", " << Cam.y;
                    cout << " FPS: " << (1.0f / Screen.GetFrameTime()) << endl;
                    info = false;
                }
                if ( false
                    || fx < (Cam.x - 512)
                    || fx > (Cam.x + 480)
                    || fy < (Cam.y - 384)
                    || fy > (Cam.y + 352)
                    ) break;
                int id = iter->Data[y][x].ID;
                TempSprite = Terrain[id];
                TempSprite.SetPosition(fx, fy);
                Screen.Draw(TempSprite);
            }
        }
    }
}
#endif // AREA_H_INCLUDED

---

zone.h

Code:

---

//
// Copyright © 2000-2012
// Matthew Tober
//
// Permission to use, copy, modify, distribute and sell this software and its documentation for any
// purpose is hereby granted without fee, provided that the above copyright notice appears in all
// copies and that both that copyright notice and this permission notice appear in supporting
// documentation. Matthew Tober makes no representations about the suitability of this software for
// any purpose. It is provided "as is" without express or implied warranty.
//

#ifndef ZONE_H
#define ZONE_H

#include <vector>
#include "tile.h"
#include <iostream> // debug purposes
#include <cstdlib> // random

const int TileColsX = 1024/32;
const int TileRowsY = 768/32;

typedef std::vector<Tile> Row;

class Zone
{
    public:
        // Ctor
        Zone() : ZonePos(0,0), Data(0) {};
        // Data
        Coord ZonePos;
        std::vector<Row> Data;
        // Functions
        void Create(Coord Origin);
};

void Zone::Create(Coord Origin)
{
    int counter = 0;
    ZonePos = Origin;
    Data.clear();
    std::vector<Tile> NewRow;
    for (int y = 0; y < TileRowsY; ++y)
    {
        NewRow.clear();
        for (int x = 0; x < TileColsX; ++x)
        {
            Tile NewTile;
            NewTile.ID = (rand()%3)+1;
            NewTile.Type = 0;
            NewTile.Pos.x = x;
            NewTile.Pos.y = y;
            //std::cout << x << "/" << y << std::endl;
            NewRow.push_back(NewTile);
            ++counter;
        }
        Data.push_back(NewRow);
    }
}


#endif // ZONE_H

---

tile.h

Code:

---

#ifndef TILE_H_INCLUDED
#define TILE_H_INCLUDED

//
// Copyright © 2000-2012
// Matthew Tober
//
// Permission to use, copy, modify, distribute and sell this software and its documentation for any
// purpose is hereby granted without fee, provided that the above copyright notice appears in all
// copies and that both that copyright notice and this permission notice appear in supporting
// documentation. Matthew Tober makes no representations about the suitability of this software for
// any purpose. It is provided "as is" without express or implied warranty.
//

#include "coord.h"

class Tile
{
    public:
        Tile() : ID(0), Type(0), Pos(0, 0) {}
        int ID;
        int Type;
        Coord Pos;
};

#endif // TILE_H_INCLUDED

---

coord.h

Code:

---

#ifndef COORD_H_INCLUDED
#define COORD_H_INCLUDED

//
// Copyright © 2000-2012 Matthew Tober
//
// Permission to use, copy, modify, distribute and sell this software and its
// documentation for any purpose is hereby granted without fee, provided that
// the above copyright notice appears in all copies and that both that copyright
// notice and this permission notice appear in supporting documentation.
// Matthew Tober makes no representations about the suitability of this software
// for any purpose. It is provided "as is" without express or implied warranty.
//

class Coord
{
    public:
    Coord() : x(0.0), y(0.0) {}
    Coord(float _x, float _y) : x(_x), y(_y) {}

    float x, y;

    friend bool operator==(Coord &lhs, Coord &rhs);
    friend bool operator!=(Coord &lhs, Coord &rhs);
    friend bool operator< (Coord &lhs, Coord &rhs);
    friend bool operator> (Coord &lhs, Coord &rhs);
    friend bool operator<=(Coord &lhs, Coord &rhs);
    friend bool operator>=(Coord &lhs, Coord &rhs);
};

bool operator== (Coord &lhs, Coord &rhs)
{
    return (lhs.x == rhs.x && lhs.y == rhs.y);
};

bool operator!= (Coord &lhs, Coord &rhs)
{
    return (lhs.x != rhs.x || lhs.y != rhs.y);
};

bool operator< (Coord &lhs, Coord &rhs)
{
    if (lhs.x < rhs.x) return true;
    if ((lhs.x == rhs.x) && (lhs.y < rhs.y)) return true;
    return false;
};

bool operator> (Coord &lhs, Coord &rhs)
{
    if (lhs.x > rhs.x) return true;
    if ((lhs.x == rhs.x) && (lhs.y > rhs.y)) return true;
    return false;
};

bool operator<= (Coord &lhs, Coord &rhs)
{
    if (lhs.x < rhs.x) return true;
    if ((lhs.x == rhs.x) && (lhs.y < rhs.y)) return true;
    if (lhs.x == rhs.x && lhs.y == rhs.y) return true;
    return false;
};

bool operator>= (Coord &lhs, Coord &rhs)
{
    if (lhs.x > rhs.x) return true;
    if ((lhs.x == rhs.x) && (lhs.y > rhs.y)) return true;
    if (lhs.x == rhs.x && lhs.y == rhs.y) return true;
    return false;
};

#endif // COORD_H_INCLUDED

---

O_o

Not everyone has SDL, and most will not take the time to glue the source together.

Find yourself a file drop and upload a binary.

If you want most regulars to take a look you should also consider a certificate from a known virus engine or a link to the scanned file at Jotti.

Soma

Good Call! http://dl.dropbox.com/u/38587998/2DTileEngine It's Linux Binary. Jotti's down for maintenance, but the only dangerous thing about my programs is terrible formatting. :)
If anyone needs a windows version, here's the source's in zip format http://dl.dropbox.com/u/38587998/2DTileEngine.zip (don't tell anyone I have non-FOSS shyte on my system! lol Windows people don't like tar.bz2's) IF there's demand (and this is my chance to be ASSASSIN'S CREED big, I can prolly compile a windows version on a... uh... friend's computer.

Edit: I just wanted to thank you again, it's darn difficult to learn c++ and such informally, and I am always greatful for -any- help -- however -- this kind of tangible, dedicated, thoughtful teaching is especially praise worthy. Thank you Phanto!!! Oh, and the binary's and source are from my latest iteration, and feature a 50x50screen world! It runs at 80fps on my system - so for... 78,600 32x32 tiles every loop, that's not bad! Of course, after adding any real substance, the fps will drop to negative 4.2 predicatably.

I can't compile this as I don't have a C++ compiler to hand, but looking through the code you seem to do a lot of duplicate assignment, like:-

Code:

---

auto iter = Zones.begin();
for (iter = Zones.begin(); ...

---

But from a profiling perspective, the problem is definately in Area:: Draw.

This particular roadblock - the failure to cull the western edge of the viewable screen.

I spent 18 hours looking for a math error. An off-by-one, or perhaps a float-to-int convertion someplace - but no matter what - all the math checked out. It was a simple logic error. All the math WAS right, but the logic in the culling was warped.

I replaced the

Code:

---

if ( false || fx < (Cam.x - 512) || fx > (Cam.x + 480) ||
 fy < (Cam.y - 384) || fy > (Cam.y + 352)) break;

---

with a logic waterfall setup and it worked flawlessly. It's slow as shyte now, but it's solid. After I optimize it - we move on the Phantomop-inspired Loading/Unloading fetching issue.

It's 8am, I'm going to catch some sleep =D So Awesome. Can't wait to hack some more.

The Corrected (but not optimized) Area.Draw function:

Code:

---

void Area::Draw(sf::RenderWindow &Screen, Coord Cam, std::vector<sf::Sprite>& Terrain, std::vector<sf::String>& Messages)
{
    std::stringstream ss;
    sf::String Text;
    sf::Sprite TempSprite;
    std::vector<Zone>::iterator iter = Zones.begin();
    for (iter = Zones.begin(); iter != Zones.end(); ++iter)
    {
        int ZoneOffsetX = iter->ZonePos.x * 1024;
        int ZoneOffsetY = iter->ZonePos.y *  768;
        // For each Zone:
        for (int y_counter = 0; y_counter < TileRowsY; ++y_counter)
        {
            for (int x_counter = 0; x_counter < TileColsX; ++x_counter)
            {
                int TilesXOffset = iter->Data[y_counter][x_counter].Pos.x * 32;
                int TilesYOffset = iter->Data[y_counter][x_counter].Pos.y * 32;

                int target_x = ZoneOffsetX + TilesXOffset;
                int target_y = ZoneOffsetY + TilesYOffset;

                if (target_x > (Cam.x - 512))
                    if (target_x < (Cam.x + 512))
                        if (target_y > (Cam.y - 384))
                            if (target_y < (Cam.y + 384))
                            {
                                TempSprite = Terrain[iter->Data[y_counter][x_counter].ID];
                                TempSprite.SetPosition(target_x, target_y);
                                Screen.Draw(TempSprite);
                            }
            }
        }
    }
    ss << "FPS: " << (1.0f / Screen.GetFrameTime()) << "\nPosition: " << static_cast<int>(Cam.x) << ", " << static_cast<int>(Cam.y);
    Text.SetText(ss.str());
    Messages.push_back(Text);
    ss.str("");
}

---

The final optimized Area.Draw: (Comments encouraged)

Code:

---

void Area::Draw(sf::RenderWindow &Screen, Coord Cam, std::vector<sf::Sprite>& Terrain, std::vector<sf::String>& Messages)
{
    static bool DrawTile;
    static std::stringstream ss;
    static sf::String Text;
    static sf::Sprite TempSprite;
    int CamZoneX = Cam.x / 1024;
    int CamZoneY = Cam.y / 768;
    if (Cam.x < 0) --CamZoneX;
    if (Cam.y < 0) --CamZoneY;
    for (std::vector<Zone>::iterator iter = Zones.begin(); iter != Zones.end(); ++iter)
    {
        if ((abs(iter->ZonePos.x - CamZoneX) > 2) || ( abs(iter->ZonePos.y - CamZoneY) > 2)) continue;

        int ZoneOffsetX = iter->ZonePos.x * 1024;
        int ZoneOffsetY = iter->ZonePos.y *  768;
        // For each Zone:
        for (int y_counter = 0; y_counter < TileRowsY; ++y_counter)
        {
            for (int x_counter = 0; x_counter < TileColsX; ++x_counter)
            {
                int TilesXOffset = iter->Data[y_counter][x_counter].Pos.x * 32;
                int TilesYOffset = iter->Data[y_counter][x_counter].Pos.y * 32;

                int target_x = ZoneOffsetX + TilesXOffset;
                int target_y = ZoneOffsetY + TilesYOffset;

                DrawTile = true;

                if (target_x < Cam.x - 544) DrawTile = false;
                else if (target_x > Cam.x + 512) DrawTile = false;
                else if (target_y < Cam.y - 416) DrawTile = false;
                else if (target_y > Cam.y + 384) DrawTile = false;

                if (DrawTile)
                {
                    TempSprite = Terrain[iter->Data[y_counter][x_counter].ID];
                    TempSprite.SetPosition(target_x, target_y);
                    Screen.Draw(TempSprite);
                }
            }
        }
    }
    ss << "FPS: " << static_cast<int>(1.0f / Screen.GetFrameTime());
    ss << "\nPosition: " << static_cast<int>(Cam.x) << ", " << static_cast<int>(Cam.y);
    ss << "\nCamZone: " << CamZoneX << ", " << CamZoneY;
    Text.SetText(ss.str());
    Messages.push_back(Text);
    ss.str("");
}

---

Around 250 FPS at the center of 300x300 area. 90,000 zones takes a few seconds to load initially, then the engine fires up and you can zip around 150 screens in any direction.

My limitation so far was my own RAM. That made sizes like 500x500 impossible to test - as a quater of a million zones makes le linux start paging to disk. (Even though I run LXDE and my OS takes 2% of my CPU) Go LXDE!
Thank you all. :)

A side note: Alot of people read, but don't post stuff! I encourage participation. I had alot of questions 2 days ago, now I have an awesome engine as a foundation to work with. Everyone who responded was supportive and everything turned out great! How can people not post?

- Matt

Considering your scale I would ditch the iterate through every element method, and set up a quadtree or oct-tree to cut the amount of checks you have to do each frame.

I would recommend you do not cull based on the edges of the screen. You should instead slide the 'view' window around the virtual world.

Code:

---

int startRow = scrollY / tileHeight;
int startCol = scrollX / tileWidth;
startRow -=1;
startCol -=1;
if (startRow < 0)
{
  startRow = 0;
}

if (startCol < 0)
{
  startCol = 0;
}

int offset = startRow * mapWidth + startCol;
int startDrawY = (scrollY - tileHeight) % tileHeight;
int startDrawX = (scrollX - tileWidth) % tileWidth;
int posX = startDrawX;
int posY = startDrawY;
int rightSide = screenWidth + cellWidth;
int bottomSide = screenHeight + cellHeight;

while (posY <bottomSide)
{
    DrawTile(posX,posY,map[offset]);
    ++offset;
    posX += cellWidth;
    if (posX > rightSide)
    {
        posX = startDrawX;
        posY += tileHeight;
        offset += mapWidth;
    }
}

---

Even though the code checks the right side of the screen it is only 1 check per tile. The code calculates where in the world map it is as well as where on the screen to start rendering. It then renders from top left to bottom right on the screen. Since you are only drawing 1 extra row and column on all sides of the screen this algorithm is extremely fast at rendering as it is.

This code does not handle tile zones....but the it could be altered just a bit to handle that. Tile zones are really just loading zones. You are loading a portion of the large tile map into the smaller version that is in memory. If it is too small you cache too much and if it is too large you waste memory.

There are several other optimizations you can do. Tile maps are quite repetitive. If the current texture is the same as the texture of the tile to be rendered then you do not need to set the texture again. As well you can do RLE on tiles. RLE can be done by following this algorithm:
1. Store a count of identical tiles in a run called tileCount
2. Store the tileID that the tileCount refers to
3. Before rendering check the tileID to render
4. If the tileID is different that the current tileID then render the previous span by drawing a quad with texture coordinates (0.0f,0.0f,tileCount,1.0f) and set tileID to the the new tileID
5. If the tileID is the same then increment tileCount and return to step 3

This algorithm has the limitation that it can only handle a run that has as many tiles that will fit on the screen + 2. The +2 is so you can scroll left / right without having empty columns. You 'could' use a quadtree to determine which zones to load but I think it is overkill.

To scroll the grid left / right you simpy translate the world matrix of the grid on X and Y by scrolX and scrollY. If there is no grid, then use the parent matrix of the tiles. However note that this is not optimal since all tiles will use the same parent matrix so storing it in every tile is a waste of memory. As you scroll the values for scrollX and scrollY will change and the code above will compute where in the map the current scrollX,scrollY is as wel as where on the screen to begin drawing which will always be some negative offset from 0,0 depending on the current values of scrollX and scrollY.

And I cannot stress this point enough but tile maps should be filled with nothing more than integers that represent tileIDs. These TileIDs can then be used to gather more data at run time. This keeps the size of the tile map extremely small and it also makes loading the map fast. You might take a hit when loading the textures into your texture manager but even that can be minimized. I see so many tile engines that try to cram a ton of data into each tile and it is a complete waste of memory.

The scheme I propose is much like a relational database.

Map - 0,1,2,4,1,5,6,2,5,6.....
Tiles
..ID - correponds to number in the Map
..TextureID - corresponds to ID in the texture manager
..AnimationID - corresponds to ID in the animation manager

Textures
..TextureID - ID of the texture and its ID in the texture manager
..TextureData - actual texture data

Animation
..AnimationID - ID of the animation and its ID in the animation manager
..TextureID collection - collection of textureID representing each frame of animation
..AnimationData

Quote:

---

Originally Posted by VirtualAce

I would recommend you do not cull based on the edges of the screen. You should instead slide the 'view' window around the virtual
world.

...

Animation
..AnimationID - ID of the animation and its ID in the animation manager
..TextureID collection - collection of textureID representing each frame of animation
..AnimationData

---

Thank you both Raigne and VirtualAce! You're suggestions are appriciated, and though I'm at the extent of my programming ability in this project - you've both shown some excellent areas to move into.

I picked up 'Beginning C++ Game Programming' by Micheal Dawson and am going to order 'Programming Game AI by Example' by Mat Buckland. Needless to say, the next time I post, I will be wealthy and -possibly- have job offers for you both. I run a tight ship, there'd be an intense interview process of course...

- MRT