GameMaker Smart Isometric drawing order

chaz13

Member
Hi,

I'm messing about with an isometric game. The logic is all 2D, and it is drawn as an isometric game.

The idea is to be able to draw a map something like the old xcom games:





To do this, depth sorting is needed. In order to have objects that are larger than a single tile, it's best to generate a directed acyclic graph of which objects are behind others, then topologically sort that (like shown here: https://shaunlebron.github.io/IsometricBlocks/).

The problem is this is O(N^3), so, not ideal if there's a lot of objects. Additionally, it's not clear how to achieve multi-level buildings and things in this setup - as the floor is 'flat' and should always be beneath everything.

It's necessary for the depth sorting to be able to determine if one object is in front of another, which requires them to have a 3D volumes and for them not to intersect. So, one option is that floor tiles can be considered objects and have a height of 1. Then, the second level of walls be at a z position of the wall height + 2, (Floor is wall height + 1, then +1 height). This is not ideal, as then when there are walls atop each other spanning multiple levels but without a floor in between, we have a gap. I suppose there could be 'different' walls for when there is and is not a floor, but that's getting excessively complicated. Also, each floor tile then needs to be depth-sorted. However, if you look at the green 'cursor' in the top image, it seems as if there is indeed a gap between levels in the original game. Another issue with this approach is that I'm having issues with cycles in the directed graph using this method (i.e, two objects say they're behind each other, so it'll loop indefinitely when trying to topologically sort). I believe this happens when objects are intersecting.

Another options to use layers. Layer 1 for the ground floor, layer 2 for all ground-level objects, layer 3 for second level floor, layer 4 for second level objects. This is nice as it handles a bit of the depth handling, and we don't need to do any depth sorting for the flat floors. Furthermore, depth sorting is done on a layer-by-layer basis. This has the downside that now objects must be axis-aligned in the z direction, and can't be taller than whatever we define as a level's height. So it has some upsides but is probably way too restrictive.

I'm struggling to come up with other ideas for how to achieve this, so any thoughts would be good.
 

Tthecreator

Your Creator!
You should realize that you have two different types of objects: static and dynamic. I'd definitely make yourself a floor layer to begin with that doesn't have to be sorted. That's like 60% of all computation gone, that should be a no-brainer.
Then besides the floor layer, you want to add another static level layer. I refer to layer very loosely, this can be any type of list of any kind. This list is sorted at the begin of the game.
Now for the dynamic and moving elements: What you want to try do now is sort these dynamic elements separately. Then you can combine them with your static list in runtime inside of some loop. This gives your problem O(sorting_algorithm,Ndynamic) + ~O(Nstatic).
If you just keep a variable of the next dynamic object depth in your draw static object loop you can simply keep checking: if(nextDynamicDepth > currentStaticDepth){//run dynamic object draw code;}//continue static draw code;

You could even use the Z axis.
Also you don't need the X axis, just the Y.
You can actually make your sorting more efficient by first sorting the Z direction and then the Y. You can then only update the Z direction when that actually changes. Depending on your game this may change less than other factors. Or you can chose to only update your depth position at all only when it changes per object.

If you don't do that however, pick a sorting algorithm that fits the types and amount of depth changes the best. If you are casually walking around with a lot of NPC's that only move every so often you should pick an algorithm that is very efficient with almost-sorted lists.

I hoped that sparked some ideas in your head. Again these are just suggestions so good luck!
 

GMWolf

aka fel666
One technique is also to hack the depth buffer and use z testing.
That will require shaders to write the z value though
 

RujiK

Member
I'm currently working on an isometric-ish game and depth has been a huge headache.

Here are two gifs to show my current status on depth:


It works reasonably well but only supports pretty small objects or the depth starts glitching out. Cars and the like have to be split into many smaller pieces which is quite tedious and not very efficient. Here is an example of smaller objects working as a single object:


In my case I can't easily define the "floor" or "background wall" layers as I wanted the engine to support minecraft-esque building without the depth breaking. The depth for every static object/tile is calculated once. The player and NPC's are calculated every frame. Both use a variation of this code:
Code:
var xx = x >> 4; //this is the same as "xx = floor(x/16)*16" but in binary
var yy = y >> 4;
var zz = z >> 4;
depth = -(-xx*2+yy*3-zz)*16;
Even though I'm using that code, I only give it a weak recommendation. It doesn't work well for anything that isn't "block-sized" and there are a handful of special cases for moving objects that require annoying "if" statements to fix like:
Code:
if distance(solid_wall_on_right) < one pixel {depth += 20;}
if standing_on_elevator {depth -= 40;}
Somewhat consoling to me, I've noticed that Project Zomboid has some of the same issues that I do. I suspect they are using a 2d method of depth-sorting as well.


I would probably recommend looking into a 3d sorting shader like @GMWolf mentioned if you need larger/irregularly shaped objects. Unfortunately I wasn't able to find any examples or guidelines that worked in my minecraft like engine and I'm pretty bad at 3d.

Also this tech blog on z-tilting is worth a read and may or may not help your situation: https://www.yoyogames.com/blog/458/z-tilting-shader-based-2-5d-depth-sorting

PS: If anyone knows how I could convert my game to use a 3d graphics pipeline/shader for depth I would be very thankful. Note that it's basically isometric minecraft and there is no easily defined walls or floors.

EDIT: Oops, I didn't realize/forgot depth is a big no-no in GMS2. Man, I'm behind the times.
 
Last edited:
  • Like
Reactions: Rob
M

MishMash

Guest
The most efficient and precise way to achieve true depth in this sort of instance is ideally to make use of the hardware depth buffer and late-Z testing. You don't necessarily need to setup a 3D rendering projection to achieve this, but you may be able to output your own depth value from a shader, which is a value that gets tested against when new objects are drawn.

I haven't used GM in a while, but GLSL ES technically supports "gl_FragDepth" as an output value from the fragment shader. If you were to customise this, that value would get written out to the hardware depth buffer. There are a few main advantages to this:
  • You maintain a depth representation of your entire scene, which can be useful later on
  • You can render front to back, which is far more efficient and reduces (or entirely eliminates) overdraw
  • You have the option (if you ever wanted) to render complexly shaped 3D meshes and have them correctly intercept with the scene
  • As each object being rendered also gets depth tested, you can have a perfect blending between partially obstructed objects, as you would in 3D.
Note, to take full advantage of any of those extra features, and say you still wanted to render using sprites, you would need to provide heightmaps for each sprite, which would be a value specifying the vertical offset from the base of a given pixel in an object. The benefit of using a fixed isometric projection is that you can easily calculate depth from the scene itself by just using the y value, augmenting that with some height offset.

Again, not sure if this is immediately possible in GM, but it is possible as far as the spec GL spec goes.
 

YellowAfterlife

ᴏɴʟɪɴᴇ ᴍᴜʟᴛɪᴘʟᴀʏᴇʀ
Forum Staff
Moderator
I find that the more advanced your isometric projection gets, the more tempting it becomes to straight up make the whole thing 3d with non-perspective projection - make walls and floors into actual geometry (with minor math to map coordinates for correct pixel looks), make objects into flat planes (either angled or camera-facing), apply a matrix to correct for camera tilt. This is also an approach commonly used for 3/4 projection games to avoid clipping & depth-sorting adventures (Enter the Gungeon comes to mind)
 

RujiK

Member
@YellowAfterlife (or anyone) Do you have a link or know the formula for the math needed to correct for the position based on camera tilt/distance?

I found a nice billboard shader by @flyingsaucerinvasion that's pixel perfect but I don't know enough geometry to keep the positions from being "warped" in 3d space.

Visual explanation: Notice the width of the square is smaller in the back than in the front. Any formula to fix?


Thanks!
 

YellowAfterlife

ᴏɴʟɪɴᴇ ᴍᴜʟᴛɪᴘʟᴀʏᴇʀ
Forum Staff
Moderator
Visual explanation: Notice the width of the square is smaller in the back than in the front. Any formula to fix?
Compatibility scripts disable perspective like so:
Code:
var __mat = camera_get_proj_mat(camera_get_default());
__mat[11] = 0.0;
camera_set_proj_mat(camera_get_default(), __mat);
 

RujiK

Member
Disabling the perspective worked great! It's essentially pixel perfect but in a 3d world:

(Turning the camera ruins the illusion as the sprites weren't designed to fit from multiple angles. That's an art issue, not a technical issue.)

Unfortunately, as far as I can tell there is no good way to draw 2d sprites in 3d space without passing a uniform for every sprite. This means every draw call breaks the batch and really kills the FPS. I've spent the last week learning about shaders and trying to borrow the alpha channel or something but this has me stuck.

Shader code:

Text Version:
Code:
attribute vec3 in_Position;
attribute vec4 in_Colour;
attribute vec2 in_TextureCoord;

varying vec2 v_vTexcoord;
varying vec4 v_vColour;

uniform vec3 sprite_pos; //<- FPS KILLER. New uniform needed for every draw call
uniform vec2 cam_size; //3d camera size

void main() {
    gl_Position = gm_Matrices[MATRIX_WORLD_VIEW_PROJECTION] * vec4( sprite_pos, 1.0 );
    gl_Position.xy += in_Position.xy * cam_size * gl_Position.w;
    v_vColour = in_Colour;
    v_vTexcoord = in_TextureCoord;
}
Code:
varying vec2 v_vTexcoord;
varying vec4 v_vColour;

void main()
{
   vec4 sprite_col = v_vColour * texture2D( gm_BaseTexture, v_vTexcoord );
   if (sprite_col.a < 0.5) { discard; } else {gl_FragColor = sprite_col;}
}
And the GMS2 project file if anyone wants to try it: http://www.filedropper.com/3disometric

The large majority of the code is by @flyingsaucerinvasion so big credit to him. If any shader wiz can find a way to skip all of the uniform_sets this would probably be the fastest method of depth sorting in GMS2.
 

GMWolf

aka fel666
Rather than passing it as a uniform, you can add this info to a vertex buffer.
Then you batch your sprites to a large vertex buffer and draw that.
Super efficient.
 

RujiK

Member
@GMWolf I looked into that vertex idea briefly, and although it would work well for the terrain my google searches lead me to believe that it would be very slow for NPC's as I would need to destroy and rebuild the vertex buffer for every frame of animation and movement.

I suppose I could use the uniform shaders for NPC's and vertex buffers for the terrain though. As long as I have NPC's < 50ish it should have a good framerate. It's not exactly ideal, but it seems to be the best approach at the moment.
 

GMWolf

aka fel666
@GMWolf I looked into that vertex idea briefly, and although it would work well for the terrain my google searches lead me to believe that it would be very slow for NPC's as I would need to destroy and rebuild the vertex buffer for every frame of animation and movement.

I suppose I could use the uniform shaders for NPC's and vertex buffers for the terrain though. As long as I have NPC's < 50ish it should have a good framerate. It's not exactly ideal, but it seems to be the best approach at the moment.
Most batching systems work by doing just that. It's more efficient than individual draw calls.

You can be more efficient by having static batches, which never change, dynamic batches, which allows you to change the position of the vertices (only change the position attributes), and transient batches that allows you to have objects that pop in and out of existence (rebuilt from scratch every frame).

Remember you can convert a buffer to a vertex buffer, which allows you to keep your batches around and only change the parts you are interested in.

The best speedup you will have is by keeping your static batches separate from your dynamic batches, as you can keep the static batches on the GPU, without needing to upload it every frame, and usually, your dynamic batches are small enough to easily build and upload them every frame.



Aside note for non GM users:
You can be even more efficient by storing changing attributes in a separate buffer from static attributes. Then you only have to upload the changing attributes.

You can also speed up some more by carefully choosing your attributes, and storing positional data and such in a coherently mapped shader storage buffer, and indexing into them.
 

YellowAfterlife

ᴏɴʟɪɴᴇ ᴍᴜʟᴛɪᴘʟᴀʏᴇʀ
Forum Staff
Moderator
If anyone here is also on /r/gamemaker Discord server, you probably already know, but I started playing around with my proposed idea few days ago. This achieves pixel-perfect isometric projection with 3d geometry
upload_2019-1-13_22-5-53.png
How it looks in top-down view:
upload_2019-1-13_22-8-8.png
and side-ish view
upload_2019-1-13_22-11-0.png
this uses static batches for, well, static geometry (rebuilt on demand) and transient batches for entities (in this case, pretty much just that marble). I don't think dynamic batches are really worth it unless you have stupid quantities of entities or have plenty of extra data for shaders.

Not really decided on whether to try making this free and hope that anyone gives me money, or make it into a marketplace asset, or what
 

GMWolf

aka fel666
I don't think dynamic batches are really worth it unless you have stupid quantities of entities or have plenty of extra data for shaders.
No I don't think they are worth it in GM either.
Though outside of GM with careful planning they can offer a huge speedup over transient batches.
With my current renderer I only have to upload 32 bytes per object to the GPU to update they position, scale and rotation, no matter how many vertices it has.
 

Juju

Member
my google searches lead me to believe that it would be very slow for NPC's as I would need to destroy and rebuild the vertex buffer for every frame of animation and movement.
GM does that anyway for sprite batches - that's what batches are, after all.

Also, you can achieve non-perpsective projection by using an orthographic projection, but I see you've solved that already.
 
Top