Solution for big size of array

[Mossar]

Firsteval look at the screenshots.

http://oi39.tinypic.com/15mzev5.jpg
http://oi44.tinypic.com/23j4s9c.jpg

Ok so this is normal platform game but additionally you can draw something on a screen with your mouse and you can use it as a landing, shield, barrier, etc. On the screens you can see that you can jump on it.

The problem is algorithm which do that lines. Every line contains hundred of points which are done with sf::Shape:

Image[BarrierCounter] = new Shape(sf::Color::Black, 3, 3);
 

Of course Shape is my own Class which has sf::Shape in it.

As I said every line contains on average two hundred of 3px:3px points (of course you can do a line or circle or what you want with thousand points for example but I want to describe a problem). It means that if I have array with 2000 elements I can draw ~10 lines. Of course I want to make that amount bigger. And now there is a problem because I can't do array with bigger amount because there is a problem with graphic card memory, I think. I read that this is connected with many calls of draw function.

So what should I do to avoid it, to make possible creating a lot of lines. VertexArray? Or what?

[Nexus]

First, you should reduce the number of points. The geometric objects in your image are almost straight, thus they don't need many points for the approximation. When you draw a platform, define a minimum distance to the last point drawn before you add a new one. That's also the way I drew waypoints in my game Airport. The reduction of geometry objects doesn't only help you for rendering, but it will also speed up game logic, most notably collision detection.

On SFML side, draw lines between the points, instead of points themselves. You could have a look at custom sf::ConcaveShape. Or even sf::VertexArray, but I would keep things simple until you really need the flexibility or performance.

And you should definitely not use new and delete.

[Not so important] If you are already given the points, there are many options to gather them together; you can start with a line that fits a set of points using least-squares approximation, more elaborate approaches go towards spline interpolation or even the field of segmentation in machine learning (just to mention a few keywords).

[Mossar]

Thank you for your reply

First, you should reduce the number of points. The geometric objects in your image are almost straight, thus they don't need many points for the approximation. When you draw a platform, define a minimum distance to the last point drawn before you add a new one.

I thought about it, this is a little harder, but I won't learn anything if I don't do more difficult things I still don't know if I want to be a programmer or graphic designer but I really want to be better programmer so I have to try it. But there is one problem for me. We can imagine that there is player who draw something very weird and lines are very crooked. In that case approximation will help of course but not very much. I will implement that idea, but I'm not sure if it solves a problem in 100%. Will using approximation + ,for example, VertexArray give me enough effect?

On SFML side, draw lines between the points, instead of points themselves. You could have a look at custom sf::ConcaveShape. Or even sf::VertexArray, but I would keep things simple until you really need the flexibility or performance.

I must read something about that ConcaveShape because I don't know what is it. This is my second game ever and second game in SFML and as I can see I didn't know every element of this great library.

And you should definitely not use new and delete.

Me and my friends from University, we always say that pointers are not nice Thank you for confirming Seriously, nice pdf, thanks

[FRex]

I'm assuming you're only drawing circles that have 3 points each and same radius, if not the instruction would need adjusting:
1. put points as float pairs into std::vector or something(maybe add radius or color if you need to customize that)
2. make static array of vertices so you won't have to allocate one each frame
3. each frame start setting vertices in that static array to proper value so that every three are a circle around pair in that list of pairs from point 1(can also discard using points outside the screen+radius bounding rectangle here)
4. draw that vertex as sf::Triangles vertex array when it's full or when you run out of float pairs
5. repeat until done with all float pairs

Shape has lots of variables that you don't seem to use here and it wastes several hundred bytes and one draw after two or three virtual function calls per instance. This may seem to take more CPU to build vertex tables each time but it can be optimized with constants so it's just few bytes and float additions per each point and really few draw calls, as opposed to hundreds of bytes, two or three virtual function calls per point and hundreds of draw calls you're doing now.

[Mossar]

I'm assuming you're only drawing circles that have 3 points each and same radius, if not the instruction would need adjusting:
1. put points as float pairs into std::vector or something(maybe add radius or color if you need to customize that)
2. make static array of vertices so you won't have to allocate one each frame
3. each frame start setting vertices in that static array to proper value so that every three are a circle around pair in that list of pairs from point 1(can also discard using points outside the screen+radius bounding rectangle here)
4. draw that vertex as sf::Triangles vertex array when it's full or when you run out of float pairs
5. repeat until done with all float pairs

I am not sure if I understand it well but if I understand it well it will be good idea in my opinion. I'm drawing only RectangleShapes which are 3px by 3px. A lot of them. And you propose me btter idea of drawing it with a VertexArray arround the points from another array containing coordinates of points. Using sf::Triangles.

And I can optimize it (using approximation) with sf::TrianglesStrip? Is it good approach?

[FRex]

You can draw quads too, if all you want is just drawing tons of points there is no need for anything else. Don't actually use vertex array because it's dynamic, just use C array or std::array of vertices that is like 400 or 800 or other multiple of amount of vertices you have per point.
Super messy pseudocode, you can make offsets up to left and right constants and access .x and .y of vertices directly and set color to all black beforehand.

Code: [Select]

for each point in points:
 if not point in screen skip
 vertices[i++].position=point+offset_up_left;
 vertices[i++].position=point+offset_down_left;
 vertices[i++].position=point+offset_down_right;
 vertices[i++].position=point+offset_up_right;
 if i==vertices size draw_quads_and_set_i_to_0
but don't forget to draw last partially filled array too.

Edit: Like this: i should be zero before the loop and half_radius should be half of your desired radius like 1.5f if you want 3x3 squares for points.

    for(auto it=points.begin();it!=points.end();++it)
    {
       
        vertices[i].position.x=it->x-half_radius;
        vertices[i++].position.y=it->y-half_radius;
       
        vertices[i].position.x=it->x-half_radius;
        vertices[i++].position.y=it->y+half_radius;
       
        vertices[i].position.x=it->x+half_radius;
        vertices[i++].position.y=it->y+half_radius;
       
        vertices[i].position.x=it->x+half_radius;
        vertices[i++].position.y=it->y-half_radius;
       
        if(i==vertices.size())
        {
            render_window.draw(vertices,i,sf::Quads);
            i=0;
        }
    }
    render_window.draw(vertices,i,sf::Quads);//last partially fileld batch

This should be much faster and much much less memory consuming than what you're doing now, because sf::Transform in shape is not checking for being ready, there are no hundreds of virtual calls and draw calls, there is no operating on pointers and the vertices object is a linear array so cache misses are minimal probably, there is just tiny bit of float subtraction and addition.

[Nexus]

make static array of vertices so you won't have to allocate one each frame

Don't use static unless you really need it; it will only cause trouble with destruction order or multithreaded environments. Here, the correct choice would be a member instead of a local variable, and make sure the object lives long enough.

I'm drawing only RectangleShapes which are 3px by 3px. A lot of them. And you propose me btter idea of drawing it with a VertexArray arround the points from another array containing coordinates of points.

Try it with lines represented by sf::RectangleShape first. The API is considerably simpler than sf::VertexArray. If you run into performance problems, you can still optimize it -- but it's likely that you know better how to build a vertex array if you have already represented the lines with rectangle shapes. You can then use sf::Lines for thin lines of single pixel thickness, or sf::Quads for thicker ones.

Don't actually use vertex array because it's dynamic, just use C array or std::array of vertices that is like 400 or 800 or other multiple of amount of vertices you have per point.

What's the problem with being dynamic? One dynamic allocation does certainly not carry weight compared with the whole vertex array logic and draw calls. You are more flexible by using sf::VertexArray, since you can set the number of vertices you actually need and not just a magic number such as 400, and you won't get into problems with limited automatic storage (stack) because of huge objects.

[FRex]

Don't use static unless you really need it; it will only cause trouble with destruction order or multithreaded environments. Here, the correct choice would be a member instead of a local variable, and make sure the object lives long enough.

static as in allocated statically(std::array<T,N>, T[N], std::vector<T> with ::resize(N) and never again pushed,resized or popped) as opposed to dynamically(std::vector<T>, new T[N])

What's the problem with being dynamic?

It draws itself so you'd have to resize it every frame(= placement new and delete every frame) to make partial last batch correct(or get a pointer and mantain count yourself, = what's the point? just get static array or use a vector you never resize if you're paranoid of stack space).
That or rebuild entire thing every frame into single array(you can't keep the quads because there is visibility culling for points), which implies thousands of placement new for sf::Vertex and greedy memory allocations(1.5 or 2x as big as actually needed) and copies every frame because of std::vector.

[Nexus]

It's simple: Arrays are the wrong choice because they can't adapt their size. You have to specify an arbitrary upper bound on the number of elements, and if that one is still exceeded, you're lost.

That's why you take vectors. If you think the reallocations are a severe problem, use std::vector<sf::Vertex> and call reserve() initially. But they occur only once and have no continuous impact on the performance, thus I doubt sf::VertexArray is a real issue.

Just as a comparison: I'm using sf::VertexArray for particles in Thor and I refill it completely every time the particles change -- that is, every frame. There may be far more than 400 particles at the same time, yet everything works smoothly. You're overestimating the severity of a placement new operation; it amounts to a constructor call, which in turn consists of a few initializations. Apart from that, most often elements are assigned, not constructed in uninitialized space, so I don't exactly see why you're argumenting with placement new.

[Mossar]

Thank you guys.

Today I've changed it to VertexArray and I did it with an algorithm which is very similar to that written by FRex. It differs, but this is connected with the same idea.

And I decided to create my own class Primitive, Figure is a base class, Primitive and Image inherits from Figure. With that and with virtual functions and polymorphism I can check collision on primitives and sprites with the same algorithm using Figure class. I dont know, maybe that approach will give me performance problems later, but now there are no problems with it

Later I will optimize it with approximation to collect primitives into bigger primitives (maybe TriangleStrip or bigger sf::Quads). Now I have to concentrate on gameplay things and I have to draw a lot.

Thanks again