use pseudocode Suppose you work for a computer game company, which is designing

Question

use pseudocode Suppose you work for a computer game company, which is designing a first person shooting game. In this game, players stand just outside of a circular playing field and shoot at targets inside the circle. There are a lot of players and targets, however, so, for any given player, it only makes sense to display the targets that are close by that player. Thus, whenever a new target, t, appears, the game should only make it visible to the players that are in the same “zone" as t. In order to support the fast processing of such queries, you offer to build a binary space partitioning (BSP) tree, T, for use in the game engine. You are given the (x, y) coordinates of all n players, which are in no particular order, but are constrained to all lie at different locations on a circle, C. Your job is to design an efficient algorithm for building such a BSP tree, T, so that its height is O(log n). Thus, the root, r, of T is associated with a line, L, that divides the set of players into two groups of roughly equal size. Then, it should recursively partition each group into two groups of roughly equal size. Describe an O(n log n)-time algorithm for constructing such a tree T. 6

Explanation / Answer

Algorithm 1:

Purpose: Calculate shortest path between target and player to display only those targets which are close to the palyer

Step 1: Initialize players P1 to Pn.

Step 2: Initialize targets t1 to tk at k random locations of the circle.

Step 3: For all new ti {i=1 to k} calculate distance(P, t) using any shortest path algorithm.

Algorithm 2:

Purpose: BSP Tree

ACCEPTABLE BALANCE FACTOR (BF): -1,0,1

Step 1: Choose P1

Step 2: Make P1 the root of the BSP.

Step 3: For each other Pk (k= 2 to n)

                3a. If left subtree (Pk-1) is NULL insert Pk as its left child and check balance factor

                                else insert Pk as its right child and check balance factor

                3b. After each new insertion, if unbalanced, balance the tree using AVL rotations.

Step 4: Continue Step 3 till all players are placed.

               

NOTE: Knowledge of construction of AVL TREES and its rotation required.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.