Sunday, August 30, 2015

Python - Built a Maze Creator and a Server to Allow Clients to Connect and Navigate the Maze

Over 2 years ago I participated in a CTF where in one of the challenges you were presented with an IP Address and a port to connect to.  Upon connecting to the port you were presented with some navigational information with 3-5 seconds to make a decision of where to go inside of a maze.

I was impressed by the challenge and decided a couple of days ago I would build it in python.  First I started out with the code to be able to build, save, load, and modify mazes.  The create.py file contains the ability to initialize a maze if you have not.

From a non-privileged account run ./create.py.  You will then be presented with a greeting, then if you would like to load a maze from a file you are prompted to do so.  Then you are prompted for the number of columns and rows you would like.  This then draws the map using a '#' as a character symbolizing a wall that can not be passed through.

Then you can proceed by creating the maze through typing in 'n', 's', 'w', or 'e'.  Notice that with every maze you start on the last row in the middle.  Everything is based on an x,y coordinate system as shown in the code.  In creating the maze anywhere it touches the outside border the server will issue a win, so remember to leave a barrier of '#' between the maze and the outer rim of the maze you are creating.  The code for create.py is below:



#!/usr/bin/python

# Maze Structure
#
#  x ---------------------->
#  y  (0,0)   (1,0)  (2,0)
#  |
#  |  (0,1)   (1,1)  (2,1)
#  |
#  |  (0,2)   (1,2)  (2,2)
# \_/

import sys

def intro():
 print "Welcome to the Maze Creator"
 print
 print "This will assist you in creating a maze that is the size in columns and rows"
 print "specified.  Then you can create the navigation through the maze as you start"
 print "on the bottom row in the middle."
 print
 print "The starting spot of the maze will always be in the bottom middle.  Wherever"
 print "a '.' touches the edge it will be an exit point."
 print

def promptSize(val):
 print
 print "Input the number of " + val + " you would like your maze to have."
 output = raw_input("~: ")
 print
 return output

def createMaze(m, x, y):
 # x is columns, y is rows
 for i in range (0, y):
  for j in range (0, x):
   dictKey = str(i) + '-' + str(j)
   m[dictKey] = '#'



def loadMaze(m, x, y, f):
 try:
  prevMaze = open(f, 'r') 
 except:
  print "Failed to open the file specified. Goodbye!"
  sys.exit()
 lineCount = 0   # Number of rows or y
 charCount = 0   # Number of columns or x
 for line in prevMaze:
  if lineCount == 0:
   x = int(line.strip())
  elif lineCount == 1:
   y = int(line.strip())
  else:
   charCount = 0
   for i in line.strip(): 
    dictKey = str((lineCount-2)) + '-' + str(charCount)
    m[dictKey] = i
    charCount = charCount + 1
  lineCount = lineCount + 1
 return m, x, y 



def outputMaze(m, x, y, posX, posY, t):
 # x is columns, y is rows
 if t == 'final':
  print
  saveFile = raw_input("Save the maze as file (default: final.txt): ")
  try:
   file = open(saveFile, 'w')
  except:
   file = open('final.txt', 'w')
   saveFile = 'final.txt'
  print "Saving the below maze as " + saveFile
  print
  file.write(str(x) + '\n')
  file.write(str(y) + '\n')
 row = ''
 for i in range (0, y):
  for j in range (0, x):
   dictKey = str(i) + '-' + str(j)
   if ((posX == j) and (posY == i)):
    if t == 'redraw': row = row + '$'
    elif t == 'final': row = row + '.'
    m[dictKey] = '.' 
   else:
    row = row + m[dictKey]
  if t == 'redraw':
   print row
  if t == 'final':
   file.write(row + '\n')
  row = ''
 if t == 'final':
  file.close()



def findDirections(m, x, y, posX, posY):
 dirN = False  # Can I go North?
 dirS = False  # Can I go South?
 dirE = False  # Can I go East?
 dirW = False  # Can I go West?
 dirTravel = ''  # Return the directions that can be traveled.
 if (posY <> 0):  # Determine if you can navigate North
  dirN = True
  dirTravel = dirTravel + 'n '
 if (posY <> (y - 1)): # Determine if you can navigate South
  dirS = True
  dirTravel = dirTravel + 's '
 if (posX <> (x - 1)): # Determine if you can navigate East
  dirE = True
  dirTravel = dirTravel + 'e '
 if (posX <> 0):  # Determine if you can navigate West 
  dirW = True
  dirTravel = dirTravel + 'w '
 return dirTravel


  
def findPath(m, x, y, posX, posY):
 dirN = False  # Can I go North?
 dirS = False  # Can I go South?
 dirE = False  # Can I go East?
 dirW = False  # Can I go West?
 dirTravel = ''  # Return the directions that can be traveled.
 if (posY <> 0):  # Determine if you can navigate North
  dictKey = str(posY-1) + '-' + str(posX)
  if m[dictKey] == '.':
   dirN = True
   dirTravel = dirTravel + 'n '
 if (posY <> (y - 1)):  # Determine if you can navigate South
  dictKey = str(posY+1) + '-' + str(posX)
  if m[dictKey] == '.':
   dirN = True
   dirTravel = dirTravel + 's '
 if (posX <> 0):  # Determine if you can navigate East
  dictKey = str(posY) + '-' + str(posX+1)
  if m[dictKey] == '.':
   dirN = True
   dirTravel = dirTravel + 'e '
 if (posX <> (x - 1)):  # Determine if you can navigate West
  dictKey = str(posY) + '-' + str(posX-1)
  if m[dictKey] == '.':
   dirN = True
   dirTravel = dirTravel + 'w '
 return dirTravel



def main():
 maze = {}
 sizeX = 0 #Size of the Maze X - Number of columns
 sizeY = 0 #Size of the Maze Y - Number of rows
 posX = 0 #Position of '$' on the Maze X based on x,y coordinates
 poxY = 0 #Position of '$' on the Maze Y based on x,y coordinates
 option = '' #Option Selected for Movement or to Quit
 directions='' #The directions in which can be navigated
 listDir = [] #Create a list of the directions possible
 loadOption = ''   #Option to load a previously created maze or create a new one
 mazeFile = ''   #Filename of what the maze is called

 intro()
 loadOption = raw_input("Would you like to load a previously created maze from file (y, n)? ")
 if loadOption == 'y':
  mazeFile = raw_input("Enter the filename of the maze to load: ")
  maze, sizeX, sizeY = loadMaze(maze, sizeX, sizeY, mazeFile)
 else:
  sizeX = promptSize('columns')
  sizeX = int(sizeX)
  sizeY = promptSize('rows')
  sizeY = int(sizeY)
  createMaze(maze, sizeX, sizeY)
 posX = int(sizeX) / 2
 posY = int(sizeY) - 1 # The range goes from 0 to the number before the sizeY given so you need to subtract 1
 while (option <> "q"):
  print
  outputMaze(maze, sizeX, sizeY, posX, posY, 'redraw')
  directions = findDirections(maze, sizeX, sizeY, posX, posY)
  print
  print "You can travel in the following directions: " + directions
  option = raw_input("Select direction to navigate or 'q' to quit: ")
  listDir = directions.split()
  if option in listDir:
   if option == 'n': posY = posY - 1
   elif option == 's': posY = posY + 1
   elif option == 'e': posX = posX + 1
   elif option == 'w': posX = posX - 1
  elif option <> 'q':
   print 'Invalid direction!'
 print
 outputMaze(maze, sizeX, sizeY, posX, posY, 'final')
 print


if __name__ == "__main__":
    main()



Then the server portion of the challenge, I had the following objectives.
1.  I wanted multiple clients to be able to connect to it.
2.  It needed to be able to load a maze and then be able to return to the client the directions of where it could go next

Below is the server code that I utilized.  I was able to reuse some of the functions that are in the create.py file so you will notice that I import from that file.  If you save the file for the create portion of the maze as something else, you will need to update the import file entry at the beginning and as it is referenced throughout the code.  I also start the listener on TCP port 30,000 which can be modified.

Also as far as a client connecting to it, I initially used netcat.  At the end of this I have provided a python client that can be utilized.  The ideal goal would be to create a python client to navigate through the maze and then automate it.  Also in the challenge there was a timeout of 3-5 seconds between making decisions of the direction to go in the maze.  I have left that out of the code but can easily be put in.



#!/usr/bin/python

import socket
import sys
import thread  
import create    # Import the functions from the create.py file

mazeFilename='final.txt'  # Change this for the server to load a different maze file.



def handleClient(c, addr):
 maze = {}
        sizeX = 0       #Size of the Maze X - Number of columns
        sizeY = 0       #Size of the Maze Y - Number of rows
        posX = 0        #Position of '$' on the Maze X based on x,y coordinates
        poxY = 0        #Position of '$' on the Maze Y based on x,y coordinates
        startX = 0        #Position of '$' on the Maze X based on x,y coordinates
        startY = 0        #Position of '$' on the Maze Y based on x,y coordinates
        directions=''   #The directions in which can be navigated
 listDir = []    #Create a list of the directions possible

 print "Accepted connection from: " + str(addr)
 msg = "Welcome to the maze.  Navigate through the maze based on the directions returned.\r\n"
 msg += "You will only have 10 seconds between moves to make a decision.\r\n\r\n"
 msg += "The size of the maze selected is below:\r\n"
 maze, sizeX, sizeY = create.loadMaze(maze, sizeX, sizeY, mazeFilename) 
 msg += str(sizeX) + ',' + str(sizeY) + "\r\n\r\n"
 c.send(msg)
 posX = int(sizeX) / 2
        posY = (sizeY - 1)      # The range goes from 0 to the number before the sizeY given so you need to subtract 1
 startX = int(sizeX) / 2
        startY = (sizeY - 1)      # The range goes from 0 to the number before the sizeY given so you need to subtract 1
 while 1:
  create.outputMaze(maze, sizeX, sizeY, posX, posY, 'network')  # redraw or network
  directions = create.findPath(maze, sizeX, sizeY, posX, posY)
  directionInfo = "You can travel in the following directions: " + directions + "\r\n"
  c.send(directionInfo)
  listDir = directions.split()
  option = c.recv(1024)
  #print listDir
  option = option.strip()
                if option in listDir:
                        if option == "n": posY = posY - 1
                        elif option == 's': posY = posY + 1
                        elif option == 'e': posX = posX + 1
                        elif option == 'w': posX = posX - 1
  else:
   c.send("Invalid direction received.\r\n")
   break
  # Check to see if the player figured a way out of the maze
  #print "startX,Y: " + str(startX) + "," + str(startY)
  #print "posX,Y: " + str(posX) + "," + str(posY)
  if not ((startX == posX) & (startY == posY)):
   if ((posX == 0) | (posY == 0) | (posX == (sizeX - 1)) | (posY == (sizeY - 1))): 
    c.send("You Win!\r\n")
    break
 c.close()


def main():
 host = ''
 port = 30001
 try:
  s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
 except:
  print "Failed to create socket."
  sys.exit()
 print 'Listening for connections on port ' + str(port)
 s.bind((host, port))
 s.listen(5)  # Allows up to 5 connections at a time
 while 1:
  (client, address) = s.accept()
  thread.start_new_thread(handleClient, (client, address))
 s.close() 
 



if __name__ == "__main__":
    main()




I have included both of these files and a few mazes that I have created to test the code on my google drive located here.  An example of a maze that can be downloaded with the preceding link and use is below.

15
15
##.############
##........#####
##.######.#####
##.######.#####
##.######.#####
##.####.......#
##.####.#.#####
##.####.#....##
##.####.####.##
##.####.####.##
##.##...####.##
##.##.#.####.##
##......####.##
#######......##
#######.#######

The first line of the maze is the size in columns, the next is the size in rows, on the 3rd line the 3rd dot in is the exit to the maze.  It does not have to be on the top line, it could also be on the size of the maze.  Then the beginning of the maze is on the last line in the middle.

Below is the quick client that I designed to navigate through the maze, however it is not an automated method to navigate through the maze.



#!/usr/bin/python

import socket

host = '127.0.0.1'
port = 30001

def createMaze(m, x, y):
        # x is columns, y is rows
 x = int(x)
 y = int(y)
        for i in range (0, y):
                for j in range (0, x):
                        dictKey = str(i) + '-' + str(j)
                        m[dictKey] = ' '

def createWall(m, px, py, dir):
 if (dir == 'n'): py = py - 1
 elif (dir == 's'): py = py + 1
 elif (dir == 'w'): px = px - 1
 elif (dir == 'e'): px = px + 1
 dictKey = str(py) + '-' + str(px)
 #print m
 #print dictKey
 m[dictKey] = '#'
 return m

def outputMaze(m, x, y, posX, posY):
        # x is columns, y is rows
 x = int(x)
 y = int(y)
        row = ''
        for i in range (0, y):
                for j in range (0, x):
                        dictKey = str(i) + '-' + str(j)
                        if ((posX == j) and (posY == i)):
                                row = row + '$'
                                m[dictKey] = '.'
                        else:
                                row = row + m[dictKey]
                print row
                row = ''



def main():
 recvInfo = ''
 maze = {}
 sizeX = 0
 sizeY = 0
 newSizeX = 0
 newSizeY = 0
 coord = []
 posX = 0
 poxY = 0
 option = ''
 directions = ''
 listDir = []
        
 while 1:
  try:
   s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
  except:
   print "Failed to create socket."
   sys.exit()
  s.connect((host, port))
  recvInfo = s.recv(1024)
  print recvInfo
  size = recvInfo[191:]
  coord = size.split(',')
  #print str(coord[0]) + ' ' + str(coord[1])
  newSizeX = coord[0]
  newSizeY = coord[1]
  if not ((newSizeX == sizeX) & (newSizeY == sizeY)):
   createMaze(maze, newSizeX, newSizeY)
   sizeX = newSizeX
   sizeY = newSizeY
  posX = int(sizeX) / 2
         posY = int(sizeY) - 1     
  option = ''
  while 1:
   recvInfo = s.recv(1024)
   if not recvInfo:
    break
   else:
    if recvInfo[:7] == 'Invalid':
     break
    else:
     directions = recvInfo[44:]
     listDir = directions.split()
     if option == 'n': posY = posY - 1
     elif option == 's': posY = posY + 1
     elif option == 'e': posX = posX + 1
     elif option == 'w': posX = posX - 1
     if not ('n' in listDir): 
      maze = createWall(maze, posX, posY, 'n')
     if not ('s' in listDir): 
      maze = createWall(maze, posX, posY, 's')
     if not ('e' in listDir): 
      maze = createWall(maze, posX, posY, 'e')
     if not ('w' in listDir): 
      maze = createWall(maze, posX, posY, 'w')
     outputMaze(maze, sizeX, sizeY, posX, posY)
     print recvInfo
     option = raw_input("~: ")
     s.send(option)
  s.close() 
 



if __name__ == "__main__":
    main()





No comments:

Post a Comment

Powershell - Gather Mapped Drives from a List of Computer Names

I created the following Powershell script to gather remotely the mapped drives that users had in their profiles.  I had to create the script...