Selecting lowest position from 'array'

Question

My goal is to move a 'monster' (mX, mY) in a 2d grid towards the player (pX, pY). The monster can move 8 directions.

I have working code for this, but I'm very new to Python and have a strong inclination it is awful and there is faster ways to do it.

I do this by creating a 3 x 3 array around the monsters position (array slot 4), and filling it with the distance from that array position to the player. Then I check if any are lower than the monsters current distance, and if so, move the monster to it.

Here is my current code, apologies if it makes you puke, I'm still learning the ropes.

# get the distance between the monster and player
dist = math.hypot(pX - mX, pY - mY)

if dist > 1.5 and dist < 10:

    # make an 'array' grid to store updated distances in
    goto = np.full((3, 3), 10, dtype=float)

    # if each position in the array passes a
    # collision check, add each new distance

    if collisionCheck(mID, (mX-1), (mY-1), mMap) == 0:
        goto[0][0] = round(math.hypot(pX - (mX-1), pY - (mY-1)), 1)

    if collisionCheck(mID, mX, (mY-1), mMap) == 0:
        goto[0][1] = round(math.hypot(pX - mX, pY - (mY-1)), 1)

    if collisionCheck(mID, (mX+1), (mY-1), mMap) == 0:
        goto[0][2] = round(math.hypot(pX - (mX+1), pY - (mY-1)), 1)

    if collisionCheck(mID, (mX-1), mY, mMap) == 0:
        goto[1][0] = round(math.hypot(pX - (mX-1), pY - mY), 1)

    # goto[1][1] is skipped since that is the monsters current position

    if collisionCheck(mID, (mX+1), mY, mMap) == 0:
        goto[1][2] = round(math.hypot(pX - (mX+1), pY - mY), 1)

    if collisionCheck(mID, (mX-1), (mY+1), mMap) == 0:
        goto[2][0] = round(math.hypot(pX - (mX-1), pY - (mY+1)), 1)

    if collisionCheck(mID, mX, (mY+1), mMap) == 0:
        goto[2][1] = round(math.hypot(pX - mX, pY - (mY+1)), 1)

    if collisionCheck(mID, (mX+1), (mY+1), mMap) == 0:
        goto[2][2] = round(math.hypot(pX - (mX+1), pY - (mY+1)), 1)

    # get the lowest distance, and its key
    lowest = goto.min()
    lowestKey = goto.argmin()

    # if the lowest distance is lower than monsters current position, move

    if lowest < dist:
            if lowestKey == 0: 
                    newX = mX - 1
                    newY = mY - 1

            if lowestKey == 1:
                    newY = mY - 1

            if lowestKey == 2: 
                    newX = mX + 1
                    newY = mY - 1

            if lowestKey == 3: 
                    newX = mX - 1

            if lowestKey == 5: 
                    newX = mX + 1

            if lowestKey == 6: 
                    newY = mY + 1
                    newX = mX - 1

            if lowestKey == 7:
                    newY = mY + 1

            if lowestKey == 8: 
                    newX = mX + 1
                    newY = mY + 1

What is the cleanest, simplest, and fastest way to do what I'm doing? This is going to loop through many monsters at once!

Answer 1

Some thoughts from a non-game-developer:

• The second and subsequent if lowestKey should use elif to short-circuit the evaluation when it finds a match.
• I believe algorithms such as A* (A-star) are very well suited to find the shortest path between two points on a 2-dimensional map.
• Running this code through a linter such as flake8 will show how to make your code more pythonic.

Answer 2

Especially in a game where you have many monsters, and obstacles on the field, I suggest that you take a different approach.

Create a "parallel grid" that has the same size as the map, but has integers as values. Set all the values to some impossible value.

Now write a recursive "fill" algorithm that does the following:

def fill_distance_map(m, row, col, value):
    """Fill a distance map with increasing values, starting at a point."""
    if m[row][col] <= value:
        return

    m[row][col] = value

    for new_pos in surrounding(row, col):
        fill_distance_map(m, *new_pos, value + 1)

(Note: you will likely find that a "breadth-first" version is more efficient than this "depth-first" code. But not as easy to understand. :-)

The idea is to create a "gradient" map, which measures the distance from some target. The lower the number stored in the map, the closer to the target. Obviously, invalid squares should be filtered out during the generation process, as this will change the distance values (consider a wall, where if you can't pass "through" the wall you have to walk around it- the distance to the "other side" can be quite long).

Once you have this map, it's the same for all of your monsters - it's based on the current position of the target (player) and so the monsters can share it. You can then decide on monster movement by just picking the minimum value of all the positions they could move to. And you only have to update the map when the player moves, or when the monsters are about to move, depending on which is more convenient for you.

Here's an example: (P = 0 is the player, # = wall, M = monster)

 #  #  #  #  #  #  #  #  #  #     #  #  #  #  #  #  #  #  #  #
 .  .  .  .  .  .  .  .  .  #     2  1  1  1  2  3  4  5  6  #
 .  .  P  .  .  .  #  .  .  #     2  1  P  1  2  3  #  5  6  #
 .  .  #  #  #  #  #  #  .  #     2  1  #  #  #  #  #  #  6  #
 .  .  #  .  .  .  .  #  .  #     2  2  # 12 11 11 11  #  7  #
 .  .  #  .  M  .  .  #  .  #     3  3  # 12  M 10 10  #  8  #
 .  .  #  #  #  #  .  #  .  #     4  4  #  #  #  #  9  #  9  #
 .  .  .  .  .  .  .  #  .  #     5  5  5  6  7  8  9  # 10  #
 #  #  #  #  #  #  #  #  #  #     #  #  #  #  #  #  #  #  #  #

Note that I generated this assuming that diagonal moves have a cost of 1, just like cardinal moves. But you could change the surrounding() function to only consider cardinal moves and it wouldn't break anything - it would just change some numbers.

And here is some code that prints those maps (but not side-by-side):

game_board = [
    line.strip() for line in """
    #  #  #  #  #  #  #  #  #  #
    .  .  .  .  .  .  .  .  .  #
    .  .  P  .  .  .  #  .  .  #
    .  .  #  #  #  #  #  #  .  #
    .  .  #  .  .  .  .  #  .  #
    .  .  #  .  M  .  .  #  .  #
    .  .  #  #  #  #  .  #  .  #
    .  .  .  .  .  .  .  #  .  #
    #  #  #  #  #  #  #  #  #  #
    """.split('\n') if line.strip()
]

Game_map = [
    [ch for ch in row[::3]] for row in game_board
]

def find_cell(m, value):
    """Find a cell containing value in map m. Return row, col position."""
    for r, row in enumerate(m):
        for c, cell in enumerate(row):
            if cell == value:
                return (r, c)

def make_distance_map(m, fill=-1):
    """Make a distance map, filled with some number."""
    nrows = len(m)
    ncols = len(m[0])

    return [[fill] * ncols for _ in range(nrows)]

def print_map(m, legend={}):
    for r, row in enumerate(m):
        for c, ch in enumerate(row):
            if (r,c) in legend:
                cell = legend[(r,c)]
            else:
                cell = legend.get(ch, ch)

            if isinstance(cell, str):
                cell = f" {cell}"
            else:
                cell = f"{cell:2d}"

            print(cell, end=' ')
        print()

def surrounding(row, col):
    """Yield all valid surrounding map positions."""

    min_r = 0 if row == 0 else row - 1
    max_r = row + 1 if row < len(Game_map) - 1 else row

    min_c = 0 if col == 0 else col - 1
    max_c = col + 1 if col < len(Game_map[0]) - 1 else col


    for srow, map_row in enumerate(Game_map[min_r:max_r+1], start=min_r):
        for scol, ch in enumerate(map_row[min_c:max_c+1], start=min_c):
            if (row, col) == (srow, scol):
                # Don't yield current position
                continue

            if ch in "#":
                # Don't yield wall positions
                continue

            yield srow, scol

def fill_distance_map(m, row, col, value):
    """Fill a distance map with increasing values, starting at a point."""
    if m[row][col] <= value:
        return

    m[row][col] = value

    for new_pos in surrounding(row, col):
        fill_distance_map(m, *new_pos, value + 1)

FILL=100_000
distance_map = make_distance_map(Game_map, fill=FILL)
print_map(Game_map)
print("\n\n")

player_pos = find_cell(Game_map, 'P')
monster_pos = find_cell(Game_map, 'M')
fill_distance_map(distance_map, *player_pos, 0)
print_map(distance_map, legend={FILL:'#', player_pos:'P', monster_pos:'M'})