Selecting lowest position from 'array'

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!

• Could you add more description, how big is the board, is the player always in the 3x3 grid? – Peilonrayz Feb 18 at 22:50
• The board could be any size, this just creates a temporary array around the monster to decide which square it will move to – user1022585 Feb 18 at 22:59
• Is there anything the monster can collide with? – Peilonrayz Feb 18 at 23:02
• The collisioncheck() routine returns a 0 or a 1. Its an external def that checks if any other monsters, players or walls are at that position. – user1022585 Feb 18 at 23:05
• Hopefully I've not messed up my math when converting to this comment, but you can use: d = math.degrees(math.atan((pY - mY) / (pX - mY))) and 'N NE E SE S SW W NW'.split()[int((d + 22.5) // 45)] to know which direction you want to go if there are no collisions. – Peilonrayz Feb 18 at 23:48

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.

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'})