0
\$\begingroup\$

I've performed partitioning of my level into broad and narrow phase. I'm down to narrow phase and focusing on the height from the ground.

I want to see what polygon the player is on top of. Since some polygon sectors may be lower than others (this is a birds eye view), I want the player to be stand on top of the highest one. Therefore I thought what I can do is each game tick would be to check which boxes the player intersects, and then find the polygon with the highest 'height' and use that as the base height for the player.

An example would be below:

Box intersecting some edges but not others

Is this a viable way of doing it? That this game is 3D, but I only have to do two dimensional calculations for the height which reduces the computation and makes this easier.

The level has been cut up into a BSP tree so the following is a gross misrepresentation of the level, however I don't see any obvious way (immediately) to exploit the BST property to find out the highest sector that the player would be standing in. So far the best way I could think of was to use narrow phase collision detection described above and hope that is extremely fast.

I am looking for speed here, so if you know of any better algorithms or some faster way of doing this, please let me know.

EDIT: The focus of this post is for high level algorithms, of which they can be optimized later on. No actual collision detection code has been made yet.

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ "Is this a viable way of doing it?" Does your implementation work and give you correct results? Have you profiled the results and identified any performance problems? These will be the best ways to determine whether your solution is suitable. Otherwise we're just spending time discussing problems that may not actually exist. ;) \$\endgroup\$
    – DMGregory ♦
    Apr 11, 2017 at 17:34
  • \$\begingroup\$ @DMGregory Nothing has been made yet on this front, I'm strictly discussing high level algorithms and will worry about the profiling and optimization later. It is necessary however that the algorithm of choice should have the potential to be optimized heavily and also not have another algorithm have a complexity/lower bound be less than what is offered. I'll edit my post to reflect this. I'd much rather not code it, discuss higher level algorithms first before diving in and going "wish I thought this through before coding it" since I've done that too many times and wasted too much time. \$\endgroup\$
    – Water
    Apr 11, 2017 at 17:42
  • \$\begingroup\$ Just beware of "Here's my solution, may I have your approval to go ahead and implement it?" which is something we see here a lot. Judging by what you've written, you're a skilled developer who knows the important considerations, so don't undervalue your ability to evaluate solutions yourself. Time spent waiting for others to vet a solution is just as gone as time spent implementing something that's not quite right the first time, so my general advice is to try not to get bogged down in analysis paralysis seeking the best possible solution. If you have something that should work, try it! ;) \$\endgroup\$
    – DMGregory ♦
    Apr 11, 2017 at 17:55
  • \$\begingroup\$ @DMGregory I like that word, 'analysis paralysis' ;) Fortunately I have a week before I have to decide on anything so I'm hoping to test the waters so to speak. I will definitely keep your post in mind however and do the most reasonable thing possible! \$\endgroup\$
    – Water
    Apr 11, 2017 at 18:13

1 Answer 1

Reset to default
0
\$\begingroup\$

Since there may be very thin slivers that go into the bounding box, there is no choice but to take the bounding box edges and calculate if any of them intersect with the line segments in the surrounding polygon.

Some optimizations that can be done are as follows:

If there can be a bounding box on the polygon elements, it might be possible to not have to do line-to-line intersections by doing yet another "broad phase pass" in the narrow phase by checking bounding boxes (ex: Put a square around a triangle and check boundaries).

If there's a BSP tree, you can check what sector the player is in as a default by traversing it, so if it's not insanely unbalanced then you have approximately an O(log n) runtime. This can be optimized to O(1) if each chunk stores some sector for the entire chunk if nothing is in it. If the map doesn't have too many changing heights, this could amortize the cost from O(log n) to O(1).

Otherwise, using line intersection is something I appear to be stuck with, so thats O(k) which is the number of lines in the narrow phase.

As stated earlier, line intersection is required in case some small sliver/jagged edge is poking into the player. This also has to be handled with collision detection as well.

As a note for algorithms: CLRS has a chapter on efficient intersections in its computational geometry chapter.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .