Programmin' Pac-Man

Setting

You play as Pac-Man. You want to collect pellets, fruit, and power pellets before anybody else, all while avoiding ghosts.

Rules

1. Every valid Pac-Man will be in a single maze. The player with the highest cumulative score after 10 games will win.
2. A game is over when all Pac-Men are dead, all pellets are gone, or 500 turns have passed
3. If a Pac-Man dies, he continues to play as a ghost
4. Eating a Power pellet will make you invincible for 10 turns, and allows you to eat Ghosts
5. Eating a Ghost will teleport the ghost to a random location
6. Ghosts cannot eat anything except Pac-Men, and do not get any points
7. Eating the following items as Pac-Man will get you the following points:
1. Pellet: 10
2. Power Pellet: 50
3. Fruit: 100
4. Ghost: 200

The Maze

If there are n Pac-Men, then a maze of size sqrt(n)*10 by sqrt(n)*10 will be generated using Prim's algorithm (due to it's low river factor), then braided completely, giving preference to already existing dead ends. Furthermore, this braiding can be done across the edges, so that there are a few pathways from top to bottom and from left to right.

There will be:

1. 2n Ghosts
2. 4n Power Pellets
3. 2n Fruit
4. n Pac-Men in spots where connected neighbors squares are empty.
5. All remaining empty spots will be filled with pellets

Hence, an initial map with 10 players will look something like this (Ghosts = green, Pellets = aqua, fruit = red, Pac-Man = yellow):

Input/Output

At the beginning of the game, You will be given a single line of characters, representing the walls in every square of the map. For each square, starting with the top left, moving right, and wrapping to the next line, you will be given a hex digit representing the wall situation:

0: No walls
1: North wall
2: East wall
3: East & North wall
4: South wall
5: South & North wall
6: South & East wall
7: Won't occur
8: West wall
9: West & North wall
A: West & East wall
B: Won't occur
C: West & South wall
D: Won't occur
E: Won't occur
F: Won't occur


Put simply, North=1, East=2, South=4, and West=8, added together.

Then, each turn, you will be given your current position and the items in your line of sight (if you are a Pac-Man. All ghosts receive all squares from -5 to +5 from their relative position). Your line of sight will be based on the direction you travelled last turn. If you travelled north, you will be given all squares directly North, East, and West of you until a wall cuts off your view plus a single square Northwest and Northeast, if no wall cuts off your view. If you choose not to move, you will be given the squares in all 8 directions.

For the visual, I means invisible, V means visible, P means Pac-Man(assuming Pac-Man is facing north):

|I I|V|I|
|I V|V V|
|V V P|I|
|I I|I|I|


Each square will be given by a coordinate, and then it's contents. It's contents are represented by the following characters:

1. P: 1 or more Pac-Man
2. G: 1 or more Ghosts
3. o: Pellet
4. O: Power pellet
5. F: Piece of Fruit
6. X: Nothing

If there is a ghost and something else on a square, G will be returned.

Hence, if you were on square 23,70, you just moved north, the square above you is a dead end and contains a Power pellet, and you have walls on both sides of you, your input would be:

23,70X 22,70O


On your current square, it will show a G if you are a Ghost, a P if there is another Pac-Man on your square, otherwise an X

Then you will return the following items via STDOUT:

A single character representing a direction (North, East, South, West, or XStay).

Previous to passing in a direction, you may also pass in any coordinate as x,y, and the walls of that square will be passed back (as described above)

The program must be continuously running until Q is passed to it via STDIN. Programs will be restarted for each game.

Accessing other information outside of what is passed to STDIN (including other Pac-Men's data or the data held by the host program) is not allowed.

Failure to return a move within 1000 ms will terminate the program (Running on my fairly decent Win8 machine). You will be given 2 seconds to process the initial maze layout when it is given

Host will be written in Python, and code to test your bot is forthcoming.

Exceptional cases

• If multiple Pac-Men end up on the same location, neither get the contents of the current square, unless exactly 1 of them is invincible, in which case, the invincible Pac-Man will receive the pellet.
• A Pac-Man eaten by a Ghost will not be teleported somewhere else. If two Pac-Men are on a square, and one is invincible, the ghost will be teleported.
• Being teleported as a Ghost prevents you from moving for 1 turn. When playing as a Ghost, you simply will have your turn skipped
• Attempting to move through a wall will be interpreted as "Stay"
• Each of the initial ghosts will receive one of the 4 personality traits, as described here, with the following modification:

1. The bugs described will not be duplicated
2. They will all be active from the beginning
3. They are vulnerable only to the player who ate the pellet
4. They will indefinitely switch from scatter to chase, each having a fixed number of turns before switch
5. Upon switching to chase, they will find the nearest Pac-Man to chase, and will chase that Pac-Man for the duration of their chase. (If there is a tie for closeness, the Pac-Man will be picked pseudorandomly)
7. Inky will pick the nearest ghost to base his calculations off of after switching to chase.
8. Clyde will find all players 8 squares away, then follow the furthest player.
9. All ghosts except Clyde won't target a player farther than 5 squares away

I will accept compilable code from a standard language or an .exe (with accompanying code).

Programming Tips

You may with my controller. You need to put a /bots/your_bot_name/ folder in the same directory as the program. Within the folder, you need to add a command.txt containing a command to execute your program (ex: python my_bot.py), and the your bot.

The controller code is on Github (Python code, requires Pygame if you want graphics.) Tested on windows and linux

SCORES

ghostbuster: 72,840 points

pathy: 54,570 points

shortsighted: 50,820 points

avoidinteraction: 23,580 points

physicist: 18,330 points

randomwalk: 7,760 points

dumbpac: 4,880 points

• +1. This is the first time I see the word "Pacmen" – justhalf Aug 4 '14 at 1:22
• Looks like a fun challenge! By the way: (1) They're actually called "energizers" and not "power pellets." (2) The "M" in Pac-Man is capitalized, and it's hyphenated as "Pac-Man" and not "Pacman" or "PacMan". Here is a great resource for Pac-Man information: home.comcast.net/~jpittman2/pacman/pacmandossier.html – Todd Lehman Aug 4 '14 at 2:37
• Anyone working on this challenge should join us in the chat room for codegolf. chat.stackexchange.com/rooms/240/the-nineteenth-byte – Sparr Aug 4 '14 at 15:33
• Ok. The controller now works on windows and linux, but will freeze on windows if your bot doesn't respond. – Nathan Merrill Aug 4 '14 at 20:35
• I am colorblind and cannot tell the PacMen from the Ghosts, could we change the colors? – Moop Aug 5 '14 at 19:59

GhostBuster - Python

Picks a random spot on the map, uses A* algorithm to find the best path forward. Once it reaches its destination, it will pick a new one and continue. It will try to avoid ghosts, but with the limited FOV, it will occasionally run into them. It will avoid walking on spots already visited.

• Added logic for ghost. Picks a close (<8) random point and moves there, disregarding scores other than pacmen
• Adjusted point values of squares
• Bug (if he is too good and eats all the pellets, the game freezes for some reason)

Uses some code of Sparr's, thank you for the logic.

Windows 7, Visual Studios with Python Tools. Should work on linux boxes.

#!/usr/bin/env python

import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

P,G,o,O,F,X = 5,600,-10,-100,-100,10
PreviousSquarePenalty = 10

# read in the maze description
mazeSize = int(math.sqrt(len(maze_desc)))

North,East,South,West = range(4)
DIRECTIONS = ['N','E','S','W']
Euclidian,Manhattan,Chebyshev = range(3)

sign = lambda x: (1, -1)[x<0]
wrap = lambda v : v % mazeSize

class Node(object):

def __init__(self, x, y, value):
self.x, self.y = x,y
self.wallValue = int(value, 16); #Base 16
self.nodes = {}
self.item = 'o' # Start as normal pellet

def connect(self, otherNode, dir):
if dir not in self.nodes:
self.nodes[dir] = otherNode
otherNode.nodes[(dir+2)%4] = self

def distance(self, otherNode, meth = Manhattan):
xd = abs(otherNode.x - self.x)
yd = abs(otherNode.y - self.y)
xd = min(xd, mazeSize - xd)
yd = min(yd, mazeSize - yd)
if meth == Euclidian:
return math.sqrt(xd * xd + yd * yd)
if meth == Manhattan:
return xd + yd
if meth == Chebyshev:
return max(xd, yd)

def direction(self, otherNode):
for key, value in self.nodes.iteritems():
if value == otherNode:
return DIRECTIONS[key]
return 'ERROR'

def getScore(self):
score = eval(self.item)
for node in self.nodes.values():
score += eval(node.item)
return score

def nearbyGhost(self):
if self.item == 'G':
return True
for node in self.nodes.values():
if node.item == 'G':
return True
return False

def __hash__(self):
return  (391 + hash(self.x))*23 + hash(self.y)

def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)

def __ne__(self, other):
return (self.x, self.y) != (other.x, other.y)

def __str__(self):
return str(self.x)+","+str(self.y)

def __repr__(self):
return str(self.x)+","+str(self.y)

# Make all the nodes first
nodes = {}
i = 0
for y in range(mazeSize):
for x in range(mazeSize):
nodes[x,y] = Node(x,y,maze_desc[i])
i+=1

# Connect all the nodes together to form the maze
for node in nodes.values():
walls = node.wallValue
x,y = node.x,node.y
if not walls&1:
node.connect(nodes[x,wrap(y-1)], North)
if not walls&2:
node.connect(nodes[wrap(x+1),y], East)
if not walls&4:
node.connect(nodes[x,wrap(y+1)], South)
if not walls&8:
node.connect(nodes[wrap(x-1),y], West)

toVisit = set(nodes.values())
currentNode = None
destinationNode = None
previousNode = None
testInvincibilty = False
invincibility = 0
isGhost = False
turns = 0

def aStar(startNode, endNode):
openSet = set([startNode])
closedSet = set()
gScores = {startNode: 0}
cameFrom = {}
curNode = startNode
while openSet:
minF = 100000000
for node in openSet:
g = gScores[node]
h = node.distance(endNode)
f = g+h
if f < minF:
minF = f
curNode = node

if curNode == endNode:
path = []
while curNode != startNode:
path.insert(0, curNode)
curNode = cameFrom[curNode]
return path

openSet.remove(curNode)
for node in curNode.nodes.values():
if node in closedSet:
continue
g = gScores[curNode]
if isGhost:
g += 1
if node.item == 'P':
g -= 10 # prefer PacMen
else:
s = node.getScore();
if invincibility > 1:
g -= abs(s) # everything is tasty when invincible
else:
g += s
if previousNode and node == previousNode:
g += PreviousSquarePenalty # penalize previous square
isBetter = False
if node not in openSet:
isBetter = True
elif g < gScores[node]:
isBetter = True
if isBetter:
gScores[node] = g
cameFrom[node]=curNode

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

while True:
if (not info) or (info == "Q"):
break

turns += 1

# break a line of input up into a list of tuples (X,Y,contents)
info = [input_re.match(item).groups() for item in info.split()]

# update what we know about all the cells we can see
for cell in info:
nodes[int(cell[0]),int(cell[1])].item = cell[2]

currentNode = nodes[int(info[0][0]),int(info[0][1])]

if turns == 1:
print 'X'
continue

if not isGhost and currentNode.item == 'G':
isGhost = True
destinationNode = random.sample(nodes.values(), 1)[0]

if isGhost:
while destinationNode == currentNode or currentNode.distance(destinationNode) > 8:
destinationNode = random.sample(nodes.values(), 1)[0]
else:

if invincibility > 0:
invincibility -=  1

if testInvincibilty:
testInvincibilty = False
if currentNode.item == 'X':
invincibility += 10

while not destinationNode or destinationNode == currentNode:
destinationNode = random.sample(toVisit, 1)[0]

if currentNode.item == 'X':

bestPath = aStar(currentNode, destinationNode)

nextNode = bestPath[0]

direction = currentNode.direction(nextNode)

if not isGhost and nextNode.item == 'O':
testInvincibilty = True

previousNode = currentNode

print direction


shortsighted

This pac avoids adjacent ghosts unless he can eat them, moves onto adjacent fruit or pellets, and walks at random as a last resort.

#!/usr/bin/env python

import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

# read in the maze description
maze_size = int(math.sqrt(len(maze_desc)))

# turn the maze description into an array of arrays
# [wall bitmask, item last seen in square]

def chunks(l, n):
for i in xrange(0, len(l), n):
yield l[i:i+n]
maze = []
for row in chunks(maze_desc, maze_size):
maze.append([[int(c,16),'X'] for c in row])

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

turn = 0
invincibility_over = 0
last_move = None

while True:
if (not info) or (info == "Q"):
break

# break a line of input up into a list of tuples (X,Y,contents)
info = info.split()
info = [input_re.match(item).groups() for item in info]

# update what we know about all the cells we can see
for cell in info:
maze[int(cell[1])][int(cell[0])][1] = cell[2]

# current location
x = int(info[0][0])
y = int(info[0][1])

# which directions can we move from our current location?
valid_directions = []
# we might consider sitting still
# valid_directions.append('X')
walls = maze[y][x][0]
if not walls&1:
valid_directions.append('N')
if not walls&2:
valid_directions.append('E')
if not walls&4:
valid_directions.append('S')
if not walls&8:
valid_directions.append('W')

# which direction has the highest value item?
best_value = 0
best_direction = 'X'
for c in [(x,y-1,'N'),(x+1,y,'E'),(x,y+1,'S'),(x-1,y,'W')]:
if c[2] in valid_directions:
# am I a ghost?
if maze[y][x][1] == 'G':
if maze[c[1]%maze_size][c[0]%maze_size][1] == "P":
best_value = 999
best_direction = c[2]
else:
if maze[c[1]%maze_size][c[0]%maze_size][1] == 'F':
if best_value < 100:
best_value = 100
best_direction = c[2]
elif maze[c[1]%maze_size][c[0]%maze_size][1] == 'O':
if best_value < 50:
best_value = 50
best_direction = c[2]
elif maze[c[1]%maze_size][c[0]%maze_size][1] == 'o':
if best_value < 10:
best_value = 10
best_direction = c[2]
elif maze[c[1]%maze_size][c[0]%maze_size][1] == 'G':
if turn < invincibility_over:
# eat a ghost!
if best_value < 200:
best_value = 200
best_direction = c[2]
else:
# avoid the ghost
valid_directions.remove(c[2])

# don't turn around, wasteful and dangerous
if last_move:
reverse = ['N','E','S','W'][['S','W','N','E'].index(last_move)]
if reverse in valid_directions:
valid_directions.remove(reverse)

if best_value == 50:
invincibility_over = turn + 10
if best_direction != 'X':
# move towards something worth points
# sys.stderr.write("good\n")
last_move = best_direction
elif len(valid_directions)>0:
# move at random, not into a wall
# sys.stderr.write("valid\n")
last_move = random.choice(valid_directions)
else:
last_move = random.choice(['N','E','S','W'])
print last_move

turn += 1


avoider

Avoid all ghosts as a pacman, and all pacmen when a ghost. Tries to avoid any of its own kind if possible, and then avoids turning 180 if possible.

#!/usr/bin/env python
import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

# read in the maze description
maze_size = int(math.sqrt(len(maze_desc)))

# turn the maze description into an array of arrays of numbers indicating wall positions

def chunks(l, n):
for i in xrange(0, len(l), n):
yield l[i:i+n]
maze = []
for row in chunks(maze_desc, maze_size):
maze.append([[int(c,16),'X'] for c in row])

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

last_moved = 'X'

while True:
if (not info) or (info == "Q"):
break

# break a line of input up into a list of tuples (X,Y,contents)
info = info.split()
info = [input_re.match(item).groups() for item in info]

# location
x = int(info[0][0])
y = int(info[0][1])

# update what we know about all the cells we can see
for cell in info:
maze[int(cell[1])][int(cell[0])][1] = cell[2]

# which directions can we move from our current location?
valid_directions = []
walls = maze[y][x][0]
if not walls&1:
valid_directions.append('N')
if not walls&2:
valid_directions.append('E')
if not walls&4:
valid_directions.append('S')
if not walls&8:
valid_directions.append('W')

for c in [(x,y-1,'N'),(x+1,y,'E'),(x,y+1,'S'),(x-1,y,'W')]:
if c[2] in valid_directions:
# am I a ghost?
if maze[y][x][1] == 'G':
# it's a pacman, run. interaction is always a risk.
if maze[c[1]%maze_size][c[0]%maze_size][1] == "P":
valid_directions.remove(c[2])
# another ghost? let me move away.
elif maze[c[1]%maze_size][c[0]%maze_size][1] == "G":
else:
# it's a ghost, run. ghosts are evil.
if maze[c[1]%maze_size][c[0]%maze_size][1] == "G":
valid_directions.remove(c[2])
# its another pacman, move away!
elif maze[c[1]%maze_size][c[0]%maze_size][1] == "P":

# if possible to avoid normal contact, do so
if len(good_directions) > 0:
valid_directions = good_directions

# if not the only option, remove going backwards from valid directions
if len(valid_directions) > 1:
if last_moved == 'N' and 'S' in valid_directions:
valid_directions.remove('S')
elif last_moved == 'S' and 'N' in valid_directions:
valid_directions.remove('N')
elif last_moved == 'W' and 'E' in valid_directions:
valid_directions.remove('E')
elif 'W' in valid_directions:
valid_directions.remove('W')

# if possible, continue in the same direction
if last_moved in valid_directions:
print last_moved
# prefer turning left/right randomly instead of turning 180
#   backwards has been removed from valid_directions if not
#   the only option
elif len(valid_directions) > 0:
last_moved=random.choice(valid_directions)
print last_moved
# can't move, so stay put. desire to continue in original
#   direction remains.
else:
print 'X'

• This answer throws an error. You haven't defined x or y – Nathan Merrill Aug 5 '14 at 1:40
• File "avoider.py", line 42, in <module> maze[int(cell[1])][int(cell[0])][1] = cell[2] TypeError: 'int' object does not support item assignment – Nathan Merrill Aug 5 '14 at 4:12
• valid_directions.remove('W') ValueError: list.remove(x): x not in list – Nathan Merrill Aug 5 '14 at 5:08
• @NathanMerrill Should be fixed now. – es1024 Aug 5 '14 at 5:41

The physicist Pac-Man believe that Newton's law of universal gravitation can help him win the game. Then he just apply it to all other objects he know during the game. Since the physicist is old and has bad memory, he can only remember things in 5 rounds. Hooooly, the bad memory actually helps him to score better.

• Main.hs, contains the interesting part.
• Pacman.hs, just some boring code the handle the protocol. You may use it to write your own haskell solution. It doesn't contain any AI code.

Oh, wait, we have a Makefile, too.

Here they comes:

Main.hs

import Pacman
import Data.Complex
import Data.List
import Data.Function
import qualified Data.Map as Map
import Data.Maybe
import System.IO

data DebugInfo = DebugInfo {
debugGrid :: Grid
, debugForce :: Force
, debugAction :: Action
} deriving (Show)

data Physicist = Physicist [(Int, Object)] (Maybe DebugInfo)

type Force = Complex Double

calcForce :: Int -> Position -> PlayerType -> Object -> Force
calcForce n p1 t1 object = if d2 == 0 then 0 else base / (fromIntegral d2 ** 1.5 :+ 0)
where
(x1, y1) = p1
(x2, y2) = p2
wrap d = minimumBy (compare on abs) [d, n - d]
dx = wrap $x2 - x1 dy = wrap$ y2 - y1
Object t2 p2 = object
d2 = dx * dx + dy * dy
base = (fromIntegral dx :+ fromIntegral dy) * case t1 of
PacmanPlayer -> case t2 of
Pellet -> 10.0
PowerPellet -> 200.0
Ghost -> -500.0
Pacman -> -20.0
Fruit -> 100.0
Empty -> -2.0
GhostPlayer -> case t2 of
Pellet -> 10.0
PowerPellet -> 200.0
Ghost -> -50.0
Pacman -> 500.0
Fruit -> 100.0
Empty -> -2.0

instance PlayerAI Physicist where
findAction player info = (action, player') where
Player {
playerType = type_
, playerField = field
, playerMemory = Physicist objectsWithAge _
} = player

n = fieldSize field
NormalRound pos _ objects = info
objectsWithAge' = combineObjects objectsWithAge objects
objects' = map snd objectsWithAge'
directionChoices = filter (not . gridHasWall grid) directions4
totalForce = sum $map (calcForce n pos type_) objects' grid = fromMaybe (error$ "invalid position " ++ show pos) $(fieldGetGrid field) pos action = if magnitude totalForce < 1e-10 then if null directionChoices then Stay else Move$ head directionChoices
else Move $maximumBy (compare on (projectForce totalForce)) directionChoices debugInfo = Just$ DebugInfo grid totalForce action
player' = player {
playerMemory = Physicist objectsWithAge' debugInfo
}

-- roundDebug player _ = do
--   let Physicist objects debugInfo = playerMemory player
--       type_ = playerType player
--   hPrint stderr (objects, debugInfo)

combineObjects :: [(Int, Object)] -> [Object] -> [(Int, Object)]
combineObjects xs ys = Map.elems $foldr foldFunc initMap ys where foldFunc object@(Object type_ pos) = Map.insert pos (0, object) addAge (age, object) = (age + 1, object) toItem (age, object@(Object _ pos)) = (pos, (age, object)) initMap = Map.fromList . map toItem . filter filterFunc . map addAge$ xs
filterFunc (age, object@(Object type_ _))
| type_ == Empty = True
| age < maxAge = True
| otherwise = False

maxAge = 5

projectForce :: Force -> Direction -> Double
projectForce (fx :+ fy) (Direction dx dy) = fx * fromIntegral dx + fy * fromIntegral dy

main :: IO ()
main = runAI $Physicist [] Nothing  Pacman.hs module Pacman ( Field(..) , Grid(..) , Direction(..) , directions4, directions8 , Position , newPosition , Player(..) , PlayerType(..) , ObjectType(..) , Object(..) , RoundInfo(..) , Action(..) , runAI , PlayerAI(..) ) where import Data.Bits import Data.Char import Data.List import Data.Maybe import qualified Data.Map as Map import qualified System.IO as SysIO data Field = Field { fieldGetGrid :: Position -> Maybe Grid , fieldSize :: Int } data Grid = Grid { gridHasWall :: Direction -> Bool , gridPos :: Position } instance Show Grid where show g = "Grid " ++ show (gridPos g) ++ ' ':reverse [if gridHasWall g d then '1' else '0' | d <- directions4] data Direction = Direction Int Int deriving (Show, Eq) directions4, directions8 :: [Direction] directions4 = map (uncurry Direction) [(-1, 0), (0, 1), (1, 0), (0, -1)] directions8 = map (uncurry Direction)$ filter (/=(0, 0)) [(dx, dy) | dx <- [-1..1], dy <- [-1..1]]

type Position = (Int, Int)
newPosition :: (Int, Int)  -> Position
newPosition = id

data Player a = Player {
playerType :: PlayerType
, playerField :: Field
, playerRounds :: Int
, playerMemory :: a
}
data PlayerType = PacmanPlayer | GhostPlayer
deriving (Show, Eq)

class PlayerAI a where
onGameStart :: a -> Field -> IO ()
onGameStart _ _ = return ()

onGameEnd :: a -> IO ()
onGameEnd _ = return ()

findAction :: Player a -> RoundInfo -> (Action, Player a)

roundDebug :: Player a -> RoundInfo -> IO ()
roundDebug _ _ = return ()

data ObjectType = Pacman | Ghost | Fruit | Pellet | PowerPellet | Empty
deriving (Eq, Show)
data Object = Object ObjectType Position
deriving (Show)

data RoundInfo = EndRound | NormalRound Position PlayerType [Object]

data Action = Stay | Move Direction
deriving (Show)

parseField :: String -> Field
parseField s = if validateField field
then field
else error $"Invalid field: " ++ show ("n", n, "s", s, "fieldMap", fieldMap) where field = Field { fieldGetGrid = flip Map.lookup fieldMap , fieldSize = n } (n : _) = [x | x <- [0..], x * x == length s] fieldMap = Map.fromList [ ((i, j), parseGrid c (newPosition (i, j))) | (i, row) <- zip [0..n-1] rows, (j, c) <- zip [0..n-1] row ] rows = reverse . snd$ foldr rowFoldHelper (s, []) [1..n]
rowFoldHelper _ (s, rows) =
let (row, s') = splitAt n s
in (s', row:rows)

validateField :: Field -> Bool
validateField field@(Field { fieldGetGrid=getGrid, fieldSize=n }) =
all (validateGrid field) $map (fromJust.getGrid) [(i, j) | i <- [0..n-1], j <- [0..n-1]] validateGrid :: Field -> Grid -> Bool validateGrid field@(Field { fieldGetGrid=getGrid, fieldSize=n }) grid@(Grid { gridPos=pos }) = all (==True) [gridHasWall grid d == gridHasWall (getNeighbour d) (reverse d) | d <- directions4] where reverse (Direction dx dy) = Direction (-dx) (-dy) (x, y) = pos getNeighbour (Direction dx dy) = fromJust . getGrid . newPosition$ (mod (x + dx) n, mod (y + dy) n)

parseGrid :: Char -> Position -> Grid
parseGrid c pos = Grid gridHasWall pos
where
walls = zip directions4 bits
bits = [((x shiftR i) .&. 1) == 1 | i <- [0..3]]
Just x = elemIndex (toLower c) "0123456789abcdef"
gridHasWall d = fromMaybe (error $"No such direction " ++ show d)$
lookup d walls

parseRoundInfo :: String -> RoundInfo
parseRoundInfo s = if s == "Q" then EndRound else NormalRound pos playerType objects'
where
allObjects = map parseObject $words s Object type1 pos : objects = allObjects objects' = if type1 elem [Empty, Ghost] then objects else allObjects playerType = case type1 of Ghost -> GhostPlayer _ -> PacmanPlayer parseObject :: String -> Object parseObject s = Object type_ (newPosition (x, y)) where (y, x) = read$ "(" ++ init s ++ ")"
type_ = case last s of
'P' -> Pacman
'G' -> Ghost
'o' -> Pellet
'O' -> PowerPellet
'F' -> Fruit
'X' -> Empty
c -> error $"Unknown object type: " ++ [c] sendAction :: Action -> IO () sendAction a = putStrLn name >> SysIO.hFlush SysIO.stdout where name = (:[])$ case a of
Stay -> 'X'
Move d -> fromMaybe (error $"No such direction " ++ show d)$
lookup d $zip directions4 "NESW" runPlayer :: PlayerAI a => Player a -> IO () runPlayer player = do roundInfo <- return . parseRoundInfo =<< getLine case roundInfo of EndRound -> return () info@(NormalRound _ type_' _) -> do let updateType :: Player a -> Player a updateType player = player { playerType = type_' } player' = updateType player (action, player'') = findAction player' info roundDebug player'' info sendAction action let updateRounds :: Player a -> Player a updateRounds player = player { playerRounds = playerRounds player + 1} player''' = updateRounds player'' runPlayer player''' runAI :: PlayerAI a => a -> IO () runAI mem = do field <- return . parseField =<< getLine let player = Player { playerType = PacmanPlayer , playerField = field , playerRounds = 0 , playerMemory = mem } runPlayer player  Makefile physicist: Main.hs Pacman.hs ghc -O3 -Wall Main.hs -o physicist  command.txt ./physicist  • I'm unable to run this. I get "File name does not match module name: Saw Main' Expected Pacman'" when I try to make it. Also, in order to run it, do I just need to make it, or is there another command I need to run? – Nathan Merrill Aug 6 '14 at 19:33 • @NathanMerrill You should first make it then run the physicist executable. Edited and added command.txt, now. – Ray Aug 6 '14 at 19:42 • I am making it. The error I listed is thrown when I make it. Also assume you are in the physicist directory. Wouldn't it be ghc physicist in the command.txt? – Nathan Merrill Aug 6 '14 at 19:43 • @NathanMerrill That's strange. Maybe due to different behaviour of GHC on Windows. Renaming physicist.hs to Main.hs may work. I've updated the answer. – Ray Aug 6 '14 at 19:51 • @NathanMerrill Did you combined these two files? That wouldn't work. – Ray Aug 6 '14 at 19:53 dumbpac This pac just moves at random, with no regard for the maze layout or ghosts or any other factors. Perl: #!/usr/bin/perl local$| = 1; # auto flush!
$maze_desc = <>; while(<>) { if($_ eq "Q"){
exit;
}
$move = (("N","E","S","W","X")[rand 5]); print ($move . "\n");
}


Python:

#!/usr/bin/env python

import os
import sys
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

while True:
if (not int) or (info == "Q"):
break
print random.choice(['N', 'E', 'S', 'W', 'X'])


randomwalk

this pac walks at random, but not into walls

#!/usr/bin/env python

import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

# read in the maze description
maze_size = int(math.sqrt(len(maze_desc)))

# turn the maze description into an array of arrays of numbers indicating wall positions
def chunks(l, n):
for i in xrange(0, len(l), n):
yield l[i:i+n]
map = []
for row in chunks(maze_desc, maze_size):
map.append([int(c,16) for c in row])

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

while True:
if (not info) or (info == "Q"):
break

# break a line of input up into a list of tuples (X,Y,contents)
info = info.split()
info = [input_re.match(item).groups() for item in info]

# this pac only cares about its current location
info = info[0]

# which directions can we move from our current location?
valid_directions = []
# we might consider sitting still
# valid_directions.append('X')
walls = map[int(info[1])][int(info[0])]
if not walls&1:
valid_directions.append('N')
if not walls&2:
valid_directions.append('E')
if not walls&4:
valid_directions.append('S')
if not walls&8:
valid_directions.append('W')

# move at random, not into a wall
print random.choice(valid_directions)


Pathy, Python 3

This bot use path finding a lot. Given a start position and end condition, it use the simple BFS to find the shortest path. Path finding is used in:

• Find power pellets, fruits or pellets.
• If it's invincible, chase ghosts
• If it's ghost, chase Pac-Men
• Flee from ghosts
• Calculate distance between a given pair of positions.

command.txt

python3 pathy.py


pathy.py

import sys
import random
from collections import deque

DIRECTIONS = [(-1, 0), (0, 1), (1, 0), (0, -1)]
GHOST = 'G'
PACMAN = 'P'
FRUIT = 'F'
PELLET = 'o'
POWER_PELLET = 'O'
EMPTY = 'X'

PACMAN_PLAYER = 'pacman-player'
GHOST_PLAYER = 'ghost-player'

class Field:
def __init__(self, s):
n = int(.5 + len(s) ** .5)
self.size = n
self.mp = {(i, j): self.parse_grid(s[i * n + j]) for i in range(n) for j in range(n)}

@staticmethod
def parse_grid(c):
x = int(c, 16)
return tuple((x >> i) & 1 for i in range(4))

def can_go_dir_id(self, pos, dir_id):
return self.mp[pos][dir_id] == 0

def connected_neighbours(self, pos):
return [(d, self.go_dir_id(pos, d)) for d in range(4) if self.can_go_dir_id(pos, d)]

def find_path(self, is_end, start):
que = deque([start])
prev = {start: None}
n = self.size

def trace_path(p):
path = []
while prev[p]:
path.append(p)
p = prev[p]
path.reverse()
return path

while que:
p = x, y = que.popleft()
if is_end(p):
return trace_path(p)
for d, p1 in self.connected_neighbours(p):
if p1 in prev:
continue
prev[p1] = p
que.append(p1)
return None

def go_dir_id(self, p, dir_id):
dx, dy = DIRECTIONS[dir_id]
x, y = p
n = self.size
return (x + dx) % n, (y + dy) % n

def distance(self, p1, p2):
return len(self.find_path((lambda p: p == p2), p1))

def get_dir(self, p1, p2):
x1, y1 = p1
x2, y2 = p2
return (self.dir_wrap(x2 - x1), self.dir_wrap(y2 - y1))

def dir_wrap(self, x):
if abs(x) > 1:
return 1 if x < 0 else -1
return x

class Player:
def __init__(self, field):
self.field = field

def interact(self, objects):
" return: action: None or a direction_id"
return action

def send(self, msg):
print(msg)
sys.stdout.flush()

class Pathy(Player):
FLEE_COUNT = 8

def __init__(self, field):
super().__init__(field)
self.type = PACMAN_PLAYER
self.pos = None
self.mem_field = {p: GHOST for p in self.field.mp}
self.power = 0
self.flee = 0
self.ghost_pos = None
self.ghost_distance = None

@property
def invincible(self):
return self.type == PACMAN_PLAYER and self.power > 0

def detect_self(self, objects):
((x, y), type) = objects[0]
self.type = GHOST_PLAYER if type == GHOST else PACMAN_PLAYER
self.pos = (x, y)

def update_mem_field(self, objects):
for (p, type) in objects:
self.mem_field[p] = type

def find_closest_ghost_pos(self, objects):
try:
return min(
(p for (p, t) in objects if t == GHOST),
key=lambda p: self.field.distance(self.pos, p)
)
except:
return None

def chase(self, types):
is_end = lambda p: self.mem_field[p] in types
path = self.field.find_path(is_end, self.pos)
if not path:
return None
return DIRECTIONS.index(self.field.get_dir(self.pos, path[0]))

def interact(self, objects):
self.detect_self(objects)
self.update_mem_field(objects)

action = None
if self.invincible:
self.debug('invincible!!!')
action = self.chase((GHOST,))
if action is None:
action = self.chase((POWER_PELLET,))
if action is None:
action = self.chase((FRUIT, PELLET,))
elif self.type == GHOST_PLAYER:
action = self.chase((PACMAN,))
else:
# PACMAN_PLAYER
ghost_pos = self.find_closest_ghost_pos(objects)
if ghost_pos:
ghost_distance = self.field.distance(ghost_pos, self.pos)
if not self.flee or ghost_distance < self.ghost_distance:
self.flee = self.FLEE_COUNT
self.ghost_distance = ghost_distance
self.ghost_pos = ghost_pos

if self.flee > 0:
self.flee -= 1
action = max(
self.field.connected_neighbours(self.pos),
key=lambda dp: self.field.distance(dp[1], self.ghost_pos)
)[0]
# self.debug('flee: ghost_pos {} pos {} dir {} dist {}'.format(
#     self.ghost_pos, self.pos, DIRECTIONS[action], self.field.distance(self.pos, self.ghost_pos)))
else:
self.ghost_pos = self.ghost_distance = None
action = self.chase((POWER_PELLET, FRUIT))
if action is None:
action = self.chase((PELLET,))
if action is None:
action = random.choice(range(5))
if action > 3:
action = None

# Detect power pellet
if action is None:
next_pos = self.pos
else:
next_pos = self.field.go_dir_id(self.pos, action)
if self.mem_field[next_pos] == POWER_PELLET:
self.power = 9
elif self.invincible and self.mem_field[next_pos] == GHOST:
self.debug('Got a ghost!')
else:
self.power = max(0, self.power - 1)
return action

def debug(self, *args, **kwargs):
return
print(*args, file=sys.stderr, **kwargs)

def start_game(player_class):
field = Field(input())
player = player_class(field)
while True:
line = input()
if line == 'Q':
break
objects = [(tuple(map(int, x[:-1].split(',')))[::-1], x[-1]) for x in line.split(' ')]
action = player.interact(objects)
player.send('NESW'[action] if action is not None else 'X')

if __name__ == '__main__':
start_game(Pathy)

• objects = [(tuple(map(int, x[:-1].split(',')))[::-1], x[-1]) for x in line.split(' ')] throws a ValueError: invalid literal for int() with base 10: '8o' – Nathan Merrill Aug 12 '14 at 14:01
• What did the controller send? Does it fail every time? It works here and I think this statement should work well. – Ray Aug 12 '14 at 14:16