digitalajf / quadtree Goto Github PK

since ver 3.16

Change the code in the "example usage" section of the Quadtree repository so that it is easier to understand what is going on.

Vectors storing objects have been replaced by LinkedLists resulting in improved efficiency iterating through object lists. This was intended once a viable release of this project was available.

Currently, Quadtree.java is designed to only work with the AABB (Axis-Aligned Bounding Box) data type. Quadtree.java should be revamped so that it may be used with more geometry-based data types such as points and circles.

In instances where many AABBs have been positively tested to be in close proximity to one another, there is no way to determine which groups of AABBs they are. A graphical means to show the pairs of AABBs that are in close proximity should be implemented to clarify this ambiguity. Perhaps the use of lines connected to one another may depict this best. UI elements should be added to allow this to be toggled on or off.

since ver 3.12

Currently in Quadtree.java, Quadnode AABB lists are cleared at the beginning of the update method to be made ready for the next search through the tree where they will again be filled as necessary. This process is done through the "reset_Quadnodes" method. It may be more efficient to simply clear these lists before searching deeper into the tree during the search pass instead of having a dedicated "reset_Quadnodes" method which searches the whole tree over again and clears AABB lists that are not empty before the search pass.

since ver 3.15

A data-only view of the Quadtree should be implemented to offer the user a text-based view of the Quadtree. This will remove the overhead of graphics painting from the simulation which should offer a clear view of the Quadtree's actual performance figures. The text should replace the Quadtree and AABB graphics by showing a list of key and value readings of everything that is happening within the simulation. The data view/graphical view should be capable of being toggled by use of two radio buttons or similar binary type UI element.

Tester.java still appears to cause flickering during render of screen graphics despite improvements since previous release. This is especially true after pausing the simulation.

The @param square javadoc tag and its description should be removed since the parameter is no longer present.

Add "intersects" method to AABB.java to test for intersections between AABBs.

Adjusting the velocities of AABBs should be implemented.

"The Sprite class has been renamed to AABB (axis aligned bounding box) since this is what "Sprite.java" was in essence. "AABB.java" has been streamlined to contain only the members and methods it needs for its intended purpose so there is no "paint(Graphics g)" method nor does it contain a "Color" object to be used within the old "paint" method. Currently, an AABB contains:

• four values to determine its top left and bottom right coordinates (x1,y1) and (x2,y2)
• width and height (faster than checking x2-x1 or y2-y1
• direction and velocity stored in (dx,dy)
• a reference to an AABB that may be discovered to be within close proximity to itself.
• a number of methods used to access or change any of the above

Convert all remaining regular for loops into advanced for loops where possible

Tester.java should have the quadnodes at the deepest tree depth which intersect at least 2 AABBs be painted in a different color.

A more descriptive name should be used to describe the UI.

Like the "Tree Depth" section with only two buttons, the buttons to resize AABBs should be placed side by side and not over each other as they are now. The height of the buttons can then be increased to fill the section vertically.

The "About" Dialog in Tester.java (soon to be renamed ProximityTest.java) mentions old name "Main.java" as source file. This should be changed to "Tester.java" for now and later renamed to "ProximityTest.java".

since ver 3.15

Generate javadocs for this project.

since ver 3.15

It is more intuitive to use radio buttons instead of a regular button to convert the Quadtree from rectangular to square and vice versa

Add public method within the Quadtree class to rectangulate or square the quadtree. It is currently done by calling the Constructor with required "square" parameter set to "true" or "false".

Convert all required comments to be compatible with Javadoc documentation generator.

Discovered a bug in Tester.java where the number of AABBs shown in the title bar maxes out at 32767. The reason for this was because the variable that stored this value was of type "short". It is now an "int" which allows larger values to be stored in the variable.

since ver 3.16

Currently, the "set_nearby" method will simply have the calling AABB object point to a given AABB provided to the method as a paramater:

public void set_Nearby(AABB nrby)
{
   nearby = nrby;
} 

This method was meant to simply test the Quadtree's ability to determine nearby AABBs by having the calling AABB mark the first one it encounters through the search as being "nearby". In reality, this is illogical in that there can be many AABBs that may be determined to be nearby at any given time throughout the simulation. Nearby AABBs are already marked by a Quadnode at the deepest tree depth. That is how the Quadtree works after all. Instead of using a "nearby" marker which marks the first AABB that is tested to be in close proximity, each AABB that is marked can reference the common Quadnode that intersects all of them.

since ver 3.15

The constructor AABB(int _x1, int _y1, int _x2, int _y2) needs to be modified to throw an error in the situations where _x2 <= _x1 or _y2 <= _y1. This means the AABB must be a rectangle in which the top left corner is always (x1,y1) and bottom right corner is always (x2,y2).

A number of UI elements should have pop-up tool tips for immediate information.

Tester.java should have button to add "100" AABBs.

The Quadtree can now be converted to be square in real-time. The Quadtree is rectangular by default and fills the entire coordinate space however you may choose to "square" the Quadtree as well. A square Quadtree will ensure all quadnodes are also square which in turn will ensure that a positive proximity test will always have the same probability whether AABBs are approaching each other from the top\bottom or left\right. Rectangular quadnodes on the other hand will result in more frequent positive proximity results on the axis where Quadnodes have longer edges. A square Quadtree will be partially extended beyond the coordinate space (to the South). Not only is there no performance cost for this but on the contrary, there appears to be a small gain in performance (based on personal real-world testing).

A square Quadtree will ensure AABBs will have the same maximum distance between each other before being marked as being in close proximity to one other. A rectangular Quadtree will determine two AABBs as being in close proximity to one another more often on the axis that is longer. It is thus less logical to use a rectangular Quadtree and the default should be square but the option to make it rectangular to fit the screen should still be available. It would be best to use a pair of radio buttons with "square" and "fit window" with the default being "square".

since ver 3.15

Currently, updating of AABB positions, searching quadtree and rendering are all done within the same pass of the main loop. The application may perform better if rendering loop is done within a separate thread.

since ver. 3.01

When there are many AABBs, Tester.java often crashes when the tree depth is increased to higher values.

Currently in the process of converting all required comments to be compatible with Javadoc documentation generator.

A rectangular quadtree where quadrants are longer horizontally (for example) means that AABBs approaching each other horizontally will be determined to be in close proximity sooner than if they were to be approaching each other vertically. This model creates inconsistent results based on the direction of travel of AABBs and should simply be removed. Only a square quadtree will reflect consistent proximity tests regardless of the direction of travel of AABBs.

The UI for Tester.java (soon to be renamed ProximityTest.java) should be redesigned to appear more modern. Adding a menu bar may allow the addition of some extra functionality and it would be best to allow the user to choose a "dark theme" as is common for modern UIs today.

In Tester.java, remove all buttons from top menu bar and place them in the side panel. Delete the top menu bar.

Explore using the BufferStrategy class in rendering visuals in ProximityTester.java. BufferStrategy may be far more effective for active rendering than using an off-screen image buffer as it is the case currently.

Quadtree is made from top to bottom immediately. The root quadnode is made and then all sub-quadnodes are made until the requested tree depth has been reached. As a result of this new working model, quadnodes are not initialized in real-time and instead, simple minimum and maximum querries are made against objects to find which (ready made) quadnodes they intersect and where to continue checking within the tree hierarchy. This static model eliminates the real-time creation of "Quadnode" objects and multiple calculations done to identify their (x,y) centers. Instead, the data is already available beforehand.

The tree depth is either deeper than what is recorded in "max_Tree_Depth" or the paint method for the quadnodes paints more sub-quadrants than what is required.

Tester.java will flicker at the quadnode borders while they are painted on the screen. This seems to happen as the tree depth goes up.

When running the ProximityTester simulation, there is a bug that occurs when the user clicks to remove all but one AABB. There should be only one AABB left on screen but the last AABB is also removed.

e.g. If there are 6 AABBs on screen and the user clicks to remove 5, there will be 0 AABBs on screen.

e.g. If there are 21 AABBs on screen and the user clicks to remove 20, there will be 0 AABBs on screen.

since ver 3.15

Tester.java should have a button or radio button allowing the Quadtree to be toggled between "hidden" or "showing" so that only the AABBs are visible

Create extra AABB constructor "AABB(int _x1, int _y1, int _x2, int _y2)"

The window in Tester.java is no longer resizable.

since ver 3.15

reshape(int wdth, int hght, boolean square) within the Quadtree class should be changed to remove the redundant "square" parameter. The method should also be modified to catch an error if erroneous values for "wdth" and "hght" are provided by the user.

A new simulator called "Heatmap.java" should be made and added to the "extras" directory to further demonstrate the capabilities of Quadtree.java and AABB.java.