[ad_1]
I am constructing a 2D BSP based mostly physics recreation and am having hassle implementing what may appear to be a simple characteristic. Right here is an Imgur album of visuals for this submit. I’ll consult with them as (fig1-8). I am utilizing Gamemaker as the idea for this challenge.
Fundamental Data and Level of Influence Discovering
Figuring out the purpose of affect utilizing a BSP traversal algorithm is comparatively easy. What I am making an attempt to establish is which wall the phase collided with. This isn’t solely to collect the proper floor data utilized in collision decision, but additionally to invoke that floor’s technique for being impacted (play the proper sound, enter a door, and many others).
Every node shops its wall in a struct variable known as cut up, which comprises its two factors, its regular, and another related details about the wall. Throughout building, these partitions are used to cut up the opposite partitions and distribute them to both the entrance or again subtree, therefore the identify. Colinear partitions are dealt with as such: If it faces our cut up, ship it to our entrance. In any other case, ship it to the again.
Leaf nodes have a cut up of int -1 for empty and -2 for strong. That is checked as the bottom case for the traversal algorithm (GML is dynamically typed).
All nodes are saved in an array with their index getting used as their deal with in reminiscence. A node’s kids are saved utilizing the integer variables frontChild and backChild.
I cannot be protecting the main points on how BSP traversal is usually carried out. This could simply be discovered on-line and I have never achieved something out of the bizarre to my data up to now. Discovering the purpose of affect works nicely, and I’ve accounted for floating level errors utilizing an epsilon worth (fig1, fig2, fig3). Collision decision additionally works nicely, granted we’ve the proper wall of affect.
Wall of Influence Discovering
The difficulty is in figuring out which wall was the primary alongside the phase to be impacted. The best doable method is to cross a pointer w (GML does not have correct pointers so I exploit an array) to the traversal perform, and at any time when a cut up is straddled whereas the phase is heading towards it, that node overrides the pointer with its cut up (wall). Subsequently, the bottom node on the tree that the phase ran head-first into will declare the affect as its personal, and assign its cut up (wall) to the pointer (fig4). This works for many instances (fig5).
The difficulty is when a node claims the wall of affect as its personal, and is then overridden by a node in its rear sub-tree. The phase might be cut up by the proper node, however a node behind it is going to find yourself satisfying each situations (phase is heading in direction of and straddling) and override the pointer incorrectly (fig6).
Tried Options
If a phase intersects the BSP, the purpose of affect is assured to be the place to begin of the phase that reaches a strong node. A strong node is simply reached when a phase is straddling a wall. When a phase is straddling a wall, the phase is cut up, and the sub-segment between its midpoint and endpoint is the one despatched to the strong leaf (granted it is headed towards the node that cut up it). Subsequently, we are able to assure that the purpose of affect is the midpoint of some node’s cut up phase. Logically, this midpoint goes to belong to the proper wall of affect.
If a node splits the phase (once more, whereas the phase is headed towards it), we contemplate it a possible candidate for the wall of affect. As soon as we have reached a strong leaf, we are able to then stroll again up the tree and evaluate this level of affect with each candidate’s midpoint. Solely the one which matches (or is inside epsilon distance of) the purpose of affect will declare the wall of affect (fig7).
(be aware: I’ve my very own vector constructor. hit,* seg[0-2], p1*, and* p2 are all 2D vectors. the strategy lenSqr() returns the vector’s squared magnitude for distance comparisons.)*
This works, however then creates a brand new challenge. If a rear descendant is colinear with a node, the descendant’s rightful declare to the wall might be overridden by its ancestor node on the stroll again up (fig8).
One other try had me constructing the tree such that any colinear wall was handed right down to the entrance sub-tree. Then, throughout traversal, within the case the place our phase lies fully in entrance of the cut up, I allowed it to assert the wall if the endpoint of the phase was colinear with it. This fails as not solely is it doable for a entrance descendant to be colinear and completely elsewhere, it is also claimed whereas strolling down the tree, which means the beforehand applied stroll again up overrides it.
I am unable to discover analysis as to how this particular a part of the traversal is dealt with and but I do know it’s as a result of many BSP based mostly engines deal with this simply wonderful. If anybody may help or level me to an excellent useful resource I would be greater than just a little grateful.
[ad_2]
