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

Offline Yankes

  • Commander
  • *****
  • Posts: 3185
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #45 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

  • Colonel
  • ****
  • Posts: 286
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #46 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: 3185
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #47 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

  • Colonel
  • ****
  • Posts: 286
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #48 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: 3185
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #49 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

  • Colonel
  • ****
  • Posts: 286
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #50 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

  • Colonel
  • ****
  • Posts: 286
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #51 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: 11401
  • WE MUST DISSENT
    • View Profile
    • Nocturmal Productions modding studio website
Re: XCOM Inspired Fantasy Game
« Reply #52 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

  • Colonel
  • ****
  • Posts: 286
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #53 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: 11401
  • WE MUST DISSENT
    • View Profile
    • Nocturmal Productions modding studio website
Re: XCOM Inspired Fantasy Game
« Reply #54 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. ;)

Offline Yankes

  • Commander
  • *****
  • Posts: 3185
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #55 on: April 20, 2019, 07:47:48 pm »
One solution would be not use hex but triangles, if they are arranged in hex then you keep all hex good properties but you still can have orthogonal moment.
Trick is that 1TU allow you to move thought 2 triangles. I added small graphic that show this, All red dots are valid unit positions, black lines are allowed "half" moves. Effective this is multiple hex grids overleaped on each other.

Offline Nikita_Sadkov

  • Colonel
  • ****
  • Posts: 286
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #56 on: April 21, 2019, 03:08:18 am »
One solution would be not use hex but triangles, if they are arranged in hex then you keep all hex good properties but you still can have orthogonal moment.
Trick is that 1TU allow you to move thought 2 triangles. I added small graphic that show this, All red dots are valid unit positions, black lines are allowed "half" moves. Effective this is multiple hex grids overleaped on each other.
Yeah. That could work. And you can still reuse the same hex tileset.

Offline Nikita_Sadkov

  • Colonel
  • ****
  • Posts: 286
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #57 on: April 21, 2019, 01:15:23 pm »
Digging out procedural map generation. The following appears to be the state of art:
https://github.com/redblobgames/mapgen4

Offline Nikita_Sadkov

  • Colonel
  • ****
  • Posts: 286
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #58 on: April 21, 2019, 05:20:08 pm »
A reverse engineered explanation of the original Civilization map generation algorithm:
https://forums.civfanatics.com/threads/civ1-map-generation-explained.498630/

basically, Civ1 accumulated several random-walks, and then fixed the resulting map so unit wont be moving across what appears impassable body of water.

I've used similar code in my ancient Warcraft II map generator: https://github.com/saniv/wc2gen/blob/master/src/wc2gen.c

But instead of random walk patches, I've just put several seeds, and then applied cellular automation to the whole map, first for landmasses, then for hills, and then for forests. After that trying to place resources and player bases.

Mapgen4 also uses same tactics with placing emitters, but then builds voronoi polygonal surface, instead of running cell automata or random walk.

Alternatives: fractal generation, with midpoint displacement; overlaying some noise functions (like Minecraft does with perlin noise); and XCOM and Spelunky style of combining premade map pieces (Minecraft also embeds premade pieces inside noses-function generated map).

Instead of voronoi, one can probably uses other methods to interpolate inside point cloud, like quadtrees or metacircles: https://dribbble.com/shots/1776495-Metacircle-effect-source-file
« Last Edit: April 21, 2019, 08:10:42 pm by Nikita_Sadkov »

Offline Nikita_Sadkov

  • Colonel
  • ****
  • Posts: 286
    • View Profile
Re: XCOM Inspired Fantasy Game
« Reply #59 on: April 23, 2019, 07:14:52 pm »
Decided to use midpoint displacement. It is trivial to implement, and orders of magnitude easier to control, compared to say perlin noise, voronoi or random walk. Although one can surely tweak random walk to produce something similar to midpoint displacement. In the end, all these methods are closely related.

Also, naive perlin noise generator producing circular(!) rivers:
https://mccormick.cx/news/entries/blog-post-game-code-dabbling

But yeah, some people love crazy abstract stuff. Many fans very unhappy when Minecraft's map generation got tuned down to be less extravagant, killing stuff like overhanging terrain.

« Last Edit: April 23, 2019, 07:21:15 pm by Nikita_Sadkov »