Efficiently Displaying Objects?

[OverlordYertle]

So i'm programing a 2d isometric game. I'm using C++ and OpenGl. And it's been going really good, except now i've hit a problem where i can not figure out a fast technique for displaying my map. In the past two days i've come up with four or so completely different ways of storing all the objects and printing them to the screen. But i don't feel it's displaying as fast as it should.

The map is 400 x 300 units long and i made each floor image cover 10 units, giving me 1200 floor tiles.
Two days ago i was averaging around 20 fps but as of today i was able to get it up to 40 when all the tiles were being drawn simultaneously.
Alternatively i have another method that gives me between 30 - 40 fps when im moving and 300 - 400 fps when i stay still (but AI still move on screen), This method keeps track of only the items that are on the screen, but also handles items that come on screen from being off. This alternative method demonstrates to me that there must be a better way to get higher fps when i move around.

I often come to this site when i get stuck and can find articles with people who have similar problems. However i haven't really found articles on methods of tracking and displaying objects anywhere on the internet. And most of the articles i've been able to find on isometric games are either from 95 and talking about how i should probably switch over to 32bit integers =P or they're QBasic tutorials on how to draw and such. So i was wondering if anyone had any thoughts on this? or if they know a good place i could read some things about it?

Also, is 1200 floor tiles a lot? because it doesn't seem like it, especially when drawn. I think back to games such as rollercoaster tycoon 1 and 2 with their isometric drawings, they ran incredibly fast on slow computers and you could zoom out and view the entire parks which must have had thousands of floor tiles.


I'm including a link to a screenshot i took two days ago when it was running around 20 fps. Each of those tiles is a separate image.
http://img22.imageshack.us/img22/2474/texte.png

Thank you so much!

[MarauderIIC]

So, to make sure I'm on the same page:
You have a method to keep track of what is and what's not on the screen, and you do not draw what is off of the screen, and it works? (Test this by changing your #s to something that is in the screen and see if drawing is cut off)
But the way you index into your lists of stuff is so bad, it slows you down?

well, if you have your map class or whatever, you can do:

Code: Select all

#define MAP_WIDTH 400
#define MAP_HEIGHT 300
const size_t VISIBLE_WIDTH = 1024.0/32.0; //Assuming 1024x760 resolution and tile is 32x32
const size_t VISIBLE_HEIGHT = 768.0/32.0;
Tile* tiles[MAP_WIDTH][MAP_HEIGHT]; //Load all images once, then point to them
Object* objects[MAP_WIDTH][MAP_HEIGHT]; //Same, except you don't draw when you encouter a NULL.

And use your camera coordinates (ie: player at, so screen starts drawing at) to index the starting position in those arrays, and then use your screen width/tile width, screen height/tile height to know when to stop. As long as you don't mind the wasted space in the objects array, you're fine, but I think in general here that the mem cost vs cpu speed trade-off leans pretty heavily to the cpu speed side.

You could also do something like

Code: Select all

#include <vector>
using namespace std;

vector <Object*> objects;
...
sort objects by x-coordinate (or y-coordinate, whichever is 'more important') on load
...
Jump in at x-coordinate

Although I have no practice with that approach, hence the generality of it. STL has some built-in sorting algorithms, IIRC. Just provide it with an overloaded operator.

[OverlordYertle]

You understand the problem exactly!

I tried what you said with having an array of the objects and only calling the visible ones (which does work).
I use a 1D array, i was under the assumption that this was a better practice?
Although im beginning to believe i'm mistaken? Because when i tried what you advised making an array to hold the objects and filling in the between spaces with NULL and it ran at around 24 fps. However the tiles i'm currently using are 10 units in the game and when i divided the Map width and height by 10 (as well as calculating the spots to look over) the speed soared to 300fps. Which is fantastic but not as dynamic as i was hoping. I'm thinking the element access is slow?

Code: Select all

//Variables
vector<CSpriteImg*> BGTest; // Vector to hold all of the background tiles
int cMapX, cMapY; //Current map's x and y dimensions

//So rather than:
for(int i = 0; i < cMapX * cMapY; i++){
	BGTest.push_back(NULL);
}

//I have:
for(int i = 0; i < (cMapX / 10) * (cMapY / 10); i++){
	BGTest.push_back(NULL);
}

//And to call a given point at the center of my map i would have:
int point = ((centY / 10) * (cMapX / 10)) + (centX / 10);
Draw(BGTest.at(point));

I'm using a vector to hold all of the elements. And i'm wondering if myVector.at(num) is really slow access? which would explain why it's so much slower then when the numbers are divided by 10. My other thought is that i sort up and down 80 spots on the vector (and across as well), but when i divide by 10 its only 8 elements which again would be logically much faster.

[MarauderIIC]

Use [] to access vector unless you really need it to throw exceptions, yes .at() is "slow" (due to the built-in error checking).
Try a 2D vector or array and let me know how it goes. Also, you aren't pushing every frame, are you?

[OverlordYertle]

Alright i played around with it for a bit, and the 2d array seems quite a bit faster. I'm going to have to play around with it some more, but i don't think i'll have much free time till friday. The one problem i'm having is my array of object pointers. It works for the current map, but if i have multiple maps of different sizes how could i get just a regular array? Right now i've had to use a vector. And i believe i need an array pointer if i want it to be dynamic i just can not figure out how to have an array pointer of object pointers or if thats possible. The array did seem to work faster than the vector, every few seconds the vector would slow the program down for a frame where as this did not happen with the array.

I also need to work out a way to read the objects just on the edges. But since it's isometric i'm having some problems figuring out the for loop for this, to calculate along at the right angle. Right now i have it checking a square at 45 degrees. But since my view is not a perfect square and i'm checking the entire area every time this isn't very efficient.


What do you mean by pushing every frame?

[dandymcgee]

What do you mean by pushing every frame?

I'm pretty sure he meant this:

Code: Select all

BGTest.push_back(NULL);

As pushing values every frame would likely make the code very slow.

[MarauderIIC]

A vector of vectors (a 2D vector) would be easier to manage than a dynamic 2D array. Just use myVector[x][y] to access it, don't use myVector.at(x).at(y).
Also, if you're iterating through it, use

Code: Select all

vector< vector<myMapObj*> >::iterator i;
vector<myMapObj*>::iterator j;
for (i = myMapVec.begin(); i != myMapVec.end();++i) {
    for (j = i.begin();j != i.end();++j) {
        j->getAttribute(); //equivalent to myMapVec[index]->getAttribute();
        passThePointer(&(*j)); //j == ...::iterator, *j == myMapObj due to dereference overload, so &(*j) == &myMapObj == myMapObj*, I think
        //I might have this confused and passThePonter(*j) might be the one that works... actually it probably is, so yeah.
    }
}

For speed purposes. Really iterating through a 1D array is easier, and I'm not sure if that ^ works, but it should be something like that.

You could always still do myMap[MAX_X_EVER][MAX_Y_EVER], as long as your map fits in that...
A dynamic 2D array (an array of arrays) would involve dynamically allocating your sub-arrays and then dynamically allocating your main array w/ number of sub arrays, I think.

You'd wind up doing something like

Code: Select all

myYArray* myMapArray[]

Which, for both dimensions to be dynamic, would maybe wind up being something sort of like

Code: Select all

myYArray** myMapArray = new myArrayOfPointersToYArrays[NUMBER_OF_Y_ENTRIES]
myMapArray[0] = new myYArray(first column)
myMapArray[1] = new myYArray(second column)

I think.

Try using sin etc for viewing angle calculation. So you could maybe try using that for 45 degrees... or just use sqrt(2.0)/2.0f in some calculation, along with your viewing width and viewing height, ie

Code: Select all

const float ROOT_2_OVER_2 = sqrt(2.0)/2.0f;
const int SHOW_WIDTH = ceil(ROOT_2_OVER_2 * VIEW_WIDTH);
const int SHOW_HEIGHT = ceil(ROOT_2_OVER_2 * VIEW_HEIGHT);
for (int x = cameraX;x < SHOW_WIDTH;++x) {
    for (int y = cameraY; y < SHOW_WIDTH;++y) {
        draw(tile[x][y]);
    }
}

Assuming cameraX and cameraY point to the point on the map that is at the top-left of your screen. Due to Ch16 restrictions :), I can't paste code here, so hope that works.

Does that help?

[OverlordYertle]

I don't push every frame... kinda? I only push the items that have been updated. So if and item is picked up, or a character moves i tell the display to add or remove, or to update the item position. See all of my objects are serialized so keeping track of them becomes very easy and allows me to update specific items. I've also limited my world step movements to 60 times a second. So that would give me 60fps. However i'm just not hitting that.

I've had some time the past two days so i've been playing around with a lot of ideas. I updated the game to work with 2d arrays and changed all the .at to []'s
I've realized that the problem i'm having is the for loops in the display method. Yesterday i came up with this method of having a grid of all the objects as was suggested, but instead of reading every point on the field of view, i took the edges of my movements and added or removed items from the edges of the field of view to a map. This map's key was the objects id. This allowed for extremely fast adding and removal. I was seeing 300+ frames per second even when moving. The problem to this method was that none of the objects were sorted when i then displayed them, so things were behind objects they should have been in front of.

I played around with then dropping these mapped items into a vector every time the camera moved and then sorting the vector and then displaying the sorted vectors. But this caused major slow down and brought me to seeing 40 or so fps. Which is the speed i get when i read all the items in the field of view and print them.

To me 40 fps is incredibly slow for a 2d game, and i'd be blown away with the 300fps i just have no clue how i would go about dealing with the unsorted map

[OverlordYertle]

So after playing around i found that OpenGL limits the frame rate based on the display rate of a monitor. The reason i was reportedly getting over 60fps was the fps counter averaged between the times i didnt step the program and the times i did. The problem is that OpenGL is slowing down my program as it waits to draw again.

OpenGL also can not draw inside threads, it can only draw in the main loop. I have since threaded off my world movement and am getting around 500+ fps, which is wonderful but i have no idea how to relay the objects to the draw function and still be fast and thread safe about it.

one method i found that works is:

Code: Select all

void GraphicsBuffer::addCleans(vector<Clean> toAdd){
	addTemp.insert(addTemp.end(), toAdd.begin(), toAdd.end());
	if(!swappingA){
		adding = true;
		add.insert(add.begin(), addTemp.begin(), addTemp.end());
		addTemp.erase(addTemp.begin(), addTemp.end());
		adding = false;
	}
}

void GraphicsBuffer::getCleans(vector<Clean> &toGet){
	if(swappingB){return;}
	getting = true;
	toGet = get;
	get.erase(get.begin(), get.end());
	getting = false;
}

void GraphicsBuffer::step(){
	while(adding){}
	swappingA = true;
	swap = add;
	add.erase(add.begin(), add.end());
	swappingA = false;
	while(getting){}
	swappingB = true;
	get.insert(get.begin(), swap.begin(), swap.end());
	swappingB = false;
}

But this is very slow going and often times the graphics take a while to get the right opportunity. However if i make the if(swapping) statements while loops it bogs down and makes the whole program slow.

Any thoughts?

[avansc]

im not sure what the command is. but im pretty sure you can change the refresh rate.
i know when you init gl you use a string like 1280X1024X32@60


the 60 being the Hz of the monitor, you can try making that a bigger number.
also 60 fps is a lot, why dont you do game calcs during this "idle" period. i actually think you register a idle function.

ask MDK he might know more about this.

also, you can build a quad tree to quickly display and calculate only on the objects that you need to.

[OverlordYertle]

yea thats exactly what i was thinking. The problem seems to be that OpenGL doesnt give you control over the idol time. Thats why i have been trying to get it working fast between threads. I'll look into trying to possibly change the frame rate of opengl though.

[qpHalcy0n]

Spawning the movement code off to a separate thread is certainly not a bad idea. However, in response to the actual problem at hand is just masking the symptom.

The issue is that OpenGL does not have any inherent understanding of the concept of v-sync. So anytime double or triple buffering is enabled and your render calls are finalized, then the device waits to perform the swap then returns. This is where your stall is because you have not defined anything in the idle function. The reason you must use that function is because the application can not execute until the device returns. Specifying an idle function allows the device to return back to the OS that it is ok to execute those pieces of code before the swap is finished.

So, this is where OpenGL extensions come in. If you're on Windows you're going to use WGL ("wiggle"). See: SwapIntervalEXT

Code: Select all

// Define function signature   GLOBAL SCOPE  //
typedef BOOL (APIENTRY *PFNWGLSWAPINTERVALFARPROC)( int );

// Initialize func ptr  GLOBAL SCOPE //
PFNWGLSWAPINTERVALFARPROC wglSwapIntervalEXT = 0;

// Subsequent code is in Initialization time //
//Obtain supported extensions string //
LPCSTR extstr = glGetString(GL_EXTENSIONS);

// Check that function is supported //
if(strstr(extstr, "WGL_EXT_swap_control") == 0)
       return;   // device does not support this extension

// Otherwise obtain procedure address //
else
{
    wglSwapIntervalEXT = (PFNWGLSWAPINTERVALFARPROC) wglGetProcAddress("wglSwapIntervalEXT");

    // Check that function pointer was obtained //
    if(wglSwapIntervalEXT)
    {
          // Turn v-sync off //
          wglSwapIntervalEXT(0);    // A value of 1 turns it back on //
    }

}

The other method is to resort to your video card driver control panel and force v-sync off for GL.