Find the closest enemy

Question

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.

Answer 1

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:

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()

Answer 2

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)

Answer 3

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
   

Answer 4

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".