3

I'm working on a Minecraft-style game, and I need a way to reduce the amount of the world rendered. Currently, I'm using a naive, render-everything approach, which is having obvious scaling problems. I need a way to take an array of blocks, and in some way find out which ones are touching air, water, or any other translucent block.

I'm open to using external modules like NumPy or SciPy, though some of their documentation is a bit over my head. Alternatively, it would also be acceptable to iterate through each block and get a list of neighbors, though the performance cost of doing these calculations in Python instead of C would be pretty hefty.

For the record, I've already tried looking at NetworkX, but it seems to be more for scientific analysis or pathfinding than visibility checking.

James
  • 1,239
  • 1
  • 11
  • 18

2 Answers2

4

If you only need to do this once, performance should not be an issue. If you also incrementally update the .isBoundary property of blocks whenever the world is changed, you will never have to do it again.

However you still run into issues if your world is too large or full of holes and caverns and transparent-interleaved-with-nontransparent. If you need to dynamically determine what is visible, you can keep an octree ( http://en.wikipedia.org/wiki/Octree ) where you can have giant expanses of air/water/etc. as a single node (giant block), labeled as "transparent". Then use the "paintbucket" algorithm (modified to perform Dijkstra's algorithm, so it is easy to detect when you've "gone around a corner" by checking to see if blocks exist between the current block and the origin) to quickly figure out which blocks are in sight. Updates for things far in the distance can be delayed significantly if the player is moving slowly.

ninjagecko
  • 88,546
  • 24
  • 137
  • 145
  • Sounds like a pretty solid technique, even if it is a bit more than I was looking for. Is there some library that can do this for me? I can't write my own C for performance, and I'd like to keep as much as possible throughout development. – James Jul 15 '11 at 07:26
  • 1
    @James: generally, one should not consider dropping down to a lower-level language for performance, unless you are writing a massive program, you have isolated a critical section, and the payoff is massive (e.g. new users, large cash bonus, etc.). Opinions on this may differ though. I'd recommend looking to see how MMORPGs and other 3d games solve these issues of scale; it may be a solved problem, or it might not be (due to the block-like nature of your game). Barring that, your solution is easy enough to code in a few lines and test to see if you really need bigger guns right now. – ninjagecko Jul 15 '11 at 08:22
2

You could use the Z-Buffer solution. Concerning speed, I'd write as much as possible in python and use pypy. EVE Online (a successful 3D MMO) was written in stackless python I believe.

ubershmekel
  • 11,864
  • 10
  • 72
  • 89