Author Topic: XCOM Inspired Fantasy Game  (Read 2366 times)

Offline Nikita_Sadkov

  • Captain
  • ***
  • Posts: 94
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #45 on: April 15, 2019, 01:52:04 am »
I for long time think amount 2.5D graphic engine. This mean that each screen pixel have not only color but depth too. With something like this drawing order will be only secondary thing. You will check for each pixel you draw if you it behind or on front of background pixel.
That is called z-buffering. It is slower than draw-order sorting and doesn't solve the problem of higher layer popping through the layer below, or floor in front of a sprite cutting legs off large characters (that is why XCOM tanks are split into several cubes). Here is an example from Daimonin of what happens with naive approach (notice the cut off dragon legs and the poor botched wurm)


To solve the problem you need actual 3d transformations,  and mapping each sprite as texture to a polygon. I actually tried doing it in software and it is orders of magnitude slower than topological sort. Although Ultima Online did it somehow in 90ies. I.e. it needs OpenGL, which requires 32bit textures in precise 512x512 pages, forcing to pack all graphics into such pages, which requires writing very tricky packing algorithms. In addition OpenGL doesn't support paletted textures, so no way to recolor units or do color cycling, so you need write a lot of tricky shaders to support that. And you will still need to sort transparent surfaces, which is especially nasty, when most of your sprites have some transparency. It is also harder to control 3d polygons. For example, same cell may have a pebbles sprite, a unit standing on top of said pebbles, a weapon that unit is holding and some effect, like explosion or fire over that unit. These elements should be drawn in that precise order, it would be silly if weapon gets drawn before the unit.

So yeah, OpenGL and any 3d brings in more problems than it solves. And of course say good bye to portability, because each graphics card does something differently.
« Last Edit: April 15, 2019, 02:51:53 am by Nikita_Sadkov »

Offline Yankes

  • Commander
  • *****
  • Posts: 2064
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #46 on: April 15, 2019, 09:24:24 pm »
You missed one important aspect, EVERY pixel have depth, this mean destination and source too. If unit clip it should look like it dive into water.
And performance will not be very bad, OXC already do half of work that I image will be needed. Overall my idea how it will work is based on my work on OXC.
I already use some custom surfaces to make some special effects, like globe illumination using normal vectors. All done in software.

Offline Nikita_Sadkov

  • Captain
  • ***
  • Posts: 94
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #47 on: April 16, 2019, 04:24:51 pm »
You missed one important aspect, EVERY pixel have depth, this mean destination and source too. If unit clip it should look like it dive into water.
And performance will not be very bad, OXC already do half of work that I image will be needed. Overall my idea how it will work is based on my work on OXC.
I already use some custom surfaces to make some special effects, like globe illumination using normal vectors. All done in software.
Triangle rasterizing code is much slower than a direct blit, even if you optimize it with SSE. For each sprite you will have to project 4 vertices, draw 2 triangles, interpolating Z and UV across them. Here is the bare minimum to implement OpenGL-like triangle drawing in software:

Code: [Select]
static void draw_span(lerp *l, int y, int x, int end_x) {
typedef unsigned short fixcol;
#define fix(x) ((fixcol)(signed short)((x)*0xffff))
#define unfix(x) ((float)(x)/(0xffff))

int tt[640];
memset(tt, 0, 4*640);

// color layout: AAAA|RRRR|GGGG|BBBB

Uint16 mm0[4];
mm0[3] = fix(A(l));
mm0[2] = fix(R(l));
mm0[1] = fix(G(l));
mm0[0] = fix(B(l));

Uint16 mm1[4];
mm1[3] = fix(AD(l));
mm1[2] = fix(RD(l));
mm1[1] = fix(GD(l));
mm1[0] = fix(BD(l));

Uint16 mm2[4];
mm2[3] = fix(0.0); // ambient color shouldn't affect alpha
mm2[2] = fix(ambient_r);
mm2[1] = fix(ambient_g);
mm2[0] = fix(ambient_b);

// uv layout: 0000|0000|VVVV|UUUU
Uint16 mm6[4], uv_delta[4], uv_wh[4], uv_bp[4];

mm6[0] = fix(U(l));
mm6[1] = fix(V(l));
mm6[2] = 0;
mm6[3] = 0;

uv_delta[0] = fix(UD(l));
uv_delta[1] = fix(VD(l));
uv_delta[2] = 0;
uv_delta[3] = 0;

uv_wh[0] = texture->w-1;
uv_wh[1] = texture->h-1;
uv_wh[2] = 0;
uv_wh[3] = 0;

uv_bp[0] = texture->format->BytesPerPixel;
uv_bp[1] = texture->pitch;
uv_bp[2] = 0;
uv_bp[3] = 0;

fixcol one[4] = {0xffff, 0xffff, 0xffff, 0xffff};
float z = Z(l);
float zd = ZD(l);

Uint8 *dst = (Uint8*)screen->pixels + y*screen->pitch +
x*screen->format->BytesPerPixel;

// now we have following arrangements:
// EAX is temporary
// EBX points to zbuffer
// ECX is used for debugging
// EDX holds final location in screen buffer
// ESI points to texture
// EDI points to screen buffer
// MM0 holds light color
// MM1 holds delta for light color
// MM2 holds ambient
// MM3 holds resulting color between stages
// MM4 is temporary
// MM5 is temporary
// MM6 holds uv
// MM7 holds 0
// XMM6 holds Z
// XMM7 holds Z Delta
// others are unsed
// MMX code assumes that botch: screen and textrue are in BGRA format
asm (
"movq %0,%%mm0\n\t"
"movq %1,%%mm1\n\t"
"movq %2,%%mm2\n\t"
"movq %3,%%mm6\n\t"
"pxor %%mm7,%%mm7\n\t" // mm7 = 0

"movss %8,%%xmm6\n\t" // z
"movss %9,%%xmm7\n\t" // zd

"jmp loop_start\n\t"

"loop_body:\n\t"

// Z-BUFFER TEST
"test $1, %%ecx\n\t"
"jz skip_ztest\n\t"
"movss (%%ebx), %%xmm5\n\t"
"cmpss $2, %%xmm6, %%xmm5\n\t" // xmm5 <= xmm6
"movd %%xmm5, %%eax\n\t"
"test %%eax, %%eax\n\t"
"jz loop_advance\n\t"
"movss %%xmm6, (%%ebx)\n\t" // save new z-value of this pixel
"skip_ztest:\n\t"

// TEXTURE MAPPING (mm3 holds result)
"movq %%mm6,%%mm3\n\t" // mm3 = uv
"pmulhuw %5,%%mm3\n\t" // mm3 = u*w, v*h
"pand %5,%%mm3\n\t" // mm3 = (u*w)%w,(u*h)%h : wrap
"pmaddwd %7,%%mm3\n\t" // mm3 = linesz*vh+colorsz*uw
"movd %%mm3,%%eax\n\t"
"movd (%%eax,%%esi),%%mm3\n\t" // mm3 = packed_texture
"punpcklbw %%mm7,%%mm3\n\t" // mm3 = texture

// LIGHTS (mm3 holds result)
"test $2, %%ecx\n\t"
//"jz skip_lights\n\t"
"movq %%mm0,%%mm4\n\t" // mm4 = light
"pmulhuw %%mm3,%%mm4\n\t" // mm4 = light*texture
"pmulhuw %%mm2,%%mm3\n\t" // mm3 = ambient*texture
"paddusb %%mm4,%%mm3\n\t" // mm3 = (light + ambient)*texture
"skip_lights:\n\t"

// BLENDING (mm3 holds result)
"test $4, %%ecx\n\t"
"jz skip_blending\n\t"
"pshufw $0xff,%%mm3,%%mm4\n\t" // mm4 = src_alpha
"psllw $8,%%mm4\n\t" // convert mm4 to fixed point
"pmulhuw %%mm4,%%mm3\n\t" // mm3 = src*src_alpha
"movq %6,%%mm5\n\t" // mm5 = 1
"psubw %%mm4,%%mm5\n\t" // mm5 = 1-src_alpha
"movd (%%edi),%%mm4\n\t" // mm4 = dst_packed
"punpcklbw %%mm7,%%mm4\n\t" // mm4 = dst
"pmulhuw %%mm5,%%mm4\n\t" // mm4 = dst*(1-src_alpha)
"paddw %%mm4,%%mm3\n\t" // mm3 = src*src_alpha + dst*(1-src_alpha)
"skip_blending:\n\t"

// ENDING
"packuswb %%mm7,%%mm3\n\t" // pack pixel in mm3...
"movd %%mm3,(%%edi)\n\t" // and puti it to final resting place

// ADVANCE
"loop_advance:\n\t"
"paddw %%mm1,%%mm0\n\t" // advance light
"paddw %4,%%mm6\n\t" // advance uv
"addss %%xmm7,%%xmm6\n\t" // advance z
"add $4,%%edi\n\t" // advance x
"add $4,%%ebx\n\t"

// LOOP CONTROL
"loop_start:\n\t"
"cmp %%edx,%%edi\n\t"
"jl loop_body\n\t" // jmp if edi < edx

"emms\n\t" // reset FPU after MMX
:
:
"m" (*mm0), // 0
"m" (*mm1), // 1
"m" (*mm2), // 2
"m" (*mm6), // 3
"m" (*uv_delta), // 4
"m" (*uv_wh), // 5
"m" (*one), // 6
"m" (*uv_bp), // 7
"m" (z), // 8
"m" (zd), // 9
"c" (flags), // ecx
"b" (zbuffer+y*screen->w+x), "d" (dst+(end_x-x)*4),  "D" (dst), "S" (texture->pixels)
);
}
« Last Edit: April 16, 2019, 04:30:18 pm by Nikita_Sadkov »

Offline Yankes

  • Commander
  • *****
  • Posts: 2064
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #48 on: April 17, 2019, 04:16:39 am »
I want 2.5D engine, not 3D engine :>
I not even try implement drawing triangles. Simply biting 2D sprites with depth (that can be implemented as two normal surfaces but one is not treated as color but as depth).

https://github.com/Yankes/OpenXcom/blob/master/src/Geoscape/Globe.cpp#L987
https://github.com/Yankes/OpenXcom/blob/master/src/Geoscape/Globe.cpp#L175
This is shading I spoke before, each pixel have predefined normal vector and based on this I calculate sun shading on globe.
And everything still 8bit.

Offline Nikita_Sadkov

  • Captain
  • ***
  • Posts: 94
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #49 on: April 17, 2019, 05:05:04 pm »
I want 2.5D engine, not 3D engine :>
I not even try implement drawing triangles. Simply biting 2D sprites with depth (that can be implemented as two normal surfaces but one is not treated as color but as depth).
Where will you get the depth surface? 3d software generates it together with sprite? I remember there was some zombie-shooter game demo, where artists hand-drawn such z-surface onto each pixelart sprite, so dynamic light would highlight these sprite properly from any angle. A ton of work, and I havent heard about them since then. Guess their project is dead. And as I said with just z-buffer you will still get wrong draw order like: https://www.youtube.com/watch?v=BJYH-UrQ2xs
That guy solved it with two zbuffers, one for draw order, another the usual depth buffer. I solved it with topologically linking objects in a tree of what occludes what, but did that locally and only for specific units. I'm not using zbuffer now (although I had it in the first version), instead just sorting by x,y,z towards frustum.


https://github.com/Yankes/OpenXcom/blob/master/src/Geoscape/Globe.cpp#L987
https://github.com/Yankes/OpenXcom/blob/master/src/Geoscape/Globe.cpp#L175
This is shading I spoke before, each pixel have predefined normal vector and based on this I calculate sun shading on globe.
And everything still 8bit.
XCOM globe is an actual 3d object, so you get normal vectors for free with it.
« Last Edit: April 17, 2019, 05:18:44 pm by Nikita_Sadkov »

Offline Yankes

  • Commander
  • *****
  • Posts: 2064
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #50 on: April 17, 2019, 07:41:57 pm »
Where will you get the depth surface? 3d software generates it together with sprite? I remember there was some zombie-shooter game demo, where artists hand-drawn such z-surface onto each pixelart sprite, so dynamic light would highlight these sprite properly from any angle. A ton of work, and I havent heard
about them since then. Guess their project is dead.

Yes, you need prove it as separate surface, this need be lot of simpler than doing main graphic on its own. Flat shades that represents different depths could be enough in 99% cases. Alternative could be done using approximation form main graphic (inner parts should have more thickness that edges).

And as I said with just z-buffer you will still get wrong draw order like: https://www.youtube.com/watch?v=BJYH-UrQ2xs
That guy solved it with two zbuffers, one for draw order, another the usual depth buffer. I solved it with topologically linking objects in a tree of what occludes what, but did that locally and only for specific units. I'm not using zbuffer now (although I had it in the first version), instead just sorting by x,y,z towards frustum.
I do not think he use z-buffer in same way as I thinking how it should be used. You could consider each pixel of graphic as voxel in space 3D space. How one voxel with less z can occlude voxel with bigger z? Trick is that flat tiles shroud have ramp in z values, and tile ramps in some cases should have flat z values (this depend on angle of ramp compare to screen). You could even blit together background as one surface and reuse it in each frame.

This is important difference. You can see in this YT video that this buffer get brighter when it going to left side, this is wrong, it should be brighter when going to bottom edge of the screen.

I dig up my very old z-buffer test. Example in images. Red circle is draw as last but it overwrite all green "boxes". Second image is normalized z-buffer.

XCOM globe is an actual 3d object, so you get normal vectors for free with it.
globe is not 3d object, its drawn using 2d polygons, all 3d math is done on our side. Normals are only avaialbe because we know that globe is sphere, with this I can precalculate them for each pixel of screen and zoom level.

https://github.com/Yankes/OpenXcom/blob/OpenXcomExtended/src/Geoscape/Globe.cpp#L914
https://github.com/Yankes/OpenXcom/blob/OpenXcomExtended/src/Geoscape/Globe.cpp#L1988

Offline Nikita_Sadkov

  • Captain
  • ***
  • Posts: 94
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #51 on: April 17, 2019, 11:09:20 pm »
globe is not 3d object, its drawn using 2d polygons, all 3d math is done on our side. Normals are only avaialbe because we know that globe is sphere, with this I can precalculate them for each pixel of screen and zoom level.
Reminds me of Ecstatica, but they actually preserved all 3d geometry from the raytrace stage to properly occlude everything:
http://dingevoninteresse.de/wpblog/?cat=12

During the raytracing stage they also used really interesting texturing method by filling rocks with randomly placed sharp boxes, and organic objects with ellipsoids, instead of modelling then in a 3d editor. They had no 3ds Max or Maya back then, or large memory sizes to push that many polygons even for offline rendering. That gave the game its immediately recognizable clean art style.

« Last Edit: April 17, 2019, 11:16:46 pm by Nikita_Sadkov »

Offline Nikita_Sadkov

  • Captain
  • ***
  • Posts: 94
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #52 on: April 19, 2019, 03:28:02 pm »
With a game world split into discrete cells, especially large ones, there is another tricky design moment: picking hexes or squares. Squares are a bit easier to implement, yet naturally allow movement into only 4 directions. That is - squares create space with non-Euclidean topology and use Manhattan distance as a metric. Of course, trying to remedy that, you can also allow diagonal movement, opening a can of worms on its own, because units now move diagonally faster than they do horizontally. Surprise!

You can try solving that by further replacing the discrete number of action points with say a floating point number, subtracting 1.41421356237 for each diagonal move, instead of 1, but sqrt(2) is an irrational number, so there will always be some bias, unacceptable for a competitive turn-based strategy. Even worse, if you have two walls, sharing a corner, then a unit could still stick through it, even if it looks impassable.



Diagonal movement is clearly bolted on, but moving in just 4 directions would be too inaccurate and limiting for an strategy game, and that is why people prefer hexes to squares.

Yet with picking hexes, we have to make another important design decision: hex lattice can be rotated differently on screen. For example, Heroes of Might & Magic uses grid with vertically shared edges, while Battle for Wesnoth uses horizontally shared edge.

The case of vertical sharing allows for wide-screen friendly viewport, when each player has its own side of field, and units move without zig-zaging. Battle for Wesnoth maps on the other hand tend to placing two opponents at the north and south, because movement east and west will go in zig-zag.

Heroes of Might & Magic style grid also cheapens graphics production. In Wesnoth they have to draw units both facing south and north, while HOMM unit's sprite can be simply mirrored. That is in addition to nicer looking diagonal walls on castle siege maps. That saves both artist's time and and video memory.

Another decision is how to lay out hexes in a map. Obvious decision is to lay them in a square grid. Yet it would be a very bad idea to organize hexes as a square. A round world would be orders of magnitude better, as it allows easily making well balanced symmetric maps for any number of players, instead of just 4 corners or 4 edges of square grid. Round maps are important, because in hexagonal world area of effect and just larger structures too have hexagonal form. That is in addition to simplifying programming (it is a tricky task to pack hexes into a box).

That what they call good design - not fighting mathematics, but go along with it.

TLDR: my biggest mistake was picking squares over hexes. I would recommended hexagonal lattice even for real-time strategies. Unfortunately Blizzard doesn't feel enough competition to fix their competitive games and make the next Stracraft into a perfect game.



« Last Edit: April 19, 2019, 04:01:08 pm by Nikita_Sadkov »

Offline Solarius Scorch

  • Global Moderator
  • Commander
  • *****
  • Posts: 8309
  • WE MUST DISSENT
    • View Profile
    • Nocturmal Productions modding studio website
Re: XCOM Inspired Fantasy Game
« Reply #53 on: April 19, 2019, 03:41:34 pm »
I gotta say though, I hate hexes with a passion. The reason is simple: you can go in a straight horizontal line, but not vertical (or vice versa). This feels pretty shitty.

Offline Nikita_Sadkov

  • Captain
  • ***
  • Posts: 94
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #54 on: April 19, 2019, 09:49:51 pm »
I gotta say though, I hate hexes with a passion. The reason is simple: you can go in a straight horizontal line, but not vertical (or vice versa). This feels pretty shitty.
That can be remedied a bit by moving units vertically, when that is possible (i.e. there are no blocking units or triggers in the way), but only visually, behind the scenes units would still move on the lattice. In case of RTS, that will require more hacking obviously. Of course wargames, like Panzer General, move units directly in straight line right to their destination.

Offline Solarius Scorch

  • Global Moderator
  • Commander
  • *****
  • Posts: 8309
  • WE MUST DISSENT
    • View Profile
    • Nocturmal Productions modding studio website
Re: XCOM Inspired Fantasy Game
« Reply #55 on: April 19, 2019, 09:58:20 pm »
That can be remedied a bit by moving units vertically, when that is possible (i.e. there are no blocking units or triggers in the way), but only visually, behind the scenes units would still move on the lattice. In case of RTS, that will require more hacking obviously. Of course wargames, like Panzer General, move units directly in straight line right to their destination.

I'm fine with dirty tricks. ;)