Search code examples
arraysbashconways-game-of-life

Checking neighbour elements in flat array

Problem description:
I want to iterate over an array (flattened 2D --> 1D array right now) and keep checking it's nearest neighbours. From that I want to determine if they are dead/alive ('X' or '.') and change their state accordingly to my rules(simplified conway's).

My grid looks like this e.g.:

...............
...........X...
.X.......X...X.
...............
....X..........
....X..........
...............
.....XX........
..........X....
...............
Cells alive: 9

But I have this array flattened to 1D array to iterate over it. So basically it turns to something like this: ....X...X....X. etc. After writing it down on a paper I think there are several cases to check in this "grid":

  • TopLeft element (i = 0) - first element, 3 neighbours/cases to check
  • TopRight element (i = nColumns - 1), as above
  • BottomLeft element (i = nColumns * nRows - nColumns), as above
  • BottomRight element (i = nColumns * nRows - 1) - last element, as above
  • "Border" elements (5 neighbours each without corner elements)
  • Middle elements with 8 neighbours

But it seems totally stupid to check it with some if's and case statements. If I could use real 2D arrays I think I could just create array of offset (-1, 1), (0, 1)... and so on. But I can't think of a way how to handle this with my code. I will be very glad for any tips/examples and so on.

My code so far: 

cellsAlive=0

#STDIN variables
geneFile=$1
nRows=$2 
nColumns=$3
let "cells = $nRows * $nColumns" 
declare -i tick_rate # instead maybe use watch or sleep

readarray -t geneArr < $geneFile # -t removes a trailing newline from each line read.
elementsCounts=${#geneArr[@]}

echo -e "--- Coordinates ---"
for (( i = 0; i < $elementsCounts; i++ )); do
    echo "${geneArr[$i]}" #| cut -d' ' -f2 $geneFile | head -2
done

echo -e "\n--- Grid ---"
#file must end with a newline
[[ $geneFile && -f $geneFile && -r $geneFile ]] || { printf >&2 'arg must be readable file.\n'; exit; }

array=()
for ((i=0; i<nRows*nColumns; ++i)); do
    array+=( '.' )
done
printf "\n"

while read -r x y; do 
    [[ $x && $y ]] || continue
    [[ $x = +([[:digit:]]) && $y = +([[:digit:]]) ]] || continue
    ((x=10#$x,y=10#$y)) #10 digit base
    (( x<nRows && y<nColumns )) || continue
    array[x+y*nRows]='X' 
    if [[ ${array[x+y*nRows]} == 'X' ]]; then
        let "cellsAlive += 1"
    fi
done < "$geneFile"

# print to stdout and to file
for((i=0;i<nColumns;++i)); do
    printf '%s' "${array[@]:i*nRows:nRows}" $'\n'
done | tee currentState 

arrayCopy=("${array[@]}")  
printf "Cells alive: %d" $cellsAlive ; printf "\n"

# printf "\n"

for (( i = 0; i < ${#arrayCopy[@]}; i++ )); do 
    #neighboursCount=0
    case $i in

        "0") if [[ ${arrayCopy[$(($i - 1))]} == 'X' ]] || [[ ${arrayCopy[$(($i + $nColumns))]} == 'X' ]] || [[ ${arrayCopy[$(($i + $nColumns + 1))]} == 'X' ]] ; then #TopLeft
            echo "That is just ridiculous way to check it..."
        fi ;;
        "$(($nColumns - 1))") printf "${arrayCopy[$i]}" ;; #TopRight
        "$(($nColumns*$nRows-1))") printf "${arrayCopy[$i]}" ;; #BottomRight
        "$(($nColumns*$nRows-$nColumns))") printf "${arrayCopy[$i]}" ;; #BottomLeft
        *) ;; #Middle elements with 8 neighbours
    esac
done
printf "\n"

Thanks in advance for help.

Example geneFile.txt (add blank like at the end):

1 2
4 5
6 7
13 2
5 7
4 4
9 2
11 1
10 8
Solution

  • ok. Here we go. Because i found this question interesting to be implemented in bash i just wrote an implementation of conway's game of life.

    The main part to answer your question is probably: how to access neighbours for a position in a matrix if it is linearized?.

    So you can access an element in a flatted matrix by 

    (row*fieldwidth)+columnoffset.

    Every neighbour then can be accessed by adjusting row and columnoffset by +/-1 starting with row and columnoffset at 0.

    Have a look at the getnextstate function to view the specialcases.

    So here is the implementation. You are able to provide a file as input containing just CELLALIVEMARKER,CELLDEADMARKER and spaces. If the length for the flatted matrix does not fit the width/height parameter for the FIELD it just pads with random values.

    #!/bin/bash

# system values
BASENAME="/usr/bin/basename"
ECHO="/bin/echo"
SLEEP="/bin/sleep"
TPUT="/usr/bin/tput"
GREP="/bin/grep"
WC="/usr/bin/wc"
CAT="/bin/cat"

if [ "${#}" != "4" -a "${#}" != "5" ]; then
  ${ECHO} "USAGE:    ./$(${BASENAME} ${0}) FIELDWIDTH FIELDHEIGHT RULESALIVE RULESDEAD [LINSTARTMATRIX]"
  ${ECHO} "EXAMPLES: ./$(${BASENAME} ${0}) 50         50          \"2 3\"    \"3\""
  ${ECHO} "          ./$(${BASENAME} ${0}) 50         50          \"2 3\"    \"3\""    init.mtx
  exit
fi

# field values
FWIDTH=${1}
FHEIGHT=${2}
# number of living neighbours for a living cell to stay alive in the next generation
RULESALIVE=($(${ECHO} ${3}))
# number of living neighbours for a dead cell to become alive in the next generation
RULESDEAD=($(${ECHO} ${4}))
CELLALIVEMARKER="o"
CELLDEADMARKER="."
FIELD=() # flatted matrix representation
# if there are just marker values or spaces in the file it is a valid one
${CAT} ${5} | ${GREP} -oq '[^\'${CELLALIVEMARKER}'\'${CELLDEADMARKER}'\ ]'
isvalid="${?}"
if [ "${5}" != "" ] && [ "${isvalid}" == "1" ]; then
  FIELD=($(${CAT} ${5}))
  # fill up with randoms if the length won't fit the dimension parameters
  if [ "${#FIELD[@]}" != "$((${FWIDTH}*${FHEIGHT}))" ]; then
    ${ECHO} "I: Padding matrix with random values."
    # fill up field with randoms if its too short
    for((i=${#FIELD[@]}; i<${FWIDTH}*${FHEIGHT}; i=$((${i}+1)))); do
      cell="${CELLALIVEMARKER}"
      alive=$((${RANDOM}%2))
      if [ "x${alive}" == "x1" ]; then
        cell="${CELLDEADMARKER}"
      fi
      FIELD[${#FIELD[@]}]="${cell}"
    done
  fi
else
  # fill random field
  for((i=0; i<${FWIDTH}*${FHEIGHT}; i=$((${i}+1)))); do
    cell="${CELLALIVEMARKER}"
    alive=$((${RANDOM}%2))
    if [ "x${alive}" == "x1" ]; then
      cell="${CELLDEADMARKER}"
    fi
    FIELD[${#FIELD[@]}]="${cell}"
  done
fi

# evaluate rules and get the next state for the cell
getnextstate() {
  local i="${1}" # row
  local j="${2}" # col
  local neighbours=""

  # left upper
  if [ "${i}" -eq "0" -a "${j}" -eq "0" ]; then
    neighbours="${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}+1)))]}"
  # right upper
  elif [ "${i}" -eq "0" -a "${j}" -eq "$((${FWIDTH}-1))" ]; then
    neighbours="${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]}"
  # left bottom
  elif [ "${i}" -eq "$((${FHEIGHT}-1))" -a "${j}" -eq "0" ]; then
    neighbours="~${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}-1)*${FWIDTH})+(${j}+1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]}"
  # right bottom
  elif [ "${i}" -eq "$((${FHEIGHT}-1))" -a "${j}" -eq "$((${FWIDTH}-1))" ]; then
  neighbours="?${FIELD[$((((${i}-1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]}"
  # upper
  elif [ "${i}" -eq "0" -a "${j}" -gt "0" ]; then
    neighbours="-${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}+1)))]}"
  # bottom
  elif [ "${i}" -eq "$((${FHEIGHT}-1))" -a "${j}" -gt "0" ]; then
    neighbours="=${FIELD[$((((${i}-1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}-1)*${FWIDTH})+(${j}+1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]}"
  # right
  elif [ "${i}" -gt "0" -a "${j}" -eq "0" ]; then
    neighbours="#${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}-1)*${FWIDTH})+(${j}+1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}+1)))]}"
  # left
  elif [ "${i}" -gt "0" -a "${j}" -eq "$((${FWIDTH}-1))" ]; then
    neighbours="_${FIELD[$((((${i}-1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]}"
  # center
  else
    neighbours="@${FIELD[$((((${i}-1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}-1)*${FWIDTH})+(${j}+1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}+1)))]}"
  fi

  # count neighbours alive
  ncnt=$(${ECHO} ${neighbours} | ${GREP} -o ${CELLALIVEMARKER} | ${WC} -l)
  # evaluate rules
  local next=""
  if [ "${FIELD[$(((${i}*${FWIDTH})+${j}))]}" == "${CELLALIVEMARKER}" ] && [[ "$(${ECHO} ${RULESALIVE[@]})" =~ ${ncnt} ]]; then
    next="${CELLALIVEMARKER}"
  elif [ "${FIELD[$(((${i}*${FWIDTH})+${j}))]}" == "${CELLDEADMARKER}" ] && [[ "$(${ECHO} ${RULESDEAD[@]})" =~ ${ncnt} ]]; then
    next="${CELLALIVEMARKER}"
  else
    next="${CELLDEADMARKER}"
  fi
  ${ECHO} ${next}
}

firstrun=1
while [ true ]; do
  # print lines
  FIELD_UPDATE=()

  for((i=0; i<${FHEIGHT}; i=$((${i}+1)))); do
    line=""
    # calculate lines
    for((j=0; j<${FWIDTH}; j=$((${j}+1)))); do
      if [ "${firstrun}" == "1" ]; then
        line="${line}${FIELD[$(((${i}*${FWIDTH})+${j}))]} "
      # start calculation just after the first print
      elif [ "${firstrun}" == "0" ]; then
        line="${line}$(getnextstate ${i} ${j}) "
      fi
    done
    FIELD_UPDATE=($(${ECHO} ${FIELD_UPDATE[@]}) $(${ECHO} ${line}))
    ${ECHO} ${line}
  done
  FIELD=(${FIELD_UPDATE[@]})
  ${SLEEP} 2
  # refresh lines in the field
  for((i=0; i<${FHEIGHT}; i=$((${i}+1)))); do
    # refresh lines
    ${TPUT} cuu1
    ${TPUT} el
  done
  firstrun=0
done

    So providing the file init.mtx containing the following matrix

    . o . . . . . . . .
. . o . . . . . . .
o o o . . . . . . .
. . . . . . . . . .
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . .

    you are able to create a simple glider (from the upper left to the bottom right)

    . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . o o 
. . . . . . . . o o

    using Conway's default rules by running this script as follows:

    ./gameoflife 10 10 "2 3" "3" init.mtx

    Hope this helps. And btw it was fun to implement this in bash :)