Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
I don't know XNA, but maybe you'll have to seed that random generator to get different values? –  bummzack 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
3  
In case you are curious, the original AIs were not (entirely) random: home.comcast.net/~jpittman2/pacman/pacmandossier.html#Chapter 4 –  coderanger 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

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
1  
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.

share|improve this answer
    
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. –  coderanger 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. –  dash-tom-bang 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.