The game started as an entry to the Ludum Dare competition over a month ago with the theme “You Are The Villain.” I completed a reverse-Pacman game where you controlled the ghosts in order to trap Pacman and keep him from gobbling up your pellets. There was very little AI in it. I have a couple pathfinding classes that it uses to pick the path from the ghost to the player’s cursor, so most of my time had gone into creating the pathfollowing code and trying to get that correct.
For One Game A Month, I continued to work on it. I revamped the graphics so I would not get into intellectual property trouble should I chose to sell it and renamed it LS-MAN. I refactored many parts related to the size of the cells and gameboard, rewrote the pathfollowing code, implemented a potential field to use for AI, surrounded the game with a main menu and end conditions, and generally tried to add polish.
I did a lot of this all at the same time, which was nice because I could do something else if I got bored. Unfortunately, it also made it take longer to get a playable game since I was putting things in that weren’t necessary for the minimum threshold where you can call it a game.
What Went Right
The pathfinding was a class that came from Untold Entertainment. I had used it before in some unreleased side project and it worked well, so I grabbed it again for this. It was easy to drop in and modify for my needs. There is a Node class that contains a lot of the implementation specific stuff. I ended up using the Nodes to hold most of my data for the map.
For the invader’s AI, I learned about potential fields from AIGameDev.com. It’s a method used in real-time-strategy where the goals and threats have positive and negative effect, respectively, and those values are radiated outward. This was a very CPU intensive step. I was using the Nodes from the pathfinding to hold the potential data and it was something that needed to be recreated often. If not, LS-MAN would be using stale data to decide his path and make a wrong move. It didn’t run too bad in Release mode, but the delay was noticeable every second or so and any delay would be unacceptable. There ended up being two solutions for this and they go hand in hand.
The first fix was to change how the pathfinding algorithm went about finding the nearby nodes. The pathfinding connected node function searched every node in the grid to see if it fit the requirement of being one away either horizontally or vertically. Regardless, pathfinding is really fast but we also know it’s not searching very many nodes in most cases to find a path, so this excessive connected node function wasn’t a huge deal. However, the potential field calculation searches _every_ node which means every node’s neighbors are requested. And since there are multiple sources of the field, certain nodes could be recalculated and set multiple times. This was just not going to work. I had made changes to the connected node function to enable the wrapping off the edge of the screen, so I felt that searching every single node to see if it was connected was not really that bad as long as we didn’t have to do it a lot. We do have an advantage–once loaded, the map doesn’t change. Therefore we could actually do the (relatively) slow calculation at map load time and store the result on the Node object. Now whenever potential field calculation or pathfinding needed to know what was nearby, it was returned quickly. This reduced the number of CPU cycles per frame a huge amount, but we still had a delay every few frames as it waited for the field calculation to complete.
The second solution was to refactor the potential field calculation so that it wasn’t doing it all at once. Since the default algorithm has you storing the to-be-calculated nodes in a queue, it was easy to add a state machine to it and iterate through that queue over multiple frames. Whereas before it was looping until the queue was over, my implementation would now also quit the loop if a certain amount of time had passed. In my case, it would only do up to 5ms per frame and then stop, letting the rest of the game continue, and pick up where it left off the next turn. Once it completed a batch, the old values were replaced by the new values, and the cycle started over again. Now when LS-MAN reached an intersection, he would look at the potential field values for each path and take the one with the highest value. This would lead him to pellets and away from the creatures trying to get him.
Debug mode screenshot showing the positive potential field of the pellets and the negative field given off by the creatures. Blue is a positive field, red is a negative field. Black is nothing. Upper left corner of each node is the actual value.
Super pellets were a different matter. In order to give LS-MAN some kind of above-minimal survival instinct, I had the pellets give off a large positive potential when LS-MAN was within a certain distance of a creature. This results in the appearance of him seeking a pellet when he knows he’s being actively chased. In order to keep the pellets around longer, I actually have them give off a negative field which should dissuade LS-MAN from choosing that path when no creatures are around and instead have him continue eating regular pellets.
In my original LD48 implementation, people said it was hard to select the ghosts. I took that critique and added keypresses that would select individual creatures, as well as adding buttons to the screen. If I eventually port to a touchscreen format, these buttons would be perfect.
I used OGMOv2 to create the levels. I really enjoy being able to rapidly create even though I only had two for the released game.
What Went Wrong
Not really wrong per-se, but it would have been nice to have had a working game earlier. I did spend the middle of the month focusing mostly on pathfollowing, even rewriting the code at one point, but I also spent a long time tracking down bugs that the game ended up ‘shipping’ with anyway. I should have noted that they were not show-stoppers much earlier and went on to finish aspects that would make it that much closer to a game.
I’m not really happy with the scoring. I knew time and the number of pellets should be the gauge, but I never had time to come up with a score based on those two values.
As time went on the code became more difficult to manage. I think it was because the board was lumped in with the main world code. They are tightly connected, which is fine, but I think pulling out the board stuff into it’s own class would have kept the code neater and probably easier to navigate.
I gave each creature different levels of ability to give them somewhat of a personality, but I’m not really happy with the level of balance. I never really got any external playtesting so I don’t know how they feel for everyone else.
Looking Forward
I would love to add high scores and new levels at some point. If I end up writing the server code to store scores, I would certainly add something that reports back.
Bonus Reading
Long after the point of no return I found this gem of a post at GameInternals.com. Since the goal of LS-MAN is different from traditional Pacman, the AI didn’t carry over much, if any, however I if I had seen it earlier I might have picked up the method of board construction and makeup for my own instead of using a static grid size for everything. I recommend reading, especially if you like simple implementations that result in the appearance of a more complicated intelligence.
