That's why you need an Oct-Tree, they fit perfectly with what we're talking about.

To get around the infinite recursion issue of spreading oxygen you should implement things like I discussed. Generate the world and store a flag with every level in the oct-tree. the flag states if the containing region has been altered or not.

Now decide where has oxygen. are there natural pockets of oxygen in caves etc? they get generated by your terrain-gen etc. You have to ensure in your generator that any cave that would have oxygen, is not exposed to the outside world (do this during generation).

If you can do that, that means if you walk around that natural cave, you don't have to simulate oxygen *at all* unless you dig a hole etc. if you do, then you only have to simulate the oxygen in a certain radius around the player, or around the change (Whatever you decide to do)

You could use another flag to determine if a block or indeed whole level of the oct tree is in contact with space. Your simulation would stop there, it would treat access to 'space' as if it were a solid wall, with the exception that you can physically pass thru it, but oxygen won't spread, only get 'eaten' by it.

It's even easier if the only source of oxygen in the whole world is what the player adds as then you only need to store data about oxygen, space etc in the areas the player is in / has visited.

You'd see a very clear way to optimize this if you understood and implemented oct-trees.

What you're thinking is correct, you are going to have to simulate a hell of a lot, your A* will be very busy. What you have to do is restrain it as much as possible with every trick you can implement. You will also need to slow down the oxygen simuation, spread it out across a number of frames, update it once a second for example.

By using oct-trees, optimizing the oct-nodes with 'chunk' flags that can help you skip over calculations, by only updating the world that's actually around the player etc you can make this work in a game.

Another thing you can do is for areas with spreading oxygen? if a player was just in a %100 oxygen block and hasn't passed a 'leads to space' block, then there's %100 oxygen. Don't simulate and just assume whenever possible. You only really need to simulate oxygen around generators and holes to space. There's nothing wrong at all with keeping a record with every node in the oct-tree of all the 'holes to space' inside it. There won't be that many compared to the actual number of voxels.

Now the really tricky thing is how to 'suck' objects, players etc towards holes to space when there's an explosion etc I have many solutions to that as well but I don't know if that's what you're aiming for.