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.

enter image description here

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!

• Peilonrayz: Could you add more description, how big is the board, is the player always in the 3x3 grid?
• user1022585: The board could be any size, this just creates a temporary array around the monster to decide which square it will move to
• Peilonrayz: Is there anything the monster can collide with?
• user1022585: 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.
• Peilonrayz: 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.

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