Random Ghost Behavior in PacMan Clone Not Random?

I'm currently programming a PacMan clone as my first ever game with the XNA Game Studio before eventually going to DirectX.

As a first ever game, lots of things have given me great headaches, especially collision detection with the walls.

The problem I have now is the "AI" I have implemented for the ghosts. It's wish-wash, really. The basic method is that, if the Ghost runs into a corner, it will change its speed vector, and ultimately its direction.

However, the seed seems to be giving me the same pattern. If I launch them from the same corner multiple times, they keep taking the same direction. They have only rarely ever not taken the same route before getting stuck.

I'm not sure how much code can be posted here, but this is my current algorithm. Beware, it's not very pretty at the moment. It was implemented just to see if it's viable. Now I just want it to work properly before refactoring it and making it more intelligent.

// OMG! Is the ghost trying to hit a wall? Ha! No wall-hacking for you!
if (!wall_.Collides(frameSize_, pos_, direction_))
pos_ += direction_;
else
{
// a and b will change speed.
// if a and b are both 1 (diagonal vector), then c will determine
// which value a or b shall be taken.
// d negates the values for reversed direction.
Random rand = new Random();
int a, b, c, d;
a = b = 0;
while (0 == a && 0 == b)
{
a = rand.Next(2);
b = rand.Next(2);
}

if (1 == a && 1 == b)
{
c = rand.Next(2);
if (0 == c)
spd_ = new Vector2(a * 2, 0);
else
spd_ = new Vector2(0, b * 2);
}
else
{
d = rand.Next(2);
if (1 == d)
{
if (1 == a)
spd_ = new Vector2(a * 2, 0);
else
spd_ = new Vector2(0, b * 2);
}
else
{
if (1 == a)
spd_ = new Vector2(-a * 2, 0);
else
spd_ = new Vector2(-b * 2, 0);
}
}
}

Addendum: What I also meant to add is that the ghosts get stuck eventually. They stop taking corner with a different direction. I've waited for about 20-40 tries, but they simply reversed direction. This happened repeatedly with several restarts of the game.

• I don't know XNA, but maybe you'll have to seed that random generator to get different values? Sep 9 '10 at 18:42
• XNA seeds random number generators based on the clock by default, so you do need to seed them if you instantiate many generators at once. But assuming different values across invocations, or at disparate times in the program, is safe enough for games.
– user744
Sep 9 '10 at 18:49
• In case you are curious, the original AIs were not (entirely) random: home.comcast.net/~jpittman2/pacman/pacmandossier.html#Chapter 4 Sep 9 '10 at 20:04
• @coderanger: Thank you for the link! Yes, I know that each ghost has quite a sophisticated algorithm to use, but this is a test-run. I just want them to navigate the bloody squares without getting stuck before getting on with the real problem of pathfinding and AI. bookmarks link That shall be a great help though, when that time comes ^^
– IAE
Sep 9 '10 at 20:36
• Did you ever come up with a solution SoulBeaver?
– Robb
Jan 4 '11 at 20:25

Break down the probabilities. Work down the tree of your conditionals, figuring out the probabilities at each step.

There is a 1/3 chance of a == b == 1. Then is a 1/2 chance of (2, 0) and a 1/2 chance of (0, 2), so a 1/6 chance overall of either.

Within the remaining 2/3 chance, there is a 1/2 chance of d = 1; then either a = 1 and you get (2, 0) or b = 1 and you get (0, 2) with equal probability, 1/2 each. So 2/3 * 1/2 * 1/2 = 1/6 chance each overall.

Then the same math for d = 0. Either (-2, 0) or (0, -2), 1/6 overall chance of each.

Summing those, we find there is a total of 1/3 chance for (2, 0), 1/3 chance for (0, 2), 1/6 chance for (-2, 0), and 1/6 chance for (0, -2).

Since e.g. up/right is now twice as likely as down/left, they will get stuck.

• And by the way, this would be a lot easier to read if instead of conditionals you just had a = random.Next(2); b = a ^ 1; d = random.Next(2); spd = new Vector(-d * a * 2, -d * b * 2).
– user744
Sep 9 '10 at 18:48
• Thanks! I actually hadn't thought if the probability was different for each direction. Since the pattern looked as if it repeated, I thought the RNG was to blame. I'll work out a better algorithm and @Joe again: I'll work in your code if I can!
– IAE
Sep 9 '10 at 19:13

Your problem is that you are recreating the Random object every time you do your computation. You should only create one Random object (and assign it to a member variable, for instance) and query it when you want new random values.

• That isn't actually a problem, though it might be a tiny performance hit. Not really something to worry about while you are still getting your sea legs. Sep 9 '10 at 21:41
• Ah ok. I don't know C# and guessed that maybe the Random object was being initialized to the same thing each time it was brought up. Sep 9 '10 at 22:13
• This is a problem if you are making many Random instances in a short period of time, because they are clock-seeded. It is not the main problem in this case, and it can't explain non-random behavior across program invocations.
– user744
Sep 9 '10 at 22:15