Mahjong 3D tile depth sorting

[mariogarranz]

So, I'm trying to achieve a realistic mahjong 3D tile sorting with Phaser.

Tiles are sorted on layers (the lower the layer index, the higher), and have a column and a row value as well. Every tile occupies 2 rows and 2 columns, so they can overlap horizontally and vertically with 2 tiles at the same time.

The thing is I can't find a sorting algorithm that works in all situations. I came up with this messy function that works in almost all cases:
 

if(a.row === b.row - 1 || a.row === b.row + 1){
				return a.layer.index < b.layer.index ? 1 : -1;
			} else if(a.row > b.row){
				return 1;
			} else if(a.row === b.row){
				if(a.col === b.col - 1 || a.col === b.col + 1){
					return a.layer.index < b.layer.index ? 1 : -1;
				} else {
					if( a.col < b.col - 1){
						return 1;
					} else if(a.col <= b.col){
						return a.layer.index < b.layer.index ? 1 : -1;
					} else {
						return -1;
					}
				}
			} else {
				return -1;
			}

However, when there is a tile that is covering another 4 tiles on the lower layer (one quarter of each), the whole sorting algorithm becomes unpredictable and creates weird situations.

I know the customSort function does not compare all tiles one to another, but inferes their z value with the sorting algorithm. So maybe what I'm trying to achieve is technically impossible with Phaser?

This screen shows an example game using the same graphical tile positioning.

[drhayes]

I might be misunderstanding... but do you have four layers? If not, don't you have four heights (as it were) and you could sort by that? Or, don't sort by it... just put the appropriate tiles in each layer?

If everything has to be in the same group, maybe your initial tile placement could add a "tileZ" or "majongZ" property that has 0 (highest) to 3 (lowest)? Then you could sort by that directly with no ifs.

BTW: that is some seriously beautiful art.

[Jackolantern]

Is having the tiles take up two columns what is making it so complex? Because if you look at the layout of the pieces, it seems that if you just nudged each layer except the bottom up to the upper-left, that you would then have a nice multi-dimensional array to work with. Of course then when you are rendering them, you just render each layer with an increasing offset to make them display correctly. If that would work, I think that would simplify your logic dramatically. 

[mariogarranz]

Thanks for your replies.

I forgot to mention something that's very important to this problem:  There is an animation where a tile moves vertically. This means I can't have layers (the example game image has layers) because a tile can animate vertically so it should still be drawn on top of tiles being on higher layers on columns that are to its right.

I created a sample image I'm attaching. The yellow tile is the reference one. Red tiles are the ones that should be drawn behind it. Green one is drawn on top of it. As you can see there is a tile on a superior layer that's drawn behind it. This is so because when the yellow tile moves up following the arrow direction, it should still be drawn on top of it to keep the perspective.

The picture as it is, I already solved it with the sorting algorithm added on my original post. But things get a lot weirder when tiles can be on intermediate positions and I'm starting to think it's impossible to solve with Phaser's sorting system.
 

[chg]

I really doubt it's "impossible", after all in the general case tiles are pictures (orthographic projections) of boxes, where the boxes are all non-intersecting convex hulls - thus you can more or less just sort their midpoints in 3d view space I suspect and render them from furtherest away to nearest (ie. painters algorithm).

However you do it, I suspect the view vector (the angle from which the tile sprites are shown being rendered, and by which tile sprites are offset by [at least in 2 dimensions] in successive layers) will need to be in the sorting algorithm somewhere, whether it's explicitly used (as hinted at above) or if you find some clever trick that makes it less obvious...

[Tom Atom]

Hi, if you have all tiles in one group, then solution is easy. Call customSort method on group - it takes custom sort function that is called to compare two objects and decide which will get higher in sorted list and which lower. I used this in my mahjong connect game (sbc.littlecolor.com/woodventure).

Custom sort function in it looks like this:

        sortStones(aA: Tile, aB: Tile): number {
            var a: number = aA.x + aA.y * 4096;
            var b: number = aB.x + aB.y * 4096;

            return (a > b) ? -1 : (a < b) ? 1 : 0;
        }

and I call it like this:

            // sort tiles in group
            this._tilesGroup.customSort(this.sortStones, this);

(my Tile class extends Phaser.Group)

What it does is, that it calculates "screen position" index like x + y * some_number_higher_than_number_of_columns for both tiles.

You can extend it to 3D if you keep track of your "dept" on board and change calculation to x +  y * 100 + depth * 100000 (or use any numbers that fits your needs)

[drhayes]

What about adding a fifth layer for tiles that move? Then anything in that layer would be drawn on top of everything else.

BTW, when I say "layer" I literally mean a Phaser Group. You can sort by tile's y property inside a group (like @Tom Atom said) to get the effect you want within a single layer.

[mariogarranz]

Thanks everyone for your replies again, the problem is actually more complex than it seems and maybe I didn't express myself very clear, but I'm afraid most answers don't solve it.

What @Tom Atom suggests doesn't work in a 3D matrix of tiles, and just adding the depth as another value doesn't work either, because tiles on lower layers must be drawn AFTER tiles on higher layers with lower column or row, but BEFORE tiles on higher layers with higher column or row. That's the generic logic. However, when tiles are overlapping that creates a special case, because even if a tile is on a lower column or row, it must be drawn AFTER the tile that it's covering is drawn, which breaks the whole ordering process (you can't follow a straight pattern to assign z indexes anymore).

@drhayes, what you suggest doesn't work either. That's the way I did it on the game I showed in the first image. What happens then is that as soon as the tile starts moving it is drawn on top of all other layers, but what if that tile is partially covered (ie: there's a tile one row closer to the player's view and in a higher layer) then that tile is suddenly drawn on top of it, which breaks the whole 3D effect. 


I was thinking about it the whole weekend and I'm not sure if there is any solution to it, but my best guess is building a data structure that detects tiles that should be drawn behind each tile. Then start assigning the lower z index to the tile that does not have any tiles drawn behind, and remove the dependency from this tile for all tiles that required it to be drawn first, repeating the process until all tiles have been assigned a z index. If there is a solution to the problem then this algorithm should find it. However I doubt it's a very efficient system, and should be called many times during the game because more layers of tiles keep being added to the board.

[drhayes]

Sorry, in your image from a couple of posts ago you had two stacked tiles on the left that were both colored red. I thought you wanted those both behind the moving tile that was supposed to be underneath them.

I still think careful application of layers could do it (maybe 8 Groups, one each for moving tiles and placed tiles)... but it's also pretty clear you've thought a lot about this and we probably don't have the solution. I'd love to see what you come up with once you solve it, though!

[chg]

Seriously? I feel like I've already described the solution...

[mariogarranz]

@chg Maybe you did and I don't understand it. What I can tell is every tile must be drawn only AFTER:

1 - All tiles in all layers with lower column or row value have been drawn, except in case they intersect (they share a column or row and are close enough to visually overlap).
2 - All tiles in lower layers which intersect with it have been drawn.

I don't think it's just about the view vector, but maybe I'm not understanding your suggestion. Take this example I'm attaching.

I drew the zIndex corresponding to each tile. Tile 2 and 6 are on the highest layer, yet tile 2 was drawn before most of lowest layers tiles, because it has a lower row and column. Tile 6 has a lower column and row than tile 5, but must be drawn after, because they are intersecting.

 

 @drhayes I'm not sure I can do the moving layer, since finding it's zIndex sounds as complex as the rest of the problem, but it may be.



Thanks a lot for all your replies, maybe we don't completely understand each others because the problem is a little bit complex to be discussed here, but all your replies are very valuable to me!

[chg]

What you want is just "painters algorithm" - no "overlap" special cases here, just draw the scene from back to front and everything will be drawn correctly. It's basic computer graphics code, your issue is just that you don't have a good model for comparing two tiles and deciding which is further away from the viewer... that's where considering the view vector comes in.

While you could infer the "Z coord" of the tile in world space (not view space!) from the tile layer and produce a special case that hides the 3d calculation, I suggest trying to understand and implement the general case (tiles have an explicit z coord) at least to get it working and wrap your head around the 3d stuff (it sounds like you'd get in a mess trying to optimise it away before you really understand it) - having an explicit z coord will also let you do stuff like have tiles that are between tile layers so that you can animate tiles raising or lowering.

...So tiles have an x,y,z coord for their position in world space. when sorting you take into account the view vector - the view vector is needed to work in "view space" so that for tile 1 in your example is seen as being tile 3 (which itself is behind tile 4, etc) ...well actually you only need the depth coord of the tile in view space (but yeah, work in the general case before trying to optimise the maths away) to compare tiles

[mariogarranz]

 @chg Thanks a lot for your reply. I've barely worked with 3D environments, so I'll dig into it definitely.

Anyways, correct me if I'm wrong, but I understand that the z value you're saying, which depends on x, y and layer index, I guess, must be recalculated when the tile is moving, right? Because that's something I would like to avoid.

[chg]

6 hours ago, mariogarranz said:

 @chg Thanks a lot for your reply. I've barely worked with 3D environments, so I'll dig into it definitely.

Anyways, correct me if I'm wrong, but I understand that the z value you're saying, which depends on x, y and layer index, I guess, must be recalculated when the tile is moving, right? Because that's something I would like to avoid.

Actually, I keep insisting that that can be pretty much be optimised away, but because you are stuck implementing any version of the algorithm you need to write & understand the more straight forward version before you try and optimise it for your special case/s.

[Jackolantern]

Have you tried looking for an open source implementation of a Mahjong game to see the logic? There are so many Mahjong games out there that I would imagine someone has to have one open sourced. Typically, when we reach a point where something feels impossible to do in a given system, it is because we have coded ourselves into a corner. There most definitely is a solution to the problem, but the question may be if the solution is compatible with how you are approaching the issue so far. 

I am definitely not suggesting to just lift code from an open source project, but I suspect if you found one, there will be a major "Eureka!" moment where you realize you were either: A. approaching the problem in a much more complicated way than it has to be, or B. not breaking down the problem into small enough parts. Then perhaps taking a few steps back will catapult you many steps forward. 

Best of luck!