AndrewScheidecker / BrickGame

A demo of Minecraft-style voxel rendering in UE4
398 stars 145 forks source link

Water Simulation? #20

Closed iUltimateLP closed 7 years ago

iUltimateLP commented 8 years ago

Okay, lets get to a real hot topic. Water simulation? How would I proceed? And, how do I generate just a simple ocean? I think I need to drop my project because this is all stuff I'm not aware of :cry:

miguelemosreverte commented 8 years ago

Hey I did it. Not the real-time flooding part, but the part where water instantly floods what it can, being the only parameter to it that it should never flood anything taller than its origin point. (Which is a gross simplification, given pascal law and all).

So, the idea is simple, for it to work fast I developed a data structure (not compressed... which is bad), that stores every possible 2d surface for a given 3d lake/ocean.

I can make a pull request if you guys think it is a good idea. Oh, but here is the kicker, and this Scheidecker probably knew all the time: About the water. You can drag and drop any water material to the surface material of a given block material. Which is awesome. Here is a screenshoot of my results: (You can find the water material I use here: https://github.com/UE4-OceanProject/OceanProject)

screenshoots:

water

And by doing some tweaking now the blocks under water blocks are rendered too:

translucent water with the blocks rendered correctly under water surface

iUltimateLP commented 8 years ago

That looks awesome! Sure thing that you can apply any material you want onto stuff, so I would like a pull request :+1: :joy:

miguelemosreverte commented 8 years ago

Give me a sec (maybe a couple days) to clean it up so it is ready to merge, and then I will make the pull request. About the data structure, on a basic level it stores the FInt3 Coordinates of the bricks that conform each one of the XY slices of a XYZ lake. Something I am working on is to reuse that information for custom pathfinding. Because if you use the collision of BrickGrid along with UE4 NavMesh you will get unrealistic movement: People will find no trouble climbing unnecesary elevations. But if you use the data of the lakes, then you could develop your own pathfinding (which could be cheaper) where the people will always walk on flat surfaces, unless its not possible.

iUltimateLP commented 8 years ago

Nice to hear that somebody is actually working here :+1: Looking forward :)

miguelemosreverte commented 8 years ago

My goal is an RTS on top of a voxel world, whats yours?

iUltimateLP commented 8 years ago

A crossover between Starbound + Minecraft + Factorio :joy: Not even sure if I bring this to a certain point

miguelemosreverte commented 8 years ago

Sounds like you are going to work a lot more than I on the gameplay dynamics. Factorio especially, is all about that. Tons of different options and winning strategies.

iUltimateLP commented 8 years ago

Yep, and I'm not sure if I even finish this, but if I do, it'll go on Steam :)

miguelemosreverte commented 8 years ago

Greenlight is the way to go. Kickstarter + Greenlight, really. Kickstarter can be used for the money, but the exposure is in my opinion more important. There you can find artists ready to work on the art on top of your game. Maybe not kickstarter, is not like I have done proper research, but on a general scale, that would be the way to go. Develop the logic, expose the product, find the team (ussually the artists), and then Greenlight. Maybe I am wrong but, again, its not like I am close to that part of the developing process so.

What I sometimes find weird is what is the motivation of Andrew to build this absolutly fantastic piece of code. I mean, you want to make your game, I want to make mine, whats up with the creator of the most complicated part of the work we are working on top of? I would not be suprised if tomorrow a game is shipped and it was made by Andrew. I am ust curious what genre would it be of. One thing is certain, it would have a Minecraft feel to it for sure.

iUltimateLP commented 8 years ago

I don't think he is working on this currently. I hate people calling games "Minecraft Ripoffs" just because they share the way of doing a terrain and a building system...

miguelemosreverte commented 8 years ago

Indeed! Is like minecraft has the monopoly of voxel use in games! That said, given the popularity of it, it can be said that games using cubes as the representation of voxels have a similar aestethic. *aesthetic

iUltimateLP commented 8 years ago

Does your simulation also generate water lakes through the world or does it only support "oceans" yet?

miguelemosreverte commented 8 years ago

Not really a simulation, but a reduntant database. The information I am creating is implicit on the Region.BrickContents. It satifies the following query:

What bricks can I "flood" from this location. Where "flood" means access all adjacent empty bricks of the same height or less.

You could access this information by using a search algorithm every time. Or you could "cook" it. Which bring us to the redundant database. Now, about its data structure:

It works like this. Inside the function SetBrick it checks if the brick set is of a given material. Lets say the material that floods depressions is 1. And the material used for the water effect is 9.

Then it accesses with the given coordinate to an index file that says what lake this block belongs to. On this file, absolutly all the blocks coordinates are linked to LakeIndexes. Non Empty bricks has a LakeIndex of -1, as they cannot be flooded. A LakeIndex is the key to then access the Lake information itself. Right now if you see a LakeIndex of 4, it means the LakeInitialCoordinate was X = 0, Y= 0, and Z = 4.

Anyway. With the LakeIndex found, now you can access the lake information, which is inside the file that has the LakeIndex as name.

Inside the file you can access all the floodable bricks, and for each one of them you change their material and boom. The lake/ocean is flooded.

To make things more complicated: Everytime I talk about accesing a Lake information, well, I should be saying LakeSlice information. Because there are as many slices in a lake as possible floodable heights. So say you are flooding a recipient at the middle, for it to flood only to the middle it would use the LakeSlice that correspond to the middle of it, not the one at the top. So, with that out of the way, how then can you flood the LakeSlices underneath the one you are flooding?... Each LakeSlice has the information of what LakeSlices to flood underneath:

example

So, in this way, now you store all the floodable bricks for each LakeSlice, and the indexes of the underneath LakeSlices too.

Next complexity step: How to simulate the breaking of a dam?

You add a third reduntant information to the data structure. Now each LakeSlice stores it X, Y, and -X, and -Y frontiers. Each one is an array of brick coordinates. This way when you destroy a brick you check its LakeIndex, or LakeSliceIndex, whatever. Uhm... well, not literally the coordinates of the brick you are goind to destroy, but the one adjacents to it. That sounds right. Okay so you access the LakeSliceIndex of each one of the adjacent bricks and if that adjacent brick belongs to the frontier of the LakeSlice then you create a flooding brick on the place of the brick you just destroyed. And boom, now you can breaks dams, or any water recipient, and expect flooding.

AndrewScheidecker commented 8 years ago

@miguelemosreverte, that looks great!

I'd definitely merge a pull request to make translucent bricks render correctly. If you submit a PR for water flow, I'd consider merging it, but only if I was prepared to support the code (though I know my support lately has been lacking). Even if I don't merge it, the PR can still be helpful for other people who want to use your changes.

From reading your overview of how it works, my primary concern would be the performance of recomputing the flood volumes when a brick changes. If you add or remove a single brick, it could cause the flooding information to change over a very large area, so it might be hard to do incrementally. I think that's an argument for something more like Minecraft, Dwarf Fortress, and other games that implement water that flows from block to block in real-time: it localizes the effect of modifying the bricks.

What I sometimes find weird is what is the motivation of Andrew to build this absolutly fantastic piece of code. I mean, you want to make your game, I want to make mine, whats up with the creator of the most complicated part of the work we are working on top of? I would not be suprised if tomorrow a game is shipped and it was made by Andrew.

BrickGame was a fun side-project I did when UE4 was first released publically, and wanted to provide an example to folks how to implement rendering plugins like this. I've just been doing minimal maintenance work since then, except for my VXGI experiment. You don't have to worry about me competing with you if you want to release a game using this code!

miguelemosreverte commented 8 years ago

I knew you where going to be specially attracted to the implementation of translucent bricks, because while flooding algorithms are cool and all, they can made with time and effort. But tweaking the render code? That requires more thought! And you specially would be, if not the only one, the one to know this since you are the creator of it!

So, yeah. With that to a side (looking back to it I just added two or three lines of code, its not impresive to look at if you do not know the complexity of the code), about the flooding algorithm:

Cellular automaton is a naive algorithm, it does not provide scalability. What I am looking for is to make the information much more redundant, to the point where PC A can say to PC B:

"PC A : Hey, remember the LakeSlice 204534 of the Region 300? PC B: Yup. PC A: Player 0 just flooded it. These are the holes done, so you know the flux. PC B: Right. So given all the previously recorded data, we both know it will take an hour to fill. PC A: Yup. Important locations flooded include: This guy castle, and etc. PC B: I know, why are you telling me this? PC A: Sorry, sometimes I forget the flooding logic is deterministic. PC B: Duh."

So, the idea would be that by having a reduntant dabatase communication would be small, if at all needed. About the real-time super cool flooding effects I believe a centralized cloud-based computing could solve the problem. It would give the clients the vertices of the poligon used for the wall of incoming water. Okay, I am rammbling away. I expect to have the Pull request ready for today .

If my database teacher heard me talking about redundancies as a good thing he would be so mad...

iUltimateLP commented 8 years ago

When I was thinking about basic water simulation, my idea was pretty simple: When you populate the blocks according to the noise (the three loops), you basicially get every block which is below a limit (like the material selection works right now) - the sea limit. Then when a block is under the sea limit, you create an additional block which goes some values below the original one in the height axis. That forms the ground of the sea. The block you had originally is the new sea block, so that gets the ocean shader on it. Two problems still: aligning the post process volume to fit under the blocks, and second: the transition between non-water and water would be rough, as non-existent.

miguelemosreverte commented 8 years ago

Oh do not worry about the post-process volume. Andrew gave us the example on how to create redundant blocks on top of each other: You have the ones you use to render, and all is good. But now what about collision?? Well, as seen in the example given, you create collision boxes in the exact same spot. Do the same with post process and then with Physics Volumes (to add buoyancy forces, for example) and you are done!

I believe I should appoint this as my next task now that I see the urgency of it. Now a problem I should solve too is when you use a tesselated material on the rendering brick, and the brick surface goes higher in space, but the collision, PP, and physics boxes are still the same size. Now thats a problem. And if Andrew does not hace a space under his slive then we are all doomed! hahaha *spade under his sleeve not space under his slive

iUltimateLP commented 8 years ago

I look forward to test your pull request out! Thanks for contributing to this and helping me with it the same time!

miguelemosreverte commented 8 years ago

I guess so, but really, thanks to Andrew. He is exactly what every developer community needs. To code for fun speaks volume of his qualities as a programmer. Is like those olimpic runners that go to "work out" every day and by working out I mean do stuff we mortals can only imagine because we grow tired half way.

miguelemosreverte commented 8 years ago

ISP change complicated downloading the repository. Downloading it now. Delay 1 day. Oh and Nvidia open sourced Gameworks.

iUltimateLP commented 8 years ago

Oh nice! Could this also allow glass blocks?

miguelemosreverte commented 8 years ago

sure. A list of transclucent materials could be implemented so that instead of just checking for material 9 it would check for the ones you added as translucent.

iUltimateLP commented 8 years ago

Nice stuff! I will test it out soon!

miguelemosreverte commented 8 years ago

First problem found: All this time it worked because the water flooded until it found a non empty cube. But now, by spawning translucent blocks with empty neighboors at the sides, this happens:

image

The translucent cube has vertices with index 0 at the sides. This way the only well rendered translucent cubes are the ones surrounded by other cubes: (which had been the case until not long ago):

image

image

Bassically its a matter of changing the vertex index of the two bottom vertices on the side faces of the translucent cubes. I will get onto it. But for now, you have the same code I used to make translucent surfaces for water.

See how the faces at the other side are invisible? Well they are not, they too have vertices with index 0 and go straight down to the corner of the region.

Same problem with the top surface faces: Right now it only works right if it has non empty neighboors to the sides:

image

image

image

image

image

It should be easy to fix.

iUltimateLP commented 8 years ago

It should be easy to fix.

For you my friend, for you :joy: :+1:

miguelemosreverte commented 8 years ago

I am trying to find a pattern:

Before (orange silouettes represent how the cubes should look like, but dont) image After (I add more non empty bricks to the sides) image

iUltimateLP commented 8 years ago

it looks like there is an vertex missing to make it a rectangle..

miguelemosreverte commented 8 years ago

Yup. Vertex Index = 0 ---> Problem image

iUltimateLP commented 8 years ago

Couldn't you just add another vertex to that position (maybe there are two missing because of the lower one of the two)?

miguelemosreverte commented 8 years ago

Exactly. Trouble is to understand why this has gone wrong, since in theory this should not be happening. But... oh well. It will be a matter of looking at the code for a while sipping coffee. Will update immediately when the culprit is found.

Edit 1: I think I solved it: Debugging breakpoints show that only once per translucent brick the boolean IsTranslucentBrick is true. Which sound right, right? Not at all. That variable used to be called something like IsWaterLocalVertex, or along something along those lines. The thing it that every time that was true a vertex was created. And behold, it was only true once per translucent brick. So only one vertex was created. What was I thinking. Anyway. That has been changed, and the code is bug free now. Enjoy your glass cubes!

miguelemosreverte commented 8 years ago

Bug free version uploaded to the pull request: image

iUltimateLP commented 8 years ago

Good work!!

iUltimateLP commented 8 years ago

My little test: image So, back to water. I'll test out later if I can just put a water shader on a block and place it that way. In generation terms: Would you mind sharing the generation of the ocean? Maybe in a seperate Pull request?

miguelemosreverte commented 8 years ago

Absolutly. But first I think I should share the database first. Because it was the implementation of it that speeded up the access and modification of bricks contents.

Then this could happen:

image

Each one of those pieces of rock is a differerent BrickGrid. They access their contents in the following manner: An FString variable is added, the BuildingName. Or StructureName. The important part is that with that name it can access the file that contains both the BrickContents themselves as the "flooding" information. Which can be used to modify all the bricks contained in a lake, (which Scheidecker is right, is a bad idea. I had to copycat his implementation of multithreading to allow for stable framerates during flooding. To defend my code, it was a placeholder all along for a better solution), but also allows for a more nutritious indexing of the terrain. Thats what I am refering to when I show the PC's talking to each other. With this extra layer of information, the communication is much more efficient.

Last point about a custom made data base, then you can import Minecraft schematics with a little bit of code. Third party software like World Machine generates absolutly gorgeous terrain. Then the heighmap can be imported to UE4. Or it can be read by WorldEdit which converts it to voxels. WorldEdit creates minecraft schematics files with then can be read and converted to our own database.

I have done this, the question should be about legal problems. Is it legal to do this?

*I forgot to say and maybe it is not obvious: This database would allow to only calculate once the terrain generation of a region, since then it would read it from the database. And it would only access X terrain generation parameter if StructureName was X. This would allow for biomes too. Oh and right now I am working on merging the buildings with a flat brickgrid under them. Really important mechanic on an RTS, to place buildings. One the merging is done the building brickgrid itself is deleted or moved to a far far away coordinate.

iUltimateLP commented 8 years ago

Hmh, I don't get where "having different brickgrids in one level and allowing them to join each other" and "water flooding" meets. Oh, and could you please do a new post if you find something out instead of edits, because I don't check this page daily and then I miss some stuff :joy:

miguelemosreverte commented 8 years ago

Yeah, I do not see that connection either. It derrailed there, but going back to where we left it, the water flooding algorithm needs a database to work. One could argue there is already one, the information stored on RAM, but I like the idea of using data stored on disk. Being one of the reasons that after you go though the trouble of saving the created blocks on disk you will not have to calculate their position again. Second argument is that once you create a flow of information, now you can use it to import information from outside BrickGame. Example given: Heighmaps created on software like WorldMachine.

And finally I know that there is implemented a way of saving the entire game state to disk. And I believe that my own custom implementation of a database is better because instead of reading and writing the entirety of the game state it just reads one region at the time. Oh well. I have a branch ready to PR once the first PR is accepted.

Good stuff about my custom database:

.It allows for importing of external data (like Minecraft schematics (is this legal?)) .On top of it a redundant database can be created, (the one the flooding algorithm uses), that stores 2d "floodable" surfaces. Surfaces which frontiers are made of non emtpy blocks.

This redundant database, (the second one on top of the first) would not only allow for the instant flooding explained before. But most importantly it would give a domain for pathfinding algorithms to work on. I have tested navigation on top of the bricks and the guys have no problem going up and down again and again. This way they would prefer to take longer paths, by walking horizontal.

In short: The first database that stores the Region.BrickContents is ready for PR, and its main attraction is that it allows for communication with external sources.

The second one is redundant of the first and adds a really cool extra layer of information.

iUltimateLP commented 8 years ago

I read stuff about saving the game here, and I actually did that before. Andrew's way of saving the game was just a Save Game Object containing the Brick Grid Data, the player transform and the daytime, and that save file was 600 MB big on my end, so I decided to make up a simple compressed save game system, which decreased the file size to 2MB. The code for that is here. The overloaded << operator for FBrickRegion (BrickGrid/Classes/BrickGridComponent.h):

//Overload << for FBrickRegion
FORCEINLINE FArchive& operator<<(FArchive& Ar, FBrickRegion& data)
{
    Ar << data.BrickContents; //TArray<uint8>
    Ar << data.Coordinates; //Fint3
    Ar << data.MaxNonEmptyBrickRegionZs; //TArray<int8>

    return Ar;
}
miguelemosreverte commented 8 years ago

Hmm. Seems like competition! ;) One thing is clear, both our ways use compression, and lots of it.

Edit 1: My database of the Region.BrickContents size after the first boot is of 2.44 MB, too. We probably are both using Zlib, one way or the other.

iUltimateLP commented 8 years ago

From what I read, you're using zlib directly where I use Unreal's wrappers for that, but in the end, it has the same result..

miguelemosreverte commented 8 years ago

Yup. Yours is cleaner.

iUltimateLP commented 8 years ago

I actually made it in a seperate plugin, but it could also go in the BrickGridComponent directly. Should I do a PR?

miguelemosreverte commented 8 years ago

Sure, it is good quality code and compression is needed. After that I will post my database PR, using your compression implementation instead of mine. Good stuff!

iUltimateLP commented 8 years ago

Should I keep it in a plugin or make it directly in the BrickGridComponent?

miguelemosreverte commented 8 years ago

My opinion is that you should do the later, since BrickGame is a plugin by itself.

iUltimateLP commented 8 years ago

I'm a bit new to the PR stuff.. Do I need to do my stuff on top of your code, when Andrew merges your PR or does the code get merged together automaticially..

miguelemosreverte commented 8 years ago

Uhm, I am kind of new too. But my idea would be to wait until my PR is accepted, then immediately do your own PR. Like, seconds later. hahaha. But really, I would guess github can merge about anything, right?

iUltimateLP commented 8 years ago
    FString title, title2;
    title = Directory;
    title += FString::FromInt(RegionToSave.Coordinates.X);
    title += " ";
    title += FString::FromInt(RegionToSave.Coordinates.Y);
    title += " ";
    title += FString::FromInt(RegionToSave.Coordinates.Z);
    title += ".bin";

You're saving each chunk inside a custom .bin file, like Minecraft does? Or is this just your method of saving, where you said mine is better?

miguelemosreverte commented 8 years ago

Yes, and when I said yours was cleaner I was talking about your implementation of compression: Both our methods use compression. Yours use it in a more elegant way.

About my method of saving: Yours, like Scheidecker's, save the entirety of the Regions on one big file. Mine saves each Region on a different file. The reason for this is: When the moment of replicating information between PC's come, you wont want a big file. You will want small little files. So you can implement the little files later on, or do it like I did. To do it first, like I did, comes with the additional advantage that you wont ever need to read the complete file every time you want to decompress it, which in the Scheidecker code happens every time you load the game. I believe F7 fires the loading event.

So, in the end it is a "Divide and Conquer" approach to the loading of the data. Once you analize it you realize it is the best way of loading the data, and using small chunks becomes the only reasonable way to do it. And that is why Minecraft happens to use a similar approach.

Talking about Minecraft: Is it legal to import Minecraft related data?

*PS: Is not like Scheidecker does not know about Divide and Conquer. It was obvious from the moment compression was not implemented that the data saving code was a placeholder for something better. Apparently he made the entirety of BrickGame on just one month, including the sky which with some tweaks is being sold in the Marketplace at around 30 bucks. So, yeah.

iUltimateLP commented 8 years ago

Yeah, I think your version is better.. To the Minecraft stuff: I think it is, because it's just a file format (an open one, see mcedit which is even open-source)..

iUltimateLP commented 8 years ago

So with this system we basicially load a save and this only loads 4 chunks or so in the game. If I enter the distance for loading another chunk, it loads that chunk from the file into the world?