Barnes-Hut n-body quadtree

Here's an attempt I've made of implementing the Barnes-Hut n-body algorithm, or its initial stage - The quadtree. That there're lots of lengthy doc strings might excuse the lack of detailed explanation here.

My primary concerns as a beginner are to

• Avoid complexity

• Avoid library imports

• Make fast and short code whenever possible.

Being said that, I think the code is bulky (and 'unpythonic'?). Advice me on how to improve it in terms of speed, design pattern and readability. Is functional programming even suitable here?

Summary of the code

• Every node and body is identified by a global ID.

• A body is added to the quadtree by registering its mass, position and velocity. It is assigned an ID (called bid).

• A node is made by specifying the South-West vertex and box length (an ID is issued here too - called nid).

• updatecom is called for updating the quadtree's (or individual nodes') centre of mass.

• walk is called throughout the script for navigating the quadtree.

• Accelerating the bodies, updating position for each time-frame and plotting are yet to be established.

The docstrings are what makes the code lengthy which otherwise would be short. Since there're no special areas to which attention needs to be drawn, I've added the complete code here.

```
"""Quadtree construction module.

ESSENTIAL TERMINOLOGY

a. Quadtree : A tree structure with four quadrants that are
coplanar. Quadrants are named SW, NW, NE and SE as
in compass directions, and are usually adressed in
the same order.
b. Node : Same as a quadrant; it can be internal or external.
c. Internal Node : A node that has child nodes inside. It contains no
bodies since they are distributed among the child
nodes.
d. External Node : A node that doesn't have child nodes inside. It

You may well have a good reason for using Python 2.x. If you don't, I'd suggest that using the latest version is more Pythonic. In particular, as you describe yourself as a beginner, it may be easier to use the latest version now rather than having to unlearn certain quirks of 2.x at some point in future. I would also describe myself as a beginner, and of course I'm biased by having learned Python 3.3 first...

If you prefer to keep it as Python 2.x it might be worth adding the tag python-2.7 to attract answers from people expert in it.

"""Quadtree construction module.

ESSENTIAL TERMINOLOGY

    a. Quadtree         :   A tree structure with four quadrants that are
                            coplanar. Quadrants are named SW, NW, NE and SE as
                            in compass directions, and are usually adressed in
                            the same order.
    b. Node             :   Same as a quadrant; it can be internal or external.
    c. Internal Node    :   A node that has child nodes inside. It contains no
                            bodies since they are distributed among the child
                            nodes.
    d. External Node    :   A node that doesn't have child nodes inside. It
                            contains a body.
    e. Empty Node       :   A node which has neither child nodes nor a body
                            inside it.
    f. Root Node        :   The topmost node (parent) of all nodes.
    g. Occupant         :   A body bound within a node (lowest host node).
    h. nid              :   Node ID
    i. bid              :   Body ID
    j. Centre of mass   :   The weighted average of mass distribution.
                            X = (m1x1+m2x2+...mnxn) / (m1+m2+...mn)
                            This must be replaced with centre of gravity if the
                            bodies are non-uniform mass distributions, unlike a
                            point object.
"""

You are right, this comprehensive docstring does indeed make the code longer. I don't see that as a bad thing. Anyone in a hurry can skip over it easily as it is self contained, and anyone confused by the code can refer back to this rather than having to work it all out for themselves. Helpful docstrings are definitely Pythonic. In particular, I wouldn't have been able to write this review without the insight provided by the docstrings.

from __future__ import division

# Dictionaries to map body parameters
masses = {}
positions = {}
velocities = {}
# Dictionaries to map node parameters
lengths = {0: None}
vertices = {0: None}
occupants = {0: None}
childnodes = {0: []}
totalmasses = {0: 0}
centremasses = {0: None}
# Global ID counter starts with 1 (0 is dedicated for root node)
ID = 1

def newid(reset=False):
    """newid(reset=False)

    Returns an unused ID of type 'int'. Consequtive integers starting from one
    are returned avoiding repetition.

    If optional argument 'reset' is True, ID counter restarts from one. Those
    IDs which aren't active anymore can be retrieved by this manner.
    """

The misspelling of 'Consequtive' (correct spelling Consecutive) will only have a minor effect on someone reading the code, but I point it out since Python is all about readability.

global ID
    if reset:
        ID = 1
    while any(ID in maps for maps in (masses, childnodes)):
        ID += 1
    return ID

This function is called when assigning a new nid and also when assigning a new bid. I'm not sufficiently familiar with your algorithm to say for certain, but I'm guessing that the numbering of nodes (nid) and the numbering of bodies (bid) are unrelated. If so, then there is no need to check for an existing node id in masses, and no need to check for an existing body id in childnodes. I would be inclined to replace the function newid with two similar functions newnid and newbid. This will make assigning new ids slightly more efficient, and allow all numbers to be available (currently any given number can only be used as either a nid or a bid, not both, if I understand correctly).

This will also be more readable, as both functions will be simpler and more intuitive than newid. Currently the question of why a new nid can't have the same number as an existing bid makes the algorithm appear more complex than it needs to.

If you split the function this way, you will also need to have two global variables so that they don't share ID. For example, nextBodyID and nextNodeID. I would avoid all upper case as this is usually used for constants.

def initiate(vertex, length):
    """initiate(vertex, length)

    Initiates the quadtree by specifying the SW vertex and side length.
    """
    lengths[0] = length
    vertices[0] = vertex

You don't need to include the name of the function at the start of the docstring. The suggested approach is to start with a one line description of the function. Changing this will save you two lines per function, making your code

StackExchange Code Review Q#43749, answer score: 5