I have to create a pseudo wolfenstein 3D as an assignement in school, and I need a structure to represent the map. As all the calculations will be based on a two-dimensionnal grid, I thought that a quad tree would be what I needed.
How would you parse a file that contains this for example:
1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1
where the 1s are wall blocks and the 0s empty blocks, into a quad tree structure?
You have a couple of options here. One way would be to read the entire file into memory into some kind of array, and then build the quadtree top-down from there. This is probably the most straightforward way to do this, as long as the map is not extremely huge.
Another option would be to build the tree bottom-up from each individual node at the bottom, then once you have parsed enough nodes to form a parent node from what you have read, do so. In this example, you would form leaf nodes for each value read. Then on even columns on even rows, after you have formed your leaf node, form your second-level nodes from there.
You will get this kind of structure:
1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2
1 1 1 1 1 1 1 1
1 2 1 3 1 2 1 3
1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2
1 1 1 1 1 1 1 1
1 2 1 3 1 2 1 4
Each number represents the highest level of node to form once reading the number in that position. Also form all levels below each (i.e. on level 3, also form a level 2 node and a leaf (level 1) node).
You could build the tree in a top-down manner: Asumming that the whole array (let's say it's dimension is 8x8) is mixed with zeros and ones, partition it, e. g. in 4x4 tiles. Now check whether each tile contains only ones or zeros or both. When a tile contains both, then partition it again (2x2) and recheck. Repeat until you are on "pixel"-level (1x1). You can store this in a struct containing pointers to the four neighboring tiles.
This picture on Wikipedia shows it pretty good.
