9
\$\begingroup\$

I'm currently creating a 2d game in python. I have to calculate the closest enemy so the player knows which one to target. I have the following function to accomplish this task:

import math

def find_closest(character: tuple, enemies: list) -> (int, int):
    """
    Finds the closest enemy in enemies

    :param character: An (x, y) representing the position of the character\n
    :param enemies: A list of tuples (x, y) that represent enemies

    :return: A tuple (x, y) of the closest enemy
    """
    closest_enemy = None
    smallest_distance = 100_000_000 # Set to large number to ensure values can be less #
    for enemy in enemies:
        distance = math.sqrt(math.pow(character[0] - enemy[0], 2) + (math.pow(character[1] - enemy[1], 2)))
        if distance < smallest_distance:
            closest_enemy = (enemy[0], enemy[1])
            smallest_distance = distance
    return closest_enemy

if __name__ == "__main__":

    # Test Case #

    character = (5, 6)
    enemies = [(1, 2), (3, 4), (7, 6), (11, 4)]
    closest = find_closest(character, enemies)
    print(closest)

I would like to know if there's any better way to go about doing this. While it is a simple function, I'm sure there's some built in python function that can accomplish this even shorter. I use tuples because, in my opinion, they're the best way to represent coordinates. Any and all suggestions and/or improvements are welcome and appreciated.

\$\endgroup\$
6
  • \$\begingroup\$ If you can use scipy, kdtree.query does exactly that docs.scipy.org/doc/scipy/reference/generated/… \$\endgroup\$ Oct 14, 2019 at 10:21
  • 3
    \$\begingroup\$ I assume you need the distance as the crow flies, not factoring in pathfinding? \$\endgroup\$
    – Flater
    Oct 14, 2019 at 10:53
  • \$\begingroup\$ You could easily simplify this by using return "code" ;P \$\endgroup\$
    – S.S. Anne
    Oct 14, 2019 at 12:28
  • \$\begingroup\$ This question was basically asked ~6 years ago: codereview.stackexchange.com/questions/28207/… \$\endgroup\$
    – JeffC
    Oct 15, 2019 at 4:41
  • \$\begingroup\$ For large number you should use math.inf (infinity). \$\endgroup\$
    – RomainL.
    Oct 15, 2019 at 8:43

4 Answers 4

19
\$\begingroup\$

For small lists of enemies, linearly scanning all of them and computing the distance to the character is sufficient. However, if you have many enemies, a more efficient data structure is needed.

If your list of enemies does not change (or changes less often than you need to find the closest enemy), I would use scipy.spatial.cKDTree. kd-trees take \$\mathcal{O}(n\log n)\$ time to build, but afterwards each query only takes \$\mathcal{O}(\log n)\$.

from scipy.spatial import cKDTree as KDTree

def find_closest_kdtree(character: tuple, enemies: KDTree) -> (int, int):
    """
    Finds the closest enemy in enemies

    :param character: An (x, y) representing the position of the character\n
    :param enemies: A KDTree that represent enemies

    :return: A tuple (x, y) of the closest enemy
    """
    _, i = enemies.query([character], 1)
    return i[0]


if __name__ == "__main__":

    # Test Case #

    character = (5, 6)
    enemies = [(1, 2), (3, 4), (7, 6), (11, 4)]
    enemies_tree = KDTree(enemies)
    closest = enemies[find_closest_kdtree(character, enemies_tree)]
    print(closest)

If you do regularly need to update the list of enemies (because they are spawned, get killed, move off-screen, etc), you might be able to use a R* tree instead:

from rtree.index import Rtree


def find_closest_rtree(character: tuple, enemies) -> (int, int):
    """
    Finds the closest enemy in enemies

    :param character: An (x, y) representing the position of the character\n
    :param enemies: A KDTree that represent enemies

    :return: A tuple (x, y) of the closest enemy
    """
    return next(enemies.nearest(character, 1, objects='raw'))


if __name__ == "__main__":

    # Test Case #

    character = (5, 6)
    enemies = [(1, 2), (3, 4), (7, 6), (11, 4)]
    enemies_tree = Rtree()
    for i, p in enumerate(enemies):
        enemies_tree.insert(i, p+p, p)

    closest = find_closest_rtree(character, enemies_tree)
    print(closest)

Here is how the different methods compare performance wise, including the implementation using min and your original implementation:

enter image description here

Note that building all the R* trees for this took multiple minutes, while building all the KDTrees took only a couple of seconds. So you would probably have to rebuild the KDTree quite often for it to be worth it to switch to the R* tree.


In case you are interested, this is how I generated that graph:

import numpy as np
import pandas as pd
from functools import partial
import timeit
from scipy.spatial import cKDTree as KDTree
from rtree.index import Rtree

def get_time(func, *x):
    timer = timeit.Timer(partial(func, *x))
    t = timer.repeat(repeat=5, number=1)
    return np.min(t), np.std(t) / np.sqrt(len(t))

def get_times(func, inputs):
    return np.array(list(map(partial(get_time, func), inputs))

def find_closest(character: tuple, enemies: list) -> (int, int):
    closest_enemy = None
    smallest_distance = 100_000_000 # Set to large number to ensure values can be less #
    for enemy in enemies:
        distance = math.sqrt(math.pow(character[0] - enemy[0], 2) + (math.pow(character[1] - enemy[1], 2)))
        if distance < smallest_distance:
            closest_enemy = (enemy[0], enemy[1])
            smallest_distance = distance
    return closest_enemy

def find_closest_min(character: tuple, enemies: list) -> (int, int):
    def find_enemy_distance(enemy):
        return math.hypot((character[0] - enemy[0]), (character[1] - enemy[1]))
    return min(enemies, key=find_enemy_distance)

def find_closest_kdtree(character: tuple, enemies: KDTree) -> (int, int):
    _, i = enemies.query([character], 1)
    return i[0]

def find_closest_rtree(character: tuple, enemies) -> (int, int):
    return next(enemies.nearest(character, 1, objects='raw'))

def find_closest_kdtree_with_build(character: tuple, enemies) -> (int, int):
    enemies_tree = KDTree(enemies)
    _, i = enemies_tree.query([character], 1)
    return enemies[i[0]]

if __name__ == "__main__":
    character = 5, 6
    x = [list(map(tuple, np.random.randint(-n, n, (n, 2))))
         for n in np.logspace(1, 6, dtype=int)]
    kdtrees = [KDTree(v) for v in x]
    rtrees = []
    for y in x:
        rtrees.append(Rtree())
        for i, v in enumerate(y):
            rtrees[-1].insert(i, v+v, v)

    df = pd.DataFrame(list(map(len, x)), columns=["x"])
    df["find_closest"], df["find_closest_err"] = get_times(partial(find_closest, character), x).T
    df["find_closest_min"], df["find_closest_min_err"] = get_times(partial(find_closest_min, character), x).T
    df["find_closest_kdtree"], df["find_closest_kdtree_err"] = get_times(partial(find_closest_kdtree, character), kdtrees).T
    df["find_closest_rtree"], df["find_closest_rtree_err"] = get_times(partial(find_closest_rtree, character), rtrees).T
    df["find_closest_kdtree_with_build"], df["find_closest_kdtree_with_build_err"] = get_times(partial(find_closest_kdtree_with_build, character), x).T

    for label in df.columns[1::2]:
        plt.errorbar(df["x"], df[label], yerr=df[label + "_err"], fmt='o-', label=label)
    plt.xlabel("Number of enemies")
    plt.ylabel("Time [s]")
    plt.xscale("log")
    plt.yscale("log")
    plt.legend()
    plt.show()
\$\endgroup\$
6
  • 3
    \$\begingroup\$ Another, minor optimisation - instead of the comparatively expensive series of squares and sqrts a Manhattan distance may very well be sufficient for this purpose. \$\endgroup\$
    – Baldrickk
    Oct 14, 2019 at 13:28
  • \$\begingroup\$ The values in the graph... are these single instances of find_closest()? Maybe perfoming say... 1000 lookups would provide a more realistic timing? For example, it would show the difference between the original find_closest() and the kdtree_with_build() implementations better, if the build only has to be performed once for all 1000 calls. \$\endgroup\$
    – Baldrickk
    Oct 14, 2019 at 13:34
  • \$\begingroup\$ @Baldrickk: Yes, it is one lookup each (actually the minimum of 5 runs with the same inputs). The time with the build only once is the _kdtree line, there the building of the tree is not included in the timing. \$\endgroup\$
    – Graipher
    Oct 14, 2019 at 14:01
  • \$\begingroup\$ @Baldrickk: That sounds like it would constitute its own answer. Incidentally, the KDTree supports this out of the box by using enemies.query([character], k=1, p=1) instead of the default value of p=2. \$\endgroup\$
    – Graipher
    Oct 14, 2019 at 14:04
  • 5
    \$\begingroup\$ @Baldrickk: Manhattan distance can be 41.4% wrong, which might very visible. It's possible to simply remove sqrt while comparing distances, though. \$\endgroup\$ Oct 14, 2019 at 14:17
14
\$\begingroup\$

First of all, let's talk about magic numbers. smallest_distance = 100_000_000 is a problem. Where's the hundred million come from? When you have numbers in your code, there should ideally be a specific reason for why you're using that number instead of any other, and numbers that are picked just to be ludicrously large have a weird habit of turning out to be smaller than something when your code evolves. If all your enemies happen to be further than a hundred million units away, this function will return None and possibly cause something to blow up. There are two conventional starting values for a min loop: either the maximum possible number supported by that data type, or the first element of the array. Using the first element is generally better, especially in Python where things can be a bit fuzzy on exactly what data type we're using.

That said, there's an easier way to write this min loop. Don't.
Python's biggest strength is the way that it provides functions to do a lot of this stuff for you. In particular, it provides a min function. Normally you'd use min like this:

min([4, 2, 9, 2, 8])

That would return 2 with no messing around with what initial value you want to guess. You can also provide a key function to change what you're comparing on, which you'll want to do here to use the hypotenuse to your character.

def find_enemy_distance(enemy):
     return math.sqrt(math.pow(character[0] - enemy[0], 2) + (math.pow(character[1] - enemy[1], 2)))

Then you can call min as follows:

min(enemies, key=find_enemy_distance)

Speaking of python providing functions that make things easier, there is a math.hypot which removes the need to do your own squaring and square rooting. We can then go for

def find_enemy_distance(enemy):
     return math.hypot((character[0] - enemy[0]), (character[1] - enemy[1]))

The overall function, (without your entirely appropriate docstring), looks like

def find_closest(character: tuple, enemies: list) -> (int, int):
    def find_enemy_distance(enemy):
        return math.hypot((character[0] - enemy[0]), (character[1] - enemy[1]))
    return min(enemies, key=find_enemy_distance)
\$\endgroup\$
7
  • \$\begingroup\$ In your find_enemy_distance(), you can remove all but the parens of the math.hypot function call. \$\endgroup\$
    – Gloweye
    Oct 14, 2019 at 9:13
  • \$\begingroup\$ True. I actually took them out initially, but I found it slightly more readable just for the grouping. That's very much subjective stylistic stuff. \$\endgroup\$
    – Josiah
    Oct 14, 2019 at 9:23
  • \$\begingroup\$ True, it's very subjective, and we apparently end up on different sides of the preference, then. It's rare for me to prefer any parens if I could do without them. I also didn't know that min() accepted key=, so that's nice. \$\endgroup\$
    – Gloweye
    Oct 14, 2019 at 9:34
  • \$\begingroup\$ This version only returns the distance to the closest enemy, not their identity. \$\endgroup\$ Oct 14, 2019 at 9:48
  • 1
    \$\begingroup\$ @PeterJennings, no it doesn't. min uses the key function to do the comparison, but it still returns the original item from the collection. In the provided example case, it returns (7, 6) \$\endgroup\$
    – Josiah
    Oct 14, 2019 at 10:26
10
\$\begingroup\$

Specific suggestions:

  1. I believe collection types should be taken from typing, so your signature would be something like find_closest(character: Tuple[int, int], enemies: List[Tuple[int, int]]) -> Tuple[int, int]. At which point you may want to pull out and reuse a Coordinate type.
  2. Because your coordinates could be anything from millimetres to light-years I'd probably choose a much larger initial smallest distance. Or bite the bullet and set it to None and return an Optional[Tuple[int, int]].
  3. This was probably just for illustration purposes, but just in case, test cases are usually in a separate file and use TestCase.assert* methods to verify the results.
  4. Since a² < b² implies a < b (when a and b are positive) you can remove the math.sqrt for a speed-up.

General suggestions:

  1. black can automatically format your code to be more idiomatic.
  2. flake8 with a strict complexity limit can give you more hints to write idiomatic Python:

    [flake8]
    max-complexity = 4
    ignore = W503,E203
    
  3. I would then recommend validating your type hints using a strict mypy configuration:

    [mypy]
    check_untyped_defs = true
    disallow_any_generics = true
    disallow_untyped_defs = true
    ignore_missing_imports = true
    no_implicit_optional = true
    warn_redundant_casts = true
    warn_return_any = true
    warn_unused_ignores = true
    
\$\endgroup\$
5
\$\begingroup\$

I would make the function slightly more generic. After all, you do calculate all distances anyway. I don't think list length becomes a storage space issue here, so why not return a list sorted by distance to the player?

from typing import Tuple, List

def distance(character: Tuple[int, int], enemy: Tuple[int, int]) -> int:
    return math.sqrt((character[0] - enemy[0]) ** 2 + (character[1] - enemy[1]) ** 2)

No reason to use math.pow when we have a perfectly valid ** operator. Some would also prefer to use it to get the root, but I don't really like that with regards to readability.

To sort a list, you can supply a key: Callable=(...) keyword argument. We want to supply the above distance function to sort by. I'm using functools.partial to "bake in" the characters data, but you could also declare the function inside your sorting function and leave the argument definition out.

Then return a list like this:

from functools import partial

def sort_closest(character: Tuple[int, int], enemies: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    """
    Finds the closest enemy in enemies

    :param character: An (x, y) representing the position of the character\n
    :param enemies: A list of tuples (x, y) that represent enemies

    :return: A tuple (x, y) of the closest enemy
    """
    return sorted(enemies, key=partial(distance, character))

Then retrieve the closest enemy with:

closest = sort_closest(player, enemies)[0]

Note: I also included @I0b0's typing reccomendation. You could of course omit the math.sqrt function in distance() if you only use it for sorting, but then you'd have to also rename it to not be "distance".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.