CODEWITHSUNDEEP
pythonarraysalgorithmimage-processing
Todd Davies
Todd Davies

Reputation: 5522

Finding corners in a 2d map with walls

I'm working on an AI for the aisandbox.com competition. I'm making the AI for fun, not to enter the competition (just in case I would be breaking rules by asking here if I was).

I can get a 2d map of the area by using self.level.blockHeights, and I want to find some places where my bots can hide by finding corners in the map and having them defend there.

So my question is, given a 2d array of numbers where 0 is free space and 1 is a wall, what's the best way of finding corners?

P.s. I'm using Python

EDIT: here's an example of a map (the walls are black) and the corners to be found are in red: enter image description here

Upvotes: 1

Views: 1951

Answers (4)

loopbackbee
loopbackbee

Reputation: 23322

The answers so far are extremely slow (although their complexity is linear) - particularly in python, since they involve extensive looping. Also, they're not very robust to noise (though I understand that's not required here)

A nice trick to solving this problem (if you're willing to use scipy and numpy) is to apply a gaussian filter with a small kernel to the image and subtract the original image from it (taking care not to underflow). Since the corners "bleed" more into the background, in the resulting image the corners will be the pixels with highest intensity.

Here's an actual example:

import numpy
import scipy.ndimage
import scipy.misc

image= scipy.ndimage.imread('corners.png').astype(float)
image= numpy.mean( image, axis=2) #squash color channels
filtered=   scipy.ndimage.filters.gaussian_filter(image,1)
subtracted= (256+image)-filtered #take care not to underflow
maximum, minimum=   numpy.max(subtracted), numpy.min(subtracted)
magic= 0.48 #will depend on source image. Fool around and see what works
threshold= (maximum+minimum)/2+(maximum-minimum)*magic 
thresholded= subtracted>=threshold

print list(zip(*numpy.where(thresholded)))

outputs [(190, 206), (207, 314)]

corners.png:

corners.png

filtered:

filtered

thresolded:

thresolded

Upvotes: 1

Cyrille Ka
Cyrille Ka

Reputation: 15538

From your example, one could define corners as free cells with two adjacent cells occupied by walls, the two occupied cells in a configuration North/East, North/West, South/East and South/West.

Therefore finding corners is just a matter of scanning your 2D map and look at the adjacent cell of every free cell.

I am assuming that you don't want free cells with 3 surrounding walls (like in the end of a corridor).

Assuming that you have a function isWall(x,y):

def isCorner(x, y) :
     eastHasWall = isWall(x+1, y)
     westHasWall = isWall(x-1, y)
     northHasWall = isWall(x, y-1)
     southHasWall = isWall(x, y+1)

     wallArray = [eastHasWall, westHasWall, northHasWall, southHasWall]
     wallCount = wallArray.count(true)

     if wallCount == 2 :
         return (eastHasWall and northHasWall) or (eastHasWall and southHasWall) or (westHasWall and northHasWall) or (westHasWall and southHasWall)

     return false # other wall count are not corners

I haven't tested the code, but it should compile.

One should also be careful with the boundaries of the map. Only you can say if they are considered as walls or as free space in your settings.

Upvotes: 0

Julien Vivenot
Julien Vivenot

Reputation: 2250

According to your example grid, it would seem a corner can be defined by 0 that is surrounded by at least 2 1.

You could begin by writing this definition in a dumb implementation at first (like I did below intentionally), and then maybe improve it by thinking about performance, for example.

2 represents a corner in this implementation

Example Python implementation:

g = [[1,1,1,0],
     [1,0,0,0],
     [1,0,0,0],
     [1,0,1,0],
     [1,1,1,1]]

width = len(g[0])
height = len(g)

for i in range(height):
    for j in range(width):
        if g[i][j] != 0:
            continue
        around = [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]
        walls = 0
        for (x,y) in around:
            if x < 0 or x >= height or y < 0 or y >= width:
                #Outside, count as wall
                walls += 1
            elif g[x][y] == 1:
                walls += 1
        if walls in [2,3]: # 4 would be inaccessible  
            g[i][j] = 2

Output:

[1, 1, 1, 2]
[1, 2, 0, 0]
[1, 0, 0, 0]
[1, 2, 1, 2]
[1, 1, 1, 1]

Upvotes: 1

goat
goat

Reputation: 31813

pseudo code 

function isCorner(x, y) {
    wallsFound = 0;
    if (withinBounds(x + 1, y) && grid[x + 1][y] == 1)
        wallsFound++
    if (withinBounds(x - 1, y) && grid[x - 1][y] == 1)
        wallsFound++
    if (withinBounds(x, y + 1) && grid[x][y + 1] == 1)
        wallsFound++
    if (withinBounds(x, y - 1) && grid[x][y - 1] == 1)
        wallsFound++
    return wallsFound  == 2 || wallsFound == 3;
}

function withinBounds(x, y) {
    return x >= 0
        && x < rows.len
        && y >= 0
        && y < cols.len
}

for i = 0 to rows.len
    for j = 0 to cols.len
        if isCorner(x, y)
            // do something

You could change && to || in isCorner if you want the edge of the map to count as a wall.

Upvotes: 0

Related Questions