How to make trees respond to a hit?

I have no idea how I’d do it. How I’d make it so that if you are chopping down trees the trees will respond to your hit and where you are hitting will get thinner and thinner and then the tree will fall down. Could I due it with Unity’s tree creator or would I have to make special meshes and update the mesh every time you hit it…like replace the whole tree until it falls over and then create a separate mesh for the stump after it falls over. Do you guys have any ideas or examples. I need some help with this!

EDIT: Just to clarify, this is a follow-on answer to getyour411’s approach. This would be a way to reduce the number of trees you have to loop through each frame in the scripts provided in that answer. It just wouldn’t fit in the comment.

This was intended as a comment to respond to getyour411 and turned into a lengthy answer. It’s not code-based but gives an idea how to efficiently get to the trees. If I have time, I will find and post my old code (or write some new code to make a quadtree). But you can probably find existing ones online.

Anyway, octrees, quadtrees, BSP, really not complicated stuff, but takes a lot of time to develop due to the parent/child/sibling structure and optimizations required to make it fast. I was developing my own game engine about 5 years back, before I realized a 1 man team can’t keep up with the big boys, and I had implemented the quadtree and octree algorithms. I will see if any of that code is still around, but I don’t know if it even compiles.

The general concept is to break the world up into cubes (octrees) if you need volumetric spacialization separation, or a 2D gridded groundplane (quadtree) for only 2D. BSP trees are similar or maybe a superset of these. Quadtrees makes the most sense for this scenario and are much easier to make than octrees.

The concept would be to divide the terrain into chunks, so you start with the 1 large quad, then divide it by 4. Now for each of those quads, you divide them by 4. And keep going as deep as you want, based on how fine of resolution you want (I will try to draw a diagram and update later). Let me clarify, you aren’t doing anything with the terrain. You’re just starting out with a large quad whose corners are at each corner of the terrain. And by quad, I mean literally just some class that defines 4 points, nothing rendered, etc.

Next, you implement some interface in that class to provide the corner points of each quad (at each depth where depth 0 is the large quad covering the entire terrain, depth 1 is the 4 quads it breaks into, etc). Then define an interface to retrieve the current quad the player is standing in. This is where the true power lies.

You first say “is the player in the big quad” and the player is obviously, so you can skip that part. Then you say “is the player in the 1st, 2nd, 3rd, or 4th quad at depth 1”, and when you find out which quad the player is standing in there, you can ignore the other 3 (that presents a problem in a minute). Then you dig down from that quad to find out which of the 4 sub-quads within it that the player is standing in (at depth 2). Finally, you have a single quad that the player is standing in at the lowest depth.

You take this quad and find each of the surrounding quads (hopefully linked together for quick access). You need to do this in case the player is standing exactly at the corner of 4 quads, he’ll want to process “trees” (i mean forest trees) in each of the quads around him. Armed with only 10 quads to check now (the center one and 9 surrounding), the player has reduced the tree set significantly.

I left out a part. You need to process all of the trees in the terrain (using the terrain data), get their position, find which quad that position belongs to, and add a reference to that tree and its position into the quad tree structure. Now you have a structure of quads containing a list of every tree in that quad. In other words, given any quad within the structure at any depth, you can query and get all of the trees within that quad.

Lastly, for optimization, you could look at the terrain and say “these 4 quads that form a larger quad have no trees! destroy these 4 quads)”. Or better, don’t create a quad that has no trees, thereby allowing your quadtree to have holes in it. You would do this while post processing the terrain, running across it to find all the forest trees and create the quadtree quads (nodes).

Yet another optimization of the quadtree is to not divide the quads up equidistant between each other. Let’s say you have a dense forest in one place and a large area of empty space next to it. You will want more quads in the dense area and less in the empty space, so you could move the quad walls so they are no longer square. This adds some complication to the parent/child relationship.

All of this requires quite a bit of post processing, but it’s cool stuff, and I wish Unity had a ready made solution for it, i.e. ability to just pull trees in current octree or quadtree node or ability to search a node for surrounding meshes, etc. They are using some form of Binary Space Partitioning tree (BSP).