Dfyjkt

I'm developing a "false 3D" game using Python and pygame. The gfx consists only of prisms created using 2D primitives of different sizes and colors:

How the gfx of the game works:

The issue appears in the 4th point, when I want to sort walls in correct order in render queue (to decide which one is the closest one and has to be rendered first, which one is the 2nd, which one is the last etc).

Currently, to sort walls I remove all invisible ones and measure the shortest distance between player and wall. It works... but only when there is one polygon on the scene. Example (2 polygons):

I can handle this specific kind of issue but i don't know if there will be other problems in the future. My question: is there any algorithm (which works...) that can sort my walls in correct order and I will be able to render them with smile on my face?

I'm guessing we can fairly assume that the polygons do not intersect. If this is the case, we do not need to split anything. However, finding the correct order is still computationally heavy. Although one could probably come up with an incremental approach that only updates the necessary things from frame to frame.

So here is the thing. In your 2-polygon example, basing the order on the two closest points of a line does obviously not work since they have different view directions. But if you pick points with the same view direction (in an area where they overlap), you will clearly see that A is in front of B. So, what do we need to do:

First find all walls that are visible. We will create a visibility graph for these walls. So, create a graph where every wall is represented by a node. In the end, you will calculate a topological sort of this graph to get the drawing order. Now, how do we find the edges, i.e., information about what wall is in front of another? For this, first find the wall pairs that overlap (the extruded wall). You might want to use an acceleration data structure like a AABB tree to make this fast.

Then we need a 1D parametrization of the view direction. The angle between the direction and the x-axis might work pretty well (a = atan2(lineY - playerY, lineX - playerX)), although it has this annoying periodicity that you need to handle. We will now only consider the original polygon edges for the two walls (not the extruded ones). Find the 1D intervals for the two lines (e.g., line 1 is between 10° and 35° and line 2 is between 20° and 135°). If these two intervals do not overlap, you can skip this pair as their relative order does not matter. If they do, find any point in the overlapping interval (e.g. 25°), find the corresponding view direction (x = playerX + cos(25°), y = playerY + sin(25°)) and the points on the line that correspond to this direction (e.g. by calculating the intersection of the line with the view ray). Then, simply calculate the distances of the two lines along this ray. It does not matter what point in the overlap interval you choose because the lines are linear and the original polygons do not intersect. If the distance to line 1 is smaller than the distance to line 2, add a directed edge from line 1 to line 2 to the visibility graph (meaning that line 1 is in front of line 2), otherwise add the reverse edge.

Finally, calculate a topological ordering of the graph and you have your drawing order.

Option 2

Here is an alternative to the above approach that might be more efficient for a dynamic rendering. The idea is based on this publication.

First triangulate your scene, i.e., fill the voids with triangles (this needs to be done only once). Then, our visibility graph stores the triangles (not the edges). For each triangle edge that you see from the inside, add an edge from the triangle to the neighboring triangle incident to that edge. In the end, again calculate a topological sort and draw your walls in that order (skipping void triangles).

The efficiency in the dynamic case comes from the fact that you only have to do small updates to your graph. For each of the edges, you want to determine if you see them from the front or from the back. Hence, the direction of the edge will only be reversed if the view point crosses the infinite line specified by the edge. If you find all those edges (that changed direction since the last frame), you can update your graph and sort accordingly.