STILBRUCH

Recursive constructors and Quad-trees


This blog has been relocated to blog.ryangrieve.com. You will be redirected shortly.


After much faffing about last night with my tilemaps, I realized that what I actually was looking for was much more akin to a quad-tree than a tilemap. So that’s what I’ve implemented.

My new class “CorruptedSector” should allow me to be much more sensible about this generation malarkey. Firstly, it is the only class used for corruption, as opposed to my previous implementations of “CorruptedTile” and “CorruptedTilemap”, and secondly, each instance retains references to only its neighbours, its parent, and its children, those it will directly affect.

With regards to efficiency, we will only go as deep into the tree as necessary to update and draw changes. This is logically quite simple, when calling the update function for a CorruptedSector, if none of the sector’s children have been flagged as changed, then we run this sector’s update and we’re done. Else we call each of the children’s update functions in turn, which will then check their own children and so on.

This means the actual generation logic is now inherent in each sector. I had avoided this before, as it had been more efficient for the tilemap to handle this logic, but the tree nature of the structure now puts an end to that. When a sector is “spreading” it will call the generation functions of its neighbours, which will be able to determine whether it should to apply the affect to itself, or to individual children.

Quad-tree generation method

If a Sector interacts with one of its neighbours, we flag that neighbour for update. This flagging process will then bubble up the tree, marking each parent, in order, as flagged. The same happens if a sector is affected in any other way, such as being hit by the player’s weapons. This selective processing will obviously help performance in a great way, but I can also implement accuracy variations on the generation algorithm as well, as mentioned in a previous post. Hopefully my world size will not be limited by anything other than design choices after this.

I’m excited to get interfacing these changes with the current game logic, it will make a lot of future developments easier too, such as weapon collision detection and A.I. pathfinding.