Issues drawing after a call to std::stable_sort

[nore]

Hello, I have been working this past week to implement a feature in my program in which I can draw assets to a grid map independent of the individual locations of the tiles on-screen. I immediately noticed while drawing these assets that it would be important to sort the assets that I place (which I push on to a std::vector as I create them) so there is no strange overlapping, i.e. the assets should be sorted so that the elements with a lower x value or y value are drawn first. These ideas have been implemented simply.

Here are some images to display what I am describing:

The below depicts the ideal drawing:
https://imgur.com/a/U447hEB
This was done by simply creating assets from the top left to the bottom right, so the bitmaps would naturally overlap.

The below depicts the problem using an unsorted approach:
https://imgur.com/a/xMXHEh2

The below depicts the ideal drawing using a std::stable_sort:
https://imgur.com/a/sbS9LBz
Drawing assets from the top left to the bottom right results in no issues, the image confusion to come is not present.

The below depicts the issue present using std::stable_sort before drawing each asset's bitmap:
https://imgur.com/a/uUUZ3aU
Though an entirely different asset has been selected, it seems that drawing different patterns, i.e. not from the top left to the bottom right, results in a certain strangeness in which the bitmaps of assets become jumbled.

I am not sure what could be the cause of this issue. I have stepped through the paint event handler to ensure that created assets are sorted correctly according the the comparator:

Code: Select all

[](MapTile m1, MapTile m2){return m1.getBounds().x < m2.getBounds().x || m1.getBounds().y < m2.getBounds().y;}

and have found no issues there. I at first assumed that perhaps one of the special operators (move assignment, move construction -- how does std::stable_sort conduct its operations?) was not copying over the .pngs image path or something related that could result in an entirely different image being created upon clicking -- but this was not the issue. I even went so far as to assume that perhaps the wxGraphicsBitmap object that is used within each MapTile object could be the cause of the issue; and so I attempted to re-initialize the object after the sort for each asset before the drawing operations occur. This did not result in success.

Here I will include the relevant code within the paint event handler:

Code: Select all

vector<Layer*> layer_vector
		{
			&draw_boxes_background,
			&draw_boxes_layer1,
			&draw_boxes_layer2,
			&draw_boxes_layer3,
			&draw_boxes_layer4
		};
		if(Replot())
		{
			for(Layer* l : layer_vector)
			{
				const int layer_number = l->getLayer();
				vector<MapTile>& v = *l->getLayerVector();
				if(v.size() == 0){continue;}
				switch(layer_number)
				{
					case(0) :
					{
						for(int y{}, index{}; y < squares_per_column; ++y)
						{
							for(int x{}; x < squares_per_row; ++x)
							{
								lock_guard g{m};
								MapTile& t = v[index];
								/* How are the coordinates to be calculated with "free" assets? An "offset" member perhaps? */
								int x_coord = static_cast<float>(draw_origin.m_x + x) * static_cast<float>(scaled_tile_size);
								int y_coord = static_cast<float>(draw_origin.m_y + y) * static_cast<float>(scaled_tile_size);
								/* RANDOMIZATION OF BACKGROUND TILES */
								if(t == MapTile{}){v[index] = move(MapTile{1});}
								/* This can be simplified when compared to the bounds assignment in the MouseUp event. */
								if(!t.ImageInitialized()){t.InitializeImage(*gc);}
								t.UpdateCoordinates(x_coord, y_coord,
										scaled_tile_size * t.getOccupiedWidth(),
										scaled_tile_size * t.getOccupiedHeight(),
										*gc);
								++index;
							}
						}
						break;
					}
					case(1) :
					{
						for(int y{}, index{}; y < squares_per_column; ++y)
						{
							for(int x{}; x < squares_per_row; ++x)
							{
								lock_guard g{m};
								MapTile& t = v[index];

								int x_coord = static_cast<float>(draw_origin.m_x + x) * static_cast<float>(scaled_tile_size);
								int y_coord = static_cast<float>(draw_origin.m_y + y) * static_cast<float>(scaled_tile_size);
								/* An inequality operator for class MapTile needs to be defined. */
								if(!(t == MapTile{}) && !t.ImageInitialized()){t.InitializeImage(*gc);}
								t.UpdateCoordinates(x_coord, y_coord,
										scaled_tile_size * t.getOccupiedWidth(),
										scaled_tile_size * t.getOccupiedHeight(),
										*gc
								);
								++index;
							}
						}
						break;
					}
					case(2) :
					{
						if(layer2_sorted == false)
						{
							/* Remember constant and mutable may be used here (a std::vector of const MapTiles). */
							stable_sort(v.begin(), v.end(), [](MapTile m1, MapTile m2)
									{
										return m1.getBounds().x < m2.getBounds().x ||
										m1.getBounds().y < m2.getBounds().y;
									}
							);
							layer2_sorted = true;

							for(MapTile& m : v){m.InitializeImage(*gc);}
						}
						for(MapTile& m : v)
						{
							wxRect& r = m.getBounds();
							r.x = m.getNormalizedX() * map_width;
							r.y = m.getNormalizedY() * map_height;

							m.UpdateCoordinates(r.x, r.y,
									scaled_tile_size * m.getOccupiedWidth(),
									scaled_tile_size * m.getOccupiedHeight(),
									*gc
							);
							if(!(m == MapTile{}) && !m.ImageInitialized()){m.InitializeImage(*gc);}
						}
						break;
					}
				}
			}
			replot = false;
			redraw = true;
		}
		if(Redraw())
		{
			for(Layer* l : layer_vector)
			{
				const int layer_number = l->getLayer();
				vector<MapTile>& v = *l->getLayerVector();
				if(v.size() == 0){continue;}
				switch(layer_number)
				{
					case(0) : case(1) :
					{
						for(MapTile& m : v)
						{
							wxRect& r = m.getBounds();
							if(m.getValue() != -1 && m.isMainTile()) /* Invalidation may be added here, e.g. "&& t.update". */
							{
								gc->DrawBitmap(
											m.getGraphicsBitmap(),
											r.x,
											r.y,
											r.width,
											r.height
								);
							}
							else
							{
							}
						}
						break;
					}
					case(2) :
					{
						/* The sorted elements from the plot section are somehow reversed by this point. */
						for(MapTile& m : v)
						{
							//t.UpdateImage();
							//t.InitializeImage(*gc);
							wxRect& r = m.getBounds();
							if(m.getValue() != -1 && m.isMainTile()) /* Invalidation may be added here, e.g. "&& t.update". */
							{
								gc->DrawBitmap(
											m.getGraphicsBitmap(),
											r.x,
											r.y,
											r.width,
											r.height
								);
							}
							else
							{
							}
						}
						break;
					}
				}
			}
			redraw = false;
		}
	}
	delete gc;
	return;
}

The asset plotting and drawing occurs within case 2 under the Replot() and Redraw() functions. So, the issue lies somewhere within the coordinate between std::stable_sort and the drawing of the assets' bitmaps under the second part of the paint event handler. I notice that a sort of pattern occurs when creating the assets -- it is as if the last drawn assets "linger" before a newly selected asset is placed successfully. Placing the assets from left to right or from top to bottom results in no issue; but if I create the assets from right to left or from bottom to top, the last-placed asset carries along. For example, if I wish to create a large limestone, a small stone, a big stone, and a big tree in a row, I will instead have displayed a large limestone, another (lingering) large limestone, a small stone (it takes two clicks to place this after selecting the asset... as if the large limestone asset must be "cleared" before the small stone may be placed), another small stone, a big stone, another big stone, and finally the big tree. Without the sort, this does not occur, and stepping through the debugger shows that the tiles are in order after being sorted, but an asset with the correct name, image path, and bitmap might be drawn as the asset placed before it. The coordinates for each asset are correct, and so I am wholly unsure of what to make of this.

To finish, does anyone know of a possible source of this issue or have experience solving similar problems? For now I return to experimentation to see what may be the cause of the problem, I am sure it is something rather simple.

[doublemax]

I've read this three times and looked and the images, and i'm still not sure what exactly the issue is or what i'm supposed to look at in these images.

First of all: I think a paint event handler should just draw the current state, there shouldn't be any program logic and anything that modifies the state.

On thing that caught my eye:

Code: Select all

stable_sort(v.begin(), v.end(), [](MapTile m1, MapTile m2)
  {
    return m1.getBounds().x < m2.getBounds().x ||
    m1.getBounds().y < m2.getBounds().y;
  }

Shouldn't you check for y first when the tiles are drawn top-to-bottom and left-to-right?

[nore]

O.K., I found a lead in the move assignment and move construction operators -- the recent addition of normalized coordinates to my program resulted in these members being left behind. However, the bug is still not fixed. More reviewing is in order.

I've read this three times and looked and the images, and i'm still not sure what exactly the issue is or what i'm supposed to look at in these images.

First of all: I think a paint event handler should just draw the current state, there shouldn't be any program logic and anything that modifies the state.

On thing that caught my eye:

Code: Select all

stable_sort(v.begin(), v.end(), [](MapTile m1, MapTile m2)
  {
    return m1.getBounds().x < m2.getBounds().x ||
    m1.getBounds().y < m2.getBounds().y;
  }

Shouldn't you check for y first when the tiles are drawn top-to-bottom and left-to-right?

Thank you, I will try refactoring some of the paint event handler later -- I suppose I could concentrate some of the operations into functions. No, I don't think so -- vector logic would first paint from left to right, so I think a comparison of the x-values before y-values is correct. If two assets are placed with the same y-value then the asset on the left should be drawn first so that it appears to be behind the latter asset.

EDIT: You may be right about the comparator function, I have resolved to use

Code: Select all

stable_sort(v.begin(), v.end(), [](MapTile m1, MapTile m2)
	{
		return (m1.getNormalizedY() < m2.getNormalizedY() || m1.getNormalizedX() < m2.getNormalizedX());
	}
);

as my comparator function. This, along with the inclusion of the normalized coordinates in the move assignment and move construction operators seems to have mostly fixed the issue present; but now there is a slight overlapping issue on certain placed assets where a few pixels of a placed object seem to be behind another asset, then in front of the asset upon placing another on the map. I will have to experiment -- I cannot think of a cause other than objects being reordered during a sort.

EDIT2: Removing the logical-or expression from the comparator solved the overlapping issue.

Code: Select all

return m1.getNormalizedY() < m2.getNormalizedY()

is enough to determine overlap. I cannot discern why the sorting function would evaluate the first half of the expression some times, and the second half other times. I suppose the first comparator could result in varying sorts depending on which elements of the container are compared first, no? I will have to work on a stronger comparator.

EDIT3:

Code: Select all

return m1.getNormalizedX() < m2.getNormalizedX() && m1.getNormalizedY() < m2.getNormalizedY();

will have to work for now.