Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm using the marching square algorithm (2D version of marching cubes) to generate vertices.

I end up with vertices arranged in a grid.

I want to enable destructible terrain, and the way i was planning on doing this was to start simple - have one vertex buffer with the whole map, and edit the bits that change. In cases where I need to remove vertices I was thinking about just making them transparent so I can still render the whole map in one go.

Firstly, is this approach reasonable?

Secondly, I want to design my VB so that if I need to change vertices in 3x3, 5x5 or 7x7 etc. grids the locations of the vertices in the VB are close together.

Now, from university I vaguely remember an image compression algorithm that walked the image in an unusual way, which i think could apply. Basically it walked in a U / horseshoe direction. It would place a U over the image, large enough to cover the whole thing, then it would break the U up into 4 quadrants, and use a smaller U to walk those, and so on until it got down to the pixel level, or in my case it got down to a single grid unit.

Does this sound feasible? What is that algorithm called? (I can't remember the name and haven't found via general searching).

share|improve this question
    
It sounds like Hilbert's curve –  artificialidiot Jan 21 '12 at 22:52
    
That's it! Thanks. I'm still undecided whether to go with that option, or a quad-tree type structure. –  George Duckett Jan 22 '12 at 12:08
add comment

1 Answer

up vote 1 down vote accepted

It is feasible and the algorithm is called quadtree, for future reference, the 3D version is called octree and is essentially the same algorithm. You would likely store the vertexbuffer as several buffers in this method however, this way recreating part of the scenery will be less complicated and can be done by simply recreating one of the vertexbuffers. A google search should net you many tutorials and examples on both of these. Hope it helps.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.