31
2
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
- Every valid Pac-Man will be in a single maze. The player with the highest cumulative score after 10 games will win.
- A game is over when all Pac-Men are dead, all pellets are gone, or 500 turns have passed
- If a Pac-Man dies, he continues to play as a ghost
- Eating a Power pellet will make you invincible for 10 turns, and allows you to eat Ghosts
- Eating a Ghost will teleport the ghost to a random location
- Ghosts cannot eat anything except Pac-Men, and do not get any points
- Eating the following items as Pac-Man will get you the following points:
- Pellet: 10
- Power Pellet: 50
- Fruit: 100
- 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:
2n
Ghosts4n
Power Pellets2n
Fruitn
Pac-Men in spots where connected neighbors squares are empty.- 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:
P
: 1 or more Pac-ManG
: 1 or more Ghostso
: PelletO
: Power pelletF
: Piece of FruitX
: 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 (N
orth, E
ast, S
outh, W
est, or X
Stay).
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:
- The bugs described will not be duplicated
- They will all be active from the beginning
- They are vulnerable only to the player who ate the pellet
- They will indefinitely switch from scatter to chase, each having a fixed number of turns before switch
- 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)
- Blinky won't speed up
- Inky will pick the nearest ghost to base his calculations off of after switching to chase.
- Clyde will find all players 8 squares away, then follow the furthest player.
- 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
9+1. This is the first time I see the word "Pacmen" – justhalf – 2014-08-04T01:22:21.600
#!/usr/bin/env python – Sparr – 2014-08-04T02:15:55.207
5
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: http://home.comcast.net/~jpittman2/pacman/pacmandossier.html
– Todd Lehman – 2014-08-04T02:37:01.550There are a few disparities between the spec here and the controller code. Also I'm working on fixing the IO concerns. – Sparr – 2014-08-04T05:02:54.670
Here's an updated controller. First, I replaced the threaded queues for I/O with select.poll and interruptingcow.timeout which should eliminate a lot of problems with I/O exceptions and problems. I also fixed a bug with "X" moves being rejected. I removed the "0x" prefix from hex chars in the maze description. And finally I send a "Q" to all the bots at the end of the match so they know to terminate their processes. https://gist.github.com/sparr/f4269be18c933b3b7aa5
– Sparr – 2014-08-04T06:06:31.640"You will be given the characters for each square, starting with the top left, moving right, and wrapping to the next line." what is this supposed to mean, other than the same as the next sentence about getting the wall info for the maze? – Sparr – 2014-08-04T06:59:42.703
@Sparr: The first sentence describes the order of characters, the next sentence describe what each character means. – justhalf – 2014-08-04T07:03:22.807
Is there a way to find out where the pacman the program controls is at (as x,y coordinates)? – es1024 – 2014-08-04T07:25:47.453
@es1024 the first coordinate in the info you're given is where your pacman currently is. I think. I'm still figuring out exactly how the controller works, particularly while I'm confusing X/Y coords. – Sparr – 2014-08-04T08:13:50.567
I think scoring for eating ghosts needs to be diminished. It is, by far, the biggest random factor in the game. I've run a few dozen tests between my bots and the usual score spread is about 1000-2000 for shortsighted, 500-800 for a random bot that doesn't walk into walls, and 50-500 for dumbpac. However, every 10 or 20 tests I encounter a run where one bot got a power pellet while adjacent to a bunch of ghosts. I saw a score of 420000 with a second place of 1200. – Sparr – 2014-08-04T08:16:26.587
@Sparr: Yes, I envisioned that too when I saw the imbalanced exponential score on eating ghost. I think OP should just give it constant scores, like 500 or 1000. After all, the ghosts of the same personality will more likely to be in close vicinity of the same player. – justhalf – 2014-08-04T08:28:41.700
By the way, I expect the bots can do something like this: http://www.youtube.com/watch?v=xOCurBYI_gY#t=859 (at 14:22) =D
– justhalf – 2014-08-04T08:31:55.440The controller needs to be improved, there should be no expected exception in I/O. – justhalf – 2014-08-04T08:41:46.390
Maybe we should have a repo in github for the controller. – Ray – 2014-08-04T15:27:02.947
@Moop Have you tried Sparr 's code? You may start from it. – Ray – 2014-08-04T15:30:34.893
I did, but he uses
select.poll()
which is non-windows compatible – Moop – 2014-08-04T15:31:20.680the poll may be optional. however, I think interruptingcow ALSO doesn't work on Windows. If someone can come up with a windows-compatible way to do peeked-or-timeout-monitored blocking IO, we'd love to have it incorporated. – Sparr – 2014-08-04T15:33:34.660
2
Anyone working on this challenge should join us in the chat room for codegolf. http://chat.stackexchange.com/rooms/240/the-nineteenth-byte
– Sparr – 2014-08-04T15:33:55.577This seems like a possible answer: http://stackoverflow.com/questions/375427/non-blocking-read-on-a-subprocess-pipe-in-python
– Moop – 2014-08-04T18:01:22.9271Ok. The controller now works on windows and linux, but will freeze on windows if your bot doesn't respond. – Nathan Merrill – 2014-08-04T20:35:02.933
1I am colorblind and cannot tell the PacMen from the Ghosts, could we change the colors? – Moop – 2014-08-05T19:59:34.193
@Moop: On line 444 of the code, change the very last number from 0 to 255. It will make all PacMen white. Line:
circle_color = (((0, 0, 0), (255, 0, 0), (100, 200, 200), (100, 200, 200))[square.contents] if not square.ghosts else (0, 255, 0)) if not square.players else (255, 255, 255)
– Nathan Merrill – 2014-08-05T20:15:15.127@NathanMerrill Yeah, i had done something similar. Just was looking out for the other 10% – Moop – 2014-08-05T20:23:23.807
I feel like if you are a ghost and you eat a PacMan you should get some points – Moop – 2014-08-05T23:22:16.357
@Moop, you can think of eating a PacMan as a ghost as an "indirect" bonus since your enemy Pacmen won't get more points. Also, not giving points as a Ghost would give much more value to keeping alive.
I'm not saying your suggestion is bad. I'm just saying that the current system emphasizes the part where a living Pacman is top priority. – Zaenille – 2014-08-06T07:02:54.450
How do a player know if itself is invincible? Consider this case: two players step on the same grid which contains a power pellet but none of them got the power pellet. If one of them was a invincible player, then it got the pellet but the other one can't tell if the other is invincible or noet. – Ray – 2014-08-06T11:25:10.947
I don't think the FOV information being sent to the players is correct. I loaded only my bot and stepped through each turn and if i was moving North up a long hallway, i would only get something like (5,4X 5,4P) even through 5,3 5,2 5,1 etc.. were in the line of site and no walls blocking. – Moop – 2014-08-06T20:09:24.177
Here is an example of me moving east (http://imgur.com/nq4GYQM and http://imgur.com/Vn49y0q), but the message sent doesn't included the expected 1,9o and 1,8G (and possibly 1,0o)
– Moop – 2014-08-06T20:19:35.203@Moop I will take a look. – Nathan Merrill – 2014-08-06T20:36:24.300
I found a vital bug in the
Player.move
method. In the firstwhile
condition. I profiled the function and code inside the this while loop was never reached. – Ray – 2014-08-06T21:21:38.2471@Ray I found the bug. Pushed the fix, and I am rerunning the tests now. – Nathan Merrill – 2014-08-06T22:53:44.387
I get a bug where the game freezes after all the pellets have been eaten. – Moop – 2014-08-07T16:29:19.827
I've never gotten to that point @Moop. Let me try to figure out what happens. – Nathan Merrill – 2014-08-07T17:07:02.817
I think I fixed it Moop. – Nathan Merrill – 2014-08-07T17:17:49.237
Latest version isn't working at all on windows. Looks like you send the maze description twice now – Moop – 2014-08-07T18:12:49.777
Are you sure? I'm running it just fine here. – Nathan Merrill – 2014-08-07T19:04:53.890
@NathanMerrill appears to be a merging issue, not your code. Sorry for the false alarm – Moop – 2014-08-07T19:54:39.550
New Pac-Man joined, please update the scoreboard. – Ray – 2014-08-12T12:30:08.657