OpenXcom Forum
Contributions => Programming => Recycle Bin => Topic started by: Skybuck on March 08, 2022, 09:35:32 am
-
What is needed for this is X,Y,Z coordinates inside some title or so and bounding box detection of cells/tiles. Also some sun coordinates, and possibly other light source coordinates :)
Tomorrow or so and coming days, I will dive into the source code of OpenXcom and see if I can get something done.
Any help/pointers/hints where to look would be appreciated :)
-
In OXCE there is already simple version of light "ray-tracing", it is done in tile space.
-
LOL, You call that ray-tracing ? HAHA. I don't see any ray-tracing, I see some tiles slightly changing in brightness and sometimes some bullit shadows ? What are you talking about ? =D
Anyway yesterday I was a bit vague in my mind but today/"this morning" I am clear and on coke, yes coca cola lol, is that a violation btw ? Anyway.
I will describe an algorithm in case I don't come through with code, so that perhaps another programmer with more OpenXCom development experience can try.
So let's first look at what is not necessary.
The interesting thing is that it's not necessary to cast rays from the camera to the scene, because of the painter algorithm. I assume the sprites/bitmaps/tiles are painted from back to front. So this painter algorithm already solves the visibility problem to a large degree, perhaps even 100% except if we would want transparency as well.
So basically all the pixels that are visible/draw on the screen are auto resolved by the painter's algorithm and that means we can draw a conceptually line from the pixel in voxel space towards an artificial sun or other light sources.
If this ray is obstructed by other objects/voxels/bounding boxes then the pixel is not lit, otherwise it is lit. If it is lit we can perform additional calculations, like distance to sun or angle towards sun and we can shade it's color, make it brighter/or full color as it was or make it dimmer as if it's slightly in shadow receiving less light. If it's not lit we can make it a lot darker up to a maximum of zero ofcourse we don't want to wrap it around or some ambient value or so.
So what is necessary is that per pixel information is stored:
1. The tile that was drawn on this pixel.
2. The x,y,z of this tile.
3. The bounding box of this tile.
If possible maybe a zbuffer could be usefull as well or maybe not, maybe it's to limited precision or it might be difficult to incorporate since tiles all have different coordinates.
So once we have the information of 1,2,3 then we must do a ray vs tile bounding box intersection test.
Where does the ray enter the tile ? And where does the ray exit the tile ?
For this there is already an algorithm which can be transformed into a 3D version. This algorithm is called "Fast Voxel Traversion". It works very simple by computing the intersection of a line with it's x-axis, y-axis, z-axis as T slides along the line. Since the distance from tile to tile in single dimension is always the same, all that is necessary is to determine which intersection with which axis is closest and increment T with that distance. This will cause the line to slide from intersection axis to intersection axis and could and probably is just what we need to very simple compute entry and exit points for the tile.
Then once we know exactly where this line enters, we can then try and covert this coordinates into localized voxel coordinates for the tile, and then we can even use the same algorithm inside a voxelized tile to see if there are any collisions along the path of the line.
And thus the hit detection algorithm is complete and allows us to determine if a ray hits anything inside a tile or not.
Come to think of it, perhaps there is already an algorithm inside the source code, for lasers, and other weaponry that could be re-used. I am not sure if it's voxel/tile based, but probably/possibility. I am also not sure how efficient it is because I have not looked at it, perhaps it uses the exact same algorithm.
Whatever the case may be this algorithm needs to be fast, because a lot of rays have to be computed. Very maybe it might be possible to compute 2x2 in case there is not enough processing...
But the fun thing about x-com is that it is kinda static, except for the weapons... and thus there is plenty of time to do all kinds of computations, as the player as trying to make a move or waiting for the enemy movements and such, it's a turn based game, so some waiting until the graphics rendering is done, is somewhat acceptable.
That leaves the worry about dynamic/interactive/real-time/animation events. One possibility is that an algorithm tries to predict the player moves and shots and starts pre-computing the lightning path... for bullits and other dynamic events so that it is already computed and stored in memory.
If the algorithm predicts the users correctly then the animation happens fluently, otherwise there may be a short delay before the animation happens.
Multiple different events should be predictable and thus multiple animations pre-rendered/computed, once the player made it's move those that are no longer predicted by the algorithm can tbe thrown out, while others could be kept if they are independent from the other animations, or to keep it simple all could be thrown out as the player makes his next move.
Bye for now,
Skybuck.
-
Also so far I like OpenXCom best, the mods over there work the best, OpenXCom auto-deactives malfunctioning mods. So first implementation from me while be tried on OpenXCom code base, maybe later it can be integrated into OpenXCom extended.
Any help with pointers to code that I should check for maybe re-use or usefull or inspiration would be welcomed.
Now I go give it a try... with windows 7 home edition and visual studio 2019 and the openxcom dependables and that is all that is needed to build openxcom.exe and a microsoft account away and a valid license which is free for visual studio 2019 community edition.
-
LOL, You call that ray-tracing ? HAHA. I don't see any ray-tracing, I see some tiles slightly changing in brightness and sometimes some bullit shadows ? What are you talking about ? =D
Then look more closely, in OXCE object cast shadows based on where is light source and what objects are in path:
https://www.youtube.com/watch?v=9oNroA3feEw
beside I do not see that your algorithm is lot better than current OXC version, probably less accurate because current version is critical for proper handing of corner cases.
Any proves that is faster than current version? And result paths are comparable e.g. bullets will not go past though some walls because code skip checking some voxels.
btw do not create multiple forum topics on same "thread", all your post/questions about this should be in current topic.
-
That is per tile lightning. It's nothing new, the game had that since the ms-dos version in ufo enemy unknown.
What I want to do is per pixel lightning so it will look a lot better.
To be able to do per pixel/per ray lightning and so forth, it is necessary to be able to "shoot rays" into the "scene/engine" and to "detect hits" / "collisions" with any kind of object/hitbox/volume etc.
This is why I am looking into calculateLine function. Furthermore the math/function must be as perfect as possible, otherwise some pixels will remain dark and it will look ugly.
Furthermore the rays should be drawn from the scene towards the sun to reduce floating point errors. Floating point errors near the sun are not a big deal.
I think it may be the opposite the bresenham line 3d algorithm might be the one not to handle all corner cases.
I am looking into this right now to find a good voxel traversal algorith, but it's hard with the clipping and math and re-usability of code and testing.
I just found my light casting/shadow code, from 2013, I had that idea since 1995, so now I should be a lot easier to implement it. Even ported it to cuda c in 2013 ! Wow time flies ! ;)
This code should be a lot better than the even older code I initially found...
-
I used somebody elses code, modified it slightly to perfect first/last voxel and also integrated into game, this creates possibilities ! Just a test to see if it would work and indeed it does, no clipping code yet, there were some little quickers inside the game, like not being able to handle negative z but coded around that:
The same code below could also be used for lighting of voxels/pixels so this going to be interesting.
Code has been integrated into game in this branch:
https://github.com/SkybuckFlying/OpenXcom/tree/FastVoxelTraversalAttempt2
Original/slightly modified/perfected fast voxel traversal code:
The one that worked for me in 3D for both positive and negative directions (in CUDA C):
#define SIGN(x) (x > 0 ? 1 : (x < 0 ? -1 : 0))
#define FRAC0(x) (x - floorf(x))
#define FRAC1(x) (1 - x + floorf(x))
float tMaxX, tMaxY, tMaxZ, tDeltaX, tDeltaY, tDeltaZ;
int3 voxel;
float x1, y1, z1; // start point
float x2, y2, z2; // end point
int dx = SIGN(x2 - x1);
if (dx != 0) tDeltaX = fmin(dx / (x2 - x1), 10000000.0f); else tDeltaX = 10000000.0f;
if (dx > 0) tMaxX = tDeltaX * FRAC1(x1); else tMaxX = tDeltaX * FRAC0(x1);
voxel.x = (int) x1;
int dy = SIGN(y2 - y1);
if (dy != 0) tDeltaY = fmin(dy / (y2 - y1), 10000000.0f); else tDeltaY = 10000000.0f;
if (dy > 0) tMaxY = tDeltaY * FRAC1(y1); else tMaxY = tDeltaY * FRAC0(y1);
voxel.y = (int) y1;
int dz = SIGN(z2 - z1);
if (dz != 0) tDeltaZ = fmin(dz / (z2 - z1), 10000000.0f); else tDeltaZ = 10000000.0f;
if (dz > 0) tMaxZ = tDeltaZ * FRAC1(z1); else tMaxZ = tDeltaZ * FRAC0(z1);
voxel.z = (int) z1;
while (true) {
// process first and subsequent voxels here
if (tMaxX < tMaxY) {
if (tMaxX < tMaxZ) {
voxel.x += dx;
tMaxX += tDeltaX;
} else {
voxel.z += dz;
tMaxZ += tDeltaZ;
}
} else {
if (tMaxY < tMaxZ) {
voxel.y += dy;
tMaxY += tDeltaY;
} else {
voxel.z += dz;
tMaxZ += tDeltaZ;
}
}
if (tMaxX > 1 && tMaxY > 1 && tMaxZ > 1)
{
// process last voxel here
break;
}
}
-
Translated the OpenXCOM c/c++ bresenham line 3d algorithm to Delphi, tested it, examine and:
I CAN CONFIRM THE FAST VOXEL TRAVERSAL ALGORITHM IS A LOT MORE ACCURATE THEN THE BRESENHAM 3D LINE ALGORITHM, AT LEAST WHEN doVoxelCheck := false;
EVEN WITH doVoxelCheck := True; THE BRESENHAM 3D LINE ALGORITHM WILL STILL MISS SOME CELLS !
VERY INTERESTING DISCOVERY !
-
That is per tile lightning. It's nothing new, the game had that since the ms-dos version in ufo enemy unknown.
What I want to do is per pixel lightning so it will look a lot better.
To be able to do per pixel/per ray lightning and so forth, it is necessary to be able to "shoot rays" into the "scene/engine" and to "detect hits" / "collisions" with any kind of object/hitbox/volume etc.
First of all, original game do not have proper lightning, because light go troughs walls and only depend on distance and ignored levels.
My lighting obeys walls and floors. This is 10000 time more complex and compotation demanding than original.
And for your project.
Per pixel you say? Do you know that this game have 2d graphic? how you calculate normals for flat sprites?
Another thing how do you plan do it without GPU? My lightning is on edge of limits for CPU can do where I only shade whole tiles.
And you plan incense work up to by 32*40 times?
-
"First of all, original game do not have proper lightning,"
Original game had some kind of tile lightning. I am looking to improve OpenXCom to the maximum possible of graphic fidelty it can have. There is a lot of untapped potential. The goal of re-creating x-com has been achieved. Now it is time to take it to the next level.
"| because light go troughs walls and only depend on distance and ignored levels."
Valid complaint here, with real lightning inside of houses might become dark. Perhaps extra lights need to be added to game data.
"My lighting obeys walls and floors."
I am not sure what you are referring to ? OpenXCom, OpenXCom Extended ? A certain mod ? A certain set of options ?
"This is 10000 time more complex and compotation demanding than original."
Original ran on 33 MHz, so 330.000, so your version would require 330 GHz.
"And for your project. Per pixel you say?"
Yes per pixel, is the original idea to see how it looks like. This is what the original in a weird way does. Thanks to sprite rendering.The sprite rendering can be taken to a next level.
If that fails or doesn't look good, next step would be to do it per voxel. But this may not be necessary.
"Do you know that this game have 2d graphic?"
Yes, this is the brilliant part about it. It's not just 2d graphics. It's 2d graphics combined with 3d graphics.
The original had 2 kinds of graphics per sprites, not all but the 3d's yes.
The 2 kinds of graphics are:
1. 2D graphics sprites to show what the voxel 3d sprite would look like from it's orientation. In principle these 2d sprites are pre-rendered 3d voxel sprites.
2. 3D voxel, scaled down, run length compressed, 1 bit hit boxes. These were used to do hit detection of rays.
Combine these two restores the 3D voxel sprite. It is not necessary to have 3D voxel color data, the 2D colored sprites are "layered/pulled" over these 3D hit box/voxel detections.
The same can be done for lighting, the 3d voxels are used to detect hit of light rays. The sprites are then used as a texture to get color data for what the light color should be.
"How you calculate normals for flat sprites?"
Normals are not required. The 2d sprite is layered over the 3d hitboxes. The 3d hitboxes are interpreted as voxels. Each voxel has a 3D box, the normals for such a 3D box are known.
Thus these flat surfaces can be used to approxiamete the lightning. More advanced computations could be done by interpolation the voxels to create half voxels if so required.
"Another thing how do you plan do it without GPU?"
A first implementation on CPU would be easiest to see how it looks, then to asses the runtime it takes. Since the game is turn based and usually slow there is plenty of time to render the scene, very few interactive computations needed, except when a soldier moves, a bullit flies, or an explosion happens. Some of that could be pre-computed and/or re-used. Parts of the scene could also be pre-rendered and re-used if it was not changed.
As a matter of fact the entire scene could be rendered in a gigant 3D voxel scene. Since computers now have gigabytes of ram. I am pretty sure the entire level of a typical xcom level may residue in memory completely on a voxel to voxel basis.
However such incredibly memory usage might not be necessary if it can be computed per title and so forth to save some memory, this stays in line with the original idea/architecture of the game and could be used to scale up the graphics of the game to proportions never seen before in any computer game.
Sprites could be scaled by 4x times the size and re-done by artist.
It seems sprites are 16x16x24 ? At high resolution still looks nice if battlescape is not scaled. However what if the sprites are doubled in size 32x32x64. Perhaps this allows 3D artists to create nicer looking sprites and re-do the entire game at more detail. Perhaps even 64x64x128 for insanely cool graphics. Or 128x128x256 or 128x128x128 or even 256x256x256.
My preference would more likely be something like 256x256x256 and if needed to be scale it down. So that initial graphics files are max quality. This also prepares the re-imagined game for high resolution monitors like 4K and 8K.
"My lightning is on edge of limits for CPU can do where I only shade whole tiles."
I am unaware of what lightning you are referring to. So far you have showed a link to a youtube video of Terror from the Deep. I am not so much interested in TFTD. It was a nice game, but my focus will be on X-COM UFO Enemy Unknown.
"And you plan incense work up to by 32*40 times?"
OpenXCom runs fine on my laptop. The existing lightning of soldiers in the dark and such can be kept. An extra layer of lightning can be added on top of it.
The current laptop resolution is 1600x900.
Which is 1.440.000 rays.
Each pixel on the screen can and should be shaded at least once.
Once this is achieved, then asses how it looks, and perhaps add additional lightning if enough cpu is left.
Another option is to switch to multi-threading and/or cuda.
However my laptop has broken 3D chip, so for now openl and/or cuda is out of the question.
Better to have CPU rendering anyway ;)
-
> "My lighting obeys walls and floors."
I am not sure what you are referring to ? OpenXCom, OpenXCom Extended ? A certain mod ? A certain set of options ?
He's referring to OpenXcom Extended with directional lighting engine turned on.
(by default it is turned off to keep the vanilla experience)
Anyway, we're looking forward to your great new engine... if it delivers what you describe, I'll be the first one to merge it into OpenXcom.
Good luck.
-
Anyway back to the original idea for the algorithm to not confuse with what I wrote above.
Theoretically there would be indeed 1600x900 rays. However these do not need to be traversed because the end points and therefore the hit boxes/detections/intersect points are already known.
The painters algorithm, possibly incombination with voxel hit boxes can be used to compute the final points of the rays. This is what makes this algorithm incredibly fast. No rays need to be traversed. Even though with this new algorith the traversing is incredibly fast. However the traversing only has to be done for bullits, and also only for titles. So that saves already major computation.
So this will not be the typical raytracer. This is something different.
Instead of computating the intersection points of rays, this algorithm idea uses painter algorithm to decide the outcome of where the rays should end up. There is also no perspective so that also changes it a bit. Once the painter algorithm is complete the scene is basically done and we are directly looking at the final results of the rays.
Thus ray intersection/traversal computations are simply replaced by the computation necessary to perform the painther algorithm.
Here it becomes an interesting question: How much does it actually save, apperently a lot... I am not exactly sure how this works in the game, I do see some event driving handlers that react to mouses or other events.
It may be computationally cheaper to perform the painter algorithm and fill in a bunch of voxels and/or sprite colors to get the end of the ray.
So this solves the visibility problem already.
What is left is the shading problem. For this rays will need to be pulled from the location of the pixels/sprites/voxels towards a imaginery sun, or even lights inside the game itself.
One interesting candidate to try this out on are the actual lights on some terror maps, that could be an interesting start to try this idea out.
From there light traversal is done with fast voxel traversal algorithm. However I see a possibility to speed this algorithm up considerably.
It's a two phase algorithm:
1. Because of the usage of tiles, enormous ammounts of traverse time can be saved. If if the tile is an "air" title, the ray passes completely through it and thus these pixels/voxels inside this title do not need to be processed, and thus the ray travels/traverses to the next tile and so forth, until the ray traversal actually enters a title that has content/hit boxes.
and thus then phase 2 of the algorithm happens:
2. In the second phase, the ray is traverse inside the title to see which voxels inside the tile are passed through and finally hit. Once a hit is detected the algorithm can stop, unless it is transparent. This is where Terror of the Deep could also benefit from it by doing so perhaps wonky cos/sin shifting of pixels to mimic water breaking of light.
Once it returns with a hit, the x,y,z is known, the sprite pixel corresponding to the x,y,z should be known as well, and now distance to light is in a matter of fact already known, it is one of tMaxX, tMaxY, tMaxZ, possibly the maximum or the minimum, not sure yet, probably maximum. Thus this also saves on expensive square root computations, which is pretty cool.
-
"
He's referring to OpenXcom Extended with directional lighting engine turned on.
(by default it is turned off to keep the vanilla experience)
"
How does one turn it on ? Does it require a re-compile ? Changing a setting in some config file ? Or a build in option in menu ?
Does it use opengl/direct/shaders ? Or does it run on CPU ?
-
"First of all, original game do not have proper lightning,"
Original game had some kind of tile lightning. I am looking to improve OpenXCom to the maximum possible of graphic fidelty it can have. There is a lot of untapped potential. The goal of re-creating x-com has been achieved. Now it is time to take it to the next level.
"| because light go troughs walls and only depend on distance and ignored levels."
Valid complaint here, with real lightning inside of houses might become dark. Perhaps extra lights need to be added to game data.
"My lighting obeys walls and floors."
I am not sure what you are referring to ? OpenXCom, OpenXCom Extended ? A certain mod ? A certain set of options ?
OpenXCom Extended, I started this fork. Youtube video I posted previously show exactly this change, you can see "shadows" cast by objects in game.
This maximin that is possible using original game data.
"This is 10000 time more complex and compotation demanding than original."
Original ran on 33 MHz, so 330.000, so your version would require 330 GHz.
How much of this 33MHz was used for light? I would say 1MHz, this will mean 10GHz and on my CPU its 3s. On some maps literality that much take to make update of light. This mean I was not far from mark with my estimation.
"And for your project. Per pixel you say?"
Yes per pixel, is the original idea to see how it looks like. This is what the original in a weird way does. Thanks to sprite rendering.The sprite rendering can be taken to a next level.
If that fails or doesn't look good, next step would be to do it per voxel. But this may not be necessary.
"Do you know that this game have 2d graphic?"
Yes, this is the brilliant part about it. It's not just 2d graphics. It's 2d graphics combined with 3d graphics.
The original had 2 kinds of graphics per sprites, not all but the 3d's yes.
The 2 kinds of graphics are:
1. 2D graphics sprites to show what the voxel 3d sprite would look like from it's orientation. In principle these 2d sprites are pre-rendered 3d voxel sprites.
2. 3D voxel, scaled down, run length compressed, 1 bit hit boxes. These were used to do hit detection of rays.
Combine these two restores the 3D voxel sprite. It is not necessary to have 3D voxel color data, the 2D colored sprites are "layered/pulled" over these 3D hit box/voxel detections.
You can't combine them, Xcom 2d graphic data and hit boxes were only superfluous connected. You can see it yourself, I attach debug view form OXC where you can see Voxel space. You can recognize shapes and what is what but if you look closely nothing match exactly. Probably only flat walls relay match.
The same can be done for lighting, the 3d voxels are used to detect hit of light rays. The sprites are then used as a texture to get color data for what the light color should be.
"How you calculate normals for flat sprites?"
Normals are not required. The 2d sprite is layered over the 3d hitboxes. The 3d hitboxes are interpreted as voxels. Each voxel has a 3D box, the normals for such a 3D box are known.
But 3d hit boxes do not match graphic.
Thus these flat surfaces can be used to approxiamete the lightning. More advanced computations could be done by interpolation the voxels to create half voxels if so required.
"Another thing how do you plan do it without GPU?"
A first implementation on CPU would be easiest to see how it looks, then to asses the runtime it takes. Since the game is turn based and usually slow there is plenty of time to render the scene, very few interactive computations needed, except when a soldier moves, a bullit flies, or an explosion happens. Some of that could be pre-computed and/or re-used. Parts of the scene could also be pre-rendered and re-used if it was not changed.
As a matter of fact the entire scene could be rendered in a gigant 3D voxel scene. Since computers now have gigabytes of ram. I am pretty sure the entire level of a typical xcom level may residue in memory completely on a voxel to voxel basis.
Yes, there are voxel engines that could show spaces with accuracy like Xcom voxel space but you should be ready to spend years to make some thing like this for OpenXcom.
However such incredibly memory usage might not be necessary if it can be computed per title and so forth to save some memory, this stays in line with the original idea/architecture of the game and could be used to scale up the graphics of the game to proportions never seen before in any computer game.
Sprites could be scaled by 4x times the size and re-done by artist.
It seems sprites are 16x16x24 ? At high resolution still looks nice if battlescape is not scaled. However what if the sprites are doubled in size 32x32x64. Perhaps this allows 3D artists to create nicer looking sprites and re-do the entire game at more detail. Perhaps even 64x64x128 for insanely cool graphics. Or 128x128x256 or 128x128x128 or even 256x256x256.
My preference would more likely be something like 256x256x256 and if needed to be scale it down. So that initial graphics files are max quality. This also prepares the re-imagined game for high resolution monitors like 4K and 8K.
"My lightning is on edge of limits for CPU can do where I only shade whole tiles."
I am unaware of what lightning you are referring to. So far you have showed a link to a youtube video of Terror from the Deep. I am not so much interested in TFTD. It was a nice game, but my focus will be on X-COM UFO Enemy Unknown.
TFTD and UFO is SAME game, especially for OXC where you can switch between them on fly.
"And you plan incense work up to by 32*40 times?"
OpenXCom runs fine on my laptop. The existing lightning of soldiers in the dark and such can be kept. An extra layer of lightning can be added on top of it.
The current laptop resolution is 1600x900.
Which is 1.440.000 rays.
Each pixel on the screen can and should be shaded at least once.
And how many light sources you plan to support? 1? 3? or maybe 1000+ that is standard for my light engine in OXCE.
Once this is achieved, then asses how it looks, and perhaps add additional lightning if enough cpu is left.
Another option is to switch to multi-threading and/or cuda.
However my laptop has broken 3D chip, so for now openl and/or cuda is out of the question.
Better to have CPU rendering anyway ;)
You can look screens I post there, to create voxel view engine do it in 1-2s on my CPU, changing line algorithm will not fix it, to make it work you need full blown voxel engine that allow fast querying ray hits (in log(n) time or even better const time).
-
Anyway, so this new light/shadow casting/rendering idea. Let's examine how it might run.
https://www.ufopaedia.org/index.php/Battlescape_Map_Generation
Most common map size is 50x50x4
Tiles size documentation not found but it seems to be 16x16x24, which is probably width, depth, height or something ? not sure which is which. but I think 24 is probably height and not depth.
So now compute how many tiles will fit on my laptop screen 1600x900 :):
1600 / 16 = 100
900 / 24 = 37,5 so say 38.
100x38 = 3800 tiles, perhaps multiplied by a height of 4 tile levels = 15200
Anyway the tile grid for a screen is roughly 100x38x4 so this can be consider space paitioning grid.
The worst case diagonal is something like
100x2 + 38x2 + 4x2 = 284 traversals per ray max, this is over estimated.
Once a "filled" title is detected, it then needs to perform an additional traversal of the tile itself.
Worst case diagonal is 16x2 + 16x2 + 24x2 = 112 inner traversals.
Thus worst case traversal scenerio is: 284 + 112 = 396 traversals.
So for a screen of 1600x900 = 1440000
1440000 x 396 traversals = 570.240.000
One possible problem that is over looked with this approach is when the sun is very low, buildings from far away might block the sun which would make it necessary to do much larger traversals. One possible solution would be to keep the sun high up for now. Or perform low sun computations if computer allows it.
Keep it mind that this traversal algorithm could potentially be made in parallel, by computing all integers between x0,y0,z0 and x1,y1,z1 with 3 single dimension loops. Where T is computed for each integer. Producing three already sorted lists, which can be stored in arrays or cuda arrays for parallel access/computing without locking.
Once computed, arrays can be merged. One possible idea to find collision inside these arrays is to use gather approach to find which entry is closest hit. Processing it in parallel may waste some computational resources. Another possibility is to have warps compute the most likely directions to find collisions first and the preemptively kill/end the warp/kernel once found, this may require some global variable which each warps inspect to see if it's to be terminated.
Anyway back to CPU figures:
570.240.000 is a bit much for a CPU to handle. At least main RAM has a latency of about 400 nano seconds. Processing this ammount of traversal lookups would require:
570240000 * 400 nanoseconds = 228096000000 nanoseconds
228096000000 / (1000 x 1000 x 1000) = 228,096 seconds worst case scenerio which is somewhat exaggarated.
Perhaps real world scenerio is closer to 100 seconds, still a lot !
So relief will come from L2 and L3 cache hits, how much is hard to predict.
Part of the algorithm could be multi-threaded to benefit from more cache hits in L1, L2, L3 data caches.
Perhaps on a 16 core machine: 100 x 16 = 6,25 seconds rendering time.
Now it's starting to come near something usable.
However this outcome is unstatisfactory for todays hard so a better solution must be found.
One possibility which comes to mind is computing bounding boxes for empty space and using that to traverse the rays faster and to save on tile traversal computation time.
Seeing the fast ammount of empty space in x-com maps, this should offer quite some speed up, how much exactly is unknown and hard to predict but it's worth a try.
Bye for now,
Skybuck.
-
"
OpenXCom Extended, I started this fork. Youtube video I posted previously show exactly this change, you can see "shadows" cast by objects in game.
This maximin that is possible using original game data.
"
More is possible with this, I am convinced by your pictures below ! =D
"How much of this 33MHz was used for light? I would say 1MHz, this will mean 10GHz and on my CPU its 3s. On some maps literality that much take to make update of light. This mean I was not far from mark with my estimation."
How are these first person pictures produced ? Does it use opengl and/or shaders ?
"
You can't combine them, Xcom 2d graphic data and hit boxes were only superfluous connected. You can see it yourself, I attach debug view form OXC where you can see Voxel space. You can recognize shapes and what is what but if you look closely nothing match exactly. Probably only flat walls relay match.
"
From what I can see there is plenty of hit boxes to compute some shadows much better. The shadow that are computed are very "cartoonish" they don't really "shade" anything. It seems this was done intentional to keep consistent with the original look and feel and cartoonish look of the game.
I am more interested in trying out a lighting approach that is more realistic and a little bit less cartoonish or a combination of both.
By computing distance from hit point to light source and also the angle of the ray much better shading can be achieved. Even with some basic math.
https://en.wikipedia.org/wiki/Inverse-square_law
https://www.compuphase.com/electronics/candela_lumen.htm
https://www.lightsearch.com/resources/lightguides/formulas.html
I think I used like one formula of that last page to achieve better lighting/shadows then what you have achieved. I also noticed in code, the code didn't know what to do with angles.
So it seems to current shading code is simply lacking.
"But 3d hit boxes do not match graphic."
It doesn't need most likely, the shading can be somewhat in exact, it will most likely still look good, especially if some kind of radiosity is applied by for example shifting the end points a little bit and perhaps blurring/fudging the pixels around it or some other techniques that are yet unknown to me. Perhaps even interpolation between computed shadow pixels, or rendering shadows twice from slightly different light source angles. Different technique can be tried to make it look good in case it doesn't but from what I see so far it's already quite nice, the voxel data that is.
"Yes, there are voxel engines that could show spaces with accuracy like Xcom voxel space but you should be ready to spend years to make some thing like this for OpenXcom."
Perhaps you guys already have done most of the work and it just needs some refining. If you can point me towards where this voxel code is and this rendering code is I can take a looksy to see if I can maybe improve on it or expand on it.
"TFTD and UFO is SAME game, especially for OXC where you can switch between them on fly."
OXC is same, originals where slightly different, the data could be somewhat different, and certain algorithms could be enabled for TFTD only or some parameters changed. I know original TFTD was a little bit different from XCOM UFO Enemy Unknown. TFTD seemed a little bit more advanced graphically, the title/object shading might have been a little bit more advanced :)
"And how many light sources you plan to support? 1? 3? or maybe 1000+ that is standard for my light engine in OXCE."
This is a good question ! =D
At least +1 for outdoor sun would be a big bonus to this game.
For moon light missions +1 for moon light ! ;)
Interriors of UFOs could be ignored and always fully lit, assuming aliens put light leds everywhere ! ;) or give it a magical feeling, like "magic/hi-tech alien light everywhere".
Kinda makes sense too.. Aliens want to see us so they can blast us.
Another alternative would be if Aliens shut down the light, the light turns green like infrared. As if our soldiers are now suddenly looking in the dark through their green infrared, this could be a very cool effect added to the game.
Inside barn houses, light could be cast from known window tiles. Especially in combination with any outdoor sun vector...
Barn doors same thing, light computations start from there.
Perhaps holes blown into houses also start casting light from there.
And then street lamps.
So it doesn't seem that much.
The soldiers could remain in darkness or just standard tile shadow/light rendering overlayed maybe with the other rendering, be it sun moon, ufo, barn etc.
How does your engine go up to 1000+ ? Are these 1000 individual light sources ? Or are these openings or reflections or objects where new computations originate from ?
"You can look screens I post there, to create voxel view engine do it in 1-2s on my CPU"
At first glance I didn't recgonize it and thought maybe disconnected pictures of different scenes, but then I started looking at it some more and indeed the scenes seem related to each other.
The big green structures are the ufo, I can also see fences and what appear to be grass boxes or something, interesting.
This should be sufficient to cast some create lights/shadows.
Then when I look at the colored drawing, the shadows are very weak, almost non-existent, they are there, but don't really contribute much to scene.
I am convinced the problem here is how the shadows are applied to the colors, either no formula is used or a better formule needs to be used.
Most likely no formula is used, and simply if the pixel is in shade it's shade is lowered by a weak ammount like -1 or -2, or -3.
I think I actually saw this in code.
So I think I may have spotted the real problem here:
It's the palette. Your shading code is trying to force the shadow color into the pallette.
So now there are a couple of problems/lacks with your shader code:
1. No proper lighting formulas used, does not take into account distance or angle of light, even a simple candle light formula should improve on this.
2. The forcing of the shadow into the palette may be taken away a lot of the fidelity that would otherwise be achieveable. This depends on the ammount of shading colors available in the palette.
Two solutions exist for problem 2 and a third one very maybe:
2.1 Either compute the shadow in 24 bit color and ignore palette.
2.2 Use dithering to increase color possibilities.
2.3 Maybe there are enough shading colors in palette and better search algorithm for closer match needs to be used.
2.3 would be too expensive to do most likely.
So I am not sure if OpenXCom is a 8 bit/vga color game or 24 bit color game ?
But if it's still 8 bit color game, then here is where OpenXCom can improve upon the original ! ;)
"changing line algorithm will not fix it"
Changing line algorithm was an experiment to see how the engine works. To see if I can comprehend the hit detection somewhat. So far the line algorithm seems to do "tile" based traversing. Not sure what happens in "voxel check" or something like that. Perhaps there is another algorithm that actually like inside a tile to detect actual voxel hits ?
It was also necessary to examine the line algorithm to see how exact it was and to replace it with a 100% accurate algorithm, otherwise per pixel lightning will look bad.
And it sure was necessary, I could have replaced it without examining it, but examaning it proved/convinced me that it was 100% necessary and that the original line algorithm has serious flaw/inaccuracies. How much this effects the game could be studied further.
The original also had this issue and it always bothered me when I played the original and I also wondered what it would be like if the scanning/line algorithm was more exact. While yesterday that day came and that dream become reality ! =D and it was quite interesting and I could see, feel and notice it.
The quality of the game went up, the ai interaction went up, sometimes the game became a bit more easier because shots would actually connect with aliens instead of end up in the wrong wall. Somethat that always bothered me with this game but no longer ! ;)
I have not tried yet with advanced mods. But that could be fun as well, though it also somewhat scares me a bit, because of boy are the new aliens and weapons powerfull !
First I want to spent my time on trying to improve the graphics before I do a total play through of the game. Because then I hit two flies with one blow:
1. Improved accuracy !
2. Improved graphics !
Then a full play through of this classic is definetly worth it ! =D
Next steps could be:
A. Sound:
3. Better sounds/sound effects real-time generated weapon sounds, perhaps wall reflections and other mods of sounds.
4. Surround sound improvements
5. Doppler effects for bullits zipping past center of camera.
6. Reverb effects inside ufo/metal closures.
7. Water/mud step effects, dampening or bass effects.
8. Wood effects.
9. Ambient scream effects in terror missions, far away explosions, far away screams.
B. Multiplayer
I believe OpenXCom has the potential to become better than the EU/Firaxis gameplay/xcom 1 and xcom 2.
It's time to try and bring that vision alive ! =D
(It's kinda a shame how Firaxis version was not voxel based ? Is it tile based at all ? Doesn't seem like it, I am not impressed with it's destruction effects, OpenXCom has much more potential).
C. Physics effects become possible as well.
C.1. Voxels can fall down.
C.2 Rain can accumillate and flow down roof tops and streets.
C.3 Fog/smoke effects with fluid dynamics solvers in cuda.
C.4 per voxel damage instead of per tile.
C.5 per voxel fire effects.
C.6 per voxel glass/water effects.
C.7 per voxel metal/glow/melt effects.
C.8 per voxel blood/flow effects human/alien.
C.9 per voxel dirt effects flying up into the sky.
C.10 body effects, accumillation of bodies on top of each other or flesh parts.
C.11 per voxel debry effects, accummilation of blown apart parts.
C.12 light effects through holes in walls, and also better spotting.
So as far as I am concerned there is plenty of untapped potential in OpenXCom/XCOM in general.
Some of it also applies to Doom, and what BrutalDoom mod has done to Doom is quite amazing, but the best is yet to come !
So faraxis made a mistake to go to easy route and choose an existing game engine, they capped on it's success with an inferior game engine, perhaps it saved them some time, but it may be a dead end in the long run.
New game engines are also being developed, engines that are completely voxel based.
However I consider the voxel engine part the easiest part of the engine, because it's just technical mostly.
What you guys have done, actually re-writing the game logic is most likely the most difficult part, it requires a lot of creativity, lot's of analysis of original game and a lot of programming experience to bring it back to life once again !
A formidabel job !
It would be "shame" to just stop here and don't take it to the next level and let yourself be dwarfed by fancy pancing looking games just because their graphics are a little bit better with opengl/directx and such but don't actually do that much better gameplay wise.
OpenXCom has a lot more potential and it's just waiting to be unlocked ! =D
Perhaps it's time I try to unlock it a little bit. Perhaps you guys have taken it as far as you could, or perhaps not. Perhaps you exhausted (or perhaps fed up with it, but I am happy to see you guys still here and apperently still developing it further or at least corresponding/communication/I was a bit worried you guys might be gone ! =D) or perhaps you want to take a ride on the skybuck train and try and work together to bring something far better/far newer to the scene to blow away the "firaxis" ripp off ! =D and other inferior clones !
I am convinced with the fan base and legacy of XCom plenty of fans/people/artists/programmers may be willing to help to take XCom to the next level where it belongs ! ;) =D
Plus Visual Studio 2019 has advanced and improved a lot to the point where it is actually usuable, Plus your solution project is very good/excellent.
Plus hardware/computer resources have increased to the point where XCom can be taken to the next level.
Perhaps 48 bit rendering might even belong to the possibilities or perhaps that is a bridge just too far cause that monitor hardware is rare but I look forward to buying one soon ;)
Also take a look at MagicaVoxel 0.99.2
https://www.youtube.com/watch?v=mfKx4j-C6nI&t=159s
This may just be the thing that XCom needs/could use to take it to the next level. 3D Artists can use this tool. The tool looks quite complex to me haven't tried it, yet again it does seem useable and not too difficult to create some 3D sprites with.
Also other tools might exist that can do true 3D voxel sprites.
So I see stuff like this from time to time... voxels are making a come back ! ;) =D
Even the latest unreal engine is at the level of voxels, Triangles can become so tiny it no longer makes sense to use it as the basic compute unit for graphics, thus enter the voxel.
Plus voxels can be computed in parallel more easy potentially, very interesting towards the future ! ;)
"to make it work you need full blown voxel engine that allow fast querying ray hits (in log(n) time or even better const time)."
Perhaps.
However the original XCom seemed to be a genius mix of 2D sprite engine in combination with 3D voxel hit detection and 3D tile engine and run length compression of voxel data.
This mix designed to save memory and save on computions and even disk space.
This is what made the game so genius. Trying to keep it like that would at least allow the graphics to become somewhat better.
But perhaps it's time to let loose of this mix and go full voxel to be able to implement more effects.
Or stay with the original genius idea of trying to fake/reduce some of it by using different techniques to accomplish the same.
Like the sprite rendering, instead of rendering 3d voxel sprites, they are pre-computed into 2D bitmaps.
Hard to imagine that something like that can be done for water flow, or smoke flow, or fire flow, but perhaps, at least some pre-computations could be done or some other cheats ! ;) :)
So far I like my bounding box idea of computing as many big bounding boxes as possible to reduce ray/box/voxel intersections. Perhaps octrees could be of some use, or perhaps some new data structure that is more suited for 3d voxel engine.
(I also highly recommend the login time for this forum to be increased to 3 hours or so, otherwise posting like this may be lost, fortunately I am an experienced forumite and I know forums can be shaky as well as accidental side mouse button hits ! However I find this site/forum logs me out unusually fast... little bit annoying)
-
Anyway, so this new light/shadow casting/rendering idea. Let's examine how it might run.
https://www.ufopaedia.org/index.php/Battlescape_Map_Generation
Most common map size is 50x50x4
This is true only for original game, OXC allow lot bigger maps, especially OXCE allow at least 10 levels
Tiles size documentation not found but it seems to be 16x16x24, which is probably width, depth, height or something ? not sure which is which. but I think 24 is probably height and not depth.
So now compute how many tiles will fit on my laptop screen 1600x900 :):
1600 / 16 = 100
900 / 24 = 37,5 so say 38.
Game is isometric. you will see lot more tiles as you look on them with specific angle. Tile floor is displayed as Rhombus with 32x16 diagonals.
For height of graphic of tile is indeed 24 (tile sprite have 32x40 size to fit whole floor and height) but you should divide by 16 as floor determine how
many tiles you can see, 24 would be used only to determine what tiles from level should be show.
100x38 = 3800 tiles, perhaps multiplied by a height of 4 tile levels = 15200
Anyway the tile grid for a screen is roughly 100x38x4 so this can be consider space paitioning grid.
The worst case diagonal is something like
100x2 + 38x2 + 4x2 = 284 traversals per ray max, this is over estimated.
Once a "filled" title is detected, it then needs to perform an additional traversal of the tile itself.
Worst case diagonal is 16x2 + 16x2 + 24x2 = 112 inner traversals.
Thus worst case traversal scenerio is: 284 + 112 = 396 traversals.
Could you show some pictures of this algorithm? Especially when you use voxel dimensions like tiles were orthogonal to screen but they are isometric to it.
You can see approximation there:
http://www.strategycore.co.uk/site/assets/files/4358/1216869303fixed_lightning.png
This is example of some custom graphic that try to match voxels.
As you can see tiles are view from angle, where in game data are represented as 16x16x24 box.
So for a screen of 1600x900 = 1440000
1440000 x 396 traversals = 570.240.000
One possible problem that is over looked with this approach is when the sun is very low, buildings from far away might block the sun which would make it necessary to do much larger traversals. One possible solution would be to keep the sun high up for now. Or perform low sun computations if computer allows it.
Keep it mind that this traversal algorithm could potentially be made in parallel, by computing all integers between x0,y0,z0 and x1,y1,z1 with 3 single dimension loops. Where T is computed for each integer. Producing three already sorted lists, which can be stored in arrays or cuda arrays for parallel access/computing without locking.
Once computed, arrays can be merged. One possible idea to find collision inside these arrays is to use gather approach to find which entry is closest hit. Processing it in parallel may waste some computational resources. Another possibility is to have warps compute the most likely directions to find collisions first and the preemptively kill/end the warp/kernel once found, this may require some global variable which each warps inspect to see if it's to be terminated.
Why trying to parallel one ray? You will only duplicate work/waste work/complicate logic, you have hundreds other independent rays to compute. You can simply parallel processing of each row of your screen and rays that begin form it.
Anyway back to CPU figures:
570.240.000 is a bit much for a CPU to handle. At least main RAM has a latency of about 400 nano seconds. Processing this ammount of traversal lookups would require:
570240000 * 400 nanoseconds = 228096000000 nanoseconds
228096000000 / (1000 x 1000 x 1000) = 228,096 seconds worst case scenerio which is somewhat exaggarated.
Perhaps real world scenerio is closer to 100 seconds, still a lot !
So relief will come from L2 and L3 cache hits, how much is hard to predict.
Part of the algorithm could be multi-threaded to benefit from more cache hits in L1, L2, L3 data caches.
Perhaps on a 16 core machine: 100 x 16 = 6,25 seconds rendering time.
Now it's starting to come near something usable.
However this outcome is unstatisfactory for todays hard so a better solution must be found.
One possibility which comes to mind is computing bounding boxes for empty space and using that to traverse the rays faster and to save on tile traversal computation time.
Seeing the fast ammount of empty space in x-com maps, this should offer quite some speed up, how much exactly is unknown and hard to predict but it's worth a try.
Bye for now,
Skybuck.
bounding boxes are interesting idea that could be useful for even normal OXC as could reduce lot of calculations for Line of Sight and Line of Fire.
"
OpenXCom Extended, I started this fork. Youtube video I posted previously show exactly this change, you can see "shadows" cast by objects in game.
This maximin that is possible using original game data.
"
More is possible with this, I am convinced by your pictures below ! =D
"How much of this 33MHz was used for light? I would say 1MHz, this will mean 10GHz and on my CPU its 3s. On some maps literality that much take to make update of light. This mean I was not far from mark with my estimation."
How are these first person pictures produced ? Does it use opengl and/or shaders ?
in debug mode F10 or F11 or other F?? button that make it, and it use same logic that rest of game do, it "shoot" from each pixel and see what is hit in voxel space.
"
You can't combine them, Xcom 2d graphic data and hit boxes were only superfluous connected. You can see it yourself, I attach debug view form OXC where you can see Voxel space. You can recognize shapes and what is what but if you look closely nothing match exactly. Probably only flat walls relay match.
"
From what I can see there is plenty of hit boxes to compute some shadows much better. The shadow that are computed are very "cartoonish" they don't really "shade" anything. It seems this was done intentional to keep consistent with the original look and feel and cartoonish look of the game.
I am more interested in trying out a lighting approach that is more realistic and a little bit less cartoonish or a combination of both.
By computing distance from hit point to light source and also the angle of the ray much better shading can be achieved. Even with some basic math.
https://en.wikipedia.org/wiki/Inverse-square_law
https://www.compuphase.com/electronics/candela_lumen.htm
https://www.lightsearch.com/resources/lightguides/formulas.html
I think I used like one formula of that last page to achieve better lighting/shadows then what you have achieved. I also noticed in code, the code didn't know what to do with angles.
So it seems to current shading code is simply lacking.
"But 3d hit boxes do not match graphic."
It doesn't need most likely, the shading can be somewhat in exact, it will most likely still look good, especially if some kind of radiosity is applied by for example shifting the end points a little bit and perhaps blurring/fudging the pixels around it or some other techniques that are yet unknown to me. Perhaps even interpolation between computed shadow pixels, or rendering shadows twice from slightly different light source angles. Different technique can be tried to make it look good in case it doesn't but from what I see so far it's already quite nice, the voxel data that is.
"Yes, there are voxel engines that could show spaces with accuracy like Xcom voxel space but you should be ready to spend years to make some thing like this for OpenXcom."
Perhaps you guys already have done most of the work and it just needs some refining. If you can point me towards where this voxel code is and this rendering code is I can take a looksy to see if I can maybe improve on it or expand on it.
No, my whole point is that there NO code in OXC that could help you with your project. I could say 1% aka loading INITIAL data to memory. Then you need heavy transform to dedicated data structure it and add logic that will traversal it. And this is 99% work and will take at least year.
"TFTD and UFO is SAME game, especially for OXC where you can switch between them on fly."
OXC is same, originals where slightly different, the data could be somewhat different, and certain algorithms could be enabled for TFTD only or some parameters changed. I know original TFTD was a little bit different from XCOM UFO Enemy Unknown. TFTD seemed a little bit more advanced graphically, the title/object shading might have been a little bit more advanced :)
"And how many light sources you plan to support? 1? 3? or maybe 1000+ that is standard for my light engine in OXCE."
This is a good question ! =D
At least +1 for outdoor sun would be a big bonus to this game.
For moon light missions +1 for moon light ! ;)
Interriors of UFOs could be ignored and always fully lit, assuming aliens put light leds everywhere ! ;) or give it a magical feeling, like "magic/hi-tech alien light everywhere".
Kinda makes sense too.. Aliens want to see us so they can blast us.
Another alternative would be if Aliens shut down the light, the light turns green like infrared. As if our soldiers are now suddenly looking in the dark through their green infrared, this could be a very cool effect added to the game.
Inside barn houses, light could be cast from known window tiles. Especially in combination with any outdoor sun vector...
Barn doors same thing, light computations start from there.
Perhaps holes blown into houses also start casting light from there.
And then street lamps.
So it doesn't seem that much.
fire, a LOT of FIRE, that easy can span whole map:
https://media.moddb.com/images/mods/1/50/49281/screen015.png
Handle this. my version is pass limits to handle it and I use lot of hacks to manage it.
The soldiers could remain in darkness or just standard tile shadow/light rendering overlayed maybe with the other rendering, be it sun moon, ufo, barn etc.
How does your engine go up to 1000+ ? Are these 1000 individual light sources ? Or are these openings or reflections or objects where new computations originate from ?
"You can look screens I post there, to create voxel view engine do it in 1-2s on my CPU"
At first glance I didn't recgonize it and thought maybe disconnected pictures of different scenes, but then I started looking at it some more and indeed the scenes seem related to each other.
The big green structures are the ufo, I can also see fences and what appear to be grass boxes or something, interesting.
This should be sufficient to cast some create lights/shadows.
Then when I look at the colored drawing, the shadows are very weak, almost non-existent, they are there, but don't really contribute much to scene.
I am convinced the problem here is how the shadows are applied to the colors, either no formula is used or a better formule needs to be used.
Most likely no formula is used, and simply if the pixel is in shade it's shade is lowered by a weak ammount like -1 or -2, or -3.
I think I actually saw this in code.
So I think I may have spotted the real problem here:
It's the palette. Your shading code is trying to force the shadow color into the pallette.
This whole point of 8bit graphic, shade have only 16 values for each color and number of colors is less than 16.
So now there are a couple of problems/lacks with your shader code:
1. No proper lighting formulas used, does not take into account distance or angle of light, even a simple candle light formula should improve on this.
2. The forcing of the shadow into the palette may be taken away a lot of the fidelity that would otherwise be achieveable. This depends on the ammount of shading colors available in the palette.
Two solutions exist for problem 2 and a third one very maybe:
2.1 Either compute the shadow in 24 bit color and ignore palette.
2.2 Use dithering to increase color possibilities.
2.3 Maybe there are enough shading colors in palette and better search algorithm for closer match needs to be used.
2.3 would be too expensive to do most likely.
So I am not sure if OpenXCom is a 8 bit/vga color game or 24 bit color game ?
But if it's still 8 bit color game, then here is where OpenXCom can improve upon the original ! ;)
For OXCE 8bit is fundamental part of experience. You can change it, but it will not so simple as palettes allow some effects that are not cheap in 24bit colors.
You can look on my OXC repo for some old experiential branches that try recreate Xcom feel in 24bit colors.
-
An easy solution for the bounding box problem of empty air, in other words traversing through empty air, would be two, different possibilities:
1. Easiest/most straight forward solution is:
A special empty air tile map, where each tile map points towards a bounding box. If the pointer is nil, it can be assumed there is no large bounding box and thus the tile should be traversed normally, thus skipped.
If there is a pointer then there is a bounding box volume of empty air. The traverse algorithm is to now clip it's ray against this bounding box, to skip over many tiles. Once the exit is computed it can return to the normal traverse algorithm, where it may yet again encountering another bounding box of empty air on the next tile.
Thus all that is left to do is compute these bounding boxes. Not sure which solution would be best, this kind of reminds me of bin packing problem, but it doesn't have to be so super.
A possible algorithm of top of my head:
1. Start with assuming the entire map 50x50x4 is one large bounding of empty air. Per row/colum/depth it is only necessary to check if there is one title that is filled. If so reducing the initial bounding box, until the largest is found. This would be a greedy algorithm that tries to find a really large one. Once this one is found set all tiles to EmptyAirBoundingBoxProcessed true.
2. Now proceed to next tile which does not have this flag set. Perhaps here use a different algorithm to try and build a bigger box around it.
Algorithm could be: try to grow it vertically, try to grow it horizontally, try to grow it depth wise.
Or maybe even better, try to grow it in all directions, if that fails, see which directions where not possible and finally grow it into direction that was possible. 3D growth is probably most greedy, followed by 2D growth, followed by 1D growth.
Proceed with step 2 until all tiles are processed.
This algorithm will mostlike be much more efficient than octree, because air does not need to be dived into so to speak... just skip over.
-
"changing line algorithm will not fix it"
Changing line algorithm was an experiment to see how the engine works. To see if I can comprehend the hit detection somewhat. So far the line algorithm seems to do "tile" based traversing. Not sure what happens in "voxel check" or something like that. Perhaps there is another algorithm that actually like inside a tile to detect actual voxel hits ?
It was also necessary to examine the line algorithm to see how exact it was and to replace it with a 100% accurate algorithm, otherwise per pixel lightning will look bad.
And it sure was necessary, I could have replaced it without examining it, but examaning it proved/convinced me that it was 100% necessary and that the original line algorithm has serious flaw/inaccuracies. How much this effects the game could be studied further.
The original also had this issue and it always bothered me when I played the original and I also wondered what it would be like if the scanning/line algorithm was more exact. While yesterday that day came and that dream become reality ! =D and it was quite interesting and I could see, feel and notice it.
The quality of the game went up, the ai interaction went up, sometimes the game became a bit more easier because shots would actually connect with aliens instead of end up in the wrong wall. Somethat that always bothered me with this game but no longer ! ;)
I have not tried yet with advanced mods. But that could be fun as well, though it also somewhat scares me a bit, because of boy are the new aliens and weapons powerfull !
First I want to spent my time on trying to improve the graphics before I do a total play through of the game. Because then I hit two flies with one blow:
1. Improved accuracy !
2. Improved graphics !
Then a full play through of this classic is definetly worth it ! =D
Next steps could be:
A. Sound:
3. Better sounds/sound effects real-time generated weapon sounds, perhaps wall reflections and other mods of sounds.
4. Surround sound improvements
5. Doppler effects for bullits zipping past center of camera.
6. Reverb effects inside ufo/metal closures.
7. Water/mud step effects, dampening or bass effects.
8. Wood effects.
9. Ambient scream effects in terror missions, far away explosions, far away screams.
B. Multiplayer
I believe OpenXCom has the potential to become better than the EU/Firaxis gameplay/xcom 1 and xcom 2.
It's time to try and bring that vision alive ! =D
(It's kinda a shame how Firaxis version was not voxel based ? Is it tile based at all ? Doesn't seem like it, I am not impressed with it's destruction effects, OpenXCom has much more potential).
C. Physics effects become possible as well.
C.1. Voxels can fall down.
C.2 Rain can accumillate and flow down roof tops and streets.
C.3 Fog/smoke effects with fluid dynamics solvers in cuda.
C.4 per voxel damage instead of per tile.
C.5 per voxel fire effects.
C.6 per voxel glass/water effects.
C.7 per voxel metal/glow/melt effects.
C.8 per voxel blood/flow effects human/alien.
C.9 per voxel dirt effects flying up into the sky.
C.10 body effects, accumillation of bodies on top of each other or flesh parts.
C.11 per voxel debry effects, accummilation of blown apart parts.
C.12 light effects through holes in walls, and also better spotting.
How much it will be still be original Xcom? why at some point not make "nu-com" like Friaxis did?
And how much you really do? I have too some wild plans to implement in OXCE but majority is nor realized
because time constraint or simply idea was flawed. More you change then more original data will not fit new engine.
Probably easier will be create something from scratch.
So as far as I am concerned there is plenty of untapped potential in OpenXCom/XCOM in general.
Some of it also applies to Doom, and what BrutalDoom mod has done to Doom is quite amazing, but the best is yet to come !
But it do not try add dynamic voxels to engine that did not had it. Fundamentally this is still same game engine wise. Probably only real change in BD is that maps are not 2.5d like original had and you can have multi layered levels.
So faraxis made a mistake to go to easy route and choose an existing game engine, they capped on it's success with an inferior game engine, perhaps it saved them some time, but it may be a dead end in the long run.
New game engines are also being developed, engines that are completely voxel based.
However I consider the voxel engine part the easiest part of the engine, because it's just technical mostly.
What you guys have done, actually re-writing the game logic is most likely the most difficult part, it requires a lot of creativity, lot's of analysis of original game and a lot of programming experience to bring it back to life once again !
A formidabel job !
It would be "shame" to just stop here and don't take it to the next level and let yourself be dwarfed by fancy pancing looking games just because their graphics are a little bit better with opengl/directx and such but don't actually do that much better gameplay wise.
OpenXCom has a lot more potential and it's just waiting to be unlocked ! =D
Perhaps it's time I try to unlock it a little bit. Perhaps you guys have taken it as far as you could, or perhaps not. Perhaps you exhausted (or perhaps fed up with it, but I am happy to see you guys still here and apperently still developing it further or at least corresponding/communication/I was a bit worried you guys might be gone ! =D) or perhaps you want to take a ride on the skybuck train and try and work together to bring something far better/far newer to the scene to blow away the "firaxis" ripp off ! =D and other inferior clones !
I am convinced with the fan base and legacy of XCom plenty of fans/people/artists/programmers may be willing to help to take XCom to the next level where it belongs ! ;) =D
Plus Visual Studio 2019 has advanced and improved a lot to the point where it is actually usuable, Plus your solution project is very good/excellent.
Plus hardware/computer resources have increased to the point where XCom can be taken to the next level.
Perhaps 48 bit rendering might even belong to the possibilities or perhaps that is a bridge just too far cause that monitor hardware is rare but I look forward to buying one soon ;)
Also take a look at MagicaVoxel 0.99.2
https://www.youtube.com/watch?v=mfKx4j-C6nI&t=159s
This may just be the thing that XCom needs/could use to take it to the next level. 3D Artists can use this tool. The tool looks quite complex to me haven't tried it, yet again it does seem useable and not too difficult to create some 3D sprites with.
Also other tools might exist that can do true 3D voxel sprites.
So I see stuff like this from time to time... voxels are making a come back ! ;) =D
Even the latest unreal engine is at the level of voxels, Triangles can become so tiny it no longer makes sense to use it as the basic compute unit for graphics, thus enter the voxel.
Plus voxels can be computed in parallel more easy potentially, very interesting towards the future ! ;)
"to make it work you need full blown voxel engine that allow fast querying ray hits (in log(n) time or even better const time)."
Perhaps.
However the original XCom seemed to be a genius mix of 2D sprite engine in combination with 3D voxel hit detection and 3D tile engine and run length compression of voxel data.
This mix designed to save memory and save on computions and even disk space.
This is what made the game so genius. Trying to keep it like that would at least allow the graphics to become somewhat better.
But perhaps it's time to let loose of this mix and go full voxel to be able to implement more effects.
Or stay with the original genius idea of trying to fake/reduce some of it by using different techniques to accomplish the same.
Like the sprite rendering, instead of rendering 3d voxel sprites, they are pre-computed into 2D bitmaps.
Hard to imagine that something like that can be done for water flow, or smoke flow, or fire flow, but perhaps, at least some pre-computations could be done or some other cheats ! ;) :)
So far I like my bounding box idea of computing as many big bounding boxes as possible to reduce ray/box/voxel intersections. Perhaps octrees could be of some use, or perhaps some new data structure that is more suited for 3d voxel engine.
(I also highly recommend the login time for this forum to be increased to 3 hours or so, otherwise posting like this may be lost, fortunately I am an experienced forumite and I know forums can be shaky as well as accidental side mouse button hits ! However I find this site/forum logs me out unusually fast... little bit annoying)
After some thoughts about this topic, how I would see feasible to implemented "directional" lights in OXC.
First of all, we do not need normals with `float x float x float` accuracy, this is 8bit graphic game with 16 levels of shade.
We could simply `-1, 0, +1` values for each cord, this give us max 3x3x3 values. We can easy make table with each possible vector and store only index in that vector. Index will have will fit 8bit variable.
Now we store this index same as we store 2d graphics (that are too 8bit).
Open question is from where we get this values for indexes that match graphic, one option si have it make by some modder (very specific image that use specific colors for each normal, something that 3d engine do too) or try approximate it form voxel data. This can be done before we start game.
Next question is what light direction is for current tile, I would abandon trying guessing accurate angle, only use general one.
Calculate general angle can be used using my current light propagation engine as most data is already available, we could store 32bit value that store bit for each normal that is facing some light source.
With this two data points (current tile normals and graphic surface normal) we can do simple operation that check:
if ((tileCurrentNormals & _normals[currentPixelNormalIndex]) > 0)
{
drawPixel(currentPixelColor, shade);
}
else
{
drawPixel(currentPixelColor, shade / 2);
}
Logic like this is already present in OXC, if you look on globe it is shaded completely different than original game:
https://www.youtube.com/watch?v=TsgwgH5nVtU
Each pixel of globe have calculated normal based on sphere it should be on.
Using this normal I compare it to current sun position, with this I can determine what shade should given pixel have.
As we can see in this video there is polar night and day correctly handed by OXC.
Overall my solution is lot less ambitious but 100% doable and still could have reasonable performance without rewriting whole game from scratch
-
Concerning the fire / lighting problem, I would solve and change some things:
1. First I would make the fire caused by fire throwers, fire guns more title random, not all tiles in a perfect square pattern on fire.
2. Second for fire explosions I would make the fire also somewhat more random.
3. Perhaps fire should be computed with a different solution like fluid dynamics solver as well for the graphical effect, which kinda bothers me that it all looks the same, quite cheese, the pattern and the graphics all the same.
Anyway with current graphics approach:
4. I would not bother with trying to light cast or shadow cast any tile that is near a fire, because it will be overlit anyway. Even walls right around the corner can probably be ignored because of the reflecting against other walls, though to be sure this could be computed as well, to create some radiosity for the tiles.
5. Only when the light coming from these fires drops of considerably, basically tile range from nearest fire would I actually start applieing light casting/shadows per voxel/per pixel and such to create much nicer shadows.
6. So "flood" filling a light map around fire locations with a maximum range of drop off distance say 5x5x5 or 3x3z3 or 9x9x9 or 10x10x10, perhaps based on darkness setting or whatever looks good for fire.
7. A routine algorithm could be used to determine if there is a photon path from fire to wall behind fire/wall or so... go around basically... a little bit like mine sweeper or something :)
A simple idea could be to set each fire tile in the FireLight map to +5 or +9 or whatever the fall off distance is set to for that map setting/darkness setting.
Then a multi-pass algorithm simply scans the entire 2D or 3D FireLight map... and each time it comes across a counter that is greater than zero it copies and decrements that counter and pastes it into the tiles around it where there are floors and other light passeable tiles, doors, perhaps even windows etc.
Thus this light now gets routed around walls which do not pass light. The number of passes equals the maximum number of this counter.
8. Though I kinda like my reflection idea better... if title/wall is near this 5x5x5 or 9x9x9 then reflect the direction of the incoming light and proceed in new direction, should not be so hard to do this could add some tile radiosity to this light/tile map computation.
Both methods could be tried and I think will work fine.
So in case this idea is hard to understand maybe some pseudo code make it easier to understand:
FireLightMap.Clear;
// set all fire light map title/indexes to max fire light distance where there is a fire on the battle map
// basically add fires to fire light map as basic sources of light
for z:= 0 to MapSizeZ-1 do
begin
for y:= 0 to MapSizeY-1 do
begin
for x := 0 to MapSizeX-1 do
begin
if Map.Tile[X,Y,Z].IsOnFire then
begin
FireLightMap[X,Y,Z] := MaxFireLightDistance;
end;
end;
end;
end;
// compute light routing around objects, assuming maximum eposure/reflection/radiosity
for FireLightMapPass := MaxFireLightDistance downto 0 do
begin
for z:= 0 to MapSizeZ-1 do
begin
for y:= 0 to MapSizeY-1 do
begin
for x := 0 to MapSizeX-1 do
begin
if FireLightMap[X,Y,Z] > 0 then
begin
for SZ := Z-1 to Z+1 do
begin
for SY := Y-1 to Y+1 do
begin
for SX := X-1 to X+1 do
begin
if BattleMap[SX,SY,SZ].PassesLight then
begin
FireLightMap[SX,SY,SZ] := FireLightMap[X,Y,Z] - 1;
end;
end;
end;
end;
end;
end;
end;
end;
end;
So that should spread around the light where it can go.
Anyway some clipping/checks/optimizations could done for above code, though since maps are pretty tiny, I don't think this will be much of a processing problem.
For the light reflecting of walls/direction idea it could be sufficient to make the light "creep" along the tiles into a certain direction instead of automatically doing this in the inner loop above.
So the outer loop remains the same:
ProcessAllLightCreeps
Basically three x,y,z loops, that look for a light tile in the FireLight map which is set/occupied, for example .Counter > 0
Then instead of automatically copieing it the direction flags are checked:
Perhaps each light should have multiple direction flags.
Coolest would be to use 9 direction flags. this would be for 2D but for 3D we need a bit more.
So basically 9x9x9 not to bad still, could be cool.
So basically a direction array would suffice and be easy to automate in code.
It would still be necessary to give the light creep an direction.x, direction.y and direction.z
Now it might seem we might as well create photons, maybe we should, but let's not and just use a single voxel to present a photon as if it were going in one direction or so...
so that ultimately it doesn't become a big computational mess, though scattering around actual photons could also be interesting but for now let's try an algorithm which uses
the voxels itself to spread light around. Or in this case the tiles I mean... the tiles spread light around as if there is reflected light coming from these tiles/walls.
So when a tile is a wall.. it will start reflecting these directions that get spread across the light map.
So each "light voxel" or in this case each "title light" has a direction.x, direction.y, direction.z in which way the light is cast by a fire title before it.
Now if a fire is already on the light tile itself then ofcourse it spreads fire in all directions.... but pass 1 either takes care of that or we can set a special flag or special value to indicate
this... in case we want to not code multiple passes or different for loop sections and put it all in one for loop, this is not such a bad idea because it does save on iteration of index variables
and that could get expensive if the map is large or if we want to do the same kind of computations for actual voxels in perhaps a later algorithm.
So let's expand this concept to be ready for voxel implementation as well, where it might be usefull:
Voxel.Light.DirectionX := -1 or 0 or 1
Voxel.Light.DirectionY := -1 or 0 or 1
Voxel.Light.DirectionZ := -1 or 0 or 1
Here we can introduce a special value perhaps
Voxel.Light.DirectionX := 255; // all directions
Now let's see if we can do a voxel based light pass for let's say one shitty fire voxel hehe. This could be cool if we want to do fire voxel effects... Like explosions from riffles or bullits hitting
walls or crispy burning fire where some voxels are wood going up into the air... or some magical alien plasma effects etc.
for Z:= 0 toVoxelsZ-1 do
for Y:= 0 to VoxelsY-1 do
for X:= 0 to VoxelsX-1 do
begin
if Voxel[X,Y,Z].DirectionX = 255 then
begin
Voxel[X-1,Y,Z].Counter := Voxel[X,Y,Z].Counter-1;
Voxel[X+1,Y,Z].Counter := Voxel[X,Y,Z].Counter-1;
end else
if Voxel[X,Y,Z].DirectionX = -1 then
begin
Voxel[X-1,Y,Z].Counter := Voxel[X,Y,Z].Counter-1;
end else
if Voxel[X,Y,Z].DirectionX = +1 then
begin
Voxel[X+1,Y,Z].Counter := Voxel[X,Y,Z].Counter-1;
end;
if Voxel[X,Y,Z].DirectionY = 255 then
begin
Voxel[X,Y-1,Z].Counter := Voxel[X,Y,Z].Counter-1;
Voxel[X,Y+1,Z].Counter := Voxel[X,Y,Z].Counter-1;
end else
if Voxel[X,Y,Z].DirectionY = -1 then
begin
Voxel[X,Y-1,Z].Counter := Voxel[X,Y,Z].Counter-1;
end else
if Voxel[X,Y,Z].DirectionY = +1 then
begin
Voxel[X,Y+1,Z].Counter := Voxel[X,Y,Z].Counter-1;
end;
if Voxel[X,Y,Z].DirectionZ = 255 then
begin
Voxel[X,Y,Z-1].Counter := Voxel[X,Y,Z].Counter-1;
Voxel[X,Y,Z+1].Counter := Voxel[X,Y,Z].Counter-1;
end else
if Voxel[X,Y,Z].DrectionZ = -1 then
begin
Voxel[X,Y,Z-1].Counter := Voxel[X,Y,Z].Counter-1;
end else
if Voxel[X,Y,Z].DrectionZ = +1 then
begin
Voxel[X,Y,Z+1].Counter := Voxel[X,Y,Z].Counter-1;
end;
end;
So this is a very nice voxel spreading loop/pass which automatically causes the light to go out at distance and it can act according to voxel direction.
Now that this voxel light spreading light is in place all that is left to do is invert directions if it bounces against a wall or something.
Maybe we have to do that before the voxel goes into it's current direction.
So inside that for loop some extra code should be placed:
if Voxel[X,Y,Z].DirectionX = 1 then
begin
if Obstruction[X+1,Y,Z] then Voxel[X,Y,Z].DirectionX ;= -Voxel[X,Y,Z].DirectionX;
end else
if Voxel[X,Y,Z].DirectionX = -1 then
begin
if Obstruction[X-1,Y,Z] then Voxel[X,Y,Z].DirectionX ;= -Voxel[X,Y,Z].DirectionX;
end;
Now here is a problem we could have written this code as:
If Obstruction[X+Voxel[X,Y,Z].DirectionX,Y,Z] then Voxel[X,Y,Z].DirectionX := -Voxel[X,Y,Z].DirectionX;
So to save on unnecessary branching it might be better to store "AllDirection" into a special flag/field or so...
And that should be basically it. Obstruction can be replaced by some code or function that detects an obstruction or even better Reflection
if Reflection(X+Voxel[X,Y,Z].DirectionX,Y,Z] then Voxel[X,Y,Z].DirectionX := -Voxel[X,Y,Z].DirectionX;
if Reflection(X,Y+Voxel[X,Y,Z].DirectionY,Z] then Voxel[X,Y,Z].DirectionY := -Voxel[X,Y,Z].DirectionY;
if Reflection(X,Y,Z+Voxel[X,Y,Z].DirectionZ] then Voxel[X,Y,Z].DirectionZ := -Voxel[X,Y,Z].DirectionZ;
Pretty cool, hope it works and looks good ! =D and runs in hopefully reasonable time ! ;) otherwise only apply it to tiles and not voxels ! ;)
So would be nice if there were templates or some generic type to apply this algorithm too.
Here is where perhaps Delphi's generics might shine and be a bit more friendly/debuggeable.
Not sure if I would like c/c++ template implementation but little choice I guess... then again copy could be copied and pasted and adjusted changed for tiles and custom code and effects could be done.
-
Though in case of many fires the light could be spread in multiple directions and thus then it would be more interesting to record in which way the lights are moving across the voxels.
So then each voxel would have to have a direction entry per possible direction.
So than it becomes
Voxel.DirectionX[0..2]
Voxel.DirectionY[0..2]
Voxel.DirectionZ[0..2]
This would offer more flexiblity than the all value per direction, which would be a form of compression.
Thus we might as well write the whole thing as:
Voxel.LightDirection[-1..1,-1..1,-1..1] of byte;
This is where pascal/delphi arrays would be a bit more handy, since indexes start at different offsets.
Not sure if C/C++ can do his.
This direction array allows each voxel to accumate light coming from different voxels.
Another interesting idea could be to collect intensity/candice/lumen or whatever it's called hehe.
Voxel.Intensity[-1..1,-1..1,-1..] of Float or Double;
Not sure if this is usefull but maybe.
Also very maybe distance or min/max distance could be recorded
Voxel.Distance
and maybe
Voxel.Angle
Not sure if these fields make sense but could be interesting.
You also wanted a normal... but not sure if this is usefull maybe for interpolating between adjectent voxels but this could also be computed, but maybe storing it could also be nice.
Or a voxel could even be treated as a sphere lol.
(Voxel.Angle could be an even bigger array, maybe of list, of incoming cones/pyramid of lights to perhaps end traversion quicker, that was another idea I had but involves some math so didn't bother with it for now. So idea here was to consider a voxel emitting light if it already receives enough light of other voxels from a certain direction. but maybe this is a flawed idea.)
-
First of all, please use
[code][/ code] //without space!
tag to mark your code, it easier to read this way.
For your rest of your post, you missed one important point, fire light have range of 16 tiles, and changing this will change gameplay.
But rest of your solution is valid one. I my self plan some thing similar to implement for OXCE.
one difference that I need "flood" not for light but for "darkness". Right now my code fail when you have lot of light sources that are block by level floors.
engine can't easy say what light need be consider to when I need update given tile.
Solution is simple, I flood "darkness" from given tile and any tile reach in straight path from initial tile will be reset to black. Then for every reset tile I try calculate what light shine on it.
This is one commit that tweak my logic:
https://github.com/Yankes/OpenXcom/commit/ef2b9233d9fbc9f938934f9243c938cc7e84f89c
Idea is that you have "glowing" box of multiple tiles radiate light in every direction, and you can approximate all tiles that that are shine upon by visiting every tile only 4 times. This mean if you have map 100x100x100 you need do only 100x100x100x4 iterations of this script to have result. This mean this is effective O(n) complexity.
-
"
Why trying to parallel one ray? You will only duplicate work/waste work/complicate logic, you have hundreds other independent rays to compute. You can simply parallel processing of each row of your screen and rays that begin form it.
"
I am not sure if fast voxel traversal algoritm is completely numerically stable. There may be some floating point cases where it goes one voxel to far. Either it's numerically unstable or my clipping code is unstable or both are unstable. Trying to find two stable algorithms. But for now focusing on this traversing, which does not seem numerically stable.
And thus to get it stable all integer points on line must be computed individually and then it could be done in parallel, to speed it up, because it will require many divisions to get it stable and thus the traversing algorithm will become much slower and thus some threading to speed it up could counter that.
Maybe it's also possible to use SSE computations... didn't think of that until just now hehe. That be could.
I know SSE can do 1 or 2 bytes in parallel, maybe even 4... not sure if SSE has division instructions.
(Problem with current algorithm is it seems to overshot the grid by 1 voxel in some cases, don't know why)
-
The posted fast voxel traverl algorithm does have begin/end issues if line is directly on grid boundary, perhaps in future better versions will be created.
The cx,cy,cz checks to stay inside map should fix that and not allow this algorithm to go outside.
All that is needed now is some clipping of the line against grid and then it should no longer "hang" openxcom occasional because some lines are totally outside the grid I think.
-
(Clipping Line/Point vs Box/Grid/Map intersection for fast voxel traversal algorithm has been implemented successfully !)
Example/collision/ray detection code is implemented in TileEngine calculateLine:
Final branch for fast voxel traversal algorithm for calculateLine containing cleaned up code:
https://github.com/SkybuckFlying/OpenXcom/tree/FastVoxelTraversalAlgorithmImplementation
Pull Request for it to end up in OpenXCom master:
https://github.com/OpenXcom/OpenXcom/pull/1374
Also refactor attempt video, which failed somewhat but at least code was cleaned up:
https://www.youtube.com/watch?v=SIbsKB0ej24
Work has started on the new shading engine on this branch:
https://github.com/SkybuckFlying/OpenXcom/tree/ShadingEngine
Also a youtube video about it, New Light Engine preparations for OpenXCom:
https://www.youtube.com/watch?v=Ck3VpRq5FZs
-
Do not post the same posts in multiple threads.
This is your second and last warning.
-
Further ideas that could be worked out.
To align the sun with the geoscape, some code could interact with the geoscape.
It would probably usefull to test if the sun can actually hit the point of action, landing site, base, could make an exception for the alien base hehe.
If the sun does not hit the point of interest, then check for the moon to see if it can hit it.
This way moon light can also be implemented.
For extra wow factor it would be cool if there was:
1. Actual sun coordinates at realistic distance from earth.
2. Could even allow sun to travel through galaxy, or wobble but this is probably too excessive.
3. However do have a real earth rotate around the sun.
4. Have a real moon, rotating around the earth.
5. Other planets could be cool as well, for example for solar eclipses that would be cool haha. That be very freaky if suddenly the moon's shadow would be moving across the battlescape.
This would make it a hell lot easier to do some coold things. However some compensation in these coordinates may have to be made to account of tiny tile space and voxel space, maybe scale them down, or even better, keep them as they are in reality and scale any tiles up so they actually much through scale, like meters and such and go from there.
If realistic sun distance leads to over exposure and doesn't look good we can then try something else.
What I look forward to is long battles where the sun is setting and long shadows falling across the map. For this to work well, the battlescape may have to be extended infinitely maybe even have a slight curve so that at least the sun rays are blocked if the sun goes down and doesn't start hitting barn walls and roof tops.
Concerning moon light and perhaps morning situation, perhaps some fog could be added, and some watery vapor stuff on flowers/grass, etc, that be funny too, bit like micheal jackson thriller I guess, it's a horror game/theme after all ! =D
Actually adding some graveyard graphics would be cool, though in eu xcom 2 I found it slightly offense that crys would come out of the graves... hmmm.. also a church would be cool. Not sure if original game data already has a church.
Anyway for implementation inspiration, there is open source software called "stallerium" maybe inventing one of them programmers to write a little bit of code for this game could help and would be cool, or at least write up some formulas or so, or maybe it's easy to find the code for sun, earth, moon and planets and such.
Other planets can most likely be ignored, unless someday looking at the sky is also implemented. And even satelittles could be added or the entire stallerium lol but that is pushing it a bit, this would create strange lights in the sky sometimes ! ;)
Oh by the way, definetly check out the movie called: "moonfall 2022" it was a pretty cool movie ! ;) Not bad for a "b-movie" =D
-
I need this code:
/**
* Universal blit function
* @tparam ColorFunc class that contains static function `func` that get 5 arguments
* function is used to modify these arguments.
* @param dest_frame destination surface modified by function.
* @param src0_frame surface or scalar
* @param src1_frame surface or scalar
* @param src2_frame surface or scalar
* @param src3_frame surface or scalar
*/
template<typename ColorFunc, typename DestType, typename Src0Type, typename Src1Type, typename Src2Type, typename Src3Type>
static inline void ShaderDraw
(
const DestType& dest_frame,
const Src0Type& src0_frame,
const Src1Type& src1_frame,
const Src2Type& src2_frame,
const Src3Type& src3_frame
)
{
//creating helper objects
helper::controler<DestType> dest(dest_frame);
helper::controler<Src0Type> src0(src0_frame);
helper::controler<Src1Type> src1(src1_frame);
helper::controler<Src2Type> src2(src2_frame);
helper::controler<Src3Type> src3(src3_frame);
//get basic draw range in 2d space
GraphSubset end_temp = dest.get_range();
//intersections with src ranges
src0.mod_range(end_temp);
src1.mod_range(end_temp);
src2.mod_range(end_temp);
src3.mod_range(end_temp);
const GraphSubset end = end_temp;
if (end.size_x() == 0 || end.size_y() == 0)
return;
//set final draw range in 2d space
dest.set_range(end);
src0.set_range(end);
src1.set_range(end);
src2.set_range(end);
src3.set_range(end);
int begin_y = 0, end_y = end.size_y();
//determining iteration range in y-axis
dest.mod_y(begin_y, end_y);
src0.mod_y(begin_y, end_y);
src1.mod_y(begin_y, end_y);
src2.mod_y(begin_y, end_y);
src3.mod_y(begin_y, end_y);
if (begin_y>=end_y)
return;
//set final iteration range
dest.set_y(begin_y, end_y);
src0.set_y(begin_y, end_y);
src1.set_y(begin_y, end_y);
src2.set_y(begin_y, end_y);
src3.set_y(begin_y, end_y);
//iteration on y-axis
for
(
int y = end_y-begin_y;
y>0;
--y, dest.inc_y(), src0.inc_y(), src1.inc_y(), src2.inc_y(), src3.inc_y()
)
{
int begin_x = 0, end_x = end.size_x();
//determining iteration range in x-axis
dest.mod_x(begin_x, end_x);
src0.mod_x(begin_x, end_x);
src1.mod_x(begin_x, end_x);
src2.mod_x(begin_x, end_x);
src3.mod_x(begin_x, end_x);
if (begin_x>=end_x)
continue;
//set final iteration range
dest.set_x(begin_x, end_x);
src0.set_x(begin_x, end_x);
src1.set_x(begin_x, end_x);
src2.set_x(begin_x, end_x);
src3.set_x(begin_x, end_x);
//iteration on x-axis
for (int x = end_x-begin_x; x>0; --x, dest.inc_x(), src0.inc_x(), src1.inc_x(), src2.inc_x(), src3.inc_x())
{
ColorFunc::func
(
dest.get_ref(),
src0.get_ref(),
src1.get_ref(),
src2.get_ref(),
src3.get_ref()
);
}
}
}
to collect some data so instead of ColorFunc::func it should do:
ShadingEngine.Collect( x,y,z,source_surface,source_tile )
I am struggling with the surface part... I don't quite understand these templates and what is passed into them...
I uploaded what I got here:
https://github.com/SkybuckFlying/OpenXcom/tree/ShadingEngine
Look for this code:
ParaShadingEngine->CollectData( x, y, src0_frame );
// dest.get_ref(), src0.get_ref(), src1.get_ref(), src2.get_ref(), src3.get_ref());
Won't compile, some kind of type conflict, I also tried src0.
-
What you need exactly? Why you even try use this function? This is function for 2d graphic bliting not function to "collecting" any thing.
Beside x and y are not thing you are expecting, look what value range they have.
-
The painter's algorithm draws over the tiles.
So that the final pixels that are visible are of certain tiles and certain sprites.
It would be very usefull to know which tile and which sprite or surface each pixel on the screen came from.
So basically if you could provide one or multiple 2d maps that contain this data that would be usefull. I already wrote a GenericMap class.
So basically it would be something like:
Per screen pixel x,y:
mSurface[x,y]
mTile[x,y]
mX[x,y]
mY[x,y]
mZ[x,y]
It would also be usefull to know the X,Y,Z of each screen pixel. The x,y,z would then be the voxel coordinate across the map.
Could also be stored as
mXYZ[x,y]
Where these are struct int x,y,z
Once that data is known the shading engine can then compute/calculateLine:
Per pixel x, y:
TraceRay( FromSunX, FromSunY, FromSunZ, ToX, ToY, ToZ )
The ToX, ToY, ToZ needs to come from this collect data.
So algorithm for per pixel shading would be:
(inverting the trace for maximum precision):
phase 1:
for screen y
for screen z
store DestX,DestY,DestZ
phase 2:
for screen y
for screen x
AcquireDest( screen x, screen, y, DestX, DestY, DestZ)
Hit[x,y] := Trace( DestX, DestY, DestZ, LightX, LightY, LightZ );
Hit indicates if the light beam hits the dest or not.
Once that hit array is computed the rest can be computed as well.
For this the color of each pixel on screen should be known as well.
mColor[sx,sy]
-
So phase 1 should be something like:
Map::drawTerrain
modify such that, for each pixel that it blits to the screen:
mColor[X,Y] := color of surface/sprite/wall/etc.
mXYZ[X,Y].X := voxel x across map
mXYZ[X,Y].Y := voxel y across map
mXYZ[X,Y].Z := voxel z across map, computing this is the hard part... perhaps you know a formula... how to calculate this... for walls and maybe also sprites.
This is probably the only thing that needs to be stored.
The reason why I was trying to store surfaces and tiles is to try and compute the Z later, which is difficult, but if it can be done at once, then don't need to store tile and surface and such.
-
Do not try mix voxels with surfaces, both are independent, `Map::drawTerrain` will put pixels where is no voxel and voxel will be on places where no surface pixel is draw. Another thing is that as voxel is 3d and surface is 2d you will have lot of collisions.
Beside for given tile data there is static relation between voxel in given tile and surface draw for given tile. You do not calculate it each frame, this could be precalculated before game starts. And during game you will need only add voxel offset for given tile.
-
I need a relation from screen x,y back to voxel x,y,z.
Since the screen can also move, it seems necessary to re-compute which screen pixel x,y is related to voxel x,y,z.
Also since screen x,y are in "diamond space" and the voxels are in regular grid space, a conversion needs to happen I think.
(Doing it this way prevents the need for a ray-tracer)
Since the drawTerrain/Bitmap drawing routines known and convert voxel space, grid space, screen space, and also sprite space to diamond space, screen space, pixel space whatever, there should be a way to create this relation ship and store it.
Basically this relationship is an index or pointer from screen to voxel space. This is usefull so that only the visible voxels need to be "light/shadow traced" later on.
So it seems this relationship needs to be build inside the bitmap draw routine... it knows where the final screen x,y is and it also indirectly knows where it is coming from, a certain tile, which has a certain sprite or unit inside of it which ultimately decided the color of this screen x,y.
The difficult will also be to convert the sprite/screen x,y/color to a voxel x,y,z, sometimes this may be easier for certain walls, for sprites this will be more tricky, unless the lofts could be used to figure out which sprite pixel corresponds with which loft voxel. This relationship may also need to be build later... for units.... where the loft may need to be rotated to correspond to a certain sprite direction.
-
I tried this idea a little bit in this branch, maybe we can cooperate in this branch:
https://github.com/SkybuckFlying/OpenXcom/tree/ShadingEngineYankes
So far it seems to be drawing the floor a little bit.
If you see a way to improve on it that be great ! ;)
(So far these just some experiments, later after some good night sleep, I may give it some more serious try and maybe try out different things, maybe even a ray tracer... might be simpler than dealing with bitmap clippings and what not... not sure yet... though I also still kinda like this painter algorithm... but the conversion from screen to voxel might get expensive if this has to be done per screen pixel... there might be a better way though, but again it will get a little bit complex with the formulas and loops and the efficiency...).
-
I only can give you suggestions or answer simple questions, analyzing your code or contributing it out of question. I have my own project to do.