Flow fields

Now that we're more familiar with the concept and use of cellular automata and grid systems, it's time to stretch our applications using rules that apply to lower levels or organization to generate more interesting applications. A flow field is a representation of how a particle or fluid moves throughout a given space, and it is often used in games of Tower Defense to direct the enemies to a single exit.
We can use the concept of counting neighbors to generate paths, where every tile has a vector, or line, attached to it that represents the force and the direction in which any object that lands on that tile will move. The purpose of the algorithm is to calculate a path that connects, whenever possible, any tile in the grid with a destination tile, which represents the "exit" of the maze.
Amit Patel's webpage contains a more comprehensive, interactive explanation on the concept of Flow field generation using diverse algorithms that I encourage you to look at. This tutorial will cover the Breadth First Search algorithm.


The parameters of the Algorithm

  • MAP: [str,str,str, ...] - a collection of 0 (wall) and 1 (path), casted as strings, representing the map
  • RES: int - Size of each tile
  • SCREEN: (int,int) - Dimensions of the screen given as a width and height in pixels
  • VECTOR_LENGTH: int - Direction and force of a vector represented within the tile
  • TILE: Tile() - Basic unit of information in the program
  • TILEMAP: [[TILE, ..., n=DIMS[0]], ..., n=DIMS[1]] - 2D array of TILE
  • TARGET_TILE: TILE - A starting TILE in the grid considered the destination point for the path
  • STACK: [TILE, ...] - A collection of TILE, sorted by proximity to TARGET_TILE 
# MODULES
import pygame

# DD

MAP = [
    "101011",
    "111010",
    "100010",
    "111110",
    "100010",
]


DIMS = (len(MAP[0]), len(MAP))
RES = 64
SCREEN = (DIMS[0]*RES, DIMS[1]*RES)
display = pygame.display.set_mode(SCREEN)
VECTOR_LENGTH = RES//3

# DD. TILE
# tile = Tile()
# interp. the basic unit of information that makes the map


class Tile:
    def __init__(self, c, r, isWall):
        self.c = c
        self.r = r
        self.x = self.c*RES
        self.y = self.r*RES
        self.rect = pygame.Rect(self.x, self.y, RES, RES)
        self.isWall = False if isWall == "1" else True
        self.color = "green" if self.isWall else "white"
        self.direction = [1, 0, 0, 0]  # R, D, L, U
        self.center = (self.x + RES//2, self.y + RES//2)
        self.visited = False

    def draw(self):
        pygame.draw.rect(display, self.color, self.rect)

    def drawVector(self):
        pygame.draw.line(display, "red", self.center, self.getVectorEndPoint())

    def getVectorEndPoint(self):

        if self.isWall:
            return self.center

        # RIGHT
        if bool(self.direction[0]):
            return (self.center[0]+VECTOR_LENGTH, self.center[1])
        # DOWN
        if bool(self.direction[1]):
            return (self.center[0], self.center[1]+VECTOR_LENGTH)
        # LEFT
        if bool(self.direction[2]):
            return (self.center[0]-VECTOR_LENGTH, self.center[1])
        # UP
        else:
            return (self.center[0], self.center[1]-VECTOR_LENGTH)


# DD. TILEMAP
# tileMap = [[TILE, ..., n = DIMS[0]], ..., n = DIMS[1]]
# interp. the map of tiles that represent the map
tileMap = []
for r in range(DIMS[1]):
    tileRow = []
    for c in range(DIMS[0]):
        tile = Tile(c, r, MAP[r][c])
        tileRow.append(tile)
    tileMap.append(tileRow)

# TEMPLATE FOR TILEMAP
# for tileRow in tileMap:
#   for tile in tileRow:
#       ... tile


def fn_for_tileMap(fn, *args):
    for tileRow in tileMap:
        for tile in tileRow:
            fn(tile, *args)


# DD. TARGET_TILE
# tt = tileMap[int][int]
# interp. the tile on which objects placed in the map have to move
tt = tileMap[0][0]
tt.color = "orange"
tt.visited = True

# DD. STACK
# stack = [TILE, ...]
# interp. the order in which the tiles will be visited relative to the search algorithm
stack = [tt]

The Algorithm

  • Are there elements in the Stack?:
    • Pick the first TILE in the STACK
    • Add neighbors of this TILE to STACK: RIGHT, DOWN, LEFT, UP, if neighbor tile exists, hasn't been visited and is not a wall
    • Set neighbor TILE to visited
    • Update the neighbor direction and calculate the updated direction of the red line representing the vector
    • Erase first TILE from STACK

Let's implement this algorithm using Python! 
# MODULES
import pygame

# DD

MAP = [
    "101011",
    "111010",
    "100010",
    "111110",
    "100010",
]


DIMS = (len(MAP[0]), len(MAP))
RES = 64
SCREEN = (DIMS[0]*RES, DIMS[1]*RES)
display = pygame.display.set_mode(SCREEN)
VECTOR_LENGTH = RES//3

# DD. TILE
# tile = Tile()
# interp. the basic unit of information that makes the map


class Tile:
    def __init__(self, c, r, isWall):
        self.c = c
        self.r = r
        self.x = self.c*RES
        self.y = self.r*RES
        self.rect = pygame.Rect(self.x, self.y, RES, RES)
        self.isWall = False if isWall == "1" else True
        self.color = "green" if self.isWall else "white"
        self.direction = [1, 0, 0, 0]  # R, D, L, U
        self.center = (self.x + RES//2, self.y + RES//2)
        self.visited = False

    def draw(self):
        pygame.draw.rect(display, self.color, self.rect)

    def drawVector(self):
        pygame.draw.line(display, "red", self.center, self.getVectorEndPoint())

    def getVectorEndPoint(self):

        if self.isWall:
            return self.center

        # RIGHT
        if bool(self.direction[0]):
            return (self.center[0]+VECTOR_LENGTH, self.center[1])
        # DOWN
        if bool(self.direction[1]):
            return (self.center[0], self.center[1]+VECTOR_LENGTH)
        # LEFT
        if bool(self.direction[2]):
            return (self.center[0]-VECTOR_LENGTH, self.center[1])
        # UP
        else:
            return (self.center[0], self.center[1]-VECTOR_LENGTH)


# DD. TILEMAP
# tileMap = [[TILE, ..., n = DIMS[0]], ..., n = DIMS[1]]
# interp. the map of tiles that represent the map
tileMap = []
for r in range(DIMS[1]):
    tileRow = []
    for c in range(DIMS[0]):
        tile = Tile(c, r, MAP[r][c])
        tileRow.append(tile)
    tileMap.append(tileRow)

# TEMPLATE FOR TILEMAP
# for tileRow in tileMap:
#   for tile in tileRow:
#       ... tile


def fn_for_tileMap(fn, *args):
    for tileRow in tileMap:
        for tile in tileRow:
            fn(tile, *args)


# DD. TARGET_TILE
# tt = tileMap[int][int]
# interp. the tile on which objects placed in the map have to move
tt = tileMap[0][0]
tt.color = "orange"
tt.visited = True

# DD. STACK
# stack = [TILE, ...]
# interp. the order in which the tiles will be visited relative to the search algorithm
stack = [tt]


# CODE

def draw():
    display.fill("#1e1e1e")
    fn_for_tileMap(Tile.draw)
    fn_for_tileMap(Tile.drawVector)
    pygame.display.flip()

def updateTile(tile):
    r = tile.r
    c = tile.c
    # neighbor RIGHT
    if c< DIMS[0]-1 and not tileMap[r][c+1].visited and not tileMap[r][c+1].isWall:
        neighbor = tileMap[r][c+1]
        neighbor.direction = [0,0,1,0]
        stack.append(neighbor)
        neighbor.visited = True
    # neighbor DOWN
    if r < DIMS[1]-1 and not tileMap[r+1][c].visited and not tileMap[r+1][c].isWall:
        neighbor = tileMap[r+1][c]
        neighbor.direction = [0, 0, 0, 1]
        stack.append(neighbor)
        neighbor.visited = True
    # neighbor LEFT
    if c > 0 and not tileMap[r][c-1].visited and not tileMap[r][c-1].isWall:
        neighbor = tileMap[r][c-1]
        neighbor.direction = [1, 0, 0, 0]
        stack.append(neighbor)
        neighbor.visited = True
    # neighbor UP
    if r > 0 and not tileMap[r-1][c].visited and not tileMap[r-1][c].isWall:
        neighbor = tileMap[r-1][c]
        neighbor.direction = [0, 1, 0, 0]
        stack.append(neighbor)
        neighbor.visited = True

def update():
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()

    if len(stack)>0:
        updateTile(stack[0])
        stack.pop(0)

while True:
    draw()
    update()